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

Authors: Jun Zhang; Xueyan Zhang; Yanfang Zhang
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

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 21+Qv-competitive, where Qv 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.


---

## Body

## 1. Introduction

The online-to-offline (O2O) supermarket e-commerce business model is currently very popular with middle-class consumers in China, such as Alibaba’s fresh [1] and JD’s 7fresh [2]. The online orders are picked up by pickers in the offline supermarket and then delivered by vehicles to customers within 30∼60 minutes. However, owing to the small lot-size, high-frequency, time-sensitive, and dynamic arrival of online customer orders, many O2O supermarkets face challenges in online order fulfillment [3]. Two key processes in the online order fulfillment are order picking and delivery, respectively. Thus, how to pick ordered products from the supermarket shelves and deliver them to customers within the lowest cost and shortest time are critical issues that need to be solved.In most O2O supermarkets, as online orders are small lot-size, the order batching method is used in an order picking process. It is an efficient method to group a set of orders into several subsets, i.e., batches, to minimize the maximum picking completion time [4]. To shorten the delivery completion time and provide better customer service, the delivery area of the O2O supermarket is usually divided into multiple communities (called zones in this paper) based on customers’ geographical locations, and each zone is served by several capacitated vehicles. The vehicles deliver the ordered products to the customers by the vehicle routing method to minimize the delivery completion time. To achieve more efficient online order fulfillment performance, 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). An online schedule should be generated to minimize both the maximum delivery completion time and the total delivery cost. The online IOPDP-MR can be defined using the five-field notation αβπδγ [5] as follows: Pmonline,B≤Qb,batchV∞,Qv,routingZDmax+TC.The value of the integrated schedule has been proven by Zhang et al. [6], Moons et al. [7], and Zhang et al. [3]. However, Moons et al. [7] studied the offline IOPDP with a vehicle routing delivery method; Zhang et al. [6] and Zhang et al. [3] studied the online IOPDP with no routing method. This paper closes the research gap by studying the online IOPDP with a vehicle routing delivery method. The contribution of this paper is embodied in three aspects. First, to be more realistic, we formulate the O2O supermarket order fulfillment problem into the online IOPDP-MR. Second, although Moons et al. [7] studied the offline IOPDP with a vehicle routing method, the vehicle routing method has not been studied in online environment of IOPDP. We close the research gap by studying the online IOPDP with a vehicle routing method. Third, to tackle the online IOPDP-MR, an online algorithm is proposed. The effectiveness and efficiency of the online algorithm are demonstrated by the competitive analysis and the numerical experiments. The results of this paper are as follows. An online algorithm, called A, is presented and proved to be 21+Qv-competitive. Since it is difficult to get a lower competitive ratio theoretically, the numerical experiments are conducted to further analyze the gaps between A and the offline optimal algorithm (A∗) under different situations. The experiments show that the competitive ratio is less than 2.5, and the average flow time per order, which is the time interval from the arrival time to the delivery completion time, is less than 30 minutes. Several managerial implications are also drawn from the experiments.The remainder of the paper is organized as follows. We first review some related literature in Section2. The online IOPDP-MR is formulated in Section 3, and the online algorithm A is proposed in Section 4. To further verify the effectiveness and efficiency of A, a series of experiments are presented and the results are discussed in Section 5. The paper concludes with a summary and directions for further work in Section 6.


## 2. Literature Review

