Perturbation Method for Probabilistic Search for the Traveling Salesperson Problem

Report
Authors:Cohoon, James, Department of Computer ScienceUniversity of Virginia Karro, John, Department of Computer ScienceUniversity of Virginia Martin, WN, Department of Computer ScienceUniversity of Virginia Niebel, William, Department of Computer ScienceUniversity of Virginia Nagel, Klaus, Department of Computer ScienceUniversity of Virginia
Abstract:

The Traveling Salesperson Problem (TSP), is an NP-complete combinatorial optimization problem of substantial importance in many scheduling applications. Here we show the viability of SPAN, a hybrid approach to solving the TSP that incorporates a perturbation method applied to a classic heuristic in the overall context of a probabilistic search control strategy. In particular, the heuristic for the TSP is based on the minimal spanning tree of the city locations, the perturbation method is a simple modification of the city locations, and the control strategy is a genetic algorithm (GA). The crucial concept here is that the perturbation of the problem (since the city locations specify the problem instance) allows variant solutions (to the perturbed problem) to be generated by the heuristic and applied to the original problem, thus providing the GA with capabilities for both exploration and exploitation in its search process. We demonstrate that SPAN outperforms, with regard to solution quality, one of the best GA systems reported in the literature.

Rights:
All rights reserved (no additional license for public reuse)
Language:
English
Source Citation:

Cohoon, James, John Karro, WN Martin, William Niebel, and Klaus Nagel. "Perturbation Method for Probabilistic Search for the Traveling Salesperson Problem." University of Virginia Dept. of Computer Science Tech Report (1998).

Publisher:
University of Virginia, Department of Computer Science
Published Date:
1998