Drone Arc Routing Problem Using Ant Colony Optimization in Snow Removal Operation

Abstract

Drones can overcome the limitation of ground vehicles by replacing the congestion time and allowing rapid service. For sudden snowfall with climate change, a quickly deployed drone can be a flexible alternative considering the deadhead route and the labor costs. The goal of this study is to optimize a drone arc routing problem (D-ARP), servicing the required roads for snow removal. A D-ARP creates computational burden especially in large network. The D-ARP has a large search space due to its exponentially increased candidate route, arc direction decision, and continuous arc space. To reduce the search space, we developed the auxiliary transformation method in ACO algorithm and adopted the random walk method. The contribution of the work is introducing a new problem and optimization approach of D-ARP in snow removal operation and reduce its search space. The optimization results confirmed that the drone travels shorter distance compared to the truck with a reduction of 5% to 22%. Furthermore, even under the length constraint model, the drone shows 4% reduction compared to the truck. The result of the test sets demonstrated that the adopted heuristic algorithm performs well in the large size networks in reasonable time. Based on the results, introducing a drone in snow removal is expected to save the operation cost in practical terms.

드론은 혼잡시간대를 대체하고 빠른 서비스를 가능하게 함으로써 지상차량의 한계를 극복할 수 있다. 최근 기후변화에 따른 갑작스런 강설의 경우에, 드론과 같이 빠르게 투입할 수 있는 서비스는 운행 경로와 노동비용을 고려했을 때도 유연한 운영 옵션이 될 수 있다. 본 연구의 목적은 드론 아크 라우팅(D-ARP)을 최적화하는 것이며, 이는 제설에 필요한 도로를 서비스하는 경로를 탐색하는 것이다. 드론 아크 라우팅은 특히 큰 네트워크에서 컴퓨터 부하를 생성한다. 다시 말해D-ARP는 큰 검색공간을 필요로 하며, 이는 기하급수적으로 증가하는 후보 경로 및 호의 방향 결정 그리고 연속적인 호의 공간으로부터 기인한다. 검색공간을 줄이기 위해, 우리는 개미알고리즘에 보조변환방법을 적용하는 방안을 도입하였으며 또한 랜덤워크 기법을 채택하였다. 본 연구의 기여는 제설 운영에 있어 D-ARP라는 새로운 문제를 설정하고 최적화 접근법을 도입하였으며 검색공간을 최소화한 것이다. 최적화 결과, 드론은 지상트럭에 비해 약 5% ~ 22%의 경로 비용 감소를 보였다. 나아가 길이 제약 모델에서도 드론은 4%의 비용 감소를 보였다. 또한 실험결과는 적용한 휴리스틱 알고리즘이 큰 네트워크에서도 합리적 시간 내에 최적해를 찾음을 입증하였다. 이러한 결과를 바탕으로, 드론을 제설에 도입하는 것은 미래에 제설 운영 비용을 실질적으로 감소시킬 것으로 기대된다.