ЗАДАЧА МАРШРУТИЗАЦИИ СУДОВ С РАЗЛИЧНОЙ ГРУЗОПОДЪЁМНОСТЬЮ МОРСКОГО ТРАНСПОРТНОГО КОМПЛЕКСА АРКТИЧЕСКОЙ ЗОНЫ РОССИИ
Аннотация
В статье рассматривается одна из наиболее важных задач транспортной логистики - задача маршрутизации транспортных средств. В частности, предлагается метод решения одной из наиболее актуальных для практического применения подзадач проблемы маршрутизации, а именно, задачи маршрутизации судов разной грузоподъёмности. Для нахождения решения задачи предлагается использовать двухфазный алгоритм: на первом этапе выполняется группировка вершин для каждого будущего маршрута (кластеризация), на втором этапе - решение задачи коммивояжёра для каждой полученной группы. В первой фазе вычислений применяется так называемый алгоритм GRASP (Greedy Randomized Adaptive Search Procedure). Математическая модель задачи маршрутизации судов разной грузоподъёмности разделяется на две подзадачи, первая из которых представляет собой обобщённую задачу о назначениях. Группировка вершин и решение обобщённой задачи о назначениях происходит в рамках реализации метаэвристики GRASP.
Ключевые слова
маршрутизация транспортных средств, маршрутизация судов разной грузоподъёмности, двухфазный алгоритм, задача коммивояжёра, GRASP, GRASP
Читать полный текст статьи: PDF
Список литературы
Christofides N. Thevehicleroutingproblem / N. Christofides, A. Mingozzi, P. Toth // Combinatorial Optimization. - 1979. - Pp. 315-338.
Maffioli F. The vehicle routing problem: A book review / F. Maffioli // Quarterly Journal of the Belgian, French and Italian Operations Research Societies. - 2003. - Vol. 1. - № 2. - Pp. 149-153.
Lawler E. L. The traveling salesman problem: a guided tour of combinatorial optimization / E. L. Lawler, J. K. Lenstra, A. R. Kan, D. B. Shmoys. - New York: Wiley, 1985. - 476 p.
Miller C. E. Integer programming formulation of traveling salesman problems / C. E. Miller, A. W. Tucker, R. A. Zemlin // Journal of the ACM (JACM). - 1960. - Vol. 7. - № 4. - Pp. 326-329.
Desrochers M. Improvements and extensions to the Miller-Tucker-Zemlinsubtour elimination constraints / M. Desrochers, G. Laporte // Operations Research Letters. - 1991. - Vol. 10. - № 1. - Pp. 27-36.
Clarke G. Scheduling of vehicles from a central depot to a number of delivery points / G. Clarke, J.W. Wright // Operations Research. - 1964. - Vol. 12. - № 4. - Pp. 568-581.
Osman I. H. Metastrategy Simulated annealing and tabu search algorithms for the vehicle routing problem / I. H. Osman // Annals of Operations Research. - 1993. - Vol. 41. - № 4. - Pp. 421-451.
Fisher M. A generalized assignment heuristic for vehicle routing / M. Fisher, R. Jaikumar//Networks. - 1981. -Vol. 11. - № 2. - Pp. 109-124.
Gillett B. E. A heuristic algorithm for the vehicle-dispatch problem / B. E. Gillett, L. R. Miller //Operations Research. -1974. - Vol. 22. - № 2.- Pp. 340-349.
Beasley J. E. Route-first-clustersecond methods for vehicle routing / J. E. Beasley // Omega. - 1983. - Vol. 11. - № 4. - Pp. 403-408.
Haimovich M. Bounds and Heuristics for Capacitated Routing Problems / M. Haimovich, A. H. G. RinnooyKan // Mathematics of Operations Research. - 1985. -Vol. 10. - № 4. - Pp. 527-542.
Toth P. The Vehicle Routing Problem / P. Toth, D. Vigo // SIAM monographs on discrete mathematics. - 2002. - Vol. 9. - Pp. 129-154.
Dantzig G. Solution of a large-scale traveling-salesman problem / G. Dantzig, R. Fulkerson, S. Johnson // Journal of the operations research society of America. - 1954. - Vol. 2. - № 4. - Pp. 393-410.
Feo T. A. A probabilistic heuristic for a computationally difficult set covering problem / T. A. Feo, M. G. C. Resende// Operations Research Letters. - 1989. - Vol. 8. - № 2. - Pp. 67-71.
Feo T. A. Greedy randomized adaptive search procedures / T. A. Feo, M. G. C. Resende // Journal of Global Optimization. - 1995. - Vol. 6. - № 2. - Pp. 109-133.
Cordeau J. F. A Guide to Vehicle Routing Heuristics / J. F. Cordeau, M. Gendreau, G. Laporte, J.-Y. Potvin, F. Semet// Journal of the Operational Research Society. - 2002. - Vol. 53. - № 5. - Pp. 512-522.
Glaab H. A new variant of a vehicle routing problem: lower and upper bounds / H. Glaab // European Journal of Operational Research. - 2002. - Vol. 139. - № 3. - Pp. 557-577.
Об авторах
Головцов Дмитрий Львович - начальник лаборатории
ФГАОУ ВО «ГУАП»
