×
Renaud, Jacques; Laporte, Gilbert; Boctor, Fayez F.

A tabu search heuristic for the multi-depot vehicle routing problem. (English) Zbl 0855.90055

Comput. Oper. Res. 23, No. 3, 229-235 (1996).
Summary: This article describes a tabu search algorithm for the multi-depot vehicle routing problem with capacity and route length restrictions. The algorithm is tested on a set of 23 benchmark instances. It is shown to outperform existing heuristics.

Cited in 47 Documents

MSC:

90B06 Transportation, logistics and supply chain management

Keywords:

tabu search; multi-depot vehicle routing; capacity and route length restrictions; heuristics

Software:

VRP
PDFBibTeX XMLCite
\textit{J. Renaud} et al., Comput. Oper. Res. 23, No. 3, 229--235 (1996; Zbl 0855.90055)
Full Text: DOI

References:

[1] Cassidy, P. J.; Bennett, H. S., TRAMP—a multi-depot vehicle scheduling system, Opl Res. Q., 23, 151-162 (1972)
[2] Ball, M. O.; Golden, B. L.; Assad, A. A.; Bodin, L. D., Planning for truck fleet size in the presence of a common-carrier option, Decis. Sci., 14, 103-120 (1983)
[3] Golden, B. L.; Wasil, E., Computerized vehicle routing in the soft drink industry, Opns Res., 35, 6-17 (1987)
[4] Fisher, M. L.; Greenfield, R.; Jaikumar, R.; Lester, J., A computerized vehicle routing application, Interfaces, 12, 4, 42-52 (1982)
[5] Bell, W.; Dalberto, L.; Fisher, M. L.; Greenfield, A.; Jaikumar, R.; Kedia, P.; Mack, R.; Prutzman, P., Improving the distribution of industrial gases with an on-line computerized routing and scheduling system, Interfaces, 13, 4-22 (1983)
[6] Brown, G.; Ellis, C.; Graves, G.; Ronen, D., Real-time wide area dispatch of mobil tank trucks, Interfaces, 17, 1, 107-120 (1987)
[7] Pooley, J., Integrated production and distribution facility planning at Ault Foods, Interfaces, 24, 113-121 (1994)
[8] Dror, M.; Levy, L., A vehicle routing improvement algorithm-comparison of a “greedy” and a “matching” implementation for inventory routing, Computers Opns Res., 23, 33-45 (1986) · Zbl 0614.90061
[9] Laporte, G., The vehicle routing problem: an overview of exact and approximate algorithms, Eur. J. Opl Res., 59, 345-358 (1992) · Zbl 0761.90034
[10] Laporte, G.; Nobert, Y.; Arpin, D., Optimal solutions to capacitated multidepot vehicle routing problems, Congressus Numerantium, 44, 283-292 (1984) · Zbl 0554.90031
[11] Laporte, G.; Nobert, Y.; Taillefer, S., Solving a family of multi-depot vehicle routing and location-routing problems, Transp. Sci., 22, 161-172 (1988) · Zbl 0662.90039
[12] Tillman, F. A., The multiple terminal delivery problem with probabilistic demands, Transp. Sci., 3, 192-204 (1969)
[13] Clarke, G.; Wright, J. W., Scheduling of vehicles from a central depot to a number of delivery points, Opns Res., 46, 93-100 (1964)
[14] Tillman, F. A.; Hering, R. W., A study of a look-ahead procedure for solving the multiterminal delivery problem, Transp. Res., 5, 225-229 (1971)
[15] Tillman, F. A.; Cain, T. M., An upperbound algorithm for the single and multiple terminal delivery problem, Mgmt Sci., 18, 664-682 (1972) · Zbl 0238.90047
[16] Wren, A.; Holliday, A., Computer scheduling of vehicles from one or more depots to a number of delivery points, Opns Res. Q., 23, 333-344 (1972)
[17] B. E. Gillett and J. G. Johnson, Multi-terminal vehicle-dispatch algorithm. Omega4; B. E. Gillett and J. G. Johnson, Multi-terminal vehicle-dispatch algorithm. Omega4
[18] Gillett, B. E.; Miller, L. E., A heuristic algorithm for the vehicle-dispatch problem, Opns Res., 22, 340-349 (1974) · Zbl 0274.90013
[19] Christofides, N.; Eilon, S., An algorithm for one vehicle-dispatching problem, Opl Res. Q., 20, 309-318 (1969)
[20] Golden, B. L.; Magnanti, T. L.; Nguyen, H. Q., Implementing vehicle routing algorithms, Networks, 7, 113-148 (1977) · Zbl 0359.90054
[21] Yellow, P., A Computational modification to the savings method of vehicle scheduling, Opl Res. Q., 21, 281-283 (1970)
[22] Raft, O. M., A modular algorithm for an extended vehicle scheduling problem, Eur. J. Opl Res., 11, 67-76 (1982) · Zbl 0482.90041
[23] Lin, S., Computer solution of the traveling salesman problem, Bell Syst. Comput. J., 44, 2245-2269 (1965) · Zbl 0136.14705
[24] Chao, I. M.; Golden, B. L.; Wasil, E., A new heuristic for the multi-depot vehicle routing problem that improves upon best-known solutions, Am. J. Math. Mgmt Sci., 13, 371-406 (1993) · Zbl 0808.90061
[25] Dueck, G., New optimization heuristics, the great deluge algorithm and the record-to-record travel, (Scientific center technical report (1990), IBM Germany, Heidelberg Scientific Center) · Zbl 0773.65042
[26] Li, C.-L.; Simchi-Levi, D., Worst-case analysis of heuristics for multidepot capacitated vehicle routing problems, ORSA J. Comput., 2, 64-73 (1990) · Zbl 0752.90018
[27] Min, H.; Current, J.; Schilling, D., The multiple depot vehicle routing problem with backhauling, J. Business Logist., 13, 259-288 (1992)
[28] Glover, F., Heuristic for integer programming using surrogate constraints, Decision Sci., 8, 156-166 (1977)
[29] J. Renaud, F. F. Boctor and G. Laporte, An improved petal heuristic for the vehicle routing problem. J. Opl Res. Soc.; J. Renaud, F. F. Boctor and G. Laporte, An improved petal heuristic for the vehicle routing problem. J. Opl Res. Soc. · Zbl 0851.90032
[30] Renaud, J.; Boctor, F. F.; Laporte, G., A fast composite heuristic for the symmetric traveling salesman problem, (Working paper CRT-981 (1994), Centre for research on transportation: Centre for research on transportation Montreal) · Zbl 1059.90005
[31] Osman, I. H., Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem, Annls Opns Res., 41, 421-451 (1993) · Zbl 0775.90153
[32] Taillard, É., Robust taboo search for the quadratic assignment problem, Parallel Comput., 17, 433-445 (1991)
[33] Gendreau, M.; Hertz, A.; Laporte, G., A tabu search heuristic for the vehicle routing problem, Mgmt Sci., 40, 1276-1290 (1994) · Zbl 0822.90053
[34] Renaud, J.; Laporte, G.; Boctor, F. F., A tabu search heuristic for the multi-depot vehicle routing problem, (Working paper CRT-94-44 (1994), Centre for research on transportation: Centre for research on transportation Montreal) · Zbl 0855.90055
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.