Maintaining Incremental Optimality When Building Shortest Euclidean Tours

摘要

Reported upon are experimental runs of an algorithm designed to incrementaloptimality when building tours for the Euclidean traveling salesman problem. Unlike the Lin-Kernighan edge eschange or Padberg-Rinaldi branch-and-cut techniques which begin with suboptimal tours and proceed by iterating in an attempt to converge upon or exceed the Held-Karp lower bound, the new algorithm strives to maintain optimality as each city is inserted. In previous Army research at the CECOM Center for Signals Warfare, proofs were obtained to show that the underlying search space for the Euclidean traveling salesman problem is piecemeal quartic and hyperbolic. To exploit this new knowledge, the author has developed dynamic programming algorithm which begins with a baseline tour consisting of the outer (inner) convex hull of cities, and proceeds by adding a city at a time to the interior (exterior). How the city is inserted into the existing tour is dictated by a set of quartic and hyperbolic loci which separate existing and hypothesized subtours from each other. The insertion may involve three different nonlinear operations: hyperbolic extension, quartic shunting and quartic interchange. Artificial Intelligence, Data Fusion, Dynamic Programming.