Vehicle routing with soft time windows and stochastic travel times : a column generation and branch-and-price solution approach

Onderzoeksoutput: Boek/rapportRapportAcademic

603 Downloads (Pure)

Samenvatting

We study a vehicle routing problem with soft time windows and stochastic travel times. In this problem, we consider stochastic travel times to obtain routes which are both efficient and reliable. In our problem setting, soft time windows allow early and late servicing at customers by incurring some penalty costs. The objective is to minimize the sum of transportation costs and service costs. Transportation costs result from three elements which are the total distance traveled, the number of vehicles used and the total expected overtime of the drivers. Service costs are incurred for early and late arrivals; these correspond to time-window violations at the customers. We apply a column generation procedure to solve this problem. The master problem can be modeled as a classical set partitioning problem. The pricing subproblem, for each vehicle, corresponds to an elementary shortest path problem with resource constraints. To generate an integer solution, we embed our column generation procedure within a branch-and-price method. Computational results obtained by experimenting with well-known problem instances are reported.
Originele taal-2Engels
Plaats van productieEindhoven
UitgeverijTechnische Universiteit Eindhoven
Aantal pagina's38
StatusGepubliceerd - 2012

Publicatie series

NaamBETA publicatie : working papers
Volume392
ISSN van geprinte versie1386-9213

Vingerafdruk

Duik in de onderzoeksthema's van 'Vehicle routing with soft time windows and stochastic travel times : a column generation and branch-and-price solution approach'. Samen vormen ze een unieke vingerafdruk.

Citeer dit