ПОИСК НАИБОЛЕЕ ОПТИМАЛЬНОГО АЛГОРИТМА ДЛЯ РЕШЕНИЯ ПРОБЛЕМЫ ДОСТАВКИ С ВРЕМЕННЫМИ ОКНАМИ

Необходимость оптимизации обслуживания клиентов, снижения эксплуатационных расходов и негативного воздействия на окружающую среду, которое может возникнуть в результате неоптимального планирования транспортных средств и их маршрутов, привлекает внимание научного сообщества к решению этой проблемы в течение последнего десятилетия. Разработка эффективных инструментов для решения проблем в транспортной отрасли может привести к значительному снижению затрат и эффективному потреблению ресурсов. В данной работе рассматриваются и сравниваются алгоритмы, способные обеспечить поиск оптимального маршрута, удовлетворяющего условиям решения проблемы маршрутизации доставки с временными окнами (VRPTW). Представлен анализ наиболее подходящих путей решения, способных уменьшить количество вычисляемых путей и сократить время решения задачи. Были изучены эвристические алгоритмы поиска по графу, а именно: поиск в ширину, алгоритм Дейкстры, Жадный алгоритм и алгоритм A*. Также были представлены способы улучшения каждого алгоритма на языке программирования Python, определены сильные и слабые стороны каждого из предложенных решений и наиболее подходящее для решения проблемы маршрутизации доставки с временными окнами. Результаты работы могут применяться для создания программного обеспечения, решающего проблемы маршрутизации доставки в нефтегазовой индустрии, способствуя оптимизации логистических процессов, что в долгосрочной перспективе положительно скажется на снижении затрат, рациональном потреблении ресурсов и благоприятном влиянии на окружающую среду.

1. Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck: Alternative Routes in Road Networks//Journal of Experimental Algorithmics. 2013, 23-34.

2. Rolf H. Mohring and Heiko Schilling: Partitioning Graphs to Speedup Dijkstra’s Algorithm// Journal of Experimental Algorithmics. 2007, 189-202.

3. Dominik Schultes: Fast and Exact Shortest Path Queries Using Highway Hierarchies // ESA. 2005, 68-79.

4. Goldberg, A.V., Werneck, R.F.: Computing Point-to-Point Shortest Paths from External Memory //Proceedings of the 7th Workshop on Algorithm Engineering and Experiments. 2005, 26-40.

5. Reinhard Bauer, Daniel Delling, Peter Sanders, Dennis Schieferdecker, Dominik Schultes, and Dorothea Wagner: Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra’s Algorithm?//International Workshop on Experimental and Efficient Algorithms. 2008, 303-318.