Unpublished conference/Abstract (Scientific congresses and symposiums)
Column Generation Based Algorithms for a VRP with Time Windows and Variable Departure Times
Michelini, Stefano; Arda, Yasemin; Küçükaydin, Hande
2016EURO 2016 - 28th European Conference on Operational Research
 

Files


Full Text
euro2016.pdf
Author postprint (831.45 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
VRP; Column Generation
Abstract :
[en] We investigate a solution methodology for a variant of the VRP with time windows. In the examined variant, the departure time of each vehicle from the depot can be determined by the decision-maker, who aims at minimizing the overall duration of the routes, including waiting times, while respecting the maximum allowed working duration of each vehicle. In order to solve this problem with a branch-and-price methodology, we address the associated pricing problem as an elementary shortest path problem with resource constraints (ESPPRC). We propose an adapted bidirectional dynamic programming algorithm for the studied ESPPRC. The decremental state space relaxation (DSSR) technique is also implemented as an acceleration technique both to obtain ng-routes and elementary routes. Several implementation and integration strategies are considered for the DSSR and ng-route relaxation techniques. The ng-route pricing and the elementary route pricing algorithms are compared inside a column generation procedure. For both column generation procedures, the algorithmic choices are made and the values of the numerical parameters are determined using an automatic algorithm configuration tool, the irace package. Finally, we discuss how these column generation procedures can be included as a component in the development of a matheuristic.
Disciplines :
Quantitative methods in economics & management
Author, co-author :
Michelini, Stefano ;  Université de Liège > HEC-Ecole de gestion : UER > UER Opérations : Supply Chain Management
Arda, Yasemin  ;  Université de Liège > HEC-Ecole de gestion : UER > UER Opérations : Supply Chain Management
Küçükaydin, Hande;  MEF University, Istanbul
Language :
English
Title :
Column Generation Based Algorithms for a VRP with Time Windows and Variable Departure Times
Publication date :
05 July 2016
Event name :
EURO 2016 - 28th European Conference on Operational Research
Event organizer :
EURO – the European Association of Operational Research Society
Event place :
Poznan, Poland
Event date :
from 3-7-2016 to 6-7-2016
Audience :
International
Available on ORBi :
since 05 October 2016

Statistics


Number of views
148 (12 by ULiège)
Number of downloads
105 (2 by ULiège)

Bibliography


Similar publications



Contact ORBi