Empirical analysis for the VRPTW with a multigraph representation for the road network. (December 2017)

• Record Type: Journal Article
• Authors: Ben Ticha, Hamza; Absi, Nabil; Feillet, Dominique; Quilliot, Alain
• Is Part Of: Computers & operations research. Volume 88(2017)
• Page Start: 103
• Page End: 116
• Publication Date: 2017-12
• Subjects: Vehicle routing problems -- Road networks -- Multigraph -- Branch-and-Price; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2017.06.024
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract : Highights: This work considers vehicle routing problems on road networks. A multigraph representation of the road network is investigated. A Branch-and-Price algorithm is developed for the multigraph based VRPTW. The multigraph representation can significantly improve the VRPTW solution. Abstract: 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.