No full text
Unpublished conference/Abstract (Scientific congresses and symposiums)
Optimization of Service Start Time for an Elementary Shortest Path Problem
Kucukaydin, Hande; Arda, Yasemin; Crama, Yves
2013VeRoLog 2013 - Annual Workshop of the EURO Working Group on Vehicle Routing and Logistics optimization
Editorial reviewed
 

Files


Full Text
No document available.

Send to



Details



Abstract :
[en] We are concerned with an elementary shortest path problem with resource constraints (ESPPRC), where there is a capacitated single vehicle at the depot for serving a set of delivery and backhaul customers with a time window. On a given route, the vehicle can visit a backhaul customer only after all its delivery customers are visited, where the delivery and backhaul customers are considered to be two disjoint sets. Split deliveries and pick-ups are not allowed. In this problem, the vehicle may be assigned to several routes. In addition, the vehicle can begin servicing the customers at any desired time and can be used for at most a fixed amount of time that depends on the shift duration of the assigned driver. Distance and time based variable costs are incurred by serving the customers. Namely, the total cost depends on the total distance traveled and the total amount of time that the vehicle spends by performing the assigned multiple trips. On the other hand, serving a customer yields also a revenue. Therefore, the objective is to determine the optimal service start time of the vehicle from the depot along with the trips to be performed in order to minimize the total of the distance and time costs minus the collected revenues. Such a problem can be faced as the pricing subproblem in branch-and-price algorithms for vehicle routing problems with additional constraints, where the revenues are equivalent to the dual prizes of the visited vertices. In general, ESPPRC can be solved to optimality by using a dynamic programming algorithm. However, since the vehicle can start the service at any point in time and is paid based on the total time during which it has been used, our ESPPRC has to take an infinite number of Pareto-optimal states into account. Therefore, we adapt the well-known dynamic programming algorithm according to this feature and develop piecewise linear time functions that represent total traveling and waiting time depending on a variable start time at the depot. Consequently, we propose appropriate dominance rules to discard feasible paths that cannot lead to the optimal solution. Finally, computational results are presented.
Disciplines :
Production, distribution & supply chain management
Author, co-author :
Kucukaydin, Hande ;  Université de Liège - ULiège > HEC-Ecole de gestion : UER > UER Opérations : Supply Chain Management
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
Language :
English
Title :
Optimization of Service Start Time for an Elementary Shortest Path Problem
Publication date :
08 July 2013
Event name :
VeRoLog 2013 - Annual Workshop of the EURO Working Group on Vehicle Routing and Logistics optimization
Event organizer :
University of Southampton
Event place :
Southampton, United Kingdom
Event date :
from 07-07-2013 to 10-07-2013
Audience :
International
Peer reviewed :
Editorial reviewed
Available on ORBi :
since 15 July 2013

Statistics


Number of views
112 (14 by ULiège)
Number of downloads
0 (0 by ULiège)

Bibliography


Similar publications



Contact ORBi