New Model for Vehicle Routing Problems in Real Road Networks

Session : LTSS5-3 / LTSS5 : Problèmes de transport riches
Jeudi 11 février 15:00 - 16:40 Salle : GI041
Hamza Ben Ticha, Nabil Absi, Dominique Feillet et Alain Quilliot

Vehicle routing problems have drawn many researchers’ attention. Most of proposed approaches are based on a key assumption is that the best-destination is well defined in the road network, and so the problem can be treated via a simple graph representation. In real-life applications, several attributes have to be defined on the road network. And consequently, alternative paths presenting different trade-off exist and should be considered when solving the problem. In this study, we propose to represent the road network using a multigraph representation. Each arc defines a possible path connecting two customers’ locations. In the context of time-constrained vehicle routing problem (Vehicle Routing Problem with Time Windows), we propose an Adaptive Large Neighborhood Search heuristic and a Branch-and-Price exact method. Computational experiments on modified benchmarks from the literature and on generated instances show the positive impact of the multigraph impact and cost savings obtained.

Mots clés : Vehicle Routing Problems with Time Windows, Road network, multigraph