The onlineIOPDP-MR has some similar features with the integrated production and delivery problem (IPDP). The order picking process in IOPDP-MR is a special production process in IPDP, and thus, IOPDP-MR and IPDP both contain the production process and the delivery process; IOPDP-MR can be classified into a special IPDP.The literature ofIPDP is vast. The comprehensive review can be seen in Chen [5]. In this paper, there are multiple pickers in the picking process, and thus, we only review the online IPDP with parallel-machine production environment. Table 1 provides an overview of the online IPDP articles with parallel-machine production environment. The production process, vehicle characteristics, delivery method, objective function, and competitive ratio are reviewed in Table 1 to distinguish those IPDP models. The production process includes direct process and batch process. The vehicle characteristics include the vehicle number and the vehicle capacity. The delivery method includes individual and immediate delivery (idd), batch delivery by direct shipping (direct), and batch delivery by routing (routing). The objective function includes two types: one type is the maximum delivery completion time (Dmax), and another is the sum of the maximum delivery completion time and the total delivery cost (Dmax+TC). For the online IPDP to minimize Dmax, Liu and Lu [8] studied the special IPDP with two parallel machines and direct production process. The 5+1/2-competitive online algorithm was proposed. They later expanded the problem to unbounded batch parallel-machine scheduling [9] and proposed an online algorithm with a competitive ratio of 1 + 2/m. Tian et al. [10] studied the unbounded drop-line batch machine scheduling problem and presented an online algorithm with a competitive ratio of 1 + αm. For the above three papers, the vehicle number and vehicle capacity were unlimited, and the delivery method is idd. For the online IPDP to minimize Dmax+TC, Han et al. [11] investigated different IPDPs with parallel machine in terms of the number of vehicles and the capacity of vehicles. The competitive ratios were different in different IPDPs. Zhang et al. [3] studied the online IOPDP, and the production process is a multiple picker bounded batch process, which is the same with our study. However, the delivery method was direct.Table 1
An overview of the online IPDP articles with parallel-machine production environment1.
LiteratureProduction processVehicleDeliveryObjectiveCompetitive ratioNumber of vehiclesVehicle capacityLiu and Lu [8]DirectUnlimitedUnlimitediddDmax5+1/2Liu and Lu [9]Batch unboundedUnlimitedUnlimitediddDmax1 + 2/mTian et al. [10]Drop-line batch unboundedUnlimitedUnlimitediddDmax1+αmHan et al. [11]DirectOneUnlimitedDirectDmax+TCmax5+1/2,1+D/D+TDirectUnlimitedUnlimitedDirectDmax+TCmax5+1/2,3/2+D/D+TDirectOneLimitedDirectDmax+TC2DirectUnlimitedLimitedDirectDmax+TC2Zhang et al. [3]Batch boundedUnlimitedLimitedDirectDmax+TC2This studyBatch boundedUnlimitedLimitedRoutingDmax+TC21+Qv1T: the round-trip delivery time; m: the number of machines; αm: the positive root of the equation α2+mα−1=0; Qv: vehicle capacity.In our study, therouting method is considered, which is more realistic but more complex to solve. The production process is multiple-picker bounded batch processing. The objective function is Dmax+TC. The 21+Qv-competitive online algorithm is provided to solve the online IOPDP-MR.We further discuss the literature ofIOPDP. As far as we know, only Zhang et al. [6] and Zhang et al. [3] studied the online IOPDP. In [6], the picking method is order batching with one picker, and delivery method was direct. In [3], they expanded the picking method to order batching with multiple pickers, but the delivery method was still direct. Moons et al. [7] studied the offline IOPDP with a routing method. Although the routing method was considered, the information of orders was known beforehand, and the batching method was not considered.In this study, more realistic factors in the delivery part are included, which makes the problem more complicated and harder to solve. To sum up, the onlineIOPDP-MR differs from the previous papers in the following three aspects. First, orders are batched based on the online order batching method with multiple pickers. Second, several zones need to be serviced by the routing delivery method. Third, there is enough capacitated vehicles for each zone. The combination of the three aspects above makes our paper unique in the literature.


## 3. Problem Description

