Premium
A heuristic circulation‐network approach to solve the multi‐traveling salesman problem
Author(s) -
GarciaDiaz Alberto
Publication year - 1985
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230150407
Subject(s) - travelling salesman problem , mathematical optimization , representation (politics) , heuristic , context (archaeology) , computer science , set (abstract data type) , flow network , mathematics , paleontology , politics , political science , law , biology , programming language
The overall methodology developed in this paper can be organized into two major parts. The first part consists of a representation of the Multi‐Traveling Salesman Problem as a network circulation model. The second part is a subtour elimination procedure. The circulation‐network representation of the Multi‐Traveling Salesman Problem allows the generation of a starting solution which satisfies the optimality LP conditions of the network, but which may not be feasible in the context of the original problem due to the existence of subtours. The proposed network algorithm iteratively reduces the set of solutions with subtours by eliminating one link and then rerouting its flow, using the remaining arcs without violating their LP optimality conditions. Computational results based on a sample of 91 randomly generated problems are reported.