A reoptimization algorithm for the shortest path problem with time windows
作者： Martin Desrochers , François Soumis
DOI: 10.1016/0377-2217(88)90034-3
关键词:
摘要: Abstract The shortest path problem with time windows (SPPTW) occurs in the construction of vehicle routes and schedules for which window constraints must be satisfied. SPPTW is repeatedly solved to produce disjoint form solution original problem. cost solving can reduced by reusing part preceding A primal-dual reoptimization method runs pseudo-polynomial proposed. It solve problems up 2500 nodes.
elsevier.com
sci-hub.se 参考文章(12)
Jacques Desrosiers, Paul Pelletier, François Soumis, Plus court chemin avec contraintes d'horaires Rairo-operations Research. ,vol. 17, pp. 357- 377 ,(1983) , 10.1051/RO/1983170403571
U. Pape, Netzwerk-Veränderungen und Korrektur kürzester Weglängen von einer Wurzelmenge zu allen anderen Knoten Computing. ,vol. 12, pp. 357- 362 ,(1974) , 10.1007/BF02253338
Robert Endre Tarjan, Data Structures and Network Algorithms ,(1983)
G. Gallo, Reoptimization procedures in shortest path problem Rivista Di Matematica Per Le Scienze Economiche E Sociali. ,vol. 3, pp. 3- 13 ,(1980) , 10.1007/BF02092136
V.V. Rodionov, The parametric problem of shortest distances USSR Computational Mathematics and Mathematical Physics. ,vol. 8, pp. 336- 343 ,(1968) , 10.1016/0041-5553(68)90148-1
S. Goto, A. Sangiovanni-Vincentelli, A new shortest path updating algorithm Networks. ,vol. 8, pp. 341- 372 ,(1978) , 10.1002/NET.3230080406
Satoru Fujishige, A note on the problem of updating shortest paths Networks. ,vol. 11, pp. 317- 319 ,(1981) , 10.1002/NET.3230110309
Eric V. Denardo, Bennett L. Fox, Shortest-Route Methods: 1. Reaching, Pruning, and Buckets Operations Research. ,vol. 27, pp. 161- 186 ,(1979) , 10.1287/OPRE.27.1.161
P. M. Spira, A. Pan, On Finding and Updating Spanning Trees and Shortest Paths SIAM Journal on Computing. ,vol. 4, pp. 375- 380 ,(1975) , 10.1137/0204032
Jacques Desrosiers, François Soumis, Martin Desrochers, Routing with time windows by column generation Networks. ,vol. 14, pp. 545- 565 ,(1984) , 10.1002/NET.3230140406