The full process of the onlineIOPDP-MR is shown in Figure 1. First, the orders which arrive dynamically are batched and assigned to the pickers to process. Then, the completed orders which belong to the same zones are assigned to vehicles to deliver by the routing method. The full process can be separated into the picking process and the delivery process. The notations in Table 2 will be used throughout the paper.Figure 1
The full process of the online IOPDP-MR.Table 2
The notations used in this paper.
OSet of orders,i∈OBSet of batches,j∈BRlSet of delivery routes in zonel, rl∈RlZSet of zones,l∈ZQbCapacity of the picking deviceQvVehicle capacityDlFixed delivery cost of each route to zoneltrldDelivery time of routerl in zone lThe picking process can be described as follows. Orders that arrived are combined into batches and assigned to the pickers by the online order batching algorithm (see details in Section4). The picking process includes the following decision issues: (1) which orders should assign to the same batch; (2) when and in what sequences should the batches be processed; (3) which pickers should the batches assign to. In the delivery process, the completed orders are delivered to the customers by solving the online vehicle routing problem. There are two critical issues: (1) when the deliveries should depart from the supermarket; (2) which completed orders should be loaded in each delivery.The meanings of several terms about time in Figure1 are described as follows:(i)
The arrival time is the point in time when a customer order arrives in the order fulfillment system. It also means the time that the order is available to be picked.(ii)
The starting time is the point in time when the batch starts to be processed by the assigned picker.(iii)
The picking completion time is the point in time when the batch is completed picking. All orders in the same batch start and complete at the same time.(iv)
The service time of the batch is the time picker needs to traverse the supermarket to pick the items in the batch, which is composed of travel time, pick time, and setup time. The travel time of the batch is calculated by the S-shape strategy.(v)
The departure time of the order is the point in time when the vehicle which carries the order departs from the supermarket to deliver items.(vi)
The waiting time of the order is the time interval between the picking completion time and departure time.(vii)
The travel time of the order is the time needed to deliver the order from the supermarket to the customer location of the order. It is decided by both other orders’ locations in the same delivery route and their delivery sequences, which should be calculated by the specific vehicle routing solutions.(vii)
The delivery completion time is the point in time when the order is received by the customer.(ix)
The delivery time of the route (not shown in Figure1) is the time interval from the earliest picking completion time of orders in the route to the maximum delivery completion time of orders in the route. The delivery time of route rl is trld. Each route incurs a fixed delivery cost and a variable delivery cost. The fixed delivery cost of route rl to zone l is Dl, and the variable delivery cost of route rl to zone l is identified as the delivery time trld.The assumptions and constraints are as follows:(i)
Each customer places one item, and the size of each item is identical.(ii)
Each order can be assigned to one batch, and the capacity of each batch cannot exceedQb.(iii)
Each batch needs to be processed by one of the available pickers, and each picker can only serve one batch at a time.(iv)
The layout of the supermarket is shown in Figure2, which is similar to the setting in De Koster et al. [4] and Zhang et al. [3]. The picker starts from the depot on the leftmost aisle, retrieves items from the left and right side through the aisles, and returns to the depot to hand over the picked items as the last step. The picker can pick up several items in one tour with the help of the picking device.(v)
Once the picker starts a tour through the warehouse, the interruption of the picker and the rearrangement of the picking batch are not allowed.(vi)
In this paper, we focus on the study of the online order batching algorithm, and thus, the storage assignment storage is random storage.(vii)
For the picking route strategy, there is an optimal routine [12], which offers a fast solution time and the shortest distance route for the single block warehouse. However, optimal routes are often confusing in nature and may not work within the confines of an order picking operation [4]. In practice, the problem of order picking routing is usually solved by using heuristics. For example, the S-shape strategy [4, 13] is a well-known heuristic used in the literature, providing nonconfusing picking routes for pickers. In this study, the S-shape strategy is applied to optimize the picking route.(viii)
Each delivery route starts at the supermarket and terminates at the supermarket.(ix)
Each customer can be served by one delivery route, and the capacity of each route isQv.Using the five-field notationαβπδγ [5], we can define the online IOPDP-MR as follows:(1)Pmonline,B≤Qb,batchV∞,Qv,routingZw1Dmax+w2TC.Figure 2
The layout of the supermarket.Details of the five-field notation are presented in Table3.Table 3
The five-field notation.
αPicker configuration (we regard “picker” as “machine” in this field)Pm: orders are processed by m identical pickers.βRestrictions and constraints on order parametersOnline: orders arrive dynamically.B≤Qb,batch: orders are processed by batches and the capacity of the batch is no more than Qb.πVehicle configuration.V∞,Qv: unlimited vehicles available and each vehicle can service at most Qv customers.Routing: batch delivery with routing method, i.e., orders going to different customers can be delivered together in the same route (where vehicle routing is a part of the decision).δNumber of customersZ: the delivery area is separated into Z zones.γObjective functionw1,w2: the weights of the time-dependent function and cost-dependent function, respectively, where w1,w2>0.Dmax: the time-dependent function, that is, the maximum delivery completion time of all orders.TC: the cost-dependent function, that is, the total delivery cost, i.e., the sum of the fixed delivery cost (FC) and variable delivery cost (VC), where FC=∑l∈ZRl·Dl and VC=∑l∈Z∑rl∈Rltrld.


## 4. Online Algorithm Design

The algorithm framework is discussed in Section4.1 and the competitive analysis is proposed in Section 4.2.


### 4.1. Algorithm Framework

