An Algorithm for Solving a Range Constrained Traveling Salesman Problem.
Abstract
A problem of routing earth resource survey aircraft, proposed by NASA, is formulated as a traveling salesman problem, in which the salesman (aircraft) has a range constraint. A heuristic algorithm is presented, which seeks a minimal length set of subtours through n cities. The aircraft begins a subtour at the base location, visits a subset of the n cities and returns when the range constraint prevents a visit to another city. Additional subtours are created until all cities are visited. The algorithm is programmed in FORTRAN for use on digital computers. The IBM 360/67 computer at the Naval Postgraduate School was used to find solutions to three operational problems of size seven, eighteen and twentyfive cities. Computation times for each problem was under 20 seconds and the solutions were significantly better than feasible solutions calculated without the use of the algorithm. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1976
- Accession Number
- ADA035842
Entities
People
- John William Harms
Organizations
- Naval Postgraduate School