Some new bounds for the travelling salesman problem

Abstract

The Clarke and Wright heuristic for the travelling salesman problem (TSP) has been used for several decades as a tool for finding good solutions for TSP and other vehicle routing problems (VRP). In this paper we offer a simple, but fundamental relationship between the cost of a Hamiltonian cycle measured in the original cost matrix and the cost of the same cycle measured in a saving matrix. This relationship leads to a new and simple lower bound for TSP that some times is better than more traditional bounds based on so-called 1-trees. We also offer some upper bounds for the optimal solution of TSP. Some examples are given in order to illustrate the new bounds and compare these with the classical ones.