Reference : Combining acceleration techniques for pricing in a VRP with time windows
Scientific congresses and symposiums : Unpublished conference/Abstract
Business & economic sciences : Quantitative methods in economics & management
Combining acceleration techniques for pricing in a VRP with time windows
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 > > > >]
[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.
[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.
ORBEL30 - 30th meeting of the Belgian Operational Research Society
from 28-1-2016 to 29-1-2016
Université catholique de Louvain
[en] VRP ; Branch-and-Price ; Column Generation
[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.
Researchers ; Students

File(s) associated to this reference

Fulltext file(s):

Open access
orbel30slides.pdfAuthor postprint390.37 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.