<figure><img src="image_1.png" /></figure>

HAL
open science

# Research on the O2O Takeout Orders Merger and Routing Optimization

Wenjie Wang, Xue Xia, Lei Xie, Li Jiang, Yangyun Song

► To cite this version:

Wenjie Wang, Xue Xia, Lei Xie, Li Jiang, Yangyun Song. Research on the O2O Takeout Orders Merger and Routing Optimization. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2021, Nantes, France. pp.290-298, 10.1007/978-3-030-85906-0_33 hal-04022133

HAL Id: hal-04022133

https://inria.hal.science/hal-04022133

Submitted on 9 Mar 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_3.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
# Research on the O2O Takeout Orders Merger and Routing Optimization*

Wenjie Wang, Xue Xia, Lei Xie, Li Jiang, and Yangyun Song

Glorious Sun School of Business and Management, Donghua University, Shanghai,
200051, China
wenjiew@dhu.edu.cn

**Abstract.** Delivery service of O2O takeout platforms requests the high timeliness, which frequently results in explosive orders during peak period. Because the order must be completed delivery during committed service time, the orders merger and delivery routing optimization are essential to O2O takeout delivery service. Taking into consideration the amount of the different order locations, this paper studies the order delivery with the closest pickup distance principle in O2O takeout platform. Firstly, we use the K-means algorithm to cluster and merge the orders. Secondly, due to the strictly time constraints of real-time order, we propose the delivery routing optimization model of order cluster with soft time window, and which can be solved with simulated annealing algorithm. Finally, using the actual delivery data of O2O takeout platform, we further demonstrate the orders merger and delivery routing optimization mode we proposed with Python.

**Keywords:** O2O takeout real time delivery · Cluster analysis · Soft time window · Delivery routing optimization · Simulated annealing algorithm.

## 1 Introduction

Motivated by Internet and e-commerce, O2O (Online To Offline) takeout delivery platform has shaped a new service mode of takeout ordering and delivery, which influences consumers' eating habits. By the end of 2018, there are 358 million users choosing O2O takeout platform of China, after that, the development of takeout delivery has entered a stable growth period [1]. Meanwhile, the timeliness becomes a large challenge with the accelerating social pace. Furthermore, O2O takeout platform usually faces the huge orders issue in peak period. For example, during peak period of Eleme takeout delivery platform, the quantity of real-time orders per second can reach 20000. Also, different from the traditional commodity logistics delivery network, there not exists the fixed delivery center in O2O takeout delivery platform, it means that the pickup and delivery location of each takeout order are generally non-fixing [2]. Because of the huge orders

* Supported by the key project of the National Natural Science Foundation of China (Grant No. 71832001) and project of the National Natural Science Foundation of China (Grant No. 71872038).
quantity in peak period and the non-fixed location of the pickup and delivery in O2O takeout platform, they bring great challenge to the delivery service optimization. Thus, this paper studies the delivery routing optimization problem (VRP) in O2O platform, based on the orders merger in peak and the non-fixed pickup and delivery location, aiming at reducing the order delivery time. The study has vital theoretical significance and practical value for the service management optimization of O2O takeout delivery platform.

The traditional logistics delivery vehicle routing problem (VRP) mainly studies the fixed delivery center location, which is not suitable for the real-time routing optimization problem of the O2O takeout delivery platform, due to its different delivery locations. For example, Clarke et al. [3]develop an iterative procedure that enables the rapid selection of an optimum or near-optimum route to find the optimum routing of a fleet of trucks of varying capacities from a central depot to a number of delivery points. Thus, on the basis of the related research, this paper adopts cluster analysis to merge orders of O2O takeout delivery platform, purposes to reduce the time cost of pickup orders under large orders quantity and different delivery locations in real-time delivery.

Delivery problem is noteworthy in the study, and many scholars have done a lot of research on this issue. Reference to reducing the time cost, Liu et al. [4]first propose a Crowdsourcing Dynamic Congestion Model, using the congestion model, he develop efficient algorithms for non-myopic adaptive routing to minimize the collective travel time of all vehicles in the entire transportation system. Dantzig et al. [5]find a way to assign stations to trucks in such a manner that station demands are satisfied and total mileage covered by the fleet is a minimum. Taking into account the multi-pickup and delivery problem with time windows, Naccache et al. [6]solve the problem exactly via branch-and-bound and heuristically developing a hybrid adaptive large neighborhood search with improvement operations. Muñoz-Carpintero et al. [7]present a methodology based on generic evolutionary algorithms to solve a dynamic pickup and delivery problem formulated under a hybrid predictive control approach, which consider different configurations of particle swarm optimization and genetic algorithms. Considering a family of time-dependent pickup and delivery problems with time windows, Sun et al. [8]propose an exact solution approach for solving problems from this family that is based upon branch and price. To achieve the global optimal order fulfillment performance, Zhang et al. [9]study the online integrated order picking and delivery problem for an O2O community supermarket, and the online algorithm A is established. Cherkesly et al. [10]propose models and algorithms for the pickup and delivery vehicle routing problem with time windows and multiple stacks, that is, two different branch-price-and-cut algorithms.

