×

zbMATH — the first resource for mathematics

The vehicle routing problem: An overview of exact and approximate algorithms. (English) Zbl 0761.90034
Summary: Some of the main known results relative to the vehicle routing problem are surveyed. The paper is organized as follows: (1) definition; (2) exact algorithms; (3) heuristic algorithms; (4) conclusion.

MSC:
90B06 Transportation, logistics and supply chain management
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
Software:
VRP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Agarwal, Y.; Mathur, K.; Salkin, H.M., A set-partitioning-based algorithm for the vehicle routing problem, Networks, 19, 731-750, (1989) · Zbl 0682.90050
[2] Balinski, M.; Quandt, R., On an integer program for a delivery problem, Operations research, 12, 300-304, (1964)
[3] Benders, J.F., Partitioning procedures for solving mixed-variables programming problems, Numerische Mathematik, 4, 238-252, (1962) · Zbl 0109.38302
[4] Bodin, L.D.; Golden, B.L.; Assad, A.A.; Ball, M.O., Routing and scheduling of vehicles and crews. the state of the art, Computers and operations research, 10, 69-211, (1983)
[5] Christofides, N., Vehicle routing, (), 431-448 · Zbl 0571.90059
[6] Christofides, N., Vehicle scheduling and routing, (), Presented at the · Zbl 0571.90059
[7] Christofides, N.; Mingozzi, A.; Toth, P., The vehicle routing problem, (), 315-338
[8] Christofides, N.; Mingozzi, A.; Toth, P., Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations, Mathematical programming, 20, 255-282, (1981) · Zbl 0461.90067
[9] Christofides, N.; Mingozzi, A.; Toth, P., State space relaxation procedures for the computation of bounds to routing problems, Networks, 11, 145-164, (1981) · Zbl 0458.90071
[10] Clarke, G.; Wright, J.W., Scheduling of vehicles from a central depot to a number of delivery points, Operations research, 12, 568-581, (1964)
[11] Desrochers, M.; Desrosiers, J.; Solomon, M.M., A new optimization algorithm for the vehicle routing problem with time windows, Operations research, (1991), forthcoming
[12] Desrochers, M.; Lenstra, J.K.; Savelsbergh, M.W.P., A classification scheme for vehicle routing and scheduling problems, European journal of operational research, 46, 322-332, (1990) · Zbl 0699.90053
[13] Desrosiers, J.; Soumis, F.; Desrochers, M., Routing with time windows by column generation, Networks, 14, 545-565, (1984) · Zbl 0571.90088
[14] Eilon, S.; Watson-Gandy, C.D.T.; Christofides, N., Distribution management: mathematical modelling and practical analysis, (1971), Griffin London
[15] Fisher, M.L.; Jaikumar, R., A decomposition algorithm for large-scale vehicle routing, ()
[16] Fisher, M.L.; Jaikumar, R., A generalized assignment heuristic for vehicle routing, Networks, 11, 109-124, (1981)
[17] Foster, B.; Ryan, D., An integer programming approach to the vehicle scheduling problem, Operational research quarterly, 27, 367-384, (1976) · Zbl 0327.90030
[18] Gaskell, T., Bases for vehicle fleet scheduling, Operational research quarterly, 18, 281-295, (1967)
[19] Gendreau, M.; Hertz, A.; Laporte, G., A tabu search heuristic for the vehicle routing problem, (1991), Publication # 777, Centre de recherche sur les transports Montréal
[20] Gandreau, M.; Hertz, A.; Laporte, G., New insertion and post-optimization procedures for the traveling salesman problem, Operations research, (1992), forthcoming
[21] Gillert, B.; Miller, L., A heuristic algorithm for the vehicle dispatch problem, Operations research, 22, 340-349, (1974) · Zbl 0274.90013
[22] Golden, B.L.; Assad, A.A., Vehicle routing: methods and studies, (1988), North-Holland Amsterdam · Zbl 0638.00043
[23] Golden, B.L.; Magnanti, T.L.; Nguyen, H.Q., Implementing vehicle routing algorithms, Networks, 7, 113-148, (1977) · Zbl 0359.90054
[24] Haouari, M.; Dejax, P.J.; Desrochers, M., Modelling and solving complex vehicle routing problems using column generation, (1990), LEIS École Centrale de Paris, Working Paper
[25] Laporte, G., Développements algorithmiques récents et perspectives de recherche en distributique, LES cahiers scientifiques du transport, 21, 61-84, (1990)
[26] Laporte, G., The traveling salesman problem: an overview of exact and approximate algorithms, European journal of operational research, 59/2, 231-248, (1992) · Zbl 0760.90089
[27] Laporte, G.; Mercure, H.; Nobert, Y., An exact algorithm for the asymmetrical capacitated vehicle routing problem, Networks, 16, 33-46, (1986) · Zbl 0643.90034
[28] Laporte, G.; Mercure, H.; Nobert, Y., A branch-and-bound algorithm for a class asymmetrical vehicle routing problems, Journal of the operational research society, (1991), forthcoming
[29] Laporte, G.; Nobert, Y., Exact algorithms for the vehicle routing problem, (), 147-184
[30] Laporte, G.; Nobert, Y.; Desrochers, M., Optimal routing under capacity and distance restrictions, Operations research, 33, 1050-1073, (1985) · Zbl 0575.90039
[31] Lenstra, J.K.; Rinnooy Kan, A.H.G., Some simple applications of the travelling salesman problem, Operational research quarterly, 26, 717-734, (1975) · Zbl 0308.90044
[32] Lin, S., Computer solutions of the traveling salesman problem, Bell system technical journal, 44, 2245-2269, (1965) · Zbl 0136.14705
[33] Martello, S.; Toth, P., Generalized assignment problem, (), 189-220
[34] Nelson, M.D.; Nygard, K.E.; Griffin, J.H.; Shreve, W.E., Implementation techniques for the vehicle routing problem, Computer & operations research, 12, 273-283, (1985) · Zbl 0608.90041
[35] Orloff, C., Route-constrained fleet scheduling, Transportation science, 10, 149-168, (1976)
[36] Paessens, H., The savings algorithm for the vehicle problem, europeam journal operational research, European journal of operational research, 34, 336-344, (1988) · Zbl 0635.90047
[37] Rao, M.R.; Zionts, S., Allocation of transportation units to alternative trips- A column generation scheme with out-of-killer, Operation research, 16, 52-63, (1968)
[38] Toregas, C.; ReVelle, C., Location under time or distance constraints, Papers, 28, 133-143, (1972)
[39] Wren, A., Computers in transport planning and operation, (1971), Ian Allan London
[40] Wren, A.; Holliday, A., Computer scheduling of vehicles from one or more depots to a number of delivery points, Operations research quarterly, 23, 333-344, (1972)
[41] Yellow, P., A computational modification to the savings method of vehicle scheduling, Operational research quarterly, 21, 281-283, (1970)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.