A heuristic circulation-network approach to solve the multi-traveling salesman problem

✍ Scribed by Alberto Garcia-Diaz

• Publisher: John Wiley and Sons
• Year: 1985
• Tongue: English
• Weight: 561 KB
• Volume: 15
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.3230150407

✦ Synopsis

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.