Taking into account the high timeliness of O2O takeout delivery platform, we establish the delivery routing optimization model of orders cluster and merger orders with soft time window, aiming at reduce the time cost of O2O takeout orders. Furthermore, considering the complexity of NP-hard vehicle routing optimization model and the high timeliness requirement of O2O takeout delivery platform, we solve the model via simulated annealing algorithm. Finally, us-
ing the actual delivery data of O2O takeout platform, we simulate the delivery routing optimization model with clustering and merging orders.

# 2 Modelling

## 2.1 Problem Description

O2O takeout platform based on the Internet accepts the customer's takeout order at any time, and distributes the order to deliverer in time. The distribution area of deliverer is generally within a few kilometers. Different from the traditional commodity logistics distribution network, O2O takeout distribution problems generally have the following characteristics: 1) takeout order distribution is mostly takeout food, beverage and other fresh and perishable goods, which timeliness is very strong, the delivery time is very high, takeout delivery must be delivered immediately within the prescribed time window. 2) O2O takeout orders have obvious peak period, peak order burst, takeout platform needs to merge orders reasonably, with limited capacity to meet the timely delivery of a large population of orders. 3) O2O takeout delivery often does not have a fixed distribution center, each O2O takeout order delivery location is generally different, O2O takeout deliverer needs to pickup goods in different delivery locations, and then give them to customers in different delivery locations. After completing an order delivery task, the deliverer goes directly to the next order cluster.

<figure><img src="image_4.png" /><figcaption>**Fig. 1.** A schematic diagram of the delivery O2O takeout order clustering and distribution process.</figcaption></figure>

Aimed at the characteristics of high timeliness of O2O takeout order and different location of distribution, based on clustering analysis and vehicle route optimization theory, this paper studies the cluster merging of O2O takeout peak explosive orders and the optimization of O2O takeout distribution route with soft
time window. O2O takeout order clustering and distribution process is shown in Fig. 1. During the O2O takeout peak burst period, the takeout order is clustered and distributed. Then the combined order cluster is assigned to deliverer who is currently idle and close to the takeout order cluster. After receiving the order, according to the optimized route provided by the O2O takeout platform, multiple takeout orders in the order cluster are delivered to each customer on time. The specific delivery time window requirement for each O2O delivery order is $[E_i, F_i]$, $E_i$ of which, express the earliest delivery time and $F_i$ express the latest delivery time required for orders, delivery orders in advance or overtime will cause O2O takeout platform to produce a certain time penalty cost. As shown in Fig. 1, after picking up the goods at the order cluster 1, the delivery order is delivered to the customer 1 on time according to the optimized distribution route provided by the platform, then the customer 2, finally the customer 3. After completing the delivery of all customer orders in order cluster 1 on time, according to the assignment of the platform, the deliverer directly starts the new distribution task in order cluster 2.

## 2.2 Order Cluster Distribution Routing Optimization Model

O2O takeout instant delivery service has strict delivery time requirements, take-out orders must be delivered in accordance with the promised delivery time. Therefore, considering that O2O delivery order is not delivered on time will have a certain penalty cost, for the takeout customer time window constraints $[E_i, F_i]$, the distribution routing optimization model of takeout order merging cluster with soft time window is established. When establishing the model, we also consider the constraints of delivery point location of each takeout order and deliverer ability, optimize the distribution order of multiple orders in the order cluster after the takeout order is merged, and generate the optimal delivery route of the order cluster.