For the online order batching method with multiple pickers, Zhang et al. [3] proposed the online algorithm Apick, and the competitive ratio is 2. The objective is to minimize the maximum delivery completion time. The algorithms proposed an idea to start assign the batch j to the earliest available picker at time t once t≥1+θti′a+θti′s−tjs(t is the earliest available time among the pickers, batch j is the uncompleted batch with longest service time tjs, order i′ is the one with longest service time ti′s in batch j, and ti′a is the arrival time of order i′). The arrived orders are batched by applying the batching method C&W (ii) [14]. In this paper, we use the online algorithm Apick in Zhang et al. [3] to solve the order picking part.For the onlineIOPDP, Zhang et al. [6] proposed a 4-competitive online algorithm. In their study, there were also multiple zones, but the number of vehicles in each zone was one. The round-trip travel time from the warehouse to zone l was Tl, and the round-trip delivery cost from the warehouse to zone l was Dl. The delivery decision was triggered at the end of each specific time interval Tl (when T>1+θDl) or DlTl+Dl (when T≤1+θDl) and θ=5−1/2. Zhang et al. [3] proposed a 2-competitive online algorithm to solve the online IOPDP. The number of vehicles was unlimited, the vehicle capacity was Qv, and the round-trip delivery cost from the warehouse to customers was a constant. However, the delivery method was direct, and the travel time was not considered. The delivery decision was triggered by the condition that the number of completed undelivered orders was at least Qv.In this paper, there are some identical settings with Zhang et al. [3], such as the number of vehicles, the vehicle capacity, and the fixed delivery cost, but the delivery method and objective function are different. We consider the routing delivery method, which is more realistic and complex. The specific constraints are shown as follows:(i)
For the constraints in picking part, there arem identical pickers. The orders are generated into batches, and the capacity of each batch cannot exceed Qb. Each picker can process one batch at a time.(ii)
For the constraint in the delivery part, there areZ delivery zones, the number of vehicles in each zone is unlimited, and the vehicle capacity is Qv. The customer locations of the orders belonging to the same zone can be delivered together by the routing method. Each delivery to zone l contains a fixed delivery cost Dl and a variable delivery cost trld.The objective function contains the time-dependent function and the cost-dependent function. The time-dependent function is to minimize the maximum delivery completion time of all orders, that is,Dmax. The cost-dependent function is to minimize the total delivery cost, including the fixed and variable delivery costs, that is, TC=FC+VC. To minimize the fixed delivery cost, it is reasonable to trigger the delivery decision when the number of completed undelivered orders in zone l exceeds Qv. When the number of completed undelivered orders in zone l is less than Qv, it might be beneficial to delay the delivery to wait more orders, but the waiting time should not be too long. As we know, the variable delivery cost represents the time interval from the earliest picking completion time to the maximum delivery completion time. Waiting too long would increase the variable delivery cost. To minimize the variable delivery cost, therefore, we can set an upper limit of the delivery time for each route, that is, Dl. The details of the online algorithm A are shown as follows (Algorithm 1).Algorithm 1:A.
(1)
Picking part: schedule all arrived orders according to algorithmApick [3] regardless of which zones they belong to. The completed orders are assigned to the delivery part.(2)
Delivery part: for each zonel, the delivery decision is made once one of the following two situations happens: (1) the number of completed undelivered orders is Qv; (2) the delivery time of the route trld is larger than Dl, and the route rl contains all the completed undelivered orders in zone l. As there is only one route at every delivery decision point, the delivery route can be calculated by solving the travelling salesman problem (TSP) [15].


### 4.2. Competitive Analysis

Suppose algorithmA∗ is the offline optimal algorithm. The objective functions of A and A∗ are Z (A) and ZA∗, respectively. The time-dependent function value and the cost-dependent function value of A are Z1 (A) and Z2 (A), respectively. The time-dependent function value and the cost-dependent function value of A∗ are Z1A∗ and Z2A∗, respectively.Theorem 1.
The time-dependent value of Algorithm A is not greater than 3 times the one of AlgorithmA∗: z1A/z1A∗≤3.Proof of Theorem 1.
Cmax is the maximum picking completion time. As we know, (A)≤CmaxA∗. The detailed proof processes can be seen in [3]. tr′d is the delivery time of the last delivery route r′. We can get that Z1A=CmaxA+tr′d. As Z1A∗=CmaxA∗ and tr′d is generally much less than CmaxA∗, we have Z1A/Z1A∗≤3.Theorem 2.
The cost-dependent function value of Algorithm A is not greater than21+Qv times the one of Algorithm A∗:Z2A/Z2A∗≤21+Qv.Proof of Theorem 2.
Suppose that a delivery route is called saturated if it containsQv items; otherwise, it is called unsaturated. Let q1 be the number of routes to zone l in A∗ and qlsqlu be the number of saturated (unsaturated) deliveries to zone 1 in A. The fixed delivery costs in A and A∗ are ∑l∈zqls+qluand ∑l∈zqlDl, respectively. As the delivery time of each route in A is not greater than Dl, we have Z2A≤2∑l∈zqls+qluDl. We know Z2A∗>∑l∈zqlDl+∑l∈zTl∗, where Tl∗ is the minimum total travel time needed to service all customers orders with the capacitated vehicles in zone l. As Tl∗ is hard to quantify and compare with others, we set Z2A∗>∑l∈ZqlDl. As qlu≤qlQv and qls≤ql, we have(2)z2Az2A∗≤2∑l∈zqls+qluql≤21+Qv.Theorem 3.
ZA/ZA∗≤21+Qv.Proof of Theorem 3.
AsZ1A/Z1A∗≤3 and Z2A/Z2A∗≤21+Qv, we have(3)ZAZA∗=w1Z1A+w2Z2Aw1Z1A∗+w2Z2≤21+Qv.


