×

zbMATH — the first resource for mathematics

A list based threshold accepting algorithm for the capacitated vehicle routing problem. (English) Zbl 1024.90018
Summary: The aim of this study is to describe a new stochastic search meta-heuristic algorithm for solving the capacitated vehicle routing problem, termed as the list based threshold accepting algorithm. The main advantage of this algorithm over the majority of other meta-heuristics is that it produces quite satisfactory solutions in reasonable amount of time by tuning only one parameter of the algorithm. This property makes this algorithm a reliable and a practical tool for every decision support system designed for solving real life vehicle routing problems.

MSC:
90B20 Traffic problems in operations research
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] DOI: 10.1016/0021-9991(90)90201-B · Zbl 0707.65039
[2] DOI: 10.1287/opre.6.6.791
[3] Waters C. D. J., J. Oper. Res. Soc. 38 pp 833– (1987)
[4] Christofides N., The vehicle routing problem. Combinatorial Optimization (1979) · Zbl 0413.90075
[5] Salhi S., J. Oper. Res. Soc. 38 pp 293– (1987)
[6] DOI: 10.1016/0377-2217(88)90154-3 · Zbl 0635.90047
[7] Pureza V M., Technical Report CRT-747, in: Vehicle routing via tabu search metaheuristic (1991)
[8] DOI: 10.1016/S0377-2217(98)00348-8 · Zbl 0934.90006
[9] DOI: 10.1287/opre.43.4.649 · Zbl 0857.90030
[10] Duncan T., Technical Report AIAI-TR-176, in: Experiments in the use of neighbourhood search techniques for vehicle routing (1995)
[11] DOI: 10.1287/ijoc.8.2.134 · Zbl 0866.90131
[12] Renaud J., J. Oper, I Res. Soc. 47 pp 329– (1996) · Zbl 0851.90032
[13] Rego C., Local search and neighborhood structures for vehicle routing problems: sequential and parallel algorithms (1996)
[14] Bullnheimer B., An improved ant system algorithm for the vehicle routing problem, Technical Report (1997) · Zbl 0937.90125
[15] DOI: 10.1016/S0377-2217(98)00348-8 · Zbl 0934.90006
[16] DOI: 10.1111/j.1475-3995.2000.tb00200.x
[17] Tarantilis C. D., A Backtracking Adaptive Threshold Accepting algorithm for the Vehicle Routing Problem, Technical Report (2000)
[18] DOI: 10.1007/BF02023004 · Zbl 0775.90153
[19] Rego C., Technical Report 44, in: An ecient implementation of ejection chain procedures for the vehicle routing problem (1994)
[20] Hjorring C., The vehicle routing problem and local search metaheuristics (1995)
[21] Tom P., The granular tabu search (and its application to the vehicle outing problem. (1998)
[22] DOI: 10.1016/S0305-0548(98)00047-1 · Zbl 0941.90017
[23] DOI: 10.1002/net.3230230804 · Zbl 0804.90045
[24] DOI: 10.1287/mnsc.40.10.1276 · Zbl 0822.90053
[25] DOI: 10.1287/trsc.30.4.379 · Zbl 0879.90086
[26] Shaw, P. Using Constraint Programming and Local search Methods to solve Vehicle Routing Problems. Proceedings of the Fourth International Conference on Principles and Practice of Constraint Programming. Springer.
[27] DOI: 10.1287/ijoc.11.2.161 · Zbl 1092.90503
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.