T. H. Dang, A. Letchford, B. Boyaci
Vehicle Routing Problems (VRPs) are an important and much-studied family of combinatorial optimisation problems. Most exact VRP algorithms assume that the instance is defined on a complete graph, and many heuristics assume that the instance is planar and Euclidean. In practice, of course, most VRPs are defined on road networks. It is sometimes possible to convert road-network instances into complete instances, by solving shortest-path problems. Sometimes, however, such a conversion is not possible. (This may be due to memory limitations, or to the nature of the objective and constraints.) In that case, one possible heuristic approach is to solve a modified version of the problem, in which true road distances are replaced with planar Euclidean distances. We conduct extensive computational experiments to explore the quality of this heuristic scheme. In particular, we create and solve $96$ instances of the Steiner Travelling Salesman Problem and Capacitated VRP, using real road network data from twelve cities across the world. It turns out that the heuristic works rather well in most cases.
Keywords: vehicle routing problems, traveling salesman problem, road networks, combinatorial optimisation.
Scheduled
FA3 Routing
June 11, 2021 9:15 AM
3 - TC Koopmans
