음식 배달 서비스를 위한 배달 라이더의 최적 주문 선택 및 경로 연구

The Optimal Set of Orders and Courier Path for Food Delivery Services

본 연구는 배달 라이더의 제한된 배달 시간내에서 수익을 최대화하는 주문 선택 및 최적 경로를 결정하는 문제를 다룬다. 먼저 본 문제를 해결하기 위하여 혼합정수계획 모형을 개발하였다. 그러나 대부분의 TSP(Travelling Salesman Problem)와 같이 본 연구에서 다루는 문제도 주문 건수가 증가하게 되면 최적해를 탐색하는 시간이 기하급수적으로 증가하는 NP-hard 문제이다. 때문에 현장에서 활용 가능한 3종류의 휴리스틱 알고리즘을 개발하였다. 다양한 실험을 통해서 개발한 알고리즘이 우수한 성능을 보여주고 있음을 확인하였다.

This study deals with the problem of determining the optimal order selection and courier route to maximize the profit for a limited delivery time. The mixed integer programming model is developed to solve this issue. Since this research problem is similar to the travelling salesman problem (TSP), it is considered an NP-hard (non-deterministic polynomial-time hard) problem. Hence, the time to find the optimal solution increases exponentially as the number of orders increases. To deal with this complexity, we develop three types of heuristic algorithms that can be used to solve real-world problems. Through various numerical experiments, we show that the developed algorithms perform well.