Empirical analysis for the VRPTW with a multigraph representation for the road network

Vehicle routing problems have drawn researchers' attention for more than fifty years. Most approaches found in the literature are based on the key assumption that for each pair of points of interest (e.g., customers, depot...), the best origin-destination path can be computed. Thus, the problem can be addressed via a simple graph representation, where nodes represent points of interest and arcs represent the best paths. Yet, in practice, it is common that several attributes are defined on road segments. Consequently, alternative paths presenting different trade-offs exist between points of interest. In this study, we investigate in depth a special representation of the road network proposed in the literature and called a multigraph. This representation enables one to maintain all these alternative paths in the solution space. We present an empirical analyses based on the Vehicle Routing Problem with Time Windows, as a test bed problem, solved with branch-and-price algorithms developed for the different types of graphs. Computational experiments on modified benchmarks from the literature and on instances derived from real data evaluate the impact of the modeling on solution quality.