OPTIMAL ROUTING UNDER CAPACITY AND DISTANCE RESTRICTIONS

被引：170

作者：

LAPORTE, G ^{[1
]}

NOBERT, Y ^{[1
]}

DESROCHERS, M ^{[1
]}

机构：

[1] UNIV MONTREAL, MONTREAL H3C 3J7, QUEBEC, CANADA

来源：

OPERATIONS RESEARCH | 1985年 / 33卷 / 05期

关键词：

COMPUTER PROGRAMMING - Algorithms;

D O I：

10.1287/opre.33.5.1050

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

This paper describes an integer linear programming algorithm for vehicle routing problems involving capacity and distance constraints. The method uses constraint relaxation and a new class of subtour elimination constraints. Two versions of the algorithm are presented, depending upon the nature of the distance matrix. Exact solutions are obtained for problems involving up to sixty cities.

引用

页码：1050 / 1073

页数：24

共 16 条

[1] [Anonymous], 1954, OPERATIONS RES, DOI DOI 10.1287/OPRE.2.4.393
[2] BODIN L, 1983, COMPUT OPER RES, V10, P63, DOI 10.1016/0305-0548(83)90030-8
[3] EXACT ALGORITHMS FOR THE VEHICLE-ROUTING PROBLEM, BASED ON SPANNING TREE AND SHORTEST-PATH RELAXATIONS
CHRISTOFIDES, N
MINGOZZI, A
TOTH, P
[J]. MATHEMATICAL PROGRAMMING, 1981, 20 (03) : 255 - 282
[4] Christofides N., 1979, Combinatorial optimization, P315
[5] CHRISTOFIDES N, 1976, REV FR AUTOMAT INFOR, V10, P55
[6] IMPLEMENTING VEHICLE ROUTING ALGORITHMS
GOLDEN, BL
MAGNANTI, TL
NGUYEN, HQ
[J]. NETWORKS, 1977, 7 (02) : 113 - 148
[7] Gomory R.E, 1963, RECENT ADV MATH PROG, P269
[8] Held M, 1971, MATHEMATICAL PROGRAM, V1, P6, DOI [DOI 10.1007/BF01584070, 10.1007/BF01584070]
[9] LAND AH, 1973, FORTRAN CODES MATH P
[10] A BRANCH AND BOUND ALGORITHM FOR THE CAPACITATED VEHICLE-ROUTING PROBLEM
LAPORTE, G
NOBERT, Y
[J]. OR SPEKTRUM, 1983, 5 (02) : 77 - 85

← 1 2 →