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