zbMATH — the first resource for mathematics

Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. (English) Zbl 0775.90153

90B06 Transportation, logistics and supply chain management
90C27 Combinatorial optimization
90-08 Computational methods for problems pertaining to operations research and mathematical programming
Full Text: DOI
[1] E. Aarts and J. Korst,Simulated Annealing and Boltzmann Machine (Wiley, 1989). · Zbl 0674.90059
[2] Y. Agarwal, K. Mathur and H. Salkin, A set partitioning based exact algorithm for the vehicle routing problem, Networks 19(1989)731–749. · Zbl 0682.90050 · doi:10.1002/net.3230190702
[3] K. Altinkemer and B. Gavish, Parallel savings based heuristics for the delivery problem, Oper. Res. 39(1991)456–469. · Zbl 0744.90026 · doi:10.1287/opre.39.3.456
[4] J. Beasley, Route first-cluster second methods for vehicle routing, Omega 118(1983)403–408. · doi:10.1016/0305-0483(83)90033-6
[5] W. Bell, L. Dalberto, M. Fisher, A. Greenfield, R. Jaikumar, R. Mack and P. Prutzman, Improving distribution of industrial gases with an on-line computerized routing and scheduling systems, Interfaces 13(1983)4–23. · doi:10.1287/inte.13.6.4
[6] L. Bodin, B. Golden, A. Assad and M. Ball, Routing and scheduling of vehicles and crews: The state of the art, Comp. Oper. Res. 10(1983)69–211.
[7] L. Bodin, Twenty years of routing and scheduling, Oper. Res. 38(1990)571–579. · doi:10.1287/opre.38.4.571
[8] G. Brown and G. Graves, Real-time dispatch of petroleum tank trunks, Manag. Sci. 27(1981)19–32. · doi:10.1287/mnsc.27.1.19
[9] N. Christofides, Vehicle routing, in:The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, ed. E. Lawler, J. Lenstra, A. Rinnooy Kan and D. Shmoys (Wiley, 1985).
[10] N. Christofides and S. Eilon, An algorithm for the vehicle dispatching problem, Oper. Res. Quart. 20(1969)309–318. · doi:10.1057/jors.1969.75
[11] N. Christofides, A. Mingozzi and P. Toth, The vehicle routing problem, in:Combinatorial Optimization, ed. N. Christofides, A. Mingozzi, P. Toth and C. Sandi (Wiley, 1979). · Zbl 0413.90075
[12] N. Christofides, A. Mingozzi and P. Toth, Exact algorithms for the vehicle routing problem, based on spanning tree shortest path relaxation, Math. Progr. 20(1981)255–282. · Zbl 0461.90067 · doi:10.1007/BF01589353
[13] N. Christofides, A. Mingozzi and P. Toth, State space relaxation procedures for the computation of bounds to routing problems, Networks 11(1981)145–164. · Zbl 0458.90071 · doi:10.1002/net.3230110207
[14] G. Clarke and J.W. Wright, Scheduling of vehicles from a central depot to a number of delivery points, Oper. Res. 12(1964)568–581. · doi:10.1287/opre.12.4.568
[15] S. Evans and J. Norback, The impact of a decision-support system for vehicle routing in a food service supply situation, J. Oper. Res. Soc. 36(1985)467–472.
[16] M. Fisher, R. Greenfield, R. Jaikumar and J. Lester, A computerized vehicle routing application, Interfaces 1(1982)45–52.
[17] M. Fisher and R. Jaikumar, A generalised assignment heuristic for vehicle routing, Networks 11(1981)109–124. · doi:10.1002/net.3230110205
[18] M. Fisher, Lagrangian optimization algorithms for vehicle routing problems, in:Operational Research’87, IFORS, 1988, ed. G.K. Rand (Elsevier Science/North-Holland, 1988). · Zbl 0663.90040
[19] T. Gaskell, Bases for vehicle fleet scheduling, Oper. Res. Quart. 18(1967)367–384. · doi:10.1057/jors.1967.44
[20] M. Gendreau, A. Hertz and G. Laporte, A tabu search heuristic for the vehicle routing problem, Report CRT-777, Centre de Recherche sur les Transports, Université de Montréal, Canada (1991). · Zbl 0822.90053
[21] B. Gillet and L. Miller, A heuristic algorithm for vehicle dispatches, Oper. Res. 24(1976)340–349.
[22] F. Glover, Future paths for integer programming and links to artificial intelligence, Comp. Oper. Res. 13(1986)533–549. · Zbl 0615.90083 · doi:10.1016/0305-0548(86)90048-1
[23] F. Glover, Tabu search, Part I, ORSA J. Comput. 1(1989)190–206.
[24] F. Glover, Tabu search, Part II, ORSA J. Comput. 2(1990)4–32.
[25] F. Glover, Simple tabu thresholding in optimization, Graduate of Business, Unicersity of Colorado, Boulder (May 1992).
[26] B. Golden and E. Watts, Computerized vehicle routing in the soft drink industry, Oper. Res. 35(1987)6–17. · doi:10.1287/opre.35.1.6
[27] B. Golden and A. Assad,Vehicle Routing: Methods and Studies (Elsevier Science/North-Holland, 1988).
[28] M. Haimovich and A.H.G. Rinnooy Kan, Bounds and heuristics for capacitated routing problems, Math. Oper. Res. 10(1985)527–542. · Zbl 0582.90030 · doi:10.1287/moor.10.4.527
[29] D.S. Johnson, Local optimization and the traveling salesman problem,Proc. 17th Int. Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science (1990) pp. 446–461. · Zbl 0766.90079
[30] S. Kirkpatrick, J.C.D. Gelott and M.P. Vecchi, Optimization by simulated annealing, Science 220(1983)671–680. · Zbl 1225.90162 · doi:10.1126/science.220.4598.671
[31] G. Laporte, Y. Nobert and M. Desrochers, Optimal routing under capacity and distance restriction, Oper. Res. 33(1985)1050–1073. · Zbl 0575.90039 · doi:10.1287/opre.33.5.1050
[32] G. Laporte and Y. Nobert, Exact algorithms for the vehicle routing problem, Ann. Discr. Math. 31(1987)147–184. · Zbl 0611.90055
[33] J. Lenstra and A. Rinnooy Kan, Complexity of vehicle routing and scheduling problems, Networks 11(1981)221–228. · doi:10.1002/net.3230110211
[34] S. Lin, Computer solutions of the traveling salesman problem, Bell Syst. Comp. J. 44(1965)2245–2269. · Zbl 0136.14705
[35] S. Lin and B.W. Kernighan, An effective heuristic algorithm for the travelling salesman problem, Oper. Res. 21(1973)2245–2269. · Zbl 0256.90038 · doi:10.1287/opre.21.2.498
[36] R.H. Mole and S.R. Jameson, A sequential route-building algorithm employing a generalised savings criterion, Oper. Res. Quart. 27(1976)503–511. · doi:10.1057/jors.1976.95
[37] M. Nelson, K. Nygard, J. Griffin and W. Shreve, Implementation techniques for the vehicle routing problem, Comp. Oper. Res. 12(1985)273–283. · Zbl 0608.90041 · doi:10.1016/0305-0548(85)90026-7
[38] I. Or, Traveling salesman-type combinatorial optimization problems and their relation to the logistics of regional blood banking, Ph.D. Dissertation, Northwestern University, Evanston, IL (1976).
[39] I.H. Osman, Metastrategy simulated annealing and tabu search for combinatorial optimization problems, Ph.D. Dissertation, The Management School, Imperial College of Science and Medicine, University of London, London (1991).
[40] I.H. Osman, Heuristics for combinatorial optimization problems: development and new directions,Proc. 1st Seminar on Information Technology and Applications, Markfield Conference Centre, Leicester, UK (1991).
[41] I.H. Osman, A comparison of heuristics for the generalised assignment problem, Working Paper, University of Kent, Canterbury, UK (1990).
[42] I.H. Osman and N. Christofides, Simulated annealing and descent algorithms for capacitated clustering problems, presented as EURO-XI, Beograd, Yugoslavia (1989).
[43] I.H. Osman and C.N. Potts, Simulated annealing for permutation flow-shop scheduling, Omega 17(1989)551–557. · doi:10.1016/0305-0483(89)90059-5
[44] H. Paessens, Saving algorithms for the vehicle routing problem, Eur. J. Oper. Res. 34(1988)336–344. · Zbl 0635.90047 · doi:10.1016/0377-2217(88)90154-3
[45] R.A. Russell, An effective heuristic for theM-tour traveling salesman problem with some side conditions, Oper. Res. 25(1977)517–524. · Zbl 0377.90094 · doi:10.1287/opre.25.3.517
[46] W.R. Stewart, Jr. and B.L. Golden, A Lagrangian relaxation heuristic for vehicle routing, Eur. J. Oper. Res. 15(1984)84–88. · Zbl 0525.90092 · doi:10.1016/0377-2217(84)90050-X
[47] E. Taillard, Robust tabu search for the quadratic assignment problem, Working Paper ORWP 90/10, Département de Mathématiques, Ecole Polytechnic Fédérale de Lausanne, Switzerland (1990).
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.