Loading…

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

•We study a vehicle routing problem with soft time windows and stochastic travel times.•We deal with a formulation that considers both service costs and transportation costs.•We propose an exact solution approach based on column generation and branch-and-price.•Comprehensive numerical study is provi...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2014-08, Vol.236 (3), p.789-799
Main Authors: Taş, D., Gendreau, M., Dellaert, N., van Woensel, T., de Kok, A.G.
Format: Article
Language:English
Subjects:
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•We study a vehicle routing problem with soft time windows and stochastic travel times.•We deal with a formulation that considers both service costs and transportation costs.•We propose an exact solution approach based on column generation and branch-and-price.•Comprehensive numerical study is provided. 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.
ISSN:0377-2217
1872-6860
DOI:10.1016/j.ejor.2013.05.024