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, http://www.asb.dk/staff/bs/chc.aspx?page=%7B803EFF10-69F7-4C0F-AEE3-F7F410E4B6F2%7D
Jens Lysgaard: Department of Business Studies, Postal: The Aarhus School of Business, Fuglesangs Allé 4, 8210 Aarhus V, Denmark, http://www.asb.dk/staff/bs/lys.aspx?page=%7B803EFF10-69F7-4C0F-AEE3-F7F410E4B6F2%7D

No L-2006-04, CORAL Working Papers from University of Aarhus, Aarhus School of Business, Department of Business Studies

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 (search for similar items in EconPapers)
Pages: 17 pages
Date: 2006-03-01
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.hha.dk/bs/wp/log/L_2006_04.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 500 Can't connect to www.hha.dk:80 (No such host is known. )

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hhb:aarbls:2006-004

Access Statistics for this paper

More papers in CORAL Working Papers from University of Aarhus, Aarhus School of Business, Department of Business Studies The Aarhus School of Business, Fuglesangs Allé 4, DK-8210 Aarhus V, Denmark. Contact information at EDIRC.
Bibliographic data for series maintained by Helle Vinbaek Stenholt ( this e-mail address is bad, please contact ).