Reference : A comparative study of branch-and-price algorithms for vehicle routing with time wind...
Scientific congresses and symposiums : Unpublished conference/Abstract
Business & economic sciences : Quantitative methods in economics & management
A comparative study of branch-and-price algorithms for vehicle routing with time windows and waiting time costs
Michelini, Stefano mailto [Université de Liège - ULiège > HEC Liège : UER > UER Opérations >]
Arda, Yasemin mailto [Université de Liège - ULiège > HEC Liège : UER > UER Opérations : Supply Chain Management >]
Küçükaydın, Hande mailto [MEF University, Istanbul > Industrial Engineering > > >]
EURO 2018 - 29th European Conference on Operational Research
from 8-7-2018 to 11-7-2018
EURO – the European Association of Operational Research Society
[en] Vehicle Routing Problem ; Branch-and-Price ; Time Windows ; Column Generation ; Labeling algorithms
[en] Branch-and-price is a leading methodology for solving routing problems. Several studies have investigated labeling algorithms to solve the related pricing problem, which is usually a variant of the elementary shortest path problem with resource constraints. Solving this problem efficiently is crucial, since it is a performance bottleneck for the branch-and-price procedure. Such algorithms include methods like decremental state space relaxation, ng-route relaxation, and hybrids of these two. These focus on how to treat efficiently the elementarity constraints, since they tend to make label domination difficult, which translates to more computational resources used. In this study, we investigate the performance of these methods in a branch-and-price framework. The problem under consideration is a variant of the vehicle routing problem with time windows in which waiting times have a linear cost. We first parametrize several algorithmic components. Then, we search for good parameter configurations for each algorithm with irace, a tool for automated parameter tuning that generates and runs a very high number of configurations on a set of tuning instances and uses statistical tests to determine the best performing configuration. Finally, we run all final configurations on the Solomon benchmark instances and analyze the results with statistical tests. Our results show that a class of hybrid algorithms with certain features based on ng-route relaxation outperforms all the others.

File(s) associated to this reference

Fulltext file(s):

Open access
euro2018_Michelini.pdfAuthor postprint353.77 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.