## 4.1. Algorithm Framework

For the online order batching method with multiple pickers, Zhang et al. [3] proposed the online algorithm Apick, and the competitive ratio is 2. The objective is to minimize the maximum delivery completion time. The algorithms proposed an idea to start assign the batch j to the earliest available picker at time t once t≥1+θti′a+θti′s−tjs(t is the earliest available time among the pickers, batch j is the uncompleted batch with longest service time tjs, order i′ is the one with longest service time ti′s in batch j, and ti′a is the arrival time of order i′). The arrived orders are batched by applying the batching method C&W (ii) [14]. In this paper, we use the online algorithm Apick in Zhang et al. [3] to solve the order picking part.For the onlineIOPDP, Zhang et al. [6] proposed a 4-competitive online algorithm. In their study, there were also multiple zones, but the number of vehicles in each zone was one. The round-trip travel time from the warehouse to zone l was Tl, and the round-trip delivery cost from the warehouse to zone l was Dl. The delivery decision was triggered at the end of each specific time interval Tl (when T>1+θDl) or DlTl+Dl (when T≤1+θDl) and θ=5−1/2. Zhang et al. [3] proposed a 2-competitive online algorithm to solve the online IOPDP. The number of vehicles was unlimited, the vehicle capacity was Qv, and the round-trip delivery cost from the warehouse to customers was a constant. However, the delivery method was direct, and the travel time was not considered. The delivery decision was triggered by the condition that the number of completed undelivered orders was at least Qv.In this paper, there are some identical settings with Zhang et al. [3], such as the number of vehicles, the vehicle capacity, and the fixed delivery cost, but the delivery method and objective function are different. We consider the routing delivery method, which is more realistic and complex. The specific constraints are shown as follows:(i)
For the constraints in picking part, there arem identical pickers. The orders are generated into batches, and the capacity of each batch cannot exceed Qb. Each picker can process one batch at a time.(ii)
For the constraint in the delivery part, there areZ delivery zones, the number of vehicles in each zone is unlimited, and the vehicle capacity is Qv. The customer locations of the orders belonging to the same zone can be delivered together by the routing method. Each delivery to zone l contains a fixed delivery cost Dl and a variable delivery cost trld.The objective function contains the time-dependent function and the cost-dependent function. The time-dependent function is to minimize the maximum delivery completion time of all orders, that is,Dmax. The cost-dependent function is to minimize the total delivery cost, including the fixed and variable delivery costs, that is, TC=FC+VC. To minimize the fixed delivery cost, it is reasonable to trigger the delivery decision when the number of completed undelivered orders in zone l exceeds Qv. When the number of completed undelivered orders in zone l is less than Qv, it might be beneficial to delay the delivery to wait more orders, but the waiting time should not be too long. As we know, the variable delivery cost represents the time interval from the earliest picking completion time to the maximum delivery completion time. Waiting too long would increase the variable delivery cost. To minimize the variable delivery cost, therefore, we can set an upper limit of the delivery time for each route, that is, Dl. The details of the online algorithm A are shown as follows (Algorithm 1).Algorithm 1:A.
(1)
Picking part: schedule all arrived orders according to algorithmApick [3] regardless of which zones they belong to. The completed orders are assigned to the delivery part.(2)
Delivery part: for each zonel, the delivery decision is made once one of the following two situations happens: (1) the number of completed undelivered orders is Qv; (2) the delivery time of the route trld is larger than Dl, and the route rl contains all the completed undelivered orders in zone l. As there is only one route at every delivery decision point, the delivery route can be calculated by solving the travelling salesman problem (TSP) [15].


## 4.2. Competitive Analysis

