Eprint first made available on ORBi (E-prints, working papers and research blog)
Optimization of the service start time for an elementary shortest path problem with time windows
Küçükaydın, Hande; Arda, Yasemin; Crama, Yves
2014
 

Files


Full Text
Kucukaydin_Arda_Crama_27032018.pdf
Author preprint (668.97 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
elementary shortest path problem with resource constraints; dynamic programming; column generation
Abstract :
[en] We investigate an elementary shortest path problem with resource constraints where a single capacitated vehicle, initially located at a depot, must serve a set of customers while respecting their individual time windows. When the vehicle visits a customer, it delivers the customer's demand and collects a revenue in return for the delivery. The vehicle can start its trip at any desired time. The transportation cost is a function of both the total distance traveled and the duration of the assigned trip. The objective is to determine the service start time from the depot, the subset of customers to be served, and the trip to be performed so as to minimize the total loss, which is calculated as the di erence between the transportation cost and the revenue collected from the customers. We develop two exact dynamic programming algorithms which can deal with an in nite number of Pareto-optimal states arising from the fact that the starting time and the duration of the trip act like continuous decision variables. We report computational results obtained with these algorithms and with a faster heuristic for the elementary shortest path problem. We also examine the performance of these algorithms when they are used to solve the pricing subproblem arising in the framework of a column generation algorithm for a related vehicle routing problem with time windows.
Research center :
QuantOM Research Centre
Disciplines :
Production, distribution & supply chain management
Quantitative methods in economics & management
Author, co-author :
Küçükaydın, Hande;  MEF University > Department of Industrial Engineering
Arda, Yasemin  ;  Université de Liège - ULiège > HEC Liège : UER > UER Opérations : Supply Chain Management
Crama, Yves  ;  Université de Liège - ULiège > HEC Liège : UER > Recherche opérationnelle et gestion de la production
Language :
English
Title :
Optimization of the service start time for an elementary shortest path problem with time windows
Publication date :
11 July 2014
Number of pages :
45
Funders :
F.R.S.-FNRS - Fonds de la Recherche Scientifique [BE]
Interuniversity Attraction Poles Programme of the Belgian Science Policy (Grant P7/36)
Service public de Wallonie : Direction générale opérationnelle de l'économie, de l'emploi et de la recherche - DG06 (Programme START, Convention 917018)
Available on ORBi :
since 11 July 2014

Statistics


Number of views
343 (35 by ULiège)
Number of downloads
171 (16 by ULiège)

Bibliography


Similar publications



Contact ORBi