음식 배달 산업에서의 수거 및 배송 문제를 위한 대기 전략

Abstract

This study deals with the Dynamic Pickup and Delivery Problem with Time Windows (Dynamic PDPTW) in the food delivery agency industry, in which pickup and delivery pair orders are created dynamically and given fleet of vehicles need to fulfil those orders efficiently. The Dynamic PDPTW is a generalization of the Vehicle Routing Problem (VRP) and is thus NP-hard. The problem in the food delivery agency industry has not been studied in the open literature. The primary objective of the problem is to minimize the delay at pickup and delivery locations and the second is to maximize the completed number of orders. To reflect the real issue of food delivery agency industry, the balance between the cumulative numbers of completed orders of vehicles is also considered as the third objective. To solve the problem quickly, this study exploits the cheapest insertion heuristic as a construction algorithm and 2-opt algorithm as an improvement algorithm. Computational experiments show that the proposed approach can generate better solutions compared with the manual approach of a real company. Furthermore, in order to handle the dynamics of the problem more efficiently, this study tests three existing waiting strategies (drive-first, wait-first, and stochastic-wait), and one newly proposed waiting strategy (virtual-location-wait). The latter two exploit historical data. Computational experiments demonstrate the excellence of the virtual-location-wait strategy.