No full text
Unpublished conference/Abstract (Scientific congresses and symposiums)
An exact bi-directional dynamic programming algorithm for an elementary shortest path problem with variable service start time
Arda, Yasemin; Crama, Yves; Kucukaydin, Hande
2014ORBEL 28 - 28th annual conference of the Belgian Operational Research Society
Editorial reviewed
 

Files


Full Text
No document available.

Send to



Details



Keywords :
elementary shortest path problem with resource constraints; dynamic programming; column generation
Abstract :
[en] We consider an elementary shortest path problem with resource constraints (ESPPRC), where a capacitated single vehicle serves customers by respecting their associated time windows. The vehicle can start servicing the customers at any desired time, but it can be used for a fixed amount of time. The total transportation cost depends on the total distance traveled and the total amount of time that the vehicle spends by performing the assigned trip. On the other hand, each served customer yields a revenue. Thus, the aim is to identify the path to be followed and the start time of the vehicle from the depot that minimize the total transportation cost minus the gained revenues. This kind of a problem can be encountered as a pricing subproblem when a branch-and-price algorithm is applied to solve vehicle routing problems with additional constraints. In such a case, the revenues correspond to the dual prices of the visited vertices. It is known that the classical ESPPRC can be solved to optimality by implementing a dynamic programming (DP) algorithm. However, our problem has to take an infinite number of Pareto-optimal states into consideration, since the vehicle can leave the depot at any point in time and charges depending on the total traveling and waiting time. We propose an exact DP algorithm which can deal with an infinite number of Pareto-optimal states by representing total traveling and waiting time as a piecewise linear function of the service start time at the depot and develop suitable dominance rules. Furthermore, a column generation algorithm is devised for solving the relaxed set covering formulation of the related vehicle routing problem where new columns are determined by the proposed DP algorithm. Finally, computational results are presented.
Disciplines :
Production, distribution & supply chain management
Author, co-author :
Arda, Yasemin  ;  Université de Liège - ULiège > HEC-Ecole de gestion : UER > UER Opérations : Supply Chain Management
Crama, Yves  ;  Université de Liège - ULiège > HEC-Ecole de gestion : UER > Recherche opérationnelle et gestion de la production
Kucukaydin, Hande ;  Université de Liège - ULiège > HEC-Ecole de gestion : UER > UER Opérations : Supply Chain Management
Language :
English
Title :
An exact bi-directional dynamic programming algorithm for an elementary shortest path problem with variable service start time
Publication date :
31 January 2014
Event name :
ORBEL 28 - 28th annual conference of the Belgian Operational Research Society
Event organizer :
UMons
Event place :
Mons, Belgium
Event date :
from 30-01-2014 to 31-01-2014
Peer reviewed :
Editorial reviewed
Available on ORBi :
since 15 May 2014

Statistics


Number of views
213 (1 by ULiège)
Number of downloads
0 (0 by ULiège)

Bibliography


Similar publications



Contact ORBi