A REOPTIMIZATION ALGORITHM FOR THE SHORTEST-PATH PROBLEM WITH TIME WINDOWS

被引：56

作者：

DESROCHERS, M ^{[1
]}

SOUMIS, F ^{[1
]}

机构：

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

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1988年 / 35卷 / 02期

关键词：

MATHEMATICAL PROGRAMMING - SCHEDULING - TRANSPORTATION - Operations Research;

D O I：

10.1016/0377-2217(88)90034-3

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

The shortest path problem with time windows (SPPTW) occurs in the construction of vehicle routes and schedules for which time window constraints must be satisfied. The SPPTW is repeatedly solved to produce routes with disjoint schedules which form the solution of the original problem. The cost of repeatedly solving the SPPTW can be reduced by reusing part of the solution of the preceding problem. A primal-dual reoptimization method which runs in pseudo-polynomial time is proposed. It can solve problems with up to 2500 nodes.

引用

页码：242 / 254

页数：13

共 14 条

[1] SHORTEST-ROUTE METHODS .1. REACHING, PRUNING, AND BUCKETS
DENARDO, EV
FOX, BL
[J]. OPERATIONS RESEARCH, 1979, 27 (01) : 161 - 186
[2] DESROCHERS M, 1985, PUBLICATION U MONT A, V394
[3] DESROSIERS G, 1984, NETWORKS, V14, P545
[4] DESROSIERS J, 1983, RAIRO RECHERCHE OPER, V17
[5] DIONNE R, 1978, INFOR, V16, P132
[6] A NOTE ON THE PROBLEM OF UPDATING SHORTEST PATHS
FUJISHIGE, S
[J]. NETWORKS, 1981, 11 (03) : 317 - 319
[7] Gallo G., 1980, RIV MATEMATICA SCI E, V3, P3, DOI 10.1007/BF02092136
[8] GOTO A, 1981, NETWORKS, V8, P341
[9] HAJI IN, 1982, APR P IEEE INT S CIR, P802
[10] MURCHLAND JD, 1967, LBSTNT26 LOND GRAD S

← 1 2 →