Les problèmes de tournées avec contraintes de fenêtres de temps, l'état de l'art

 Access to full text

 Full (PDF)

1. Y. K. AGARWAL, K. MATHUR et M. SALKIN, A Set-Partitioning-Based Algorithm for the Vehicle Routing Problem, Networks, 1989, 19, p. 731-749. Zbl0682.90050MR1024512
2. E. BAKER, An Exact Algorithm for the Time Constrained Traveling Salesman Problem, Oper. Res., 1983, 31, p. 938-945. Zbl0549.90072
3. E. BAKER et J. SCHAFFER, Computational Experience with Branch Exchange for Vehicle Routing Problems with Time Window Constraints, Am. J. Math. Management Sc., 1986, 6, p. 261-300. Zbl0629.90048
4. M. BALL et M. MAGAZINE, The Design and Analysis of Heuristics, Networks, 1981,11, p. 215-219. 
5. W. BELL, L. DALBERTO, M. FISHER, A. GREENFIELD, R. JAIKUMAR, P. KEDIA, R. MACK et P. PRUTZMAN, Improving the Distribution of Industrial Gases with an On line Computerized Routing and Scheduling Optimizer, Interfaces, 1983,13, p. 4-23. 
6. M. BELLMORE et J. MALONE, Pathology of Traveling Salesman Problem, Oper.Res., 1971, 19, p. 278-307. Zbl0219.90032MR391976
7. J. F. BENDERS, Partitionning Procedures for Solving Mixed Variables Programming Problems, Numer. Math., 1962, 4, p. 238-252. Zbl0109.38302MR147303
8. D. P. BERTSEKAS, Constrained Optimisation and Lagrange Multipliers Methods, Academic Press, New York, 1982. Zbl0572.90067MR690767
9. L. BODIN, B. GOLDEN, A. ASSAD et M. BALL, Routing and Scheduling of Vehicles and Crews: the State of the Art, Comput. Oper. Res., 1983,10, p. 63-212. MR758162
10. N. CHRISTOFIDES, A. MINGOZZI, P. TOTH et C. SANDI, Combinatorial Optimisation, John Wiley, New York, 1979. Zbl0401.00019MR557004
11. N. CHRISTOFIDES, A. MINGOZZI et P. TOTH, Exact Algorithms for the Vehicle Routing Problems, Based on Spanning Tree and Shortest Path Relaxation, Math. Program. 1981a, 20, p. 255-282. Zbl0461.90067MR612623
12. N. CHRISTOFIDES, A. MINGOZZI et P. TOTH, State Space Relaxation Procedures for the Computation of Bounds to Routing Problems, Networks, 1981 b, 11, p. 145-164. Zbl0458.90071MR618211
13. G. CLARK et W. WRIGHT, Scheduling of Vehicles from a Central Depot to a Number of Delivery Points, Oper. Res., 1964,12, p. 568-581. 
14. C. F. DAGANZO, The Length of Tours in Zones of Different Shapes, Transp. Res., 1984, 18 B, p. 135-145. MR748297
15. C. F. DAGANZO et G. F. NEWELL, Configuration of Physical Distribution Networks, Networks, 1986, 16, p. 113-132. Zbl0642.90036
16. C. F. DAGANZO, Modeling Distribution Problems with Time Windows, Part I, Sci., 1987 a, 21, p. 171-179. Zbl0623.90034
17. C. F. DAGANZO, Modeling Distribution Problems with Time Windows, Part II: Two Customer Types, Transp. Sci., 1987 b, 21, p. 180-187. Zbl0623.90035
18. M. DESROCHERS, La fabrication d'horaires de travail pour les conducteurs d'autobus par une méthode de génération de colonnes, Thèse de Ph. D, Dept. d'Informatique et de Recherche Opérationnelle, Université de Montréal, 1986. 
19. M. DESROCHERS, J. MENSTRA, M. SAVELSBERGH et F. SOUMIS, Vehicle Routing with Time Windows: Optimization and Approximation, in Vehicle Routing Methods and Studies, B. GOLDEN et A. ASSAD éd., p. 65-84, North Holland, Amsterdam, 1988. Zbl0642.90055MR1017690
20. M. DESROCHERS et G. LAPORTE, Improvement and Extensions to the Miller-Tucker-Zemlin Subtour Elimination Constraints, Cahiers du GERAD G-89-03, École des H.E.C., Montréal, 1989. Zbl0723.90081
21. J. DESROSIERS, P. PELLETIER et F. SOUMIS, Plus courts chemin avec contraintes d'horaires, R.A.I.R.O., Rech. Op., 1983, 17, p. 1-21. Zbl0528.90082
22. J. DESROSIERS, F. SOUMIS et M. DESROCHERS, Routing with Time Windows by Column Generation, Networks, 1984, 14, p. 545-565. Zbl0571.90088
23. J. DESROSIERS, F. SOUMIS, M. DESROCHERS et M. SAUVÉ, Routing and Scheduling with Time Windows Solved by Network Relaxation and Branch and Bound on Time Variables, in J. M. ROUSSEAU éd., Computer Scheduling of Public Transport, II, North Holland, Amsterdam, 1985. Zbl0585.90067
24. J. DESROSIERS, F. SOUMIS, M. DESROCHERS et M. SAUVÉ, Methods for Routing with Time Windows, Eur. J. Oper. Res., 1986, 23, p. 236-245. Zbl0579.90095MR825610
25. J. DESROSIERS, M. SAUVÉ, et F. SOUMIS, Lagrangean Relaxation Methods for Solving the Minimum Fleet Size Multiple Traveling Salesman Problem with Time Windows, Manage. Sc., 1988, 34, p. 1005-1022. Zbl0654.90038MR954130
26. J. DESROSIERS, M. DESROCHERS et M. SOLOMON, A Column Generation Algorithm for the Vehicle Routing Problem with Time Windows. Présenté au congrès CORS/TIMS/ORSA, Vancouver, mai 1989. Zbl0825.90360
27. G. FINKE, A. CLAUSS et E. GUNN, A Two Commodity Network Flow Approach to the Traveling Salesman Problem, Congressus Numerantium, 1984, p. 167-178. Zbl0697.90056MR749611
28. M. L. FISHER et R. JAIKUMAR, A Decomposition Algorithm for Large Scale Vehicle Routing. Working paper 78-11-05, Dept. of Decision Science, University of Pennsylvania, 1978. 
29. M. L. FISHER, Worst Case Analysis of Algorithms, Manage. Sci., 1980, 26, p. 1-17. Zbl0448.90041MR574193
30. M. L. FISHER, The Lagrangean Relaxation Method for Solving Integer Programming Problems. Manage. Sci., 1981, 37, p. 1-12. Zbl0466.90054MR720492
31. M. L. FISHER et R. JAIKUMAR, A Generalized Assignement Heuristic for Vehicle Routing, Networks, 1981, 11, p. 109-124. MR618209
32. M. L. FISHER, Lagrangian Optimization Algorithms for Vehicle Routing Problems, in Operational Research '87, Proceedings of the Eleventh International Conference on Operational Research, G. K. RAND éd., North Holland, Amsterdam, 1987. Zbl0663.90040MR1002769
33. M. L. FISHER et A. H. G. RINOOY KAN, The Design, Analysis and Implementation of Heuristics, Manage. Sci., 1988, 34, p. 263-265. MR938764
34. B. A. FOSTER et D. M. RYAN, An Integer Programming Approach to the Vehicle Scheduling Problem, Oper. Res. Quart., 19876, 27, p. 367-384. Zbl0327.90030MR489825
35. M. FRANK et P. WOLFE, An Algorithm for Quadratic Programming, Nav. Res. Log.Quart., 1956, 3, p. 95-110. MR89102
36. A. M. GEOFFRION, Lagrangean Relaxation and its Uses in Integer Programming, Math. Program. Stud, 1974, p. 82-114. Zbl0395.90056MR439172
37. I. GERTSBAKH et H. STERN, Minimal Ressources for Fixed and Variable Job Schedule, Oper. Res., 1978, p. 68-85. Zbl0371.90058MR475806
38. B. GILLETT et L. MILLER, A Heuristic Algorithm for the Vehicle Dispatching Problem, Oper. Res., 1974, 22, p. 340-349. Zbl0274.90013
39. B. GOLDEN et A. ASSAD éd., Vehicle Routing: Methods and Studies, North Holland, Amsterdam, 1988. Zbl0638.00043MR1017687
40. M. GUIGNARD et S. KIM, Langrangean Decomposition for Integer Programming: Theory and Applications, R.A.I.R.O., Rech. Oper., 1987, 21, p. 307-323. Zbl0638.90075MR932182
41. M. HAOUARI, P. DEJAX et F. SOUMIS, Étude de la complexité du problème du plus court chemin avec contraintes de fenêtres de temps, Rapport Scientifique L.E.I.S., École Centrale, Paris, 1988. 
42. M. HAOUARI et P. DEJAX, Un modèle de tournées de véhicules avec contraintes de capacité et de fenêtres de temps, in Actes du 2e Congrès International de Génie industriel, p. 181-190, Nancy, Groupement de Génie Industriel, C.E.F.I. éd., 1988. 
43. M. HAOUARI et P. DEJAX, An Exact Algorithm for Vehicle Routing with Time Windows, présenté au Congrès CORS/TIMS/ORSA, Vancouver, mai 1989 a. 
44. M. HAOUARI, F. BERGEAUD, P. DEJAX et M. TEKAYA, Une heuristique parallèle pour les problèmes de tournées avec fenêtres de temps in Actes du Colloque sur le développement des Sciences et Pratiques de l'organisation, p. 159-166, A.F.C.E.T., Paris, décembre 1989 b. 
45. K. JÖRNSTEN, M. NASBERG et P. SMEDS, Variable Splitting, a New Lagrangean Approach to some Mathematical Programming Models, Linkoping Institute of Technology, Dept of Mathematics, Report LITH-MAT 85-04, 1985. 
46. K. JÖRNSTEN, O. MADSEN et B. SORENSEN, Exact Solution of the Vehicle Routing and Scheduling Problem with Time Windows by Splitting, Research Report No. 5/1986, I.M.S.O.R., The Technical University of Denmark, 1986. 
47. G. KEYMOLEN, Les problèmes de tournées: un algorithme pour le cas monovéhicules avec restrictions temporelles et de précédence, Thèse de Doctorat, Université catholique de Louvain, 1988. 
48. K. KNIGHT et J. HOFER, Vehicle Scheduling with Timed and Connected Calls: A case Study, Oper. Res. Quart., 1968, 19, p. 299-310. 
49. A. KOLEN, A. RINOOY KAN et M. TRIENEKENS, Vehicle Routing with Time Windows, Oper. Res., 1987, 35, p. 266-273. Zbl0636.90047MR907422
50. Y. A. KOSKOSIDIS, W. B. POWELL et M. M. SOLOMON, An Optimization Based Heuristic for Vehicle Routing and Scheduling with Time Window Constraints, T.M.S. 88-09-1, The Institute for Transportation Systems, 1989. Zbl0762.90022
51. A. LANGEVIN, Planification des tournées de véhicules, Thèse de Ph. D, École Polytecthnique de Montréal, Université de Montréal, 1988. 
52. G. LAPORTE et Y. NOBERT, Exact Algorithms for the Vehicle Routing Problem, Ann. Discr. Math. 1987, 31, p. 147-184. Zbl0611.90055MR878778
53. L. S. LASDON, Optimization Theory for Large Systems, The Macmillan Company, London, 1970. Zbl0224.90038MR337317
54. E. LAWLER, J. K. LENSTRA, A. H. G. RINNOOY KAN et D. SHMOYS, The Traveling Salesman Problem, John Wiley, New York, 1985. Zbl0562.00014MR811467
55. A. LEVIN, Scheduling and Fleet Routing Models for Transportation Systems, Transp.Sc., 1971, 5, p. 232-255. MR293994
56. S. LIN, Computer Solutions to the Traveling Salesman Problem, Bell Syst. Tech. J., 1965, 44, p. 2245-2269. Zbl0136.14705MR189224
57. S. LIN et B. KERNIGHAN, An Effective Heuristic for the Traveling Salesman Problem, Oper. Res., 1973, 21, p. 498-516. Zbl0256.90038MR359742
58. T. L. MAGNANTI, Combinatorial Optimisation and Vehicle Fleet Planning: Perspectives and Prospects, Networks, 1981, 11, p. 179-213. MR618212
59. C. MILLER, A. TUCKER et R. ZEMLIN, Integer Programming Formulation of Traveling Salesman Problem, J. Assoc. Comput. Mach., 1960, 7, p. 326-332. Zbl0100.15101MR149964
60. M. MINOUX, Lagrangian Relaxation of the Constrained Shortetst Path Problem, papier non publié, 1982. 
61. M. MINOUX, Problèmes de grandes dimensiions, in Programmation Mathématique, tome 2, Dunod, Paris, 1983. 
62. R. MOLE et S. JAMESON, A sequential Route Building Algorithm Employing a Generalized Savings Criteria, Oper. Res. Quart., 1976, p. 503-511. 
63. G. F. NEWELL et C. F. DAGANZO, Design of Multiple Vehicles Tours. I: A Ring Radial Network, Transp. Res., 1986 a, 20 B, p. 345-363. 
64. G. F. NEWELL et C. F. DAGANZO, Design of Multiple Vehicles Tours. II: Other Metrics, Transp. Res., 1986 b, 20 B, p. 365-376. 
65. G. F. NEWELL et C. F. DAGANZO, Design of Multiple Vehicle Tours. III: Valuable Goods, Transp. Res., 1986 c, 20 B, p. 377-390. 
66. I. OR, Traveling Salesman Type Combinatorial Problems and their Relation to the Logistics of Blood Banking, Ph. D Thesis, Dept. of Industrial Engineering and Management Sciences, Northwestern University, 1976. 
67. C. ORLOFF, Route Constrained Fleet Routing, Transp. Sci., 1976, 10, p. 149-168. 
68. G. PARKER, R. DEANE et R. HOLMES, On the Use of a Vehicle Routing Algorithm for the Parallel Processor Problem with Sequence Dependent Changeover Costs. A.I.I.E. T., 1977, 9, p. 155-160. 
69. H. PULLEN et M. WEBB, A Computer application to a Transport Scheduling Problem, Comput. J., 1967, 10 p. 10-13. 
70. M. R. RAO et S. ZIONTS, Allocation of Transportation Units to Alternative Trips. A Column Generation Scheme with Out of Kilter Subproblems, Oper. Res., 1968, 16, p. 52-63. 
71. C. RIBEIRO, M. MINOUX et M. PENNA, An Optimal Column Generation with Ranking Algoritm for very Large Scale Set Partitionning Problems in Traffic Assignement, Eur. J. Oper. Res., 1989, 41, p. 232-239. Zbl0679.90043MR1010320
72. B. SANSO, F. SOUMIS et M. GENDREAU, Routing Models and Applications in Telecommunications Networks, présenté au Congrès EURO IX TIMS XXVIII, Paris, 1988. 
73. M. SAVELSBERGH, Local Search in Routing Problems with Time Windows, Ann. Oper. Res., 1985, 4, p. 285-305. MR948021
74. M. SAVELSBERGH, The Generalized Assignement Heuristic Revisited, présenté au congrès CORS/TIMS/ORSA, Vancouver, mai 1989. 
75. M. SOLOMON, On the Worst Case Performance of some Heuristics for the Vehicle Routing Scheduling Problem with Time Window constraints, Networks, 1986, 16, p. 161-174. Zbl0642.90058MR835635
76. M. SOLOMON, Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints, Oper. Res., 1987, 35, p. 254-265. Zbl0625.90047MR907421
77. M. SOLOMON et J. DESROSIERS, Time Window Constrained Routing and Scheduling Problems, Transp. Sci., 1988 a, 22, p. 1-13. Zbl0638.90052MR929021
78. M. SOLOMON, E. BAKER et J. SCHAFFER, Vehicle Routing and Scheduling problems with Time Window Constraints: Efficient Implementations of Solutions Improvement Procedures, in Vehicle Routing Methhods and Studies, B. GOLDEN et A. ASSAD éd., p. 85-105, North Holland, Amsterdam, 1988 b. Zbl0642.90054MR1017691
79. A. J. SWERSEY et W. BALLARD, Scheduling School Buses, Manage. Sci., 1984, 30, p. 844-853. Zbl0547.90043
80. P. M. THOMPSON et H. N. PSARAFTIS, Cyclic Transfer Algorithms for Multi-Vehicle Routing and Scheduling Problems. W.P. 89-008, Leavey School of Business and Administration, Santa Clara University, 1989. Zbl0797.90021
81. VAN LANDEGHAM, A Bi-criteria Heuristic for the Vehicle Routing Problem with Time Windows, Eur. J. Oper. Res., 1988, 36, p. 217-266. Zbl0643.90035