Scandinavian Working Papers in Business Administration

CORAL Working Papers,
University of Aarhus, Aarhus School of Business, Department of Business Studies

No L-2006-04: A Column Generation Approach to the Capacitated Vehicle Routing Problem with Stochastic Demands

Christian H. Christiansen () and Jens Lysgaard
Additional contact information
Christian H. Christiansen: Department of Business Studies, Postal: The Aarhus School of Business, Fuglesangs Allé 4, 8210 Aarhus V, Denmark
Jens Lysgaard: Department of Business Studies, Postal: The Aarhus School of Business, Fuglesangs Allé 4, 8210 Aarhus V, Denmark

Abstract: In this article we introduce a new exact solution approach to the Capacitated Vehicle Routing Problem with Stochastic Demands (CVRPSD). In particular, we consider the case where all customer demands are distributed independently and where each customer’s demand follows a Poisson distribution. The CVRPSD can be formulated as a Set Partitioning Problem. We show that, under the above assumptions on demands, the associated column generation subproblem can be solved using a dynamic programming scheme which is similar to that used in the case of deterministic demands. To evaluate the potential of our approach we have embedded this column generation scheme in a branch-and-price algorithm. Computational experiments on a large set of test instances show promising results

Keywords: Routing; Stochastic programming; Logistics; Branch and Bound; Dynamic programming

17 pages, March 1, 2006

Full text files

L_2006_04.pdf PDF-file 

Download statistics

Questions (including download problems) about the papers in this series should be directed to Helle Vinbaek Stenholt ()
Report other problems with accessing this service to Sune Karlsson ().

This page generated on 2024-02-05 17:10:04.