The number of orders contained in each order cluster after O2O takeout order clustering is *m*, regardless of the mileage limit of the takeout deliverer, assuming that the maximum delivery capacity $Q^r$ by the takeout deliverer is *r*, the average delivery speed is *v*. The important time node of the instant delivery process of O2O takeout is shown in Fig. 2. After receiving the delivery task assigned by the platform, the deliverer starts with timing from its location, the time requires to arrive at the designated order cluster is recorded as $t_w$, the pickup time for each delivery order is $t_q$. $t_{ij}^r$ represents the delivery time required from the delivery location of the order *i* in the order cluster to the delivery location of the order *j* by deliverer *r*. In particular, $t_{01}^r$ represents the time required from the center of the order cluster to the delivery location of the first order. The production time of takeout goods is short, and the merchants can use the time that deliverers drive to the order cluster to prepare the meal. In this study, the time that deliverer waiting for the merchant to prepare the meal is ignored. After the takeout deliverer arrives at the customer's location and needs to wait for the customer to confirm the goods, then the order delivery process will finally end. The time $t_s$ for the customer service is set up by the deliverer. Take an order as
an example, The delivery completion time $T_{0i}^r$ is equal to the sum of the time $t_w$ taken by the takeout deliverer to the pickup location, order cluster pickup time $mt_q$, delivery time $t_{ij}^r$, customer service time $t_s$. The unit time cost factor of the distribution process is $u_{ij}$. The soft time window indicates that if the requirement of time window $[E_i, F_i]$ is not satisfied by the delivery completion time of the order $i$, it will incur a penalty cost. Earlier than the earliest delivery time $E_i$, the corresponding waiting cost coefficient is $\lambda_1$, later than the latest delivery time $F_i$, the corresponding penalty cost coefficient is $\lambda_2$. At the same time, the decision variable $x_{ij}^r$ is introduced to indicate that when the takeout deliverer $r$ from the delivery location $i$ to the delivery location $j$, the value is 1, otherwise the value is 0. The decision variable $z_m^r$ indicates that when the takeout order $i$ assigned to the deliverer $r$, value is 1, otherwise the value is 0.

Since there is no fixed distribution center for O2O takeout distribution, the constraint of returning the distribution vehicle to the distribution center is not considered when establishing the order cluster distribution routing optimization model with O2O takeout order clustering with soft time window. Taking minimizing the total delivery time cost of O2O takeout platform as the objective function $f$, the mathematical model of order cluster distribution routing optimization combined with O2O takeout order clustering with soft time window is shown below.

Objective function:

$$f = \min \left\{ \sum_{i,j=1}^{n} u_{ij} T_{0i}^r x_{ij}^r + \lambda_1 \sum_{i,j=1}^{n} \sum_{r=1}^{R} x_{ij}^r \max(E_i - T_{0i}^r, 0) \right. \\ \left. + \lambda_2 \sum_{i,j=1}^{n} \sum_{r=1}^{R} x_{ij}^r \max(T_{0i}^r - F_i, 0) \right\} \quad (1)$$

Constraints:

$$m \le Q^r, \forall r \in R, m = 1, 2, 3... \quad (2)$$

$$T_{0i}^r = t_w + mt_q + t_{0(i-1)}^r + t_{(i-1)i}^r + t_s, m = 1, 2, 3..., i = 1, 2, 3... \quad (3)$$

$$\sum_{r=1}^{R} z_{m}^{r} = 1, \forall r \in R, m = 1, 2, 3... \quad (4)$$

$$\sum_{i=1}^{m} x_{ij}^{r} = \sum_{i=1}^{m} x_{ji}^{r}, \forall r \in R, j = 1, 2, 3... \quad (5)$$

$$\sum_{i=1}^{m} x_{ij}^{r} = 1, \forall r \in R, j = 1, 2, 3... \quad (6)$$

$$\sum_{j=1}^{m} x_{ij}^{r} = 1, \forall r \in R, i = 1, 2, 3... \quad (7)$$

$$x_{ij}^{r} = \{0, 1\}, \forall r \in R, i = 1, 2, 3..., j = 1, 2, 3... \quad (8)$$

$$z_{m}^{r} = \{0, 1\}, \forall r \in R, m = 1, 2, 3... \quad (9)$$
The objective function f in the model is the total delivery time cost of the O2O delivery platform (the first item is the delivery process time cost, the second is the waiting cost when earlier than the earliest delivery time, the third is the penalty cost when later than the latest delivery time) minimize, Constraint (2) indicates that the number of orders in the order cluster after the merger of the takeout order does not exceed the ability constraint of the takeout deliverer, Constraint (3) indicates the delivery arrival time of the delivery order i, that is, the time taken by the deliverer to pick up the goods, the time of delivery and customer service, Constraint (4) ensures that each order is assigned to only one deliverer, to avoid duplicate assignments, Constraint (5) requires the O2O takeout deliverer to leave for the next delivery location after arriving at one delivery location, Constraints (6), (7) indicate that the deliverer must visit each delivery location once during delivery, and only once to the delivery location, Constraints (8), (9) are the range of values of the introduced decision variables.

