Real-time vehicle routing: Solution concepts, algorithms and parallel computing strategies. (English) Zbl 1033.90014
Summary: In real-time fleet management, vehicle routes are built in an on-going fashion as vehicle locations, travel times and customer requests are revealed over the planning horizon. To deal with such problems, a new generation of fast on-line algorithms capable of taking into account uncertainty is required. Although several articles on this topic have been published, the literature on real-time vehicle routing is still disorganized. In this paper the research in this field is reviewed and some issues that have not received attention so far are highlighted. A particular emphasis is put on parallel computing strategies.
MSC:
| 90B20 | Traffic problems in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 68W10 | Parallel algorithms in computer science |
Software:
VRPReferences:
| [1] | P. Toth, D. Vigo (Eds.), The Vehicle Routing Problem, in: SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 2002; P. Toth, D. Vigo (Eds.), The Vehicle Routing Problem, in: SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 2002 · Zbl 0979.00026 |
| [2] | Brown, G. G.; Graves, G. W., Real-time dispatch of petroleum tank trucks, Management Science, 27, 19-32 (1981) |
| [3] | Brown, G. G.; Ellis, C.; Graves, G. W.; Ronen, D., Real-time, wide area dispatching of Mobil tank trucks, Interfaces, 17, 1, 107-120 (1987) |
| [4] | Powell, W. B., A stochastic model of the dynamic vehicle allocation problem, Transportation Science, 20, 117-129 (1986) |
| [5] | Goetschalckx, M., A decision support system for dynamic truck dipatching, International Journal of Physical Distribution and Materials Management, 14, 34-42 (1988) |
| [6] | Powell, W. B., Real-time optimization for truckload motor carriers, OR/MS Today, 18, 28-33 (1990) |
| [7] | Rego, C.; Roucairol, C., Using tabu search for solving a dynamic multi-terminal truck dispatching problem, European Journal of Operational Research, 83, 411-429 (1995) · Zbl 0904.90053 |
| [8] | Savelsbergh, M. W.P.; Sol, M., Drive: Dynamic routing of independent vehicles, Operations Research, 46, 474-490 (1998) · Zbl 0987.90511 |
| [9] | Campbell, A.; Clarke, L.; Kleywegt, A.; Savelsbergh, M., The inventory routing problem, (Laporte, G.; Crainic, T. G., Fleet Management and Logistics (1998), Kluwer: Kluwer Boston) · Zbl 0972.90500 |
| [10] | A. Larsen, The dynamic vehicle routing problem, Ph.D. Thesis, Institute of Mathematical Modelling, Technical University of Denmark, 2001; A. Larsen, The dynamic vehicle routing problem, Ph.D. Thesis, Institute of Mathematical Modelling, Technical University of Denmark, 2001 |
| [11] | Gendreau, M.; Guertin, F.; Potvin, J.-Y.; Taillard, É., Parallel tabu search for real-time vehicle routing and dispatching, Transportation Science, 33, 381-390 (1999) · Zbl 0958.90051 |
| [12] | M. Gendreau, F. Guertin, J.-Y. Potvin, R. Séguin, Neighbourhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries, Technical report CRT-98-10, Centre de Recherche sur les Transports, Université de Montréal, 1998; M. Gendreau, F. Guertin, J.-Y. Potvin, R. Séguin, Neighbourhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries, Technical report CRT-98-10, Centre de Recherche sur les Transports, Université de Montréal, 1998 |
| [13] | J.-F. Cordeau, G. Ghiani, G. Laporte, R. Musmanno, A parallel tabu search algorithm for the static dial-a-ride problem, working paper, 2002; J.-F. Cordeau, G. Ghiani, G. Laporte, R. Musmanno, A parallel tabu search algorithm for the static dial-a-ride problem, working paper, 2002 |
| [14] | Madsen, O. B.G.; Tosti, K.; Vælds, J., A heuristic method for dispatching repair men, Annals of Operations Research, 61, 213-226 (1995) · Zbl 0839.90034 |
| [15] | Weintraub, A.; Aboud, J.; Fernandez, C.; Laporte, G.; Ramirez, E., An emergency vehicle dispatching system for an electric utility in Chile, Journal of the Operational Research Society, 50, 690-696 (1999) · Zbl 1054.90524 |
| [16] | Brotcorne, L.; Laporte, G.; Semet, F., Ambulance location and relocation models, European Journal of Operational Research, 147, 3, 451-463 (2003) · Zbl 1037.90554 |
| [17] | J.F. Cordeau, G. Laporte, A tabu search heuristic for the static multi-vehicle dial-a-ride problem, Technical Report, May, 2002; J.F. Cordeau, G. Laporte, A tabu search heuristic for the static multi-vehicle dial-a-ride problem, Technical Report, May, 2002 |
| [18] | S. Roy, J.-M. Rousseau, G. Lapalme, J.A. Ferland, Routing and scheduling of transportation services for disabled: Summary report, Technical Report, Centre de Recherche sur les Transports, Université de Montréal, 1984; S. Roy, J.-M. Rousseau, G. Lapalme, J.A. Ferland, Routing and scheduling of transportation services for disabled: Summary report, Technical Report, Centre de Recherche sur les Transports, Université de Montréal, 1984 |
| [19] | Madsen, O. B.G.; Ravn, H. F.; Rygaard, J. M., A heuristic algorithm for a dial-ride problem with time windows, Annals of Operations Research, 60, 193-208 (1995) · Zbl 0839.90033 |
| [20] | Psaraftis, H. N., A dynamic programming solution to the single many-to-many immediate request dial-a-ride problem, Transportation Science, 14, 130-154 (1980) |
| [21] | Gendreau, M.; Laporte, G.; Semet, F., Solving an ambulance location model by tabu search, Location Science, 2, 75-88 (1997) · Zbl 0930.90053 |
| [22] | Gendreau, M.; Laporte, G.; Semet, F., A dynamic model and parallel tabu search heuristic for real-time ambulance relocation, Parallel Computing, 27, 1641-1653 (2001) · Zbl 0982.68053 |
| [23] | Laporte, G.; Louveaux, F. V., Solving stochastic routing problems, (Crainic, T. G.; Laporte, G., Fleet Management and Logistics (1998), Kluwer: Kluwer Boston), 159-167 · Zbl 0963.90010 |
| [24] | Powell, W. B.; Jaillet, P.; Odoni, A. R., Stochastic and dynamic networks and routing, (Ball, M. O.; Magnanti, T. L.; Monma, C. L.; Nemhauser, G. L., Handbooks in Operations Research and Management Science, 8: Network Routing (1995), Elsevier Science: Elsevier Science Amsterdam), 141-295 · Zbl 0870.90059 |
| [25] | J.-F. Cordeau, G. Desaulniers, J. Desrosiers, M.M. Solomon, F. Soumis, The vehicle routing problem with time windows, in: P. Toth, D. Vigo (Eds.), The Vehicle Routing Problem, in: SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 2001, pp. 157-193; J.-F. Cordeau, G. Desaulniers, J. Desrosiers, M.M. Solomon, F. Soumis, The vehicle routing problem with time windows, in: P. Toth, D. Vigo (Eds.), The Vehicle Routing Problem, in: SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 2001, pp. 157-193 · Zbl 1076.90543 |
| [26] | Malandraki, C.; Daskin, M. S., Time dependent vehicle routing problems: Formulations, properties, and heuristics algorithms, Transportation Science, 26, 185-200 (1992) · Zbl 0758.90029 |
| [27] | Bertsimas, D.; van Ryzin, G. J., A stochastic and dynamic vehicle routing problem in the Euclidean plane, Operations Research, 39, 601-615 (1991) · Zbl 0736.90027 |
| [28] | Psaraftis, H. N., Dynamic vehicle routing problems, (Golden, B. L.; Assad, A. A., Vehicle Routing: Methods and Studies (1998), Elsevier Science: Elsevier Science Amsterdam), 223-248 |
| [29] | Gendreau, M.; Potvin, J.-Y., Dynamic vehicle routing and dispatching, (Crainic, T. G.; Laporte, G., Fleet Management and Logistics (1998), Kluwer: Kluwer Boston), 115-126 · Zbl 0972.90501 |
| [30] | Ichoua, S.; Gendreau, M.; Potvin, J.-Y., Diversion issues in real-time vehicle dispatching, Transportation Science, 34, 426-435 (2000) · Zbl 0991.90529 |
| [31] | Psaraftis, H. N., Dynamic vehicle routing: Status and prospects, Annals of Operations Research, 61, 143-164 (1995) · Zbl 0839.90037 |
| [32] | K. Lund, O.B.G. Madsen, J.M. Rygaard, Vehicle routing problems with varying degrees of dynamism, Technical report, Institute of Mathematical Modelling, Technical University of Denmark, 1996; K. Lund, O.B.G. Madsen, J.M. Rygaard, Vehicle routing problems with varying degrees of dynamism, Technical report, Institute of Mathematical Modelling, Technical University of Denmark, 1996 |
| [33] | A. Larsen, O.B.G. Madsen, M.M. Solomon, Partially dynamic vehicle routing-models and algorithms, Technical report, Institute of Mathematical Modelling, Technical University of Denmark, 1999; A. Larsen, O.B.G. Madsen, M.M. Solomon, Partially dynamic vehicle routing-models and algorithms, Technical report, Institute of Mathematical Modelling, Technical University of Denmark, 1999 · Zbl 1059.90024 |
| [34] | Potvin, J.-Y.; Shen, Y.; Rousseau, J.-M., Neural networks for automated vehicle dispatching, Computers & Operations Research, 19, 267-276 (1992) · Zbl 0825.90352 |
| [35] | Potvin, J.-Y.; Dufour, G.; Rousseau, J.-M., Learning vehicle dispatching with linear programming models, Computers & Operations Research, 20, 371-380 (1993) · Zbl 0772.90044 |
| [36] | Bertsimas, D.; van Ryzin, G. J., Stochastic and dynamic vehicle routing problem in the Euclidean plane with multiple capacitated vehicles, Operations Research, 41, 60-76 (1993) · Zbl 0776.90018 |
| [37] | Swihart, M. R.; Papastavrou, J. D., A stochastic and dynamic model for the single-vehicle pick-up and delivery problem, European Journal of Operational Research, 114, 447-464 (1999) · Zbl 0949.90006 |
| [38] | Papastavrou, J., A stochatic and dynamic routing policy using branching processes with state dependent immigration, European Journal of Operational Research, 95, 167-177 (1996) · Zbl 0953.90502 |
| [39] | S. Mitrović-Minić, R. Krishnamurti, G. Laporte, The double-horizon heuristic for the dynamic pickup and delivery problem with time windows, submitted for publication; S. Mitrović-Minić, R. Krishnamurti, G. Laporte, The double-horizon heuristic for the dynamic pickup and delivery problem with time windows, submitted for publication |
| [40] | (Osman, I. H.; Kelly, J. P., Meta-heuristics: Theory and Applications (1996), Kluwer: Kluwer Boston) |
| [41] | Shen, Y.; Potvin, J.-Y.; Rousseau, J.-M.; Roy, S., A computer assistant for vehicle dispatching with learning capacities, Annals of Operations Research, 61, 189-211 (1995) · Zbl 0839.90039 |
| [42] | Bagchi, P. K.; Nag, B. N., Dynamic vehicle scheduling: An expert systems approach, International Journal of Physical Distribution and Logistics Management, 21, 10-18 (1991) |
| [43] | Glover, F., Future paths for integer programming and links to artificial intelligence, Computers & Operations Research, 5, 533-549 (1986) · Zbl 0615.90083 |
| [44] | Rochat, Y.; Taillard, É., Probabilistic diversification and intensification in local search for vehicle routing, Journal of Heuristics, 1, 147-167 (1995) · Zbl 0857.90032 |
| [45] | Mladenović, N.; Hansen, P., Variable neighbourhood search, Computers & Operations Research, 24, 1097-1100 (1997) · Zbl 0889.90119 |
| [46] | Crainic, T. G.; Toulouse, M.; Gendreau, M., Towards a taxonomy of parallel tabu search algorithm, INFORMS Journal on Computing, 9, 61-72 (1997) · Zbl 0891.90094 |
| [47] | (Buyya, R., High Performance Cluster Computing: Architectures and Systems, vols. 1 and 2 (1999), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ) |
| [48] | P. Caricato, G. Ghiani, A. Grieco, E. Guerriero, Parallel tabu search for a vehicle rounting problem under track contention, Parallel Computing, forthcoming; P. Caricato, G. Ghiani, A. Grieco, E. Guerriero, Parallel tabu search for a vehicle rounting problem under track contention, Parallel Computing, forthcoming |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
