메타휴리스틱 알고리즘 및 실시간 교통정보를 활용한 배차 및 동적 경로 최적화 연구

Abstract

Continuous development in the field of Information and Communication Technology (ICT) has led to a steady increase in the speed of the Internet and has expanded its penetration among the general public. The delivery service provided by large-scale retailers continues to grow as online sales occupy an increasingly large share of the market. So, our study aims to tease out efficient vehicles dispatching time intervals as well as optimal delivery routes by applying meta-heuristic algorithms. and the optimization of the real-time vehicle rerouting methodology. Our first task was to examine the status of existing routes by comparing delivery routes created using Dijkstra’s algorithm with existing delivery routes and their vehicle dispatching intervals. Monthly data on existing routes were obtained from a branch of Korea’s leading large-scale online retailer. The results of the comparative analysis revealed that the delivery distance, delivery time, and total service time for routes created through Dijkstra’s algorithm improved by 5.60%, 8.94%, and 17.50% on average. Our second task was to identify optimal delivery routes through a comparative analysis of the genetic algorithm, known for its superior applicability amongst other meta-heuristic algorithms, and the results of Tabu search. we also calculate the route of each delivery vehicle using a tabu search algorithm, which is a representative meta-heuristic algorithm. We determine the optimal number of delivery vehicles using the linear optimization technique and use it for route computation. Consequently, operation costs were reduced by 14.68% on an average, and service time and tCO2 quantity were reduced by 42.2% and 13.7%, respectively, when compared with the conventional tabu-search-based delivery system. Third, we optimized the dynamic rerouting methodology that reflects real-time traffic conditions, such as traffic accidents along the route. This enabled additional reductions in delivery distance, delivery time, and service time, on an average, by 0.3%, 6.53%, and 6.01%, respectively. These findings prove that the optimal vehicle routing problem (VRP) not only has the potential to reduce distribution cost for operators and expedite delivery for consumers, but also the added social benefit of reduced CO2emission.