## 2.3 Orders Merger Based on K-means Algorithm

In addition, as a result of O2O takeout platform in the urgent time window, on time, efficient, low-cost to complete a large population of orders instant delivery, is not easy. High order quantity and different delivery positions of different orders bring great complexity to O2O delivery problem. The deliverer needs to go to different pickup locations of different orders to pick up goods. If the different pickup locations of different orders assigned to the deliverer are far apart, it will obviously bring inconvenience to the deliverer, make takeout delivery instant difficult to meet, and increase delivery time cost. Therefore, this paper uses clustering analysis algorithm to combine a large population of orders to be delivered according to the principle of similar location of O2O takeout orders, so as to save the time cost of O2O takeout platform. The parameter $a_i$ expresses the pickup location of takeout order i, such as $a_1, a_2, a_3$, as the locations of order 1, order 2, order 3, are close, these three orders can be grouped into a class of combined distribution. The pickup location $a_4, a_5$ of delivery order 4, order 5 are close, these two orders also can be grouped into a class of combined distribution. The pickup locations $a_6, a_7, a_8, a_9$, of delivery order 6, order 7, order 8, order 9 have close distance, the four orders are clustered into a class of combined distribution.

Taking into account the characteristics of the real-time delivery process of O2O takeout orders and the different order locations, the K-means algorithm is used to cluster and merge O2O takeout orders. K-means algorithm is a dynamic fast clustering method, which can combine order clustering into K clustering centers according to the minimum distance criterion. The objective function of merging O2O takeout order cluster is D, which means the minimum sum of the distance from the order cluster $c_k$ to the center of the order cluster $p_k$, that is

$$ \min D = \left\{ \sum_{k=1}^{K} \sum_{i \in c_k} d(a_i, p_k) \right\} \qquad (10) $$
<figure><img src="image_5.png" /><figcaption>**Fig. 2.** Clustering and merging delivery orders according to the principle of close location.</figcaption></figure>

After processing the merger and allocation of orders based on the K-means algorithm, then we got order clusters $R$, and deliverer $r$ who is in charge of a designated order cluster. Based on these order clusters, algorithm is applied to the next order routing planning.

## 3 SA Algorithm and Simulation

Immediacy of O2O takeout distribution requires that the optimal route solving process must be fast and efficient. In this paper, aiming at the NP-hard characteristics of routing optimization problems, simulated annealing algorithm (Simulated Annealing, SA) is used to solve the mathematical model of O2O takeout clustering and order cluster distribution route optimization. Analog annealing algorithm is a random optimization algorithm based on Monte-Carlo iterative solution strategy, it has the characteristics of small influence of initial solution and strong global optimization ability.

Using python language programming to simulate the order cluster distribution optimization model of O2O takeout order clustering and merging, and we select 30 orders to be delivered at a certain time in a certain takeout platform. Takeout delivery time-consuming $t_w$ from current location of the deliverer $r$ to the designated order cluster, the average pickup time of each order in the order cluster is $t_q=2$min, average customer service time $t_s=2$min, average delivery speed $v=10$km/h, unit time delivery cost for delivery $u_{ij}=1$, the penalty coefficient that does not meet the distribution time window $\lambda_1=2$, $\lambda_2=3$. Test data including pickup location for 30 orders $a_i$, corresponding delivery location $b_i$, $2D$
coordinates are used to the location $a_i(x_i, y_i)$, $b_i(x_i, y_i)$. Earliest delivery time ($E_i$) of orders, latest delivery time ($F_i$), the distance between any two points is calculated by Euclidean distance.

Combined with the requirement of high timeliness and the scale of example of O2O delivery, the initial temperature of the simulated annealing algorithm is set to $T_0=1000$, termination temperature $T_{end}=0.01$, the temperature attenuation rate $q=0.9$, and the maximum number of iterations at the current temperature, that is, metropolis chain length $L=100$. The simulated annealing algorithm is used to obtain the optimal solution of the five order cluster distribution routes of O2O takeout orders clustering and merging as shown in Table 1.