Suppose algorithmA∗ is the offline optimal algorithm. The objective functions of A and A∗ are Z (A) and ZA∗, respectively. The time-dependent function value and the cost-dependent function value of A are Z1 (A) and Z2 (A), respectively. The time-dependent function value and the cost-dependent function value of A∗ are Z1A∗ and Z2A∗, respectively.Theorem 1.
The time-dependent value of Algorithm A is not greater than 3 times the one of AlgorithmA∗: z1A/z1A∗≤3.Proof of Theorem 1.
Cmax is the maximum picking completion time. As we know, (A)≤CmaxA∗. The detailed proof processes can be seen in [3]. tr′d is the delivery time of the last delivery route r′. We can get that Z1A=CmaxA+tr′d. As Z1A∗=CmaxA∗ and tr′d is generally much less than CmaxA∗, we have Z1A/Z1A∗≤3.Theorem 2.
The cost-dependent function value of Algorithm A is not greater than21+Qv times the one of Algorithm A∗:Z2A/Z2A∗≤21+Qv.Proof of Theorem 2.
Suppose that a delivery route is called saturated if it containsQv items; otherwise, it is called unsaturated. Let q1 be the number of routes to zone l in A∗ and qlsqlu be the number of saturated (unsaturated) deliveries to zone 1 in A. The fixed delivery costs in A and A∗ are ∑l∈zqls+qluand ∑l∈zqlDl, respectively. As the delivery time of each route in A is not greater than Dl, we have Z2A≤2∑l∈zqls+qluDl. We know Z2A∗>∑l∈zqlDl+∑l∈zTl∗, where Tl∗ is the minimum total travel time needed to service all customers orders with the capacitated vehicles in zone l. As Tl∗ is hard to quantify and compare with others, we set Z2A∗>∑l∈ZqlDl. As qlu≤qlQv and qls≤ql, we have(2)z2Az2A∗≤2∑l∈zqls+qluql≤21+Qv.Theorem 3.
ZA/ZA∗≤21+Qv.Proof of Theorem 3.
AsZ1A/Z1A∗≤3 and Z2A/Z2A∗≤21+Qv, we have(3)ZAZA∗=w1Z1A+w2Z2Aw1Z1A∗+w2Z2≤21+Qv.


## 5. Numerical Experiments

