Planning Approximations to the Length of TSP and VRP Problems
Access status:
Open Access
Type
Working PaperAuthor/s
Figliozzi, Miguel AndresAbstract
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 ...
See moreThis 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.
See less
See moreThis 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.
See less
Date
2007-03-01Department, Discipline or Centre
ITLSShare