Four heuristic solution procedures to the travelling salesman problem and an application to the multi-depot vehicle routing problem

Abstract

This study consists of two parts. In the first part, four heuristic algorithms for solving the Travelling Salesman Problem (TSP) is developed. Given a graph, the first algorithm forms a subgraph in which the necessary conditions for the existence of a travelling salesman tour are satisfied. In case the subgraph does not contain any travelling salesman tour, Little's bcanch and bound algorithm is partially applied to the resultant cost matrix. The second algorithm, starts with the minimum cost assignment and ranks the assignment solutions in ascending costs by introducing subtour breaking constraints. The third algorithm produces some best achievable n-paths which start from a root node and end at some node incident to the root node. These paths are then completed to travelling salesman tours and the least cost tour is taken as the best achievable solution. A geometric approach to solving the TSP is described in the last algorithm. Starting with a partial tour, the algorithm determines which of the remaining nodes are to be inserted between which consecutive pair of nodes on the subtour and in what order. After all, a summary of computational results regarding both the efficiency and the computational effort of all the algorithms is presented.