Accession Number : ADA256111


Title :   Maintaining Incremental Optimality When Building Shortest Euclidean Tours


Corporate Author : ARMY CECOM SIGNALS WARFARE DIRECTORATE VINT HILL FARMS STATION VA


Personal Author(s) : Cronin, T M


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a256111.pdf


Report Date : Jan 1990


Pagination or Media Count : 19


Abstract : Reported upon are experimental runs of an algorithm designed to incremental optimality 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.


Descriptors :   *ALGORITHMS , WARFARE , INTELLIGENCE , ARMY RESEARCH , DYNAMICS , EDGES , COMPUTER PROGRAMMING , BUILDINGS , TIME , SIGNALS , OPERATION , ARTIFICIAL INTELLIGENCE , ROUTING , ARMY , DYNAMIC PROGRAMMING , URBAN AREAS


Subject Categories : Cybernetics


Distribution Statement : APPROVED FOR PUBLIC RELEASE