음식 배달 서비스를 위한 배달 라이더의 최적 주문 선택 및 경로 연구
The Optimal Set of Orders and Courier Path for Food Delivery Services
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
본 연구는 배달 라이더의 제한된 배달 시간내에서 수익을 최대화하는 주문 선택 및 최적 경로를 결정하는 문제를 다룬다. 먼저 본 문제를 해결하기 위하여 혼합정수계획 모형을 개발하였다. 그러나 대부분의 TSP(Travelling Salesman Problem)와 같이 본 연구에서 다루는 문제도 주문 건수가 증가하게 되면 최적해를 탐색하는 시간이 기하급수적으로 증가하는 NP-hard 문제이다. 때문에 현장에서 활용 가능한 3종류의 휴리스틱 알고리즘을 개발하였다. 다양한 실험을 통해서 개발한 알고리즘이 우수한 성능을 보여주고 있음을 확인하였다.
Abstract
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.
참고문헌 (18)
- 강성민, "복수순회외판원문제 경로분할모형의 최적화연구", 한국생산관리학회지, 19(2), pp.147~177 (2008), 한국생산관리학회[DOI]
- 강자영, "동일경로 제약을 갖는 집배송 차량 경로 수립 문제의최적화 해법", 대한산업공학회지, 33(1), pp.33~43 (2007), 대한산업공학회
- 고시근, "두 단계 이종병렬기계 시스템의 일정계획", 대한산업공학회지, 47(1), pp.1~10 (2021), 대한산업공학회[DOI]
- 김경근, "수익을 최대로 하는 픽업 및 배송문제의 세분화 타부서치 알고리즘 기법 연구", 한국경영과학회지, 46(4), pp.17~31 (2021), 한국경영과학회
- 김병목, "음식배달을 위한 동적 라우팅 해법 개발", 대한산업공학회 추계학술대회, 11, pp.2023~2309 (2014)
- 김승기, "군 수송기 운영 효율성 제고를 위한 최적경로 연구", 경영과학, 33(1), pp.89~99 (2016), 한국경영과학회[DOI]
- 김태훈, "음식배달 서비스 최적운영을 위한 시뮬레이션 기반 지식추출과 강화학습", 박사, pp.2018
- 박수홍, "외식 배달서비스 품질이 고객만족 및 인지된 감정, 재이용 의도에 미치는 영향", 유통경영학회지, 21(4), pp.5~13 (2018), 한국유통경영학회[DOI]
- 배진, "여행상품 인솔자 스케쥴링 문제에 대한 휴리스틱 알고리즘 연구", 한국생산관리학회지, 30(3), pp.251~266 (2019), 한국생산관리학회[DOI]
- 서병규, "지연비용을 고려한 서비스 시간대가 존재하는 외판원 문제에 대한 발견적 해법", 대한산업공학회, 27(1), pp.18~24 (2001)
- 서창적, "도로 및 지형적 환경의 변화에 따른 택배 서비스 배송 규칙(ETD Rule)의 적용", 한국생산관리학회지, 16(2), pp.81~99 (2005), 한국생산관리학회
- Dorling, K., "Vehicle Routing Problems for Drone Delivery", IEEE, 47(1), pp.70~85 (2017)
- Feillet, D., "Traveling salesman problems with profits", Transportation Science, 39(2), pp.188~205 (2005)
- Nanry, W. P., "Solving the Pickup and Delivery Problem with Time Windows Using Reactive Tabu Search", Transportation Research, Part B, 34, pp.107~121 (2000)
- Steever, Z., "Dynamic courier routing for a food delivery service", Computers and Operations Research, 107, pp.173~188 (2019)
- Sun, P., "The time-dependent capacitated profitable tour problem with time windows and precedence constraints", European Journal of Operational Research, 264(3), pp.1058~1073 (2018)
- Yang J., "Real-Time Multivehicle Tuckload pickup and delivery problems", Transportaion Science, Vol. 38, No, 2, pp.135~148 (2004)
- Zhang Y., "Route Prediction for Instant Delivery", Proc. ACM Interact. Mob. Wearable Ubiquitous Technol., 3, pp.124, 25~ (2019)