Aarhus University Seal / Aarhus Universitets segl

A Column Generation Approach to the Capacitated Vehicle Routing Problem with Stochastic Demands

Research output: Working paperResearch

Documents

  • L 2006 04

    Final published version, 304 KB, PDF document

  • Department of Business Studies
  • CORAL - Centre for Operations Research Applications in Logistics
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.
Original languageEnglish
Place of publicationAarhus
PublisherAarhus School of Business, Department of Business Studies
Number of pages17
ISBN (Electronic)8778821215
Publication statusPublished - 2006

See relations at Aarhus University Citationformats

Download statistics

No data available

ID: 32345412