Program > By author > Quilliot Alain

The Vehicle Routing Problem (VRP) can be described as the problem of designing a set of routes starting and ending at a depot to serve a set of customers using a fleet of vehicles. Most of proposed approaches are based on a key assumption is that the best connection between each pair of customers' locations in the road network is well defined and so the problem can be modeled with a simple weighted graph. But this assumption is not guaranteed to hold in real-world applications, as several attributes needed to be considered to model correctly the road network. Consequently, alternative paths proposing different trade-offs can be defined in the road network and not considering these alternative paths when solving the problem may be disadvantageous and potential solution could be discarded from solution space. A typical example of this situation is provided by the time-constrained vehicle routing problem VRPTW (the Vehicle Routing Problem with Time Windows). In this study, we propose to represent the road network with a multigraph representation such that we consider all possible paths between each pair of customers' locations. To illustrate the impact of our modelling approach, we developed an Adaptive Large Neighborhood Search algorithm and a Branch-and-Price exact Method. Computational experiments on modified benchmarks from the literature and on real instances show the positive impact of the multigraph impact and cost savings obtained.