Fast marching methods for the continuous traveling salesman problem [electronic resource].
- Berkeley, Calif. : Lawrence Berkeley National Laboratory, 2008.
Oak Ridge, Tenn. : Distributed by the Office of Scientific and Technical Information, U.S. Dept. of Energy.
- Additional Creators:
- Lawrence Berkeley National Laboratory and United States. Department of Energy. Office of Scientific and Technical Information
- Restrictions on Access:
- Free-to-read Unrestricted online access
- We consider a problem in which we are given a domain, a cost function which depends on position at each point in the domain, and a subset of points ('cities') in the domain. The goal is to determine the cheapest closed path that visits each city in the domain once. This can be thought of as a version of the Traveling Salesman Problem, in which an underlying known metric determines the cost of moving through each point of the domain, but in which the actual shortest path between cities is unknown at the outset. We describe algorithms for both a heuristic and an optimal solution to this problem. The order of the heuristic algorithm is at worst case M * N logN, where M is the number of cities, and N the size of the computational mesh used to approximate the solutions to the shortest paths problems. The average runtime of the heuristic algorithm is linear in the number of cities and O(N log N) in the size N of the mesh.
- Report Numbers:
- E 1.99:lbnl-1313e
- Published through SciTech Connect.
Proceedings of the National Academy of Sciences FT
Andrews, J.; Sethian, J.A.
Computational Research Division
- Funding Information:
View MARC record | catkey: 14653967