A Study on Online Scheduling Problem of Integrated Order Picking and Delivery with Multizone Vehicle Routing Method for Online-to-Offline Supermarket

The online order fulfillment of online-to-offline (O2O) supermarket faces the challenge in how to pick orders from thousands of products on the supermarket shelves and deliver them to customers in different zones and locations by a vehicle routing method within the lowest cost and shortest time. It is critical to integrate the order picking and delivery processes and schedule them jointly with a coordinated manner. Thus, in this paper, we study the online integrated order picking and delivery problem with multizone routing method (IOPDP-MR) to minimize both the maximum delivery completion time and the total delivery cost. The online algorithm A is presented to solve the online problem and is proved to be $2\left(1+Q_v\right)$ -competitive, where $Q_v$ is the vehicle capacity. Since it is difficult to get a lower competitive ratio theoretically, the numerical experiments are proposed to analyze the gaps by comparing the values of algorithm A with the ones of offline optimal algorithm A∗ under different situations. It can be inferred that the competitive ratio is less than 2.5 and the average flow time for customer orders is less than 30 minutes, which verifies the good performance in both computation efficiency and customer satisfaction of algorithm A.