Item Details

Perturbation Method for Probabilistic Search for the Traveling Salesperson Problem

Cohoon, James; Karro, John; Martin, WN; Niebel, William; Nagel, Klaus
Cohoon, James
Karro, John
Martin, WN
Niebel, William
Nagel, Klaus
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.
University of Virginia, Department of Computer Science, 1998
Published Date
Libra Open Repository
Logo for In CopyrightIn Copyright


Access Online