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

Haouari, Mohamed; Dejax, Pierre; Desrochers, Martin

Haouari, Mohamed ; Dejax, Pierre ; Desrochers, Martin

RAIRO - Operations Research - Recherche Opérationnelle, Tome 24 (1990) no. 3, pp. 217-244.

MR Zbl

@article{RO_1990__24_3_217_0,
     author = {Haouari, Mohamed and Dejax, Pierre and Desrochers, Martin},
     title = {Les probl\`emes de tourn\'ees avec contraintes de fen\^etres de temps, l'\'etat de l'art},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {217--244},
     publisher = {EDP-Sciences},
     volume = {24},
     number = {3},
     year = {1990},
     mrnumber = {1075795},
     zbl = {0704.90045},
     language = {fr},
     url = {http://www.numdam.org/item/RO_1990__24_3_217_0/}
}

TY  - JOUR
AU  - Haouari, Mohamed
AU  - Dejax, Pierre
AU  - Desrochers, Martin
TI  - Les problèmes de tournées avec contraintes de fenêtres de temps, l'état de l'art
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 1990
SP  - 217
EP  - 244
VL  - 24
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/RO_1990__24_3_217_0/
LA  - fr
ID  - RO_1990__24_3_217_0
ER  -

%0 Journal Article
%A Haouari, Mohamed
%A Dejax, Pierre
%A Desrochers, Martin
%T Les problèmes de tournées avec contraintes de fenêtres de temps, l'état de l'art
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 1990
%P 217-244
%V 24
%N 3
%I EDP-Sciences
%U http://www.numdam.org/item/RO_1990__24_3_217_0/
%G fr
%F RO_1990__24_3_217_0

Haouari, Mohamed; Dejax, Pierre; Desrochers, Martin. Les problèmes de tournées avec contraintes de fenêtres de temps, l'état de l'art. RAIRO - Operations Research - Recherche Opérationnelle, Tome 24 (1990) no. 3, pp. 217-244. http://www.numdam.org/item/RO_1990__24_3_217_0/

Bibliographie
Cité par

Y. K. Agarwal, K. Mathur et M. Salkin, A Set-Partitioning-Based Algorithm for the Vehicle Routing Problem, Networks, 1989, 19, p. 731-749. | MR | Zbl

E. Baker, An Exact Algorithm for the Time Constrained Traveling Salesman Problem, Oper. Res., 1983, 31, p. 938-945. | Zbl

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. | Zbl

M. Ball et M. Magazine, The Design and Analysis of Heuristics, Networks, 1981,11, p. 215-219.

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.

M. Bellmore et J. Malone, Pathology of Traveling Salesman Problem, Oper.Res., 1971, 19, p. 278-307. | MR | Zbl

J. F. Benders, Partitionning Procedures for Solving Mixed Variables Programming Problems, Numer. Math., 1962, 4, p. 238-252. | MR | Zbl

D. P. Bertsekas, Constrained Optimisation and Lagrange Multipliers Methods, Academic Press, New York, 1982. | MR | Zbl

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. | MR

N. Christofides, A. Mingozzi, P. Toth et C. Sandi, Combinatorial Optimisation, John Wiley, New York, 1979. | MR | Zbl

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. | MR | Zbl

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. | MR | Zbl

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.

C. F. Daganzo, The Length of Tours in Zones of Different Shapes, Transp. Res., 1984, 18 B, p. 135-145. | MR

C. F. Daganzo et G. F. Newell, Configuration of Physical Distribution Networks, Networks, 1986, 16, p. 113-132. | Zbl

C. F. Daganzo, Modeling Distribution Problems with Time Windows, Part I, Sci., 1987 a, 21, p. 171-179. | Zbl

C. F. Daganzo, Modeling Distribution Problems with Time Windows, Part II: Two Customer Types, Transp. Sci., 1987 b, 21, p. 180-187. | Zbl

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.

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. | MR | Zbl

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. | Zbl

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. | EuDML | Numdam | Zbl

J. Desrosiers, F. Soumis et M. Desrochers, Routing with Time Windows by Column Generation, Networks, 1984, 14, p. 545-565. | Zbl

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.

J. Desrosiers, F. Soumis, M. Desrochers et M. Sauvé, Methods for Routing with Time Windows, Eur. J. Oper. Res., 1986, 23, p. 236-245. | MR | Zbl

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. | MR | Zbl

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. | Zbl

G. Finke, A. Clauss et E. Gunn, A Two Commodity Network Flow Approach to the Traveling Salesman Problem, Congressus Numerantium, 1984, p. 167-178. | MR | Zbl

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.

M. L. Fisher, Worst Case Analysis of Algorithms, Manage. Sci., 1980, 26, p. 1-17. | MR | Zbl

M. L. Fisher, The Lagrangean Relaxation Method for Solving Integer Programming Problems. Manage. Sci., 1981, 37, p. 1-12. | MR | Zbl

M. L. Fisher et R. Jaikumar, A Generalized Assignement Heuristic for Vehicle Routing, Networks, 1981, 11, p. 109-124. | MR

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. | MR | Zbl

M. L. Fisher et A. H. G. Rinooy Kan, The Design, Analysis and Implementation of Heuristics, Manage. Sci., 1988, 34, p. 263-265. | MR

B. A. Foster et D. M. Ryan, An Integer Programming Approach to the Vehicle Scheduling Problem, Oper. Res. Quart., 19876, 27, p. 367-384. | MR | Zbl

M. Frank et P. Wolfe, An Algorithm for Quadratic Programming, Nav. Res. Log.Quart., 1956, 3, p. 95-110. | MR

A. M. Geoffrion, Lagrangean Relaxation and its Uses in Integer Programming, Math. Program. Stud, 1974, p. 82-114. | MR | Zbl

I. Gertsbakh et H. Stern, Minimal Ressources for Fixed and Variable Job Schedule, Oper. Res., 1978, p. 68-85. | MR | Zbl

B. Gillett et L. Miller, A Heuristic Algorithm for the Vehicle Dispatching Problem, Oper. Res., 1974, 22, p. 340-349. | Zbl

B. Golden et A. Assad éd., Vehicle Routing: Methods and Studies, North Holland, Amsterdam, 1988. | MR | Zbl

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. | EuDML | Numdam | MR | Zbl

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.

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.

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.

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.

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.

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.

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.

K. Knight et J. Hofer, Vehicle Scheduling with Timed and Connected Calls: A case Study, Oper. Res. Quart., 1968, 19, p. 299-310.

A. Kolen, A. Rinooy Kan et M. Trienekens, Vehicle Routing with Time Windows, Oper. Res., 1987, 35, p. 266-273. | MR | Zbl

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. | Zbl

A. Langevin, Planification des tournées de véhicules, Thèse de Ph. D, École Polytecthnique de Montréal, Université de Montréal, 1988.

G. Laporte et Y. Nobert, Exact Algorithms for the Vehicle Routing Problem, Ann. Discr. Math. 1987, 31, p. 147-184. | MR | Zbl

L. S. Lasdon, Optimization Theory for Large Systems, The Macmillan Company, London, 1970. | MR | Zbl

E. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan et D. Shmoys, The Traveling Salesman Problem, John Wiley, New York, 1985. | MR | Zbl

A. Levin, Scheduling and Fleet Routing Models for Transportation Systems, Transp.Sc., 1971, 5, p. 232-255. | MR

S. Lin, Computer Solutions to the Traveling Salesman Problem, Bell Syst. Tech. J., 1965, 44, p. 2245-2269. | MR | Zbl

S. Lin et B. Kernighan, An Effective Heuristic for the Traveling Salesman Problem, Oper. Res., 1973, 21, p. 498-516. | MR | Zbl

T. L. Magnanti, Combinatorial Optimisation and Vehicle Fleet Planning: Perspectives and Prospects, Networks, 1981, 11, p. 179-213. | MR

C. Miller, A. Tucker et R. Zemlin, Integer Programming Formulation of Traveling Salesman Problem, J. Assoc. Comput. Mach., 1960, 7, p. 326-332. | MR | Zbl

M. Minoux, Lagrangian Relaxation of the Constrained Shortetst Path Problem, papier non publié, 1982.

M. Minoux, Problèmes de grandes dimensiions, in Programmation Mathématique, tome 2, Dunod, Paris, 1983. | Zbl

R. Mole et S. Jameson, A sequential Route Building Algorithm Employing a Generalized Savings Criteria, Oper. Res. Quart., 1976, p. 503-511.

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.

G. F. Newell et C. F. Daganzo, Design of Multiple Vehicles Tours. II: Other Metrics, Transp. Res., 1986 b, 20 B, p. 365-376.

G. F. Newell et C. F. Daganzo, Design of Multiple Vehicle Tours. III: Valuable Goods, Transp. Res., 1986 c, 20 B, p. 377-390.

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.

C. Orloff, Route Constrained Fleet Routing, Transp. Sci., 1976, 10, p. 149-168.

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.

H. Pullen et M. Webb, A Computer application to a Transport Scheduling Problem, Comput. J., 1967, 10 p. 10-13.

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.

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. | MR | Zbl

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.

M. Savelsbergh, Local Search in Routing Problems with Time Windows, Ann. Oper. Res., 1985, 4, p. 285-305. | MR

M. Savelsbergh, The Generalized Assignement Heuristic Revisited, présenté au congrès CORS/TIMS/ORSA, Vancouver, mai 1989.

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. | MR | Zbl

M. Solomon, Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints, Oper. Res., 1987, 35, p. 254-265. | MR | Zbl

M. Solomon et J. Desrosiers, Time Window Constrained Routing and Scheduling Problems, Transp. Sci., 1988 a, 22, p. 1-13. | MR | Zbl

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. | MR | Zbl

A. J. Swersey et W. Ballard, Scheduling School Buses, Manage. Sci., 1984, 30, p. 844-853. | Zbl

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. | Zbl

Van Landegham, A Bi-criteria Heuristic for the Vehicle Routing Problem with Time Windows, Eur. J. Oper. Res., 1988, 36, p. 217-266. | Zbl