FINDING THE MOST OPTIMAL ALGORITHM TO SOLVE THE DELIVERY PROBLEMS WITH TIME WINDOWS

The need to optimize customer service, reduce operating costs and negative environmental impact that may arise as a result of suboptimal planning of vehicles and their routes attracts the attention of the scientific community to solving this problem over the past decade. The development of effective tools to solve problems in the transport industry can lead to significant cost reductions and efficient resource consumption. In this paper, we consider and compare algorithms that can provide the search for the optimal route that satisfies the conditions for solving the problem of routing delivery with time windows (VRPTW). The analysis of the most suitable solution paths that can reduce the number of calculated paths and reduce the time of solving the problem is presented. Heuristic graph search algorithms were studied, namely: breadth-first search, Dijkstra's algorithm, Greedy algorithm and A * algorithm. It also presented ways to improve each algorithm in the Python programming language, identified the strengths and weaknesses of each of the proposed solutions and the most suitable for solving the problem of routing delivery with time windows. The results of the work can be used to create software that solves the problems of delivery routing in the oil and gas industry, contributing to the optimization of logistics processes, which in the long run will have a positive effect on cost reduction, rational consumption of resources and a favorable impact on the environment.

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.