It seems possible that the competitive ratio 21+Qv of algorithm A can be reduced, but it is hard to get such a result by the method of competitive analysis. Thus, we present the numerical experiments to further analyze the gaps between Z (A) and Z (A∗) under different situations.The parameters of the O2O supermarket set in this paper, shown in Table4, are frequently used in the literature [3, 16]. The supermarket contains 1000 identical storage locations, and 100 storage locations are distributed on both sides of each aisle. Pickers retrieve items from the right and left side of each aisle simultaneously. The depot is on the entrance of the leftmost aisle, shown in Figure 2. The length of the aisle is 50 m, and the width between two adjacent aisles is 2 m. The service time includes the travel time, pickup time, and setup time. The picker’s travel speed is vtravel=48m/min, the pick-up speed is vpick=6item/min, and the setup time is tsetup=3min. The storage policy is random-based policy. The number of pickers is 3, the number of delivery zones is 4, and the batch capacity is Qb = 10. From Theorems 1 and 2, we can get Z1A∗≥tnarrive and Z2A∗>∑l∈zqlDl+∑l∈zTl∗. We set Z1A∗≥tnarrive and Z2A∗=∑l∈zqlDl+∑l∈zTl∗ in the experiments. Tl∗ can be calculated by solving the capacitated vehicle routing problem.Table 4
The parameters of the O2O supermarket.
ParameterValueNumber of aisles100Length of the aisle50Number of storage locations1000Length of each location1 mWidth between two adjacent aisles2 mPicker’s travel speed48 m/minPick-up speed6 item/minSetup time3 minStorage policyRandom-basedThe interarrival times (the time between the arrival of customer orderi with i + 1) are exponentially distributed with the arrival rate λ = 4. The total number of orders is n = 100. The x-coordinates and y-coordinates of the locations of the customers are randomly sampled from U (0, 5 km). The locations are not known in advance but become available when the orders arrive. The supermarket is located at the middle of the square, i.e., (2.5 km, 2.5 km), which separates the delivery zones into four parts, as shown in Figure 3. The average vehicle speed is 30 km/h. To calculate Tl∗ in Z2A∗ and trld in Z2A, the genetic algorithm (GA) is used to get the near-optimal route for each delivery. The initial population size is 100, the iteration number is 500, crossover ratio is 0.8, and mutation ratio is 0.4. Round Robin selection rule and the single point crossing rule are selected.Figure 3
Locations of four delivery zones and one supermarket.The values of the vehicle capacity and the fixed delivery cost are varied based on a survey of O2O supermarket in China.Qv is set to be 5, 6, 7, 8, 9, or 10, and Dl is set to be 5, 10, 15, 25, 30, or 35. By choosing different values of Qv and Dl, 36 (6∗6) problem classes are generated, and for each problem, 50 instances are calculated. We provide the average results of the 36 problem classes. The experiments are carried out on an Intel Core i7 Processor and 8.0 GB RAM. The algorithm is implemented with MATLAB R2016a.Table5 shows the detailed results of A and A∗ under 36 problem classes, which includes the number of deliveries in A (N (d) for short), Z1 (A), FC, VC, Z2 (A), the number of deliveries in A∗ (N (d)∗ for short), Z1 (A∗), FC∗, VC∗, Z2 (A∗), and ZA/ZA∗ (R for short). We can see that R ranges from 1.19 to 2.34. The smallest R occurs when Qv = 5 and D1 = 35, and the largest R occurs when Qv = 1 and D1 = 10. We can see that, with the increase in Dl, R decreases. It can be explained that, with the increase in Dl, more completed orders can be delivered in full batches, then N (d) decreases, and FC would be closer to FC∗. Moreover, when Dl is large enough, N (d) would be equal to N (d)∗. For example, when Qv=5,Dl=10, the number of deliveries is 43. When Dl increases to 25, the number of deliveries decreases to 21, which equals to the one of A∗. To sum up, the competitive ratio is less than 2.5, which verifies the good performance of algorithm A.Table 5
Detailed results ofA and A∗ under 36 problem classes.
ParametersANd∗A∗RNdZ1AFCVCZ2AZ1A∗FC∗VC∗Z2A∗Qv=5,Dl=104353.69430.00304.08734.082134.37210.00197.75407.751.78Qv=5,Dl=152855.21420.00345.32765.3234.37315.00197.75512.751.50Qv=5,Dl=202354.81460.00344.24804.2434.37420.00197.75617.751.32Qv=5,Dl=252156.05525.00365.26890.2634.37525.00197.75722.751.25Qv=5,Dl=302156.05630.00361.43991.4334.37630.00197.75827.751.22Qv=5,Dl=352156.05735.00361.361096.3634.37735.00197.75932.751.19Qv=6,Dl=104253.69420.00294.61714.611834.37180.00186.30366.301.92Qv=6,Dl=152555.21375.00299.32674.3234.37270.00186.30456.301.49Qv=6,Dl=202056.06400.00309.79709.7934.37360.00186.30546.301.32Qv=6,Dl=251955.26475.00340.09815.0934.37450.00186.30636.301.30Qv=6,Dl=301856.06540.00321.27861.2734.37540.00186.30726.301.21Qv=6,Dl=351856.06630.00318.13948.1334.37630.00186.30816.301.18Qv=7,Dl=104253.69420.00293.39713.391634.37160.00182.76342.762.03Qv=7,Dl=152455.21360.00292.42652.4234.37240.00182.76422.761.55Qv=7,Dl=202054.84400.00318.40718.4034.37320.00182.76502.761.44Qv=7,Dl=251756.06425.00314.49739.4934.37400.00182.76582.761.29Qv=7,Dl=301655.19480.00317.46797.4634.37480.00182.76662.761.22Qv=7,Dl=351655.19560.00322.63882.6334.37560.00182.76742.761.21Qv=8,Dl=104253.69420.00294.61768.301534.37150.00182.09332.092.10Qv=8,Dl=152455.21360.00298.34713.5534.37225.00182.09407.091.62Qv=8,Dl=202054.87400.00318.44773.3234.37300.00182.09482.091.50Qv=8,Dl=251655.19400.00317.03772.2334.37375.00182.09557.091.31Qv=8,Dl=301556.98450.00326.59833.5734.37450.00182.09632.091.25Qv=8,Dl=351556.11525.00333.84914.9534.37525.00182.09707.091.23Qv=9,Dl=104253.69420.00294.61714.611334.37130.00168.54298.542.31Qv=9,Dl=152455.21360.00292.42652.4234.37195.00168.54363.541.78Qv=9,Dl=201956.06380.00306.24686.2434.37260.00168.54428.541.60Qv=9,Dl=251555.17375.00312.33687.3334.37325.00168.54493.541.41Qv=9,Dl=301356.06390.00284.70674.7034.37390.00168.54558.541.23Qv=9,Dl=351356.05455.00298.49753.4934.37455.00168.54623.541.23Qv=10,Dl=104253.69420.00294.61714.611334.37120.00173.31293.312.34Qv=10,Dl=152455.21360.00292.42652.4234.37180.00173.31353.311.83Qv=10,Dl=201856.06360.00290.60650.6034.37240.00173.31413.311.58Qv=10,Dl=251555.35375.00310.77685.7734.37300.00173.31473.311.46Qv=10,Dl=301255.55360.00294.51654.5134.37360.00173.31533.311.25Qv=10,Dl=351255.55420.00303.14723.1434.37420.00173.31593.311.24Next, we will discuss the values of the objective function, and the weightsw1=w2=1. Figure 4 shows the development of the objective function (the total cost) under different Dl. We can see that, with the increase in Qv, the total cost decreases. It means that when Dl is unchanged, a larger vehicle capacity is better. We can also see that the descend range of the total cost decreases with the decrease in Dl. When Dl=10, the largest cost occurs when Qv=5. With the increase in Qv, the cost changes little (shown in purple line in Figure 4). It means that if the fixed delivery cost per route is very small, it has little benefit to increase the vehicle capacity.Figure 4
The development of objective function under differentDl.For the value ofZ1A, i.e., the maximum delivery completion time, we can see that the change is not obvious under different Qv and Dl. It is because that the maximum delivery completion time is related to the last delivery route of each zone, and in general, the last route contains fewer orders, which is not full loaded. Thus, the departure time of the last route is generally the picking completion time of the last order, which has less relationship with Qv and Dl in Algorithm 1.As we know, for O2O supermarket, another important performance is the average flow time per order, which is the time interval between the arrival time and the delivery completion time. Thus, we further analyze the average flow time under different situations. The results of average flow time under differentQv and Dl values are shown in Table 6. We can see that the average flow time ranges from about 18 to 26 minutes, which is an acceptable flow time for O2O supermarket. In general, with the increase in Qv and Dl, the average flow time increases. It is because that larger Qv and Dl will make the orders wait longer when the picking process is completed. When Dl is small (for example, 10∼25), the increase in Qv has little impact on the flow time. In contrast, when Dl is large (for example, 30∼35), the increase in Qv leads to a large increase in flow time.Table 6
The results of average flow time under differentQv and Dl.
DlQv56789101018.9118.8818.8818.8718.8818.881521.3821.1821.3921.3321.5321.312022.6422.8723.3123.2423.1623.712523.4023.9624.1524.7724.6624.613023.5223.7424.9925.2625.1526.143523.5223.8025.3025.5926.2126.80To sum up, the competitive ratio of Algorithm1 is less than 2.5, and the average flow time for customer orders is less than 30 minutes, which verifies a good performance on both the computation efficiency and the customer satisfaction of Algorithm 1.


