A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands

被引：113

作者：

Christiansen, Christian H. ^{[1
]}

Lysgaard, Jens ^{[1
]}

机构：

[1] Univ Aarhus, Aarhus Sch Business, Dept Business Studies, DK-8210 Aarhus V, Denmark

来源：

OPERATIONS RESEARCH LETTERS | 2007年 / 35卷 / 06期

关键词：

routing; stochastic programming; logistics;

D O I：

10.1016/j.orl.2006.12.009

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

This article introduces a new exact algorithm for the capacitated vehicle routing problem with stochastic demands (CVRPSD). The CVRPSD can be formulated as a set partitioning problem and it is shown that the associated column generation subproblem can be solved using a dynamic programming scheme. Computational experiments show promising results. (C) 2007 Elsevier B.V. All rights reserved.

引用

页码：773 / 781

页数：9

共 20 条

[1] A VEHICLE-ROUTING PROBLEM WITH STOCHASTIC DEMAND [J].

BERTSIMAS, DJ .

OPERATIONS RESEARCH, 1992, 40 (03) :574-586

[2] AN ALGORITHM FOR VEHICLE-DISPATCHING PROBLEM [J].

CHRISTOF.N ;

EILON, S .

OPERATIONAL RESEARCH QUARTERLY, 1969, 20 (03) :309-&

[3] EXACT ALGORITHMS FOR THE VEHICLE-ROUTING PROBLEM, BASED ON SPANNING TREE AND SHORTEST-PATH RELAXATIONS [J].

CHRISTOFIDES, N ;

MINGOZZI, A ;

TOTH, P .

MATHEMATICAL PROGRAMMING, 1981, 20 (03) :255-282

[4] SCHEDULING OF VEHICLES FROM CENTRAL DEPOT TO NUMBER OF DELIVERY POINTS [J].

CLARKE, G ;

WRIGHT, JW .

OPERATIONS RESEARCH, 1964, 12 (04) :568-&

[5]

Cook W., 1999, A Parallel Cutting-Plane Algorithm for the Vehicle Routing Problem with Time Windows

[6]

Desaulniers G, 2006, Column Generation, V5

[7] ROUTING WITH TIME WINDOWS BY COLUMN GENERATION [J].

DESROSIERS, J ;

SOUMIS, F ;

DESROCHERS, M ;

GERAD .

NETWORKS, 1984, 14 (04) :545-565

[8] VEHICLE-ROUTING WITH STOCHASTIC DEMANDS - PROPERTIES AND SOLUTION FRAMEWORKS [J].

DROR, M ;

LAPORTE, G ;

TRUDEAU, P .

TRANSPORTATION SCIENCE, 1989, 23 (03) :166-176

[9] STOCHASTIC VEHICLE-ROUTING WITH MODIFIED SAVINGS ALGORITHM [J].

DROR, M ;

TRUDEAU, P .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1986, 23 (02) :228-235

[10] Robust branch-and-cut-and-price for the capacitated vehicle routing problem [J].

Fukasawa, R ;

Longo, H ;

Lysgaard, J ;

de Aragao, MP ;

Reis, M ;

Uchoa, E ;

Werneck, RF .

MATHEMATICAL PROGRAMMING, 2006, 106 (03) :491-511

← 1 2 →