Routing with time windows by column generation
作者： Jacques Desrosiers , François Soumis , Martin Desrochers
关键词: Interval (mathematics) 、 Mathematics 、 Mathematical optimization 、 Generalization 、 Set (abstract data type) 、 Fixed cost 、 Column generation 、 Dijkstra's algorithm 、 Simulation 、 TRIPS architecture 、 Routing (electronic design automation)
摘要: Consider a set of trips where each trip is specified priori by place origin, destination, duration, cost, and time interval within which the must begin. The may include visits to one or more specific points. Our problem determine number vehicles required, together with their routes schedules, so that begins its given interval, while fixed costs related vehicles, travel between trips, are minimized. generalization m-traveling salesman problem. We use column generation on partitioning solved simplex branch-and-bound; columns generated shortest path algorithm windows nodes. Numerical results for several school bus transportation problems up 151 discussed.
sci-hub.se 参考文章(14)
F. Soumis, J. Desrosiers, M. Desrochers, Optimal urban bus routing with scheduling flexibilities System Modelling and Optimization. pp. 155- 165 ,(1984) , 10.1007/BFB0008887
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
J Desrosiers, F Soumis, M Sauve, M Desrochers, ROUTING AND SCHEDULING WITH TIME WINDOWS SOLVED BY NETWORK RELAXATION AND BRANCH-AND-BOUND ON TIME VARIABLES. FROM THE BOOK COMPUTER SCHEDULING OF PUBLIC TRANSPORT 2 ,(1985)
Paul Bratley, Michael Florian, Pierre Robillard, Scheduling with earliest start and due date constraints on multiple machines Naval Research Logistics Quarterly. ,vol. 22, pp. 165- 173 ,(1975) , 10.1002/NAV.3800220113
Ilya Gertsbakh, Helman I. Stern, Minimal Resources for Fixed and Variable Job Schedules Operations Research. ,vol. 26, pp. 68- 85 ,(1978) , 10.1287/OPRE.26.1.68
C. E. Miller, A. W. Tucker, R. A. Zemlin, Integer Programming Formulation of Traveling Salesman Problems Journal of the ACM. ,vol. 7, pp. 326- 329 ,(1960) , 10.1145/321043.321046
Mandell Bellmore, John C. Malone, Pathology of Traveling-Salesman Subtour-Elimination Algorithms Operations Research. ,vol. 19, pp. 278- 307 ,(1971) , 10.1287/OPRE.19.2.278
T. L. Magnanti, Combinatorial optimization and vehicle fleet planning : perspectives and prospects Networks. ,vol. 11, pp. 179- 213 ,(1981) , 10.1002/NET.3230110209
Clifford S. Orloff, Route Constrained Fleet Scheduling Transportation Science. ,vol. 10, pp. 149- 168 ,(1976) , 10.1287/TRSC.10.2.149
Amos Levin, Scheduling and Fleet Routing Models for Transportation Systems Transportation Science. ,vol. 5, pp. 232- 255 ,(1971) , 10.1287/TRSC.5.3.232