(A) study on developing a gradient-based optimization algorithm for vehicle routing problems

Abstract

Many studies are under way on algorithms for vehicle routing problems because these algorithms are being used in delivery and parcel service, and can even be utilized for future transportation systems, which are electric scooter sharing service and on-demand public transportation service. The existing methods obtain optimal route with algorithms that first find the shortest path between all destinations and then solve the traveling salesman problem, which is a problem that finds an optimal route starting from one depot, visiting all destinations, and turning back to the depot. Existing algorithms that solve the traveling salesman problem cannot take into account the number of all cases, therefore, most of which are used to find the optimal route in a limited time. These algorithms have a problem in which as the number of destinations increases, the calculation time increases rapidly, making it difficult to use for real-time route planning. To overcome drawbacks of these algorithms, a gradient-based optimization algorithm efficiently shortening the calculation time in the traveling salesman problem is proposed in this study. The algorithm was designed by utilizing the similarity of the roadway network and electric circuit, and the theory of optimal design. The accuracy and calculation time of the new algorithm were verified by comparing with a genetic algorithm, which is the most commonly used among existing algorithms, in the virtual network, and it was confirmed that the calculation time could be effectively shortened. If the proposed algorithm in this study is used for real-time route planning, it is expected that it will be able to effectively respond to changes in real-time traffic conditions.