## 6. Conclusions

This paper is inspired by the online order fulfillment in O2O supermarket, which included two key processes: order picking and delivery. The order picking process is the online order batching problem with multiple pickers, and the delivery process is the capacitated vehicle routing problem. To provide an efficient online order fulfillment solution, we integrate the order picking process and the delivery process and formulate the joint problem as the onlineIOPDP-MR. The objective function is to minimize the maximum delivery completion time and the total delivery cost. We propose the online Algorithm 1, and the competitive ratio is proved to be 2Qv+1. As it is hard to get a lower competitive ratio theoretically, the numerical experiments are conducted to analyze the gaps between ZA and ZA∗ under different situations.The main contributions of this study are as follows: (1) modelling a specificIPDP, which is the online IOPDP-MR for O2O supermarket; (2) proposing a 2Qv+1-competitive algorithm to solve the online IOPDP-MR; and (3) the competitive ratio is less than 2.5 in the experiments, which implies a good computation efficiency of Algorithm 1. Meanwhile, several managerial suggestions can be concluded when implementing algorithm A. (1) Larger delivery cost per route generally leads to a larger total cost. (2) If the fixed delivery cost per route is very small, the change in the vehicle capacity is unnecessary to decrease the total cost. (3) If the delivery cost per route is high, the increase in vehicle capacity can effectively reduce the total cost. However, for customers, the flow time increases, which may reduce their satisfaction.There are some limitations of this paper. The competitive ratio is proven to be2Qv+1, which is not smaller enough. Further research will focus on investigating the best possible competitive ratio for algorithm A. Moreover, the delivery route is calculated by the general GA, and the time window of the customers is not considered. We will further improve the study by proposing the improved heuristic algorithm to solve the capacitated VRP with time window. We are also interested in investigating the order picking and delivery problem under a multitemperature transportation modal.



---

*Source: 6673079-2021-01-19.xml*