<table><caption>**Table 1.** Cluster route solution for delivery order.</caption><thead><tr><td>Order clusters</td><td>Delivery orders in order clusters</td><td>Optimized delivery route</td></tr></thead><tbody><tr><td>c<sub>1</sub></td><td>1, 10, 21, 22, 23, 24, 28, 29</td><td>10-24-22-1-23-21-29-28</td></tr><tr><td>c<sub>2</sub></td><td>4, 6, 7, 14, 15, 27</td><td>15-4-6-7-27-14</td></tr><tr><td>c<sub>3</sub></td><td>2, 3, 5, 12, 13, 20, 25, 30</td><td>5-13-12-25-20-3-2-30</td></tr><tr><td>c<sub>4</sub></td><td>9, 11, 17, 19</td><td>9-19-17-11</td></tr><tr><td>c<sub>5</sub></td><td>8, 16, 18, 26</td><td>8-16-18-26</td></tr></tbody></table>

According to the actual delivery time of each order in the order cluster, each order can be delivered in the specified time window, minimizing the total delivery time cost while ensuring the delivery order delivered on time, verified the feasibility and effectiveness of the order cluster distribution route optimization scheme based on O2O takeout order pickup location clustering and merging.

On the whole, the reasonable cluster and distribution of orders in the process of O2O takeout delivery can ensure that O2O takeout platform can meet the demand of a large population of orders and the demand of customer's delivery limitation with lower total delivery cost. Significantly, it improves the delivery efficiency of O2O delivery platform peak delivery order.

## 4 Conclusion

The time requirement of O2O takeout delivery service is strict, especially in the peak period of takeout order exploding, the order distribution can be completed quickly and on time, which can improve the customer satisfaction of takeout delivery service and improve the income of O2O takeout platform. To meet the immediate requirements of O2O takeout delivery and the situation of peak order explosion, the K-means clustering analysis method is used to cluster and merge the O2O takeout delivery orders according to the principle of similar location, in order to reduce the time cost of takeout delivery. The order cluster distribution routing optimization model of O2O takeout clustering with soft time window is further established, and the simulated annealing algorithm is used to solve the
model to optimize the O2O delivery time cost. Numerical simulation results show
that under the condition of meeting the constraints of delivery time window, the
optimization effect of order cluster distribution route is ideal, which can ensure
the immediate delivery of each order in the order cluster.

In the cluster analysis of O2O takeout orders, this paper mainly clusters and
single according to the principle of similar location of delivery orders. Since the
delivery locations of O2O takeout delivery orders are different, in the future
research, we can consider the clustering and merging of orders and delivery
locations at the same time to further improve the immediacy and punctuality
of O2O takeout delivery, and reduce the total delivery time cost of the takeout
platform. Moreover, for the real-time requirement of delivery scheduling of O2O
takeout platform, designing fast heuristic algorithm will also be the research
direction of operation optimization of O2O takeout platform.

References

1. Chinese online takeout industry development report 2018-2019, https://www.iimedia.cn/c400/64223.html. Last accessed 4 Mar 2021

2. He, Z., Han, G., Cheng, T. C. E., Fan, B., Dong, J.: Evolutionary food quality and location strategies for restaurants in competitive online-to-offline food ordering and delivery markets: an agent-based approach. International Journal of Production Economics **215**, 67–72 (2019)

3. Clarke, G., Wright, J. W.: Scheduling of vehicles from a central depot to a number of delivery points. Operations Research **12**(4), 568–581 (1964)

4. Liu, S., Qu, Q.: Dynamic collective routing using crowdsourcing data. Transportation Research Part B: Methodological **93**, 450–469 (2016)

5. Dantzig, G. B., Ramser, J. H.: The truck dispatching problem. Management Science **5**(1), 80–91 (1959)

6. Naccache, S., Côté, J., Coelho, L. C.: The multi-pickup and delivery problem with time windows. European Journal of Operational Research **269**(1), 353–362 (2018)

7. Muñoz-Carpintero, D., Sáez, D., Cortés, C. E., Núñez, A.: A methodology based on evolutionary algorithms to solve a dynamic pickup and delivery problem under a hybrid predictive control approach. Transportation Science **49**(2), 239–253 (2015)

8. Sun, P., Veelenturf, L. P., Hewitt, M., Van Woensel, T.: The time-dependent pickup and delivery problem with time windows. Transportation Research Part B: Methodological **116**, 1–24 (2018)

9. Zhang, J., Liu, F., Tang, J., Li, Y.: The online integrated order picking and de-ivery considering pickers' learning effects for an O2O community supermarket. Transportation Research Part E: Logistics and Transportation Review **123**, 180–199 (2019)

10. Cherkesly, M., Desaulniers, G., Irnich, S., Laporte, G.: Branch-price-and-cut algo-rithms for the pickup and delivery problem with time win-dows and multiple stacks. European Journal of Operational Research **250**(3), 782–793 (2015)