Unpublished conference/Abstract (Scientific congresses and symposiums)
Combining acceleration techniques for pricing in a VRP with time windows
Michelini, Stefano; Arda, Yasemin; Küçükaydin, Hande
2016ORBEL 30 - 30th annual conference of the Belgian Operational Research Society
Editorial reviewed
 

Files


Full Text
orbel30slides.pdf
Author postprint (399.74 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
VRP; Branch-and-Price; Column Generation
Abstract :
[en] In this study, we investigate a solution methodology for a variant of the VRP with time windows. The cost of each route depends on its overall duration (including waiting times), while the departure time of a vehicle is a decision variable. Furthermore, each route has a maximum permitted duration. In order to solve this problem with a branch-and-price methodology, we study also the associated pricing problem, an elementary shortest path problem with resource constraints (ESPPRC). Compared to the classical ESPPRC, this variant admits an infinite number of Pareto-optimal states. In order to tackle this, it was shown in [1] that it is possible to represent the total travelling time as a piecewise linear function of the service start time at the depot. Together with this representation, an appropriate label structure and domi- nance rules are proposed and integrated into an exact bidirectional dynamic programming algorithm [2]. It is possible to implement certain acceleration techniques in the dynamic program- ming algorithm used to solve the pricing problem. We focus on two of these techniques: decremental state space relaxation (DSSR), introduced in [3], and ng-route relaxation, in- troduced in [4] and [5]. DSSR aims to enforce gradually the constraints on the elementarity of the path, which adversely affect the number of generated and dominated labels. A set of critical nodes is iteratively populated, and elementarity is enforced only on these critical nodes. When using ng-route relaxation, a neighbourhood is defined for each vertex. Then, the labels are extended such that, thanks to this neighbourhood structure, it is possible to allow only cycles that are relatively expensive and therefore less likely to appear in the optimal solution. In this study, we explore several different strategies used to apply these techniques, for example initialization strategies for the critical vertex set in DSSR, or the size of the neighbourhoods for ng-route relaxation. We also analyze two ways of combining DSSR and ng-route relaxation. The different algorithmic choices are represented as categorical parameters. The categorical parameters, together with the numerical ones, can be tuned with tools for automatic algorithm configuration such as the irace package [6]. We discuss how this column generation procedure can be included as a component in the development of a matheuristic based on the idea in [7], which consists in a collaboration scheme between a branch-and-price algorithm, an exact MIP solver, and a metaheuristic.
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 :
Combining acceleration techniques for pricing in a VRP with time windows
Publication date :
28 January 2016
Event name :
ORBEL 30 - 30th annual conference of the Belgian Operational Research Society
Event organizer :
Université catholique de Louvain
Event place :
Louvain-la-Neuve, Belgium
Event date :
from 28-1-2016 to 29-1-2016
Peer reviewed :
Editorial reviewed
References of the abstract :
[1] Küçükaydin, H., Arda, Y., & Crama, Y. (2014). Optimization of the service start time for an elementary shortest path problem with time windows. Working paper, Université de Liège. http://hdl.handle.net/2268/170446. [2] Righini, G., & Salani, M. (2006). Symmetry helps: bounded bi-directional dynamic pro- gramming for the elementary shortest path problem with resource constraints. Discrete Optimization, 3(3):255-273. [3] Righini, G., & Salani, M. (2008). New dynamic programming algorithms for the resource constrained elementary shortest path problem. Networks, 51(3):155-170. [4] Baldacci, R., Bartolini, E., Mingozzi, A., & Roberti, R. (2010). An exact solution framework for a broad class of vehicle routing problems. Computational Management Science, 7(3):229-268. [5] Baldacci, R., Mingozzi, A., & Roberti, R. (2011). New route relaxation and pricing strategies for the vehicle routing problem. Operations research, 59(5):1269-1283. [6] López-Ibánez, M., Dubois-Lacoste, J., Stützle, T., & Birattari, M. (2011). The irace package, iterated race for automatic algorithm configuration. Technical Report TR/IRIDIA/2011-004, IRIDIA, Université Libre de Bruxelles, Belgium. [7] Danna, E., & Le Pape, C. (2005). Branch-and-price heuristics: A case study on the vehicle routing problem with time windows. Column Generation, 99-129.
Available on ORBi :
since 14 April 2016

Statistics


Number of views
136 (12 by ULiège)
Number of downloads
129 (2 by ULiège)

Bibliography


Similar publications



Contact ORBi