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.
차량 경로 계획을 위한 알고리즘들은 기존의 택배 및 배달 시스템에서 사용되고 있으며, 미래 교통시스템인 전기 공유 킥보드 서비스와 수요 응답형 교통 시스템까지 활용될 수 있어 많은 연구가 진행되고 있다. 기존의 방법들은 먼저 최단 경로를 찾는 알고리즘으로 목적지 사이의 최단 경로를 구하고 출발지에서 여러 목적지를 방문한 뒤 다시 출발지로 돌아올 때의 최적의 방문 순서를 찾는 외판원 문제를 해결하는 알고리즘으로 최적의 경로를 계산한다. 기존의 외판원 문제를 해결하는 알고리즘들은 모든 경우의 수를 고려할 수 없어 대부분 한정된 시간 안에 최적의 경로를 찾는 알고리즘들이 사용되고 있다. 이러한 알고리즘들은 목적지의 개수가 늘어날수록 계산 시간이 급격히 증가하여 실시간 경로 탐색에 활용되기 어려운 문제점이 있다. 이러한 단점을 보완하기 위해 다수의 목적지를 고려해야 하는 외판원 문제에서 계산 시간을 효율적으로 단축하여 계산할 수 있는 민감도 기반의 최적화 알고리즘을 제안한다. 알고리즘은 도로 네트워크와 전기회로의 유사성과 최적 설계의 이론을 활용하여 설계되었다. 새로운 알고리즘의 정확도와 계산 시간을 기존의 알고리즘 중 가장 많이 사용되는 유전 알고리즘과 가상의 네트워크에서 비교하여 검증하였고, 계산시간을 효과적으로 단축시킬 수 있음을 확인하였다. 제안하는 알고리즘을 실시간 경로 계획에 활용한다면 실시간 교통 상황 변화에 효과적으로 대응할 수 있을 것으로 기대한다.
