Адаптация эвристических алгоритмов маршрутизации на большой сети
В работе рассматривается динамическая адаптация муравьиного алгоритма на примере задачи маршрутизации транспортных средств с учетом их вместимости. Проведены эксперименты по различным критериям оценки алгоритмов, показана эффективность данной модификации и её универсальность.
Транспортная логистика занимает важное место на современном рынке, предприятия должны ориентироваться на интересы потребителей, а не на собственные. Для этого они должны сконцентрироваться на максимальном удовлетворении запросов клиентов. Оно выражается в достойном качестве товаров и услуг. Но больше всего влияют на цену товаров логистические издержки. В частности, поставщики поставляют ресурсы производителю, производитель направляет готовый товар посредникам, а те, в свою очередь – конечному покупателю. Любое предприятие заинтересовано в максимально продуманном, быстром и дешевом перемещении продукции.
Есть большое разнообразие математических моделей для описания логистических процессов. Классической задачей является проблема маршрутизации транспортного средства (Vehicle Routing Problems, VRP) – это общее название для целого класса задач, в которых для нескольких разбросанных городов или клиентов должен быть определен набор маршрутов для транспортных средств, расположенных на одном или нескольких складах. Данная модель предложена Данцигом и Рамсером в 1959 году.
VRP относится к классу NP-полных задач, что накладывает ограничение размерности задачи для целесообразной возможности применения точных алгоритмов. Для решения задачи на больших сетях используют алгоритмы, основанные на различных эвристиках и в том числе их комбинации. Но из-за особенности в вычислениях для одной и той же задачи эвристические алгоритмы могут генерировать различные решения, притом в основном лишь приближенные к оптимальному решению. В связи с этим присутствует большая заинтересованность в модификациях эвристических алгоритмов для их улучшения. У каждой реальной задачи имеются свои особенности, для которых нужны оптимизации вычислительных алгоритмов по определенным параметрам. Например, для курьерской службы важно время построения маршрутов, так как заказы могут поступать в реальном времени и есть необходимость в моментальном пересчете маршрута, в то же время для крупных предприятий важно построение маршрутов с низкой стоимостью, на которое они могут отвести определенное время, но гарантировать надежность данных маршрутов.
В первой главе рассмотрены задачи VRP и CVRP, представлена математическая модель задачи CVRP. Во второй главе подробно рассмотрен муравьиный алгоритм (ACO) и способы его применения для задачи CVRP. Проведен эксперимент по определению лучших наборов параметров для алгоритма ACO. В третьей главе дается определение динамической адаптации как критерия оценки алгоритмов и проведена оценка ACO. В четвертой главе предложен метод динамической адаптации алгоритма, приведена блок-схема алгоритма. В пятой главе рассмотрена вычислительная сложность алгоритма ACO и проведено вычисление её вида для алгоритма DAACO. В шестой главе произведен анализ алгоритма DAACO, метод экспериментального сравнения с алгоритмом ACO на ряде тестовых задач с использованием различных критериев. В седьмой главе описана проделанная работа и полученные результаты с выводами.
Виды задачи VRP
Первое появление задачи транспортной маршрутизации появилось в статье [1], где в 1959 году была поставлена математическая формулировка для поставки бензина на заправочные станции и представлено её решение. Сейчас эта задача является одной из самых известных в области комбинаторной оптимизации. Общий смысл задачи VRP представляется следующим образом: m транспортных средств, находящихся в депо, должны доставить товар n клиентам с минимальными затратами на перевозку товара. Решением является множество замкнутых маршрутов в депо, удовлетворяющие условию, что все клиенты посещались только один раз. Затраты на перевозку оптимизируются за счет уменьшения количества транспортных средств или оптимизации построенных маршрутов.
Для большинства задач транспортной маршрутизации вводят дополнительные ограничения, их можно классифицировать, как это сделано в статье [2], часто используемы из них:
Capacitated Vehicle Routing Problems (CVRP). Все транспортные средства имеют фиксированную вместимость.
Vehicle Routing Problems with Time Windows (VRPTW). Каждому клиенту задан определенный временной интервал (окно), в течение которого ему необходимо доставить груз.
Указано больше одного депо, которые могут использоваться для обслуживания клиентов.
Periodic Vehicle Routing Problem (PVRP). Задачи с возможностью доставки грузов в течение длительного времени. Общий период доставки расширяется до нескольких дней, по истечении которых каждый клиент должен быть посещен как минимум один раз. К тому же, транспортное средство может вернуться в депо в следующие дни после отправления.
Stochastic Vehicle Routing Problem (SVRP). В данной задаче для описания количества клиентов, их запросов или длины пути могут быть использованы случайные переменные. Таким образом, во время решения эти параметры могут измениться.
Постановка задачи СVRP
Модель задачи представляется в виде графа – полный направленный граф, где – множество узлов, причем узел 0 представляет депо для транспортных средств с одинаковой емкостью Q и n узлами, которые представляют географически рассредоточенных клиентов. Матрица описывает множество дуг, транспортную сеть между узлами. Каждый клиент имеет определенный положительный спрос Стоимость перемещения связана с каждой дугой Матрица стоимости симметрична, , для всех и удовлетворяет условию неравенства треугольника для всех [3]. Минимальное необходимое количество транспортных средств для обслуживания всех клиентов вычисляется как .
На Рис 1 показан пример возможного решения задачи CVRP с 7 клиентами и 3 транспортными средствами емкостью . Требование клиентов указано рядом с узлами.
В работе была исследована одна из задач транспортной маршрутизации – CVRP, а так же один из классических эвристических алгоритмов для её решения – ACO.
Подробно изучен, описан и реализован на языке программирования Java муравьиный алгоритм (ACO) для решения задачи CVRP, приведены полученные экспериментальным путем наборы параметров для запуска муравьиного алгоритма. Произведена его оценка уровня динамической устойчивости решений, генерируемых данной эвристикой. Из-за того, что эвристики не обеспечивают получение оптимальных решений, но генерирует решения близкие к оптимальным, среднее значение этой величины для рассмотренных задач получилось равно 0, из чего делается вывод, что значение итераций для ACO было недостаточно высоким, но и оно не гарантирует отсутствие зацикливания алгоритма на локальном минимуме. Таким образом, использовать чистую эвристику ACO без алгоритмов локального поиска даже при больших значениях итераций и количества муравьиных агентов не целесообразно.
Принцип динамической устойчивости показал, что любой эвристический алгоритм, который генерирует различные решения для одной и той же задачи, можно улучшить с помощью алгоритма динамической адаптации. Динамическая адаптация муравьиного алгоритма (DAACO) повысила уровень динамической устойчивости решений до 0,571. Также значения целевых функций решений, сгенерированных алгоритмом DAACO, и их среднее меньше, чем полученные с помощью классического муравьиным алгоритмом. Средний процент улучшения решений равен 8%. К тому же, динамическая адаптация муравьиного алгоритма показала лучшие результаты на меньших значениях параметров итераций алгоритма, затратив на вычисление меньше времени, чем обычный муравьиный алгоритм.
Результаты экспериментов показали, что использование динамической адаптации муравьиного алгоритма будет эффективней, чем использование простого муравьиного алгоритма, точность вычисления увеличивается, уменьшается разброс получаемых решений, а главное, позволяет уменьшить время вычислений за счет уменьшения значений параметров итераций и численности муравейника, не ухудшив значения генерируемых решений и не используя посторонние способы улучшения.
Список литературы
• Dantzig G. B., Ramser J. H., The Truck Dispatching Problem, 1959.
• Braekersab K., Ramaekersa K., Van Nieuwenhuysec I. The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering. Volume 99, September 2016, Pages 300-313.
• Toth, P., Vigo, D.(2002). Models, relaxations and exact approaches for capacitated vehicle routing problem. Discrete Applied Mathematics, 123: 487-512.
• Janacek, J., Janosikova, L., Kohani, M. (2013). Modelovanie a optimalizacia. EDIS vydavatelstvo ZU, in Slovak. (2013).
• M. Dorigo, G. Di Caro, and L.M. Gambardella. Ant algorithms for discrete optimization. Artificial Life, 5:137–172, 1999.
• J.-L. Deneubourg, S. Aron, and S. Gossand J.-M. Pasteels. The self-organizing exploratory pattern of the Argentine ant. Journal of Insect Behavuiour, 3: 159–168, 1990.
• M. Dorigo and L.M. Gambardella. Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1):53–66, 1997.
• L.M. Gambardella and M. Dorigo. Ant-Q: a reinforcement learning approach to the travelling salesman problem. In Proceedings of the Twelfth International Conference on Machine Learning, ML-95. Morgan Kaufmann, Palo Alto, California, USA, 1995.
• L.M. Gambardella and M. Dorigo. Solving symmetric and asymmetric TSPs by ant colonies. In IEEE Conference on Evolutionary Computation (ICEC96), pages 622–627, 1996.
• C.J. Watkins and P. Dayan. Q-learning. Machine Learning, 8:279–292, 1992.
• B. Bullnheimer, R. F. Hartl, and C. Strauss. Applying the ant system to the vehicle routing problem. In Proceedings of the 2nd International Conference on Metaheuristics – MIC97. INRA Sophia-Antipolis & PRiSM Versailles, 1997.
• B. Bullnheimer, R.F. Hartl, and C. Struss. An improved ant system algorithm for the vehicle routing problem. Annals of Operations Research, 89:319–328, 1999.
• Capacitated Vehicle Routing Problem Library. http://vrp.atd-lab.inf.puc-rio.br/index.php/en/.
• J.F. Cordeau, M. Gendreau, G. Laporte, J.Y. Potvin, and F.Semet. A guide to vehicle routing heuristics. Journal of the Operational Research Society, pages 512–522, May 2002.
• Jean-Francois Cordeau, Michel Gendreau, and Gilbert Laporte. A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks, 30(2):105–119, 1997.
• Петросян Леон Аганесович и Зенкевич Николай Анатольевич. Принципы устойчивой кооперации. Управление большими системами: сборник трудов, (3):100–120, 2009.
• Dorigo, M., Stutzle, T. Ant colony optimization. The MIT press, 2004
• Giorgio Ausiello, Bruno Escoffier, JeRoMe Monnot, and Vangelis Paschos. Reoptimization of minimum and maximum traveling salesman’s tours. J. of Discrete Algorithms, 7(4):453–463, December 2009.
• V. Zakharov and M. Dementieva. Multistage cooperative games and problem of time consistency. International Game Theory Review, 6:157–170, 2004.
• V.V. Zakharov and A.N. Shchegryaev. Multi-period cooperative vehicle routing games. Contributions to Game Theory and Management, 7(2):349– 359, April 2014.
• P. Stodola, J. Mazal, M. Podhorec, O. Litva. Using the Ant Colony Optimization Algorithm for the Capacitated Vehicle Routing. Proceedings of the 16th International Conference on Mechatronics – Mechatronika 2014
Хочешь уникальную работу?
Больше 3 000 экспертов уже готовы начать работу над твоим проектом!
5 (18 отзывов)
5 (1241 отзыв)
4.9 (37 отзывов)
5 (18 отзывов)
4.1 (20 отзывов)
4.2 (25 отзывов)
4.8 (40 отзывов)
4.2 (13 отзывов)
4.2 (5 отзывов)
