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.


FA3 Routing
June 11, 2021  9:15 AM
3 - TC Koopmans

Latest news

  • 6/5/21
    Conference abstract book

Cookie policy

We use cookies in order to be able to identify and authenticate you on the website. They are necessary for the correct functioning of it, and therefore they can not be disabled. If you continue browsing the website, you are agreeing with their acceptance, as well as our Privacy Policy.

Additionally, we use Google Analytics in order to analyze the website traffic. They also use cookies and you can accept or refuse them with the buttons below.

You can read more details about our Cookie Policy and our Privacy Policy.