Reference : Column Generation Based Algorithms for a VRP with Time Windows and Variable Departure...
Scientific congresses and symposiums : Unpublished conference/Abstract
Business & economic sciences : Quantitative methods in economics & management
http://hdl.handle.net/2268/202357
Column Generation Based Algorithms for a VRP with Time Windows and Variable Departure Times
English
Michelini, Stefano mailto [Université de Liège > HEC-Ecole de gestion : UER > UER Opérations : Supply Chain Management >]
Arda, Yasemin mailto [Université de Liège > HEC-Ecole de gestion : UER > UER Opérations : Supply Chain Management >]
Küçükaydin, Hande mailto [MEF University, Istanbul > > > >]
5-Jul-2016
Yes
International
EURO 2016 - 28th European Conference on Operational Research
from 3-7-2016 to 6-7-2016
EURO – the European Association of Operational Research Society
Poznan
Poland
[en] VRP ; Column Generation
[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.
http://hdl.handle.net/2268/202357

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
euro2016.pdfAuthor postprint811.96 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.