Planning Approximations to the Length of TSP and VRP Problems

Abstract

This paper studies parsimonious, intuitive, and effective formulas to approximate the length of Traveling Salesman Problems (TSP) and Vehicle Routing Problems (VRP). Using intuition derived from continuous models and graph theory, a formula to approximate the length of vehicle routes is proposed. In instances with different patterns of customer spatial distribution, time windows, customer demands, and depot locations are used to test the proposed approximation. Regression results show that the approximation can reasonably predict the length of TSP and VRP problems in randomly generated problems and real urban networks. Expressions for the incremental cost of serving an additional customer or increasing the number of routes are derived and estimated. The main contribution of this paper is to develop and test intuitive approximations to TSP and VRP problem in general settings. The approximations are valuable for strategic and planning analysis of transportation and logistics problems.