ИССЛЕДОВАНИЕ НЕКОТОРЫХ КЛАССИЧЕСКИХ АЛГОРИТМОВ ЗАДАЧИ МАРШРУТИЗАЦИИ ТРАНСПОРТА
Abstract
The article is devoted to the study of some classical algorithms for transport routing problems. The article describes the existing classical transport routing algorithms, such as the Clark-Wright algorithm and its extended algorithm. The main minus of Clarke-Wright’s algorithm has been revealed, which consists in the efficiency of its operation decreases as it approaches the end of the calculations, while at the beginning of the work, the solutions are relatively successful. To improve the performance of the Clark-Wright algorithm, three approaches have been proposed in its extended algorithm. Also were explored the algorithms of Mole-Jameson and Christofides, Mingozzi and Tossa, which can be used for tasks with an unspecified in advance number of vehicles, are investigated. The algorithm of the Notes, which is used for the initial processing of the problems of ZMT, is proposed. Classical improvement algorithms for MMT are investigated, in which either a single route at a time or several routes are processed. The above algorithms give more interesting results than their predecessors, and are considered optimal in terms of the use of certain resources.
References
Clarke G. Scheduling of vehicles from a central depot to a number of delivery points / G. Clarke, J.W. Wright // Operations Research. — 1964. — No 12 — P. 568-581.
Vigo D. A heuristic algorithm for the asymmetric capacitated vehicle routing problem // European Journal of Operational Research. — 1996. — No 89. — P. 108-126.
Gaskell T.J. Bases for vehicle fleet scheduling // Operational Research Quarterly. - 1967. - No 18. - P. 281-295.
Yellow P. A computational modification to the savings method of vehicle scheduling // Operational Research Quarterly. — 1970. — No 21. — P. 281-283.
Golden B.L. Implementing vehicle routing algorithms / B.L. Golden, T.L. Magnanti, H.Q. Nguyen // Networks. — 1977. — No 7. — P. 113-148.
Paessens H. The savings algorithm for the vehicle routing problem // European Journal of Operational Research. — 1988. — No 34. — P. 336-344.
Desrochers M. A matching based savings algorithm for the vehicle routing problem / M. Desrochers, T.W. Verhoog // Les Cahiers du GERAD G-89-04, Ecole des Hautes Etudes Commerciales de Montreal, 1989.
Altinkemer K. Parallel savings based heuristic for the delivery problem / K. Altinkemer, B. Gavish // Operations Research. — 1991. — No 39. — P. 456-469.
Lin S. Computer solutions of the traveling salesman problem // Bell System Technical Journal. — 1965. - No 44. - P. 2245-2269.
Christofides INT The vehicle routing problem. In N. Christofides, A. Mingozzi, P. Toth, C. Sandi, editors/ N. Christofides, A. Mingozzi, P. Toth // Combinatorial Optimization. — Wiley, Chichester, 1979. — P. 315-338.
Gillett B.E. A heuristic algorithm for the vehicle dispatch problem / B.E. Gillett, L.R. Miller // Operations Research. — 1974. - No 22. - P. 340-349.
Wren A. Computers in Transport Planning and Operation. — Ian Allan, London, 1971.
Wren A! Computer scheduling of vehicles from one or more depots to a number of delivery points / A. Wren and A. Holliday // Operational Research Quarterly. - 1972. - No 23. - P. 333-344.
Fisher M.L. A generalized assignment heuristic for vehicle routing / M.L. Fisher, R. Jaikumar // Networks. - 1981. — No 11. - P. 109-124.
Bramel J.B. A location based heuristic for general routing problems / J.B. Bramel, D. Simchi-Levi // Operations Research. — 1995. — No 43. — P. 649-660.
Renaud J. An improved petal heuristic for the vehicle routing problem / J. Renaud, F. F. Bostor, G. Laporte // Journal of Operational Research Society - 1996. — No 47. - P. 329-336.
Renaud J. A fast composite heuristic for the symmetric traveling salesman problem / J. Renaud, F.F. Boctor, G. Laporte // INFORMS Journal on Computing. - 1996. - No 8. - P. 134-143.
Views:
260
Downloads:
424
Copyright (c) 2019 The author
This work is licensed under a Creative Commons Attribution 4.0 International License.
All articles are published in open-access and licensed under a Creative Commons Attribution 4.0 International License (CC BY 4.0). Hence, authors retain copyright to the content of the articles.
CC BY 4.0 License allows content to be copied, adapted, displayed, distributed, re-published or otherwise re-used for any purpose including for adaptation and commercial use provided the content is attributed.
