Accelerated label setting algorithms for the elementary resource constrained shortest path problem

被引：133

作者：

Boland, N

Dethridge, J

Dumitrescu, I

机构：

[1] HEC Montreal, Canada Res Chair Distribut Management, CRT, Montreal, PQ H3C 3J7, Canada

[2] Univ Melbourne, Dept Math & Stat, Melbourne, Vic, Australia

来源：

OPERATIONS RESEARCH LETTERS | 2006年 / 34卷 / 01期

关键词：

shortest paths; networks; dynamic programming; column generation;

D O I：

10.1016/j.orl.2004.11.011

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

A label setting algorithm for solving the Elementary Resource Constrained Shortest Path Problem, using node resources to forbid repetition of nodes on the path, is implemented. A state-space augmenting approach for accelerating run times is considered. Several augmentation strategies are suggested and compared numerically. (c) 2005 Elsevier B.V. All rights reserved.

引用

收藏

页码：58 / 68

页数：11

相关论文

共 13 条

[1] SHORTEST CHAIN SUBJECT TO SIDE CONSTRAINTS [J].

ANEJA, YP ;

AGGARWAL, V ;

NAIR, KPK .

NETWORKS, 1983, 13 (02) :295-302

[2] Flight string models for aircraft fleeting and routing [J].

Barnhart, C ;

Boland, NL ;

Clarke, LW ;

Johnson, EL ;

Nemhauser, GL ;

Shenoi, RG .

TRANSPORTATION SCIENCE, 1998, 32 (03) :208-220

[3] AN ALGORITHM FOR THE RESOURCE CONSTRAINED SHORTEST-PATH PROBLEM [J].

BEASLEY, JE ;

CHRISTOFIDES, N .

NETWORKS, 1989, 19 (04) :379-394

[4] 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

[5] A NEW OPTIMIZATION ALGORITHM FOR THE VEHICLE-ROUTING PROBLEM WITH TIME WINDOWS [J].

DESROCHERS, M ;

DESROSIERS, J ;

SOLOMON, M .

OPERATIONS RESEARCH, 1992, 40 (02) :342-354

[6] NOTE ON THE COMPLEXITY OF THE SHORTEST-PATH MODELS FOR COLUMN GENERATION IN VRPTW [J].

DROR, M .

OPERATIONS RESEARCH, 1994, 42 (05) :977-978

[7] An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems [J].

Feillet, D ;

Dejax, P ;

Gendreau, M ;

Gueguen, C .

NETWORKS, 2004, 44 (03) :216-229

[8] FLIGHT CREW SCHEDULING [J].

GRAVES, GW ;

MCBRIDE, RD ;

GERSHKOFF, I ;

ANDERSON, D ;

MAHIDHARA, D .

MANAGEMENT SCIENCE, 1993, 39 (06) :736-745

[9]

Houck D. J. Jr., 1980, Opsearch, V17, P93

[10] 2-path cuts for the vehicle routing problem with time windows [J].

Kohl, N ;

Desrosiers, J ;

Madsen, OBG ;

Solomon, MM ;

Soumis, F .

TRANSPORTATION SCIENCE, 1999, 33 (01) :101-116