# Research on Coordination and Optimization of Order Allocation and Delivery Route Planning in Take-Out System

Authors: Guofeng Sun; Zhiqiang Tian; Renhua Liu; Yun Jing; Yawen Ma
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

This paper studies the take-out route delivery problem (TRDP) with order allocation and unilateral soft time window constraints. The TRDP considers the order allocation and delivery route optimization in the delivery service process. The TRDP is a challenging version of vehicle routing problem. In order to solve this problem, this paper aims to minimize the total cost of delivery, builds an optimization model of this problem by using cumulative time, and adds time dimension in order allocation and path optimization dimensions. It can not only track the real-time location of delivery personnel but also record the delivery personnel to perform a certain task. The main algorithm is the dynamic allocation algorithm designed from the perspective of dispatch efficiency, and the subalgorithm is the improved genetic algorithm. Finally, some experiments are designed to verify the effectiveness of the established model and the designed algorithm, the order allocation and route optimization are calculated with/without the consideration of traffic jam, and the results show that the algorithm can generate better solution in each scene.


---

## Body

## 1. Introduction

At present, the take-out market in China continues to develop at an extraordinary speed, and the take-out platforms are competing in all aspects, such as high-quality supply and delivery experience. The COVID-19 has begun to erupt in all parts of the world and is spreading rapidly since the end of 2019. China, as one of the countries affected earlier by the epidemic, has adopted the measures of home quarantine during the fight against epidemic diseases, which plays a vital role in overcoming the epidemic. During the period of home quarantine, a large number of purchase and distribution of life materials and medicines were completed through the take-out. The mode of sale and delivery provides certain material support for residents, effectively alleviates the risk of infection of residents going out, and makes the best effect of blockade (isolation at home). It has been proved to be effective by practice in China to use a large number of daily necessities delivered by take-out staff to urban and rural residents during the epidemic period, which is worthy of reference for other countries that are affected by the epidemic and intend to adopt blockade (home isolation). Therefore, it is of great significance to research and apply the order (food, medicine, and other daily necessities) delivered by take-out staff.Delivery timeliness and on-time rate, as important indicators of take-out delivery, are the core competitiveness of the delivery platform. Generally speaking, the most direct way to improve the delivery efficiency and punctuality rate of users is to equip more delivery personnel and expand the scale of transportation capacity. However, it also means the increase of distribution cost. Therefore, on the one hand, the delivery platform should pursue a good delivery experience; on the other hand, it is constrained by the human cost of distribution. How to improve the delivery rules, optimize the delivery route, and reduce the delivery cost while improving customer satisfaction has become a hot issue. In the current delivery problem, depending on the experience of delivery personnel to choose the delivery order and delivery path is easy to cause secondary delivery, which not only reduces the delivery efficiency but also increases the delivery cost and customer dissatisfaction, and less consideration is given to the real-time distribution of delivery orders. Therefore, how to improve the delivery efficiency and customer satisfaction is very important for delivery companies, businesses, and customers.In recent years, the issue of food delivery has become a hot topic of research. Li et al. [1] studied the task assignment and scheduling of food delivery from the perspective of game theory, aiming at maximizing the income of the dispatcher; Harman [2, 3] researched and developed the take-out order automatic management system, which realizes the interaction between customers and merchants through the order system and provides customers with the additional sales option service during the ordering process; Liu et al. [4, 5], using the spatial crowdsourcing technology, constructed the urban food distribution network and platform, and a new way to support delivery by taxi is studied. The optimization goal is to reduce the number of delivery by taxi, so as to ensure a higher income for the drivers participating in the delivery. The simulated annealing algorithm is designed for optimization, and the experiment has achieved good results in Chengdu, China. Liao et al. [6] proposed a multiobjective scheduling model for order combination and delivery path optimization in the process of meal delivery, in order to maximize customer satisfaction and balanced utilization of dispatchers in the region, and designed a two-stage solution algorithm composed of nondominated sorting genetic algorithm II (NSGA-II) and adaptive large neighbourhood search (ALNs). Jiang et al. [7] designed a dispatch system based on big data of take out logistics. The system can optimize the number of regional dispatchers, improve the efficiency and income of dispatchers, and increase customer satisfaction. The routing optimization problem in take-out delivery problem can be regarded as a variant of Vehicle Routing Problem (VRP). The general vehicle routing problem (VRP) refers to a certain number of customers with different quantity of cargo demand. The distribution center provides cargo to customers, and a fleet is responsible for distributing cargo and organizing proper driving route, the goal is to make the customer’s needs to be met, and under certain constraints, to achieve goals such as the shortest distance, the least cost, and the shortest time-consuming [7]. However, there is no delivery center for take-out delivery. Businessmen and customers correspond to each other, and there are soft time window requirements. Take-out delivery mans do not need to send to the corresponding customers immediately after taking meals at the businesses. They do not need to return to the starting point of delivery after the completion of delivery. They can continue to deliver directly from the current location as the starting point.Take-out food distribution is essentially a kind of o2o business model. Dai et al. [8] designed a task distribution and path optimization method considering the influence of detour flexibility on part-time dispatchers, aiming at the situation that dispatchers have full-time and part-time jobs in the o2o model. Shi et al. [9] proposed a B2C and o2o innovative joint distribution service and designed an improved C-W algorithm based on node insertion path merging to realize the optimization of goods receipt and delivery with time window (PDPTW). Li et al. [10] studied the task allocation and pricing strategy between o2o platform and distributors when optimizing the optimal delivery path of goods. Using mixed integer linear programming, a matching strategy was proposed. He et al. [11] also studied the impact of food quality and merchant location on o2o food ordering, established a food ordering model, and also studied the impact of different delivery policies on food quality and merchant location.The path optimization problem in the delivery problem can be regarded as a variant of vehicle routing problem (VRP) [12, 13]. General vehicle routing problem (VRP) refers to a certain number of customers, each of whom have different quantity of goods demand. The distribution center provides goods to customers, and a fleet distributes goods by appropriate driving route, with the goal of satisfying customers’ needs and achieving goals such as shortest distance, lowest cost, and shortest time consumption under certain constraints [14]. However, the delivery problem does not have a unique delivery center. Businesses and customers correspond to each other, and there are soft time window requirements. After the delivery, the delivery personnel do not need to send the food to the corresponding customers immediately. After the delivery, they do not need to return to the delivery starting point. They can continue the delivery with the current position as the starting point.The research of vehicle routing problem has been relatively mature, so now it is basically focused on the problem with deformation and algorithm research. Chen et al. [15] studied different types of vehicle routing problems with virtual warehouse and time window and proposed a two-stage heuristic algorithm based on tabu search; Chen and Shen [16] proposed a hierarchical particle swarm optimization algorithm including the inner layer and outer layer for the impact of the location of the parking lot on the transportation cost, using the determined location of the depot to obtain the best establishment of the depot Location and the corresponding optimal vehicle path, in which the inner algorithm obtains the optimal vehicle path and the outer algorithm obtains the location of the parking lot. Liu et al. [17] in order to solve the problem of resource allocation and carbon emission in green vehicle path optimization, proposed a hybrid quantum immune algorithm based on cloud model (c-hqia), which can effectively improve the distribution efficiency and reduce the distribution demand Ben. Li et al. [18] comprehensively considered the vehicle routing and fleet size decision-making problems of various vehicle types when studying the multistage heterogeneous fleet scheduling problem, transformed the problem into a mixed integer programming model, and proposed a new heuristic algorithm based on greedy algorithm and simulated annealing algorithm. Ma and Sun [19] proposed a mutation ant colony algorithm for solving the freight vehicle routing problem, which has a better performance Martinovic et al. [20] proposed a new vehicle routing problem considering single item pickup and delivery and proposed an iterative improved simulated annealing algorithm based on greedy random initial solution.Although the research on the deformation and algorithm of the vehicle routing problem has been relatively mature, for the delivery path optimization problem, we need to consider the constraints of one-sided soft time window and the special requirements of first take and send; for the regional delivery system, we must consider the distribution between the delivery order and delivery personnel. Based on this, this paper establishes a delivery path optimization model based on cumulative time and designs the shortest path order allocation algorithm and the path optimization algorithm based on the improved ant colony algorithm.The major contributions of this study are as follows: (1) for allocation and dispatch path optimization modelling, the cumulative time modelling method is used to establish the order allocation and dispatch path optimization model; (2) a dynamic optimization algorithm is designed to solve the model in this paper.Section2 describes the problem of order allocation and path optimization in the take-out system. Section 3 is the construction of the optimization model. Section 4 is the algorithm design. Section 5 summarizes the research results, and Section 6 discusses the future research.


## 2. Problem Statement and Notations

### 2.1. Problem Statement

The problem of order allocation and delivery path optimization in the take-out system is that when the take-out order is generated, the order is assigned to a specific courier according to the current location and distribution status of all couriers. After receiving the new task, the courier starts from their current location and goes to the merchant to pick up the goods under the condition of time window constraint and then sends it to the corresponding customer, or continues to the next merchant node to pick up goods and then to complete the delivery task at the same time. Generally speaking, a one-sided soft time window constraints for the courier get to the merchant to pick up the meal and to the customer’s home to deliver the order, as shown in Figure1.Figure 1
Delivery structure diagram.In the order allocation stage, we need to consider the impact of the orders already dispatched to every courier and allocate the order tasks from the aspects of delivery efficiency and service ability of all couriers. When a new order is designated to a certain courier, the originally planned delivery route of this courier may be affected rather than the most effective one. As a result, a rescheduling phase is necessary to obtain the optimal path based on current situation, which reflects the dynamic coupling characteristic between order allocation and delivery route optimization in the take-out delivery problem. In the delivery route optimization stage, it is aimed to find an optimal route with the minimum generalized cost, including the travel distance, the waiting cost, and the time penalty cost of all couriers. In Figure2, a small example is used to illustrate the interaction process of order allocation and route optimization in the delivery problem.Figure 2
Relationship between order real-time allocation and dispatch path optimization.Figure2 shows a simplified delivery problem. The node pairs (1, 2), (3, 4), and (5, 6) are the orders that have been generated before and assigned to the courier v according to certain distribution rules, in which the nodes with odd number correspond to the merchant node while the nodes with even number correspond to the customer node. As can be seen from the comparison, with the emergence of new order (7, 8) at a certain time, the optimal delivery route of courier v changed from (1-2-3-4-5-6) to (1-2-3-7-4-5-8-6). When the system has more than one take-out couriers, the result of order allocation and route optimization are changed dynamically.According to the characteristic of this problem, the set of merchant and the set of customer both have a unilateral soft time window constraint, that is, the courier can arrive at the merchant or serve the customer early but not late than the expect time window, otherwise a penalty cost associated to the delay time will be used to affect the generation of delivery route.Without losing generality, this paper makes the following assumptions:(1)
The number of couriers inside the service region is known and fixed, which can meet the demand of order dispatch(2)
All orders are compatible with any courier, that is, each order can be dispatched to any courier(3)
The delivery interruption caused by vehicles and couriers is not considered


### 2.2. Notations, Variables, and Formulation

(1)
General NotationsV: set of couriersM: set of businessesP: set of customersO: set of take-out couriers starting location nodesK: set of take-out ordersN: set of space-time nodesAv: set of take-out delivery optimizes arcs in space-time networksv: index of courierm: index of businessp: index of customerk: index of orderΨpv: set of service arc couriersv to customers pi,t,j,s: space-time nodes, i,t,j,s∈Ni,t;j,s.: a space-time arc from head node i,t to tail node j,s, i,t;j,s∈Ac: penalty coefficient of courier arriving late at business node or customer nodedi,t;j,s: the distance from node i,t to node j,slj: the latest arrival time specified by node j(2)
Space-Time Node SetsNKD: set of take-out orders leaving the nodeNKA: set of take-out orders arriving at the nodeNVD: set of courier leaving the nodeNVO: set of origin location nodes of courier(3)
Other Declaration SymbolsArea: the search area is composed of the location of the order businesses node and the radius of 3 kmDmvk: the distance between the couriers and the businesses node in the search area of order kDmpk: the distance between businesses node m and customer node p in order kSv: the distance completes orders of couriervCv: capacity limitation of courierv.(4)
Decision Variablesxi,t;j,sv=1 if the courier goes from node i,t to node j,s; =0 otherwise.ykv=1 if order k is assigned to courierv; =0 otherwise.


## 2.1. Problem Statement

The problem of order allocation and delivery path optimization in the take-out system is that when the take-out order is generated, the order is assigned to a specific courier according to the current location and distribution status of all couriers. After receiving the new task, the courier starts from their current location and goes to the merchant to pick up the goods under the condition of time window constraint and then sends it to the corresponding customer, or continues to the next merchant node to pick up goods and then to complete the delivery task at the same time. Generally speaking, a one-sided soft time window constraints for the courier get to the merchant to pick up the meal and to the customer’s home to deliver the order, as shown in Figure1.Figure 1
Delivery structure diagram.In the order allocation stage, we need to consider the impact of the orders already dispatched to every courier and allocate the order tasks from the aspects of delivery efficiency and service ability of all couriers. When a new order is designated to a certain courier, the originally planned delivery route of this courier may be affected rather than the most effective one. As a result, a rescheduling phase is necessary to obtain the optimal path based on current situation, which reflects the dynamic coupling characteristic between order allocation and delivery route optimization in the take-out delivery problem. In the delivery route optimization stage, it is aimed to find an optimal route with the minimum generalized cost, including the travel distance, the waiting cost, and the time penalty cost of all couriers. In Figure2, a small example is used to illustrate the interaction process of order allocation and route optimization in the delivery problem.Figure 2
Relationship between order real-time allocation and dispatch path optimization.Figure2 shows a simplified delivery problem. The node pairs (1, 2), (3, 4), and (5, 6) are the orders that have been generated before and assigned to the courier v according to certain distribution rules, in which the nodes with odd number correspond to the merchant node while the nodes with even number correspond to the customer node. As can be seen from the comparison, with the emergence of new order (7, 8) at a certain time, the optimal delivery route of courier v changed from (1-2-3-4-5-6) to (1-2-3-7-4-5-8-6). When the system has more than one take-out couriers, the result of order allocation and route optimization are changed dynamically.According to the characteristic of this problem, the set of merchant and the set of customer both have a unilateral soft time window constraint, that is, the courier can arrive at the merchant or serve the customer early but not late than the expect time window, otherwise a penalty cost associated to the delay time will be used to affect the generation of delivery route.Without losing generality, this paper makes the following assumptions:(1)
The number of couriers inside the service region is known and fixed, which can meet the demand of order dispatch(2)
All orders are compatible with any courier, that is, each order can be dispatched to any courier(3)
The delivery interruption caused by vehicles and couriers is not considered


## 2.2. Notations, Variables, and Formulation

(1)
General NotationsV: set of couriersM: set of businessesP: set of customersO: set of take-out couriers starting location nodesK: set of take-out ordersN: set of space-time nodesAv: set of take-out delivery optimizes arcs in space-time networksv: index of courierm: index of businessp: index of customerk: index of orderΨpv: set of service arc couriersv to customers pi,t,j,s: space-time nodes, i,t,j,s∈Ni,t;j,s.: a space-time arc from head node i,t to tail node j,s, i,t;j,s∈Ac: penalty coefficient of courier arriving late at business node or customer nodedi,t;j,s: the distance from node i,t to node j,slj: the latest arrival time specified by node j(2)
Space-Time Node SetsNKD: set of take-out orders leaving the nodeNKA: set of take-out orders arriving at the nodeNVD: set of courier leaving the nodeNVO: set of origin location nodes of courier(3)
Other Declaration SymbolsArea: the search area is composed of the location of the order businesses node and the radius of 3 kmDmvk: the distance between the couriers and the businesses node in the search area of order kDmpk: the distance between businesses node m and customer node p in order kSv: the distance completes orders of couriervCv: capacity limitation of courierv.(4)
Decision Variablesxi,t;j,sv=1 if the courier goes from node i,t to node j,s; =0 otherwise.ykv=1 if order k is assigned to courierv; =0 otherwise.


## 3. Optimization Model Construction of Delivery Coordination

In order to optimize the delivery route of take-out, it is necessary to consider the distribution of take-out tasks and the optimization of the delivery route. Set up the take-out delivery time-space network, as shown in Figure3, and use the cumulative time to build the model [21], so as to accurately express the take-out delivery route optimization problem with two sets of variables.Figure 3
Take-out delivery time-space network.In order to represent specific nodes with temporal and spatial attributes, we define them asi,t and j,s, which represent the departure node and arrival node of the order, respectively, and define a node set N=NKD∪NKA based on delivery orders, as shown below:(1)
Delivery order departure nodei,t∈NKD, where i and t represents the starting position and time of a particular take-out order k, respectively, and satisfies the λi,t=k, indicating the coupling relationship between the departure node i,t and the take-out order k(2)
Take-out order arrival nodej,s∈NKA denotes that, for a particular take-out order k, j and s represent the arrival location and time of take-out order k, respectively, and similarly satisfy λj,s=k(1)
Objective Function. The objective of this optimization model is to minimize the generated total cost of take-out delivery, including travel cost and time penalty cost, that is, the objective function can be described as(1)minZ1=∑v∈V∑i,t;j,s∈Avdi,t;j,sxi,t;j,sv+c∑v∈V∑i,t;j,s∈Avmaxs−lj,0.(2)
Delivery Start Node Constraints. From the current location, the first node that the take-out delivery courier visits must be the merchant node:(2)∑i,t;j,s∈Avxi,t;j,sv=1,i∈O,j∈M,∀v∈V.(3)
Delivery End Node Constraints. When the take-out delivery courier visits his last customer, it can be considered that the take-out dispatch process is completed and there is no need for him to return to the starting point or the merchant nodes:(3)∑i,t;j,s∈Avxi,t;j,sv=0,i∈P,j∈O,∀v∈V.(4)
Service Frequency Constraints. In a task set, for the same courier, each customer is served exactly once:(4)∑i,t;j,s∈Ψpvxi,t;j,sv=1,∀p∈P,∀v∈V.(5)
Order Task Coverage Constraints. Each order task can be delivered by only one take-out delivery courier. Task coverage constraints can be represented by route dispatch variablexi,t;j,sv and order dispatch variable ykv:(5)∑i,t;j,s∈K,λi,t;j,s=kxi,t;j,sv=ykv,∀k∈K,∀v∈V,where λi,t;j,s=k represent the coupling relationship of departure node i,t, arrival node j,s, and take-out order k.(6)
Order Distribution Constraints. For each order, only one take-out delivery courier can be assigned:(6)∑v∈Vykv=1,∀k∈K,∀v∈V.(7)
Variable Constraints. The take-out delivery couriers choice of each route is a 0-1 variable, and whether to assign orderk to courier v is also a 0-1 variable:(7)xi,t;j,sv∈0,1i,t;j,s∈Av,ykv∈0,1,∀k∈K,∀v∈V.


## 4. Solution Algorithms

The delivery order allocation and dispatch route optimization studied in this paper is a dynamic process. In the solution stage, it is necessary to determine the allocation result of the subsequent new orders according to the assigned orders and their completion status of the delivery courier, as shown in Figure4. Based on this, we design an order dynamic allocation algorithm embedded in a path optimization subalgorithm.Figure 4
Coordination and optimization algorithm design of the take-out system.First, orders generated early are assigned to couriers with the consideration of distance between the courier and the merchant and the customer, as well as the delivery ability of the couriers, and the current best delivery route is calculated according to all orders allocated to each courier. Then, the new order allocation is carried out based on the former order allocation result, and finally the optimal route after adding the new order is recalculated and this process will be repeated until all orders are allocated to the corresponding courier.The allocation of new order in the take-out system is a dynamic process, which is handled with the passage of time, and the current position and remaining tasks of all the couriers should be also considered.In this paper, from the perspective of dispatch efficiency, the evaluation function of order allocation is established based on the sum of the follow-up operation time of all the couriers in the region after receiving the new order, and the current optimal allocation scheme is determined according to the evaluation function.Let order allocation evaluation functionTk,1 represent the total remaining delivery time of the system after the allocation of order k, namely,(8)Tk,1=minFvu,k,1,vu∈VArea.The equationFvu,k,1 represents the remaining delivery time of the entire system after assigning order k to courier vu, which is equal to the sum of the delivery time of courier vu after assigning order kTvu,k,1 and the delivery time of all other couriers not allocated order Tvu,k,0.(9)Fvu,k,1=Tvu,k,1+∑vuTvu,k,0,vu∈VArea.The delivery time of couriervu not allocated order kTvu,k,0 is related to status of the courier in the previous stage:(10)Tvu,k,0=maxTvu,k−1,1−Δk,k−1,0,if Allocate orderk−1tovu,maxTvu,k−1,0−Δk,k−1,0,otherwise,where tk−1 and tk are the time of order k−1 and order k−1 appears, and Δk,k−1 represents the time span from tk−1 to tk:(11)Δk,k−1=tk−tk−1.Although the probability is small, it is possible to generate two or more orders at the same time. In this case, the way we deal with it is sorting these orders by random sequence, and then allocate the new orders to couriers one by one.In order allocation and delivery route coordination optimization algorithm of the take-out system, the main algorithm is dynamic order allocation algorithm based on dispatch efficiency, and the subalgorithm is route optimization algorithm based on current optimal. For a new delivery order, we first try to assign it to a courier in the region, use the delivery route optimization subalgorithm to optimize the delivery route of this courier in real time, and calculate his remaining delivery time and the corresponding system remaining delivery time.Repeat the process to get all the possible allocation schemes, and then, based on the evaluation function, the greedy strategy is adopted to select the optimal scheme to use. Continue the allocation process of the subsequent orders according to the sequence of their appearing time until all the orders have been allocated. The specific flow chart of the algorithm is shown in Figure5.Figure 5
Flow chart of dynamic coordination optimization algorithm.


### 4.1. Main Algorithm: Dynamic Order Allocation Algorithm

Step0: Initialization; Initializes the real-time location of all couriers and the information of all orders, letk=1, and Tvu,k,0=0 for each courier.Step1: For orderk in the system, search all the couriers in the Area to form the courier set VArea.Step2: Executevu=1,VArea,vu++, and calculate Tvu,k,1 and Fvu,k,1.Step3: Perform Sub-Algorithm of route optimization to calculate the current optimal route of couriervu.Step4: According to the evaluation functionTk,1, assign order k to the corresponding courier who has the best function value.Step5: Capacity judgment. If the capacityCv of courier vu do not exceed his maximum capacity after the order allocation in Step 4, the allocation of order k is completed; if not, return to Step 2.Step6: Judge whether the conditionK<Kmax is met, if so, execute k++, update all Tvu,k,0 according to Δk,k−1 and return to Step 1; otherwise, the algorithm meets the termination condition and output the result of order allocation and the optimal delivery route for each courier.


### 4.2. Subalgorithm: Current Optimal Route Optimization Algorithm

In order to find the optimal delivery route for the allocated but not yet completed orders for a certain courier, a genetic algorithm considering the special characteristics of the problem is designed in this paper. The flow of the algorithm is as follows:Step 0 (chromosome representation): the chromosomes are coded in natural number, i.e., the corresponding codes of orders O1 and O2 are 1, 2 and 3, 4, respectively, where the odd numbers 1, 3 represent the merchant nodes while the even numbers 2, 4 represent the customer node. Since the delivery stage of the order must occur after the picking up stage, the customer node (even number) corresponding to an order in the chromosome must be behind the merchant node (odd number), and the numbers used to represent the merchant and customer are sorted by the order generation time sequence.In the delivery system, the order delivery problem must be guaranteed to take first and send back, that is to say, for an order, in the chromosome, the corresponding point of the merchant must appear before the corresponding point of the customer. All of them can get reasonable offspring, which can satisfy the order’s first pick-up and back delivery.Step 1 (initial population selection): the initial population is randomly generated in existing individuals according to the constraints.Step 2 (cross operator): green denotes the intersection of genes, with the first half of the offspring being the first half of the corresponding parent and the second half in the order of the remaining elements in the other parent. All solutions must also satisfy one constraint, that is, for five orders, the business order is 1, 3, 5, 7, 9; the customer order is 2, 4, 6, 8, 10; the access order constraints of 1 before 2, 3 before 4, 5 before 6, 7 before 8, and 9 before 10 are required.In this paper, a visit sequence-based coding is designed to solve the delivery route optimization problem. In the process of crossover, the method of generating two children from two parents is adopted. The specific operation of crossover is shown in Figure6.First, two parent chromosomes are randomly selected from the population according their fitness function, and a crossing position is generated randomly either, as shown in the red line in the figure. Since the chromosomes are divided into the first half and the second half by the crossing position, an effective crossover operation is designed here to ensure the feasibility of the two generated children. For child 1, the first half of father 1 was copied directly, and then the missing genes were supplemented to the second half in the order in which they appeared in father 2. Similarly, this operation can be used again to generate child 2. In this mode of crossover, as long as two parents are feasible, the offspring generated by their hybridization will also be feasible. That is, the constraint of visiting the merchant nodes (1, 3, 5, 7, 9) before their corresponding customer nodes (2, 4, 6, 8, 10) can be easily satisfied.Step 3 (mutation operator): to maintain the diversity of population, the local changes of chromosome are generated by mutation operator. First, a chromosome is selected randomly from the population. Then, in order to keep the feasibility of chromosome after mutation, a variation mode based on node pair exchange is designed, that is, select two orders randomly and exchange the visit sequence of their merchant nodes correspondingly, as well as the customer nodes, so as to ensure that, for any chromosome after mutation, each customer node must appear after its corresponding merchant node. The specific mutation process is shown in Figure7.Step 4 (fitness function): the fitness function is the objective function in this paper, that is, the total delivery cost of all orders.Figure 6
A crossover operator diagram.Figure 7
A mutation operator diagram.


## 4.1. Main Algorithm: Dynamic Order Allocation Algorithm

Step0: Initialization; Initializes the real-time location of all couriers and the information of all orders, letk=1, and Tvu,k,0=0 for each courier.Step1: For orderk in the system, search all the couriers in the Area to form the courier set VArea.Step2: Executevu=1,VArea,vu++, and calculate Tvu,k,1 and Fvu,k,1.Step3: Perform Sub-Algorithm of route optimization to calculate the current optimal route of couriervu.Step4: According to the evaluation functionTk,1, assign order k to the corresponding courier who has the best function value.Step5: Capacity judgment. If the capacityCv of courier vu do not exceed his maximum capacity after the order allocation in Step 4, the allocation of order k is completed; if not, return to Step 2.Step6: Judge whether the conditionK<Kmax is met, if so, execute k++, update all Tvu,k,0 according to Δk,k−1 and return to Step 1; otherwise, the algorithm meets the termination condition and output the result of order allocation and the optimal delivery route for each courier.


## 4.2. Subalgorithm: Current Optimal Route Optimization Algorithm

In order to find the optimal delivery route for the allocated but not yet completed orders for a certain courier, a genetic algorithm considering the special characteristics of the problem is designed in this paper. The flow of the algorithm is as follows:Step 0 (chromosome representation): the chromosomes are coded in natural number, i.e., the corresponding codes of orders O1 and O2 are 1, 2 and 3, 4, respectively, where the odd numbers 1, 3 represent the merchant nodes while the even numbers 2, 4 represent the customer node. Since the delivery stage of the order must occur after the picking up stage, the customer node (even number) corresponding to an order in the chromosome must be behind the merchant node (odd number), and the numbers used to represent the merchant and customer are sorted by the order generation time sequence.In the delivery system, the order delivery problem must be guaranteed to take first and send back, that is to say, for an order, in the chromosome, the corresponding point of the merchant must appear before the corresponding point of the customer. All of them can get reasonable offspring, which can satisfy the order’s first pick-up and back delivery.Step 1 (initial population selection): the initial population is randomly generated in existing individuals according to the constraints.Step 2 (cross operator): green denotes the intersection of genes, with the first half of the offspring being the first half of the corresponding parent and the second half in the order of the remaining elements in the other parent. All solutions must also satisfy one constraint, that is, for five orders, the business order is 1, 3, 5, 7, 9; the customer order is 2, 4, 6, 8, 10; the access order constraints of 1 before 2, 3 before 4, 5 before 6, 7 before 8, and 9 before 10 are required.In this paper, a visit sequence-based coding is designed to solve the delivery route optimization problem. In the process of crossover, the method of generating two children from two parents is adopted. The specific operation of crossover is shown in Figure6.First, two parent chromosomes are randomly selected from the population according their fitness function, and a crossing position is generated randomly either, as shown in the red line in the figure. Since the chromosomes are divided into the first half and the second half by the crossing position, an effective crossover operation is designed here to ensure the feasibility of the two generated children. For child 1, the first half of father 1 was copied directly, and then the missing genes were supplemented to the second half in the order in which they appeared in father 2. Similarly, this operation can be used again to generate child 2. In this mode of crossover, as long as two parents are feasible, the offspring generated by their hybridization will also be feasible. That is, the constraint of visiting the merchant nodes (1, 3, 5, 7, 9) before their corresponding customer nodes (2, 4, 6, 8, 10) can be easily satisfied.Step 3 (mutation operator): to maintain the diversity of population, the local changes of chromosome are generated by mutation operator. First, a chromosome is selected randomly from the population. Then, in order to keep the feasibility of chromosome after mutation, a variation mode based on node pair exchange is designed, that is, select two orders randomly and exchange the visit sequence of their merchant nodes correspondingly, as well as the customer nodes, so as to ensure that, for any chromosome after mutation, each customer node must appear after its corresponding merchant node. The specific mutation process is shown in Figure7.Step 4 (fitness function): the fitness function is the objective function in this paper, that is, the total delivery cost of all orders.Figure 6
A crossover operator diagram.Figure 7
A mutation operator diagram.


## 5. Numerical Experiments

### 5.1. A Simple Example

To verify the validity of the take-out order allocation and delivery route optimization model established in this paper, taking Anning District of Lanzhou City Gansu Province in China as an example, 13 orders with 26 nodes are selected, and the latitude and longitude of each node are obtained through the Golden Map API. Assuming the following take-out delivery scenario, the location of two couriers and the location of the merchants and customers are shown in Figure8. The detailed information is shown in Table 1, where the merchants and customers correspond to each other according to the subscript. For example, the merchant node and the customer node of order O5 are m5 and c5, respectively.Figure 8
Take-out node map location.Table 1
Information tables for each node.
IDPositional coordinatesWaiting time (min)Time windowOrder generation timeCourier1103.723339, 36.1085550——Courier2103.731286, 36.1012680——O1m1103.725745, 36.1008091[0, 15]11 : 30c1103.728406, 36.1063480[0, 35]11 : 30O2m2103.725745, 36.1008091[0, 15]11 : 35c2103.728406, 36.1063480[0, 35]11 : 35O3m3103.723948, 36.1014370[1, 19]11 : 41c3103.709617, 36.0908711[0, 40]11 : 41O4m4103.724538, 36.0964873[2, 26]11 : 50c4103.699833, 36.0908972[5, 51]11 : 50O5m5103.730761, 36.0998081[2, 31]11 : 55c5103.694254, 36.0949892[10, 50]11 : 55O6m6103.730208, 36.0976882[4, 40]12 : 00c6103.697386, 36.1061891[10, 63]12 : 00O7m7103.720466, 36.1014070[3, 48]12 : 09c7103.697247, 36.1064230[0, 58]12 : 09O8m8103.723229, 36.0984212[4, 50]12 : 15c8103.717396, 36.1031981[0, 66]12 : 15O9m9103.714362, 36.1070331[6, 63]12 : 27c9103.749840, 36.0875072[5, 72]12 : 27O10m10103.745770, 36.0985162[3, 70]12 : 38c10103.741933, 36.0970611[10, 75]12 : 38O11m11103.747262, 36.0989491[4, 83]12 : 48c11103.739824, 36.1040351[5, 90]12 : 48O12m12103.748163, 36.0983901[3, 88]12 : 54c12103.743054, 36.1023411[10, 93]12 : 54O13m13103.730095, 36.0947752[2, 95]13 : 00c13103.758739, 36.0878512[6, 104]13 : 00In this paper, take-out order dispatch and route optimization with/without considering traffic jam are calculated and compared, in which the congestion of urban road network is reflected by the speed of couriers. If there is no traffic jam in each road section of the road network, the delivery speed of the courier is constant throughout the trip. If there is traffic jam in some road sections, the courier will pass the congested road at a lower speed.The computing environment of the numerical experiment in this paper is Intel Core i7-7500u CPU, with 16 GB memory and windows 10 operating system, and the algorithm proposed is programed by MATLAB R2019a software. Assuming that the vehicle dispatching speed is 24.5 km/h and 35 km/h when the congestion is considered or not, the penalty cost for overtime dispatching is 1 yuan/min, and the dispatching fee is 0.1 yuan/km. The calculation termination condition is the iteration times, which is set as 100.When considering the congestion situation in a specific period of time, it is assumed that the 30th min and 56th min of the delivery system are the start and end time of traffic jam, and the congestion section matrix is shown in Table2.Table 2
Matrix of congested road sections.
m1m2m3m4m5m6m7m8m9m10m11m12m13p1p2p3p4p5p6p7p8p9p10p11p12p13m1—1101100111011010011110111m21—110101000011010001100011m311—10110001010101111100010m4011—1010001001111011100010m51001—101000010101011100010m611101—11100010111000101000m7001101—0111011010000000011m80100110—000100100000111000m910000110—10001110101010011m10100000101—0110000111110110m111011001000—111110000100000m1200000001011—01001100001011m13111011100110—0000010010110p11101001010110—100111001100p200111101101001—10111000101p3110101101010001—0101111010p40011110000010000—011011111p500100000110101110—10010001p6101110000100111011—1100100p71111100011000111101—101110p811101101011000010011—11111p9100100011100100111001—0010p100000010100010101100110—000p1110000000010011101011100—11p12111110101101100110011101—0p131110010100100101100100100—Table3 shows the results of order allocation with/without traffic jam, and the corresponding delivery route are shown in Figures 9 and 10, respectively.Table 3
Order allocation result.
Regardless of traffic jamConsidering traffic jamCouriers1212Allocated order(O3, O5, O6, O7, O8, O9, O10, O11)(O1, O2, O4, O12, O13)(O3, O5, O6, O7, O8, O9, O10, O11)(O1, O2, O4, O12, O13)Delivery routem3-c3-m5-c5-m6-m8-m7-c6-m9-c7-c9-c8-m10-m11-c10-c11m1-c1-m2-c2-m4-c4-m12-c12-m13-c13m3-c3-m5-c5-m7-m8-m6-m9-c6-c7-c8-c9-m10-m11-c10-c11m1-c1-m2-c2-m4-c4-m12-c12-m13-c13System cost6.26316.4298Figure 9
Order assignment and delivery route diagram regardless of road congestion. (a) Delivery route of courier 1. (b) Delivery route of courier 2.
(a)(b)Figure 10
Order assignment and delivery route diagram considering road congestion. (a) Delivery route of courier 1. (b) Delivery route of courier 2.
(a)(b)From the calculation results, it can be found that the order allocation of the two couriers are the same when the traffic jam is considered or not. Courier 1 is assigned 8 orders (O3, O5, O6, O7, O8, O9, O10, O11) while courier 2 is assigned 5 orders (O1, O2, O4, O12, O13). In the first scenario, the congestion is not considered and the delivery route of courier 1 is m3-c3-m5-c5-m6-m8-m7-c6-m9-c7-c9-c8-m10-m11-c10-c11 and that of courier 2 is m1-c1-m2-c2-m4-c4-m12-c12-m13-c13. In the second scenario, when there is a traffic jam, the delivery route of courier 1 is changed to m3-c3-m5-c5-m7-m8-m6-m9-c6-c7-c8-c9-m10-m11-c10-c11, whereas the delivery route of courier 2 is still m1-c1-m2-c2-m4-c4-m12-c12-m13-c13. For the system cost, the one considered traffic jam is slightly higher than the other one.


### 5.2. Large-Sized Numerical Experiments

This section aims to conduct more numerical experiments to examine the capability of the proposed model and algorithm. In this paper, a large-scale calculation example composed of 12 couriers and 40 orders is designed. The information of couriers and orders is shown in Tables4 and 5.Table 4
Courier initial coordinates.
CourierPositional coordinatesCourier 1103.723339, 36.108555Courier 2103.731286, 36.101268Courier 3103.728457, 36.098558Courier 4103.746996, 36.092802Courier 5103.719530, 36.100986Courier 6103.707771, 36.095021Courier 7103.725882, 36.108267Courier 8103.725882, 36.108267Courier 9103.717899, 36.099737Courier 10103.753691, 36.092594Courier 11103.701592, 36.104453Courier 12103.726826, 36.099876Table 5
Information tables for each node.
IDPositional coordinatesWaiting time (min)Time windowOrder generation timeO1m1103.725745, 36.1008091[0, 15]11 : 30c1103.728406, 36.1063480[0, 35]11 : 30O2m2103.725745, 36.1008091[0, 15]11 : 32c2103.728406, 36.1063480[0, 35]11 : 32O3m3103.723948, 36.1014370[1, 19]11 : 35c3103.709617, 36.0908711[0, 40]11 : 35O4m4103.724538, 36.0964873[2, 18]11 : 36c4103.699833, 36.0908972[5, 45]11 : 36O5m5103.730761, 36.0998081[2, 19]11 : 37c5103.694254, 36.0949892[10, 50]11 : 37O6m6103.730208, 36.0976882[4, 17]11 : 38c6103.697386, 36.1061891[10, 55]11 : 38O7m7103.720466, 36.1014070[3, 17]11 : 40c7103.697247, 36.1064230[0, 50]11 : 40O8m8103.723229, 36.0984212[4, 19]11 : 42c8103.717396, 36.1031981[0, 35]11 : 42O9m9103.714362, 36.1070331[6, 18]11 : 44c9103.749840, 36.0875072[5, 40]11 : 44O10m10103.745770, 36.0985162[3, 21]11 : 45c10103.741933, 36.0970611[10, 50]11 : 45O11m11103.747262, 36.0989491[4, 23]11 : 46c11103.739824, 36.1040351[5, 40]11 : 46O12m12103.748163, 36.0983901[3, 30]11 : 47c12103.743054, 36.1023411[10, 50]11 : 47O13m13103.730095, 36.0947752[2, 40]11 : 48c13103.758739, 36.0878512[6, 65]11 : 48O14m14103.727427, 36.0991132[0, 45]11 : 50c14103.725023, 36.1102780[0, 65]11 : 50O15m15103.730259, 36.1071573[0, 45]11 : 52c15103.744507, 36.0960621[0, 65]11 : 52O16m16103.748112, 36.0905132[1, 49]11 : 54c16103.719273, 36.0952293[0, 80]11 : 54O17m17103.727083, 36.0999453[2, 47]11 : 56c17103.696957, 36.1050082[5, 85]11 : 56O18m18103.732319, 36.1051462[2, 47]11 : 58c18103.715839, 36.1059790[10, 80]11 : 58O19m19103.715754, 36.1029270[4, 49]12 : 00c19103.715153, 36.1110411[10, 85]12 : 00O20m20103.720732, 36.1001530[3, 48]12 : 02c20103.703909, 36.0968940[0, 80]12 : 02O21m21103.733177, 36.1058402[4, 51]12 : 04c21103.731203, 36.0948134[0, 80]12 : 04O22m22103.720560, 36.1059792[6, 53]12 : 06c22103.705711, 36.1049382[5, 70]12 : 06O23m23103.712750, 36.1025813[3, 60]12 : 08c23103.715582, 36.0955070[10, 80]12 : 08O24m24103.729916, 36.0991830[4, 70]12 : 10c24103.737640, 36.0952291[5, 95]12 : 10O25m25103.730345, 36.0997371[3, 75]12 : 12c25103.708887, 36.1014711[10, 100]12 : 12O26m26103.722019, 36.1003612[2, 78]12 : 14c26103.704081, 36.1016792[6, 102]12 : 14O27m27103.728199, 36.0998761[0, 80]12 : 16c27103.711805, 36.0949520[0, 100]12 : 16O28m28103.746653, 36.0942581[0, 105]12 : 18c28103.755837, 36.0916921[0, 125]12 : 18O29m29103.748198, 36.0957151[1, 105]12 : 20c29103.757811, 36.0903052[0, 125]12 : 20O30m30103.747854, 36.0934261[2, 109]12 : 22c30103.760300, 36.0896810[5, 130]12 : 22O31m31103.743563, 36.0937041[2, 109]12 : 24c31103.757124, 36.0901661[10, 135]12 : 24O32m32103.741245, 36.0950910[4, 145]12 : 26c32103.739100, 36.1056321[10, 145]12 : 26O33m33103.737211, 36.1049380[3, 107]12 : 28c33103.732061, 36.0968943[0, 140]12 : 28O34m34103.721075, 36.0993912[4, 109]12 : 30c34103.732920, 36.1077121[0, 145]12 : 30O35m35103.720389, 36.0973791[6, 108]12 : 32c35103.722534, 36.1086832[5, 5140]12 : 32O36m36103.714123, 36.1015061[3, 111]12 : 34c36103.734379, 36.1033431[10, 140]12 : 34O37m37103.723993, 36.0971372[4, 113]12 : 36c37103.741074, 36.1031703[5, 130]12 : 36O38m38103.722835, 36.0971711[3, 120]12 : 38c38103.729143, 36.0986282[10, 140]12 : 38O39m39103.725324, 36.0993212[2, 130]12 : 40c39103.737083, 36.0989744[6, 155]12 : 40O40m40103.730044, 36.0939811[0, 135]12 : 42c40103.736396, 36.1060830[0, 160]12 : 42In this paper, the calculation parameters and the running environment of the large case are the same as those of the small one, and the proportion of congested road is about 50%. The results of take-out order allocation and path optimization considering traffic jam or not are shown in Tables6 and 7, respectively.Table 6
Results of order allocation and delivery route without considering congestion.
CourierAllocated orderDelivery routeCourier 1——Courier 2(O14, O21, O24, O32, O33, O37, O38, O39, O40)m14-c14-m21-c21-m24-c24-m32-c32-m33-c33-m38-m37-m39-c38-m40-c39-c37-c40Courier 3(O2, O15, O29)m2-c2-m15-c15-m29-c29Courier 4(O28)m28-c28Courier 5(O3, O4, O6, O7, O8)m3-m8-m4-m6-m7-c8-c3-c4-c6-c7Courier 6——Courier 7(O9, O10, O11, O12, O13, O16, O17, O20, O25, O26, O27)m9-m13-m10-m11-m12-c13-c9-m16-c10-c12-c11-m25-m27-m17-m26-m20-c16-c27-c25-c20-c17-c26Courier 8(O5, O18, O19, O22)m5-c5-m19-m18-m22-c18-c19-c22Courier 9(O23, O34, O35, O36)m23-c23-m35-m34-m36-c35-c34-c36Courier 10(O30, O31)m30-m31-c31-c30Courier 11——Courier 12(O1)m1-c1Table 7
Results of order allocation and delivery route considering congestion.
CourierAllocated orderDelivery routeCourier 1——Courier 2(O11, O12, O33)m12-m11-c12-c11-m33-c33Courier 3(O2, O15, O32, O36, O39)m2-c2-m15-c15-m32-m36-m39-c36-c32-c39Courier 4(O19, O22, O23, O25, O26, O28)m19-c19-m22-m23-m25-c23-c22-c25-m26-c26m28-c28Courier 5(O3, O4, O6, O7, O8, O27)m3-m8-m4-m6-m7-c7-c6-c4-c3-c8-m27-c27Courier 6(O10, O13, O21, O24, O29, O30, O31)m21-m24-m13-c21-m10-c24-c10-m31-m29-m30-c31-c29-c30-c13Courier 7——Courier 8(O5, O9, O17, O20)m5-m9-c5-c9-m17-m20-c20-c17Courier 9(O23, O35, O40)m23-c23-m35-m40-c35-c40Courier 10(O16, O38)m16-c16-m38-c38Courier 11——Courier 12(O1, O14, O18, O34, O37)m1-c1-m14- m18-c14-c18-m34-m37-c34-c37It can be found that, in both condition with or without traffic jam, there are some differences between the result of order allocation and route optimization. The couriers 1, 6, and 11 are not assigned any delivery orders when the traffic status is good, while the couriers 1, 7, and 11 are not assigned any tasks when traffic congestion is happened. The reason for this result is that the objective function of the problem here we studied is to minimize the total system dispatch cost, but not the delivery cost or income balance of single courier.For this numerical test, the system dispatch cost considering traffic jam or not is 41.1540 yuan and 55.0888 yuan, respectively. Through 20 calculations, it can be found that the system dispatch cost under congestion is always greater than that without considering of traffic jam. When considering the road congestion, the delivery cost of some delivery paths increases, so we have to choose congested roads or suboptimal routes for dispatching, which result in the increase of system dispatching cost.This paper calculates 20 times for simple examples and large-scale numerical experiments, respectively, the core program of the algorithm can be obtained fromhttps://github.com/Guofeng-SUN/Takeaway-algorithm-core-program/tree/master, and the computing time of two scale and four cases is shown in Table 8.Table 8
Comparison of numerical test calculation time.
Type of road network congestionTotal computing time (s)Average computing time per order (s)Simple exampleRegardless of road network congestion20.15Consider road network congestion20.15Large-sized numerical experimentsRegardless of road network congestion1122.8Consider road network congestion1142.85It can be found that the computing time is almost the same for the same scale cases. For the average computing time of each order, the one of large-scale examples is significantly longer than that of simple examples. With the increase of the number of couriers and tasks, the scale of the road network is correspondingly expanded, resulting in the sharp increase of the feasible delivery routes. Therefore, the search efficiency of the algorithm in each iteration is also reduced. Although the computing time of large-scale examples has increased, it can still basically meet the application needs in practical according to this scale. In the design of this paper, the connection between nodes is simplified, and all nodes are all connected, which leads to the delivery route obtained by the algorithm being far larger than the actual problem. In practical application, when the number of paths in physical network is reduced, whereas the performance of large-scale commercial computing server is higher, the efficiency of the algorithm will be greatly improved.


## 5.1. A Simple Example

To verify the validity of the take-out order allocation and delivery route optimization model established in this paper, taking Anning District of Lanzhou City Gansu Province in China as an example, 13 orders with 26 nodes are selected, and the latitude and longitude of each node are obtained through the Golden Map API. Assuming the following take-out delivery scenario, the location of two couriers and the location of the merchants and customers are shown in Figure8. The detailed information is shown in Table 1, where the merchants and customers correspond to each other according to the subscript. For example, the merchant node and the customer node of order O5 are m5 and c5, respectively.Figure 8
Take-out node map location.Table 1
Information tables for each node.
IDPositional coordinatesWaiting time (min)Time windowOrder generation timeCourier1103.723339, 36.1085550——Courier2103.731286, 36.1012680——O1m1103.725745, 36.1008091[0, 15]11 : 30c1103.728406, 36.1063480[0, 35]11 : 30O2m2103.725745, 36.1008091[0, 15]11 : 35c2103.728406, 36.1063480[0, 35]11 : 35O3m3103.723948, 36.1014370[1, 19]11 : 41c3103.709617, 36.0908711[0, 40]11 : 41O4m4103.724538, 36.0964873[2, 26]11 : 50c4103.699833, 36.0908972[5, 51]11 : 50O5m5103.730761, 36.0998081[2, 31]11 : 55c5103.694254, 36.0949892[10, 50]11 : 55O6m6103.730208, 36.0976882[4, 40]12 : 00c6103.697386, 36.1061891[10, 63]12 : 00O7m7103.720466, 36.1014070[3, 48]12 : 09c7103.697247, 36.1064230[0, 58]12 : 09O8m8103.723229, 36.0984212[4, 50]12 : 15c8103.717396, 36.1031981[0, 66]12 : 15O9m9103.714362, 36.1070331[6, 63]12 : 27c9103.749840, 36.0875072[5, 72]12 : 27O10m10103.745770, 36.0985162[3, 70]12 : 38c10103.741933, 36.0970611[10, 75]12 : 38O11m11103.747262, 36.0989491[4, 83]12 : 48c11103.739824, 36.1040351[5, 90]12 : 48O12m12103.748163, 36.0983901[3, 88]12 : 54c12103.743054, 36.1023411[10, 93]12 : 54O13m13103.730095, 36.0947752[2, 95]13 : 00c13103.758739, 36.0878512[6, 104]13 : 00In this paper, take-out order dispatch and route optimization with/without considering traffic jam are calculated and compared, in which the congestion of urban road network is reflected by the speed of couriers. If there is no traffic jam in each road section of the road network, the delivery speed of the courier is constant throughout the trip. If there is traffic jam in some road sections, the courier will pass the congested road at a lower speed.The computing environment of the numerical experiment in this paper is Intel Core i7-7500u CPU, with 16 GB memory and windows 10 operating system, and the algorithm proposed is programed by MATLAB R2019a software. Assuming that the vehicle dispatching speed is 24.5 km/h and 35 km/h when the congestion is considered or not, the penalty cost for overtime dispatching is 1 yuan/min, and the dispatching fee is 0.1 yuan/km. The calculation termination condition is the iteration times, which is set as 100.When considering the congestion situation in a specific period of time, it is assumed that the 30th min and 56th min of the delivery system are the start and end time of traffic jam, and the congestion section matrix is shown in Table2.Table 2
Matrix of congested road sections.
m1m2m3m4m5m6m7m8m9m10m11m12m13p1p2p3p4p5p6p7p8p9p10p11p12p13m1—1101100111011010011110111m21—110101000011010001100011m311—10110001010101111100010m4011—1010001001111011100010m51001—101000010101011100010m611101—11100010111000101000m7001101—0111011010000000011m80100110—000100100000111000m910000110—10001110101010011m10100000101—0110000111110110m111011001000—111110000100000m1200000001011—01001100001011m13111011100110—0000010010110p11101001010110—100111001100p200111101101001—10111000101p3110101101010001—0101111010p40011110000010000—011011111p500100000110101110—10010001p6101110000100111011—1100100p71111100011000111101—101110p811101101011000010011—11111p9100100011100100111001—0010p100000010100010101100110—000p1110000000010011101011100—11p12111110101101100110011101—0p131110010100100101100100100—Table3 shows the results of order allocation with/without traffic jam, and the corresponding delivery route are shown in Figures 9 and 10, respectively.Table 3
Order allocation result.
Regardless of traffic jamConsidering traffic jamCouriers1212Allocated order(O3, O5, O6, O7, O8, O9, O10, O11)(O1, O2, O4, O12, O13)(O3, O5, O6, O7, O8, O9, O10, O11)(O1, O2, O4, O12, O13)Delivery routem3-c3-m5-c5-m6-m8-m7-c6-m9-c7-c9-c8-m10-m11-c10-c11m1-c1-m2-c2-m4-c4-m12-c12-m13-c13m3-c3-m5-c5-m7-m8-m6-m9-c6-c7-c8-c9-m10-m11-c10-c11m1-c1-m2-c2-m4-c4-m12-c12-m13-c13System cost6.26316.4298Figure 9
Order assignment and delivery route diagram regardless of road congestion. (a) Delivery route of courier 1. (b) Delivery route of courier 2.
(a)(b)Figure 10
Order assignment and delivery route diagram considering road congestion. (a) Delivery route of courier 1. (b) Delivery route of courier 2.
(a)(b)From the calculation results, it can be found that the order allocation of the two couriers are the same when the traffic jam is considered or not. Courier 1 is assigned 8 orders (O3, O5, O6, O7, O8, O9, O10, O11) while courier 2 is assigned 5 orders (O1, O2, O4, O12, O13). In the first scenario, the congestion is not considered and the delivery route of courier 1 is m3-c3-m5-c5-m6-m8-m7-c6-m9-c7-c9-c8-m10-m11-c10-c11 and that of courier 2 is m1-c1-m2-c2-m4-c4-m12-c12-m13-c13. In the second scenario, when there is a traffic jam, the delivery route of courier 1 is changed to m3-c3-m5-c5-m7-m8-m6-m9-c6-c7-c8-c9-m10-m11-c10-c11, whereas the delivery route of courier 2 is still m1-c1-m2-c2-m4-c4-m12-c12-m13-c13. For the system cost, the one considered traffic jam is slightly higher than the other one.


## 5.2. Large-Sized Numerical Experiments

This section aims to conduct more numerical experiments to examine the capability of the proposed model and algorithm. In this paper, a large-scale calculation example composed of 12 couriers and 40 orders is designed. The information of couriers and orders is shown in Tables4 and 5.Table 4
Courier initial coordinates.
CourierPositional coordinatesCourier 1103.723339, 36.108555Courier 2103.731286, 36.101268Courier 3103.728457, 36.098558Courier 4103.746996, 36.092802Courier 5103.719530, 36.100986Courier 6103.707771, 36.095021Courier 7103.725882, 36.108267Courier 8103.725882, 36.108267Courier 9103.717899, 36.099737Courier 10103.753691, 36.092594Courier 11103.701592, 36.104453Courier 12103.726826, 36.099876Table 5
Information tables for each node.
IDPositional coordinatesWaiting time (min)Time windowOrder generation timeO1m1103.725745, 36.1008091[0, 15]11 : 30c1103.728406, 36.1063480[0, 35]11 : 30O2m2103.725745, 36.1008091[0, 15]11 : 32c2103.728406, 36.1063480[0, 35]11 : 32O3m3103.723948, 36.1014370[1, 19]11 : 35c3103.709617, 36.0908711[0, 40]11 : 35O4m4103.724538, 36.0964873[2, 18]11 : 36c4103.699833, 36.0908972[5, 45]11 : 36O5m5103.730761, 36.0998081[2, 19]11 : 37c5103.694254, 36.0949892[10, 50]11 : 37O6m6103.730208, 36.0976882[4, 17]11 : 38c6103.697386, 36.1061891[10, 55]11 : 38O7m7103.720466, 36.1014070[3, 17]11 : 40c7103.697247, 36.1064230[0, 50]11 : 40O8m8103.723229, 36.0984212[4, 19]11 : 42c8103.717396, 36.1031981[0, 35]11 : 42O9m9103.714362, 36.1070331[6, 18]11 : 44c9103.749840, 36.0875072[5, 40]11 : 44O10m10103.745770, 36.0985162[3, 21]11 : 45c10103.741933, 36.0970611[10, 50]11 : 45O11m11103.747262, 36.0989491[4, 23]11 : 46c11103.739824, 36.1040351[5, 40]11 : 46O12m12103.748163, 36.0983901[3, 30]11 : 47c12103.743054, 36.1023411[10, 50]11 : 47O13m13103.730095, 36.0947752[2, 40]11 : 48c13103.758739, 36.0878512[6, 65]11 : 48O14m14103.727427, 36.0991132[0, 45]11 : 50c14103.725023, 36.1102780[0, 65]11 : 50O15m15103.730259, 36.1071573[0, 45]11 : 52c15103.744507, 36.0960621[0, 65]11 : 52O16m16103.748112, 36.0905132[1, 49]11 : 54c16103.719273, 36.0952293[0, 80]11 : 54O17m17103.727083, 36.0999453[2, 47]11 : 56c17103.696957, 36.1050082[5, 85]11 : 56O18m18103.732319, 36.1051462[2, 47]11 : 58c18103.715839, 36.1059790[10, 80]11 : 58O19m19103.715754, 36.1029270[4, 49]12 : 00c19103.715153, 36.1110411[10, 85]12 : 00O20m20103.720732, 36.1001530[3, 48]12 : 02c20103.703909, 36.0968940[0, 80]12 : 02O21m21103.733177, 36.1058402[4, 51]12 : 04c21103.731203, 36.0948134[0, 80]12 : 04O22m22103.720560, 36.1059792[6, 53]12 : 06c22103.705711, 36.1049382[5, 70]12 : 06O23m23103.712750, 36.1025813[3, 60]12 : 08c23103.715582, 36.0955070[10, 80]12 : 08O24m24103.729916, 36.0991830[4, 70]12 : 10c24103.737640, 36.0952291[5, 95]12 : 10O25m25103.730345, 36.0997371[3, 75]12 : 12c25103.708887, 36.1014711[10, 100]12 : 12O26m26103.722019, 36.1003612[2, 78]12 : 14c26103.704081, 36.1016792[6, 102]12 : 14O27m27103.728199, 36.0998761[0, 80]12 : 16c27103.711805, 36.0949520[0, 100]12 : 16O28m28103.746653, 36.0942581[0, 105]12 : 18c28103.755837, 36.0916921[0, 125]12 : 18O29m29103.748198, 36.0957151[1, 105]12 : 20c29103.757811, 36.0903052[0, 125]12 : 20O30m30103.747854, 36.0934261[2, 109]12 : 22c30103.760300, 36.0896810[5, 130]12 : 22O31m31103.743563, 36.0937041[2, 109]12 : 24c31103.757124, 36.0901661[10, 135]12 : 24O32m32103.741245, 36.0950910[4, 145]12 : 26c32103.739100, 36.1056321[10, 145]12 : 26O33m33103.737211, 36.1049380[3, 107]12 : 28c33103.732061, 36.0968943[0, 140]12 : 28O34m34103.721075, 36.0993912[4, 109]12 : 30c34103.732920, 36.1077121[0, 145]12 : 30O35m35103.720389, 36.0973791[6, 108]12 : 32c35103.722534, 36.1086832[5, 5140]12 : 32O36m36103.714123, 36.1015061[3, 111]12 : 34c36103.734379, 36.1033431[10, 140]12 : 34O37m37103.723993, 36.0971372[4, 113]12 : 36c37103.741074, 36.1031703[5, 130]12 : 36O38m38103.722835, 36.0971711[3, 120]12 : 38c38103.729143, 36.0986282[10, 140]12 : 38O39m39103.725324, 36.0993212[2, 130]12 : 40c39103.737083, 36.0989744[6, 155]12 : 40O40m40103.730044, 36.0939811[0, 135]12 : 42c40103.736396, 36.1060830[0, 160]12 : 42In this paper, the calculation parameters and the running environment of the large case are the same as those of the small one, and the proportion of congested road is about 50%. The results of take-out order allocation and path optimization considering traffic jam or not are shown in Tables6 and 7, respectively.Table 6
Results of order allocation and delivery route without considering congestion.
CourierAllocated orderDelivery routeCourier 1——Courier 2(O14, O21, O24, O32, O33, O37, O38, O39, O40)m14-c14-m21-c21-m24-c24-m32-c32-m33-c33-m38-m37-m39-c38-m40-c39-c37-c40Courier 3(O2, O15, O29)m2-c2-m15-c15-m29-c29Courier 4(O28)m28-c28Courier 5(O3, O4, O6, O7, O8)m3-m8-m4-m6-m7-c8-c3-c4-c6-c7Courier 6——Courier 7(O9, O10, O11, O12, O13, O16, O17, O20, O25, O26, O27)m9-m13-m10-m11-m12-c13-c9-m16-c10-c12-c11-m25-m27-m17-m26-m20-c16-c27-c25-c20-c17-c26Courier 8(O5, O18, O19, O22)m5-c5-m19-m18-m22-c18-c19-c22Courier 9(O23, O34, O35, O36)m23-c23-m35-m34-m36-c35-c34-c36Courier 10(O30, O31)m30-m31-c31-c30Courier 11——Courier 12(O1)m1-c1Table 7
Results of order allocation and delivery route considering congestion.
CourierAllocated orderDelivery routeCourier 1——Courier 2(O11, O12, O33)m12-m11-c12-c11-m33-c33Courier 3(O2, O15, O32, O36, O39)m2-c2-m15-c15-m32-m36-m39-c36-c32-c39Courier 4(O19, O22, O23, O25, O26, O28)m19-c19-m22-m23-m25-c23-c22-c25-m26-c26m28-c28Courier 5(O3, O4, O6, O7, O8, O27)m3-m8-m4-m6-m7-c7-c6-c4-c3-c8-m27-c27Courier 6(O10, O13, O21, O24, O29, O30, O31)m21-m24-m13-c21-m10-c24-c10-m31-m29-m30-c31-c29-c30-c13Courier 7——Courier 8(O5, O9, O17, O20)m5-m9-c5-c9-m17-m20-c20-c17Courier 9(O23, O35, O40)m23-c23-m35-m40-c35-c40Courier 10(O16, O38)m16-c16-m38-c38Courier 11——Courier 12(O1, O14, O18, O34, O37)m1-c1-m14- m18-c14-c18-m34-m37-c34-c37It can be found that, in both condition with or without traffic jam, there are some differences between the result of order allocation and route optimization. The couriers 1, 6, and 11 are not assigned any delivery orders when the traffic status is good, while the couriers 1, 7, and 11 are not assigned any tasks when traffic congestion is happened. The reason for this result is that the objective function of the problem here we studied is to minimize the total system dispatch cost, but not the delivery cost or income balance of single courier.For this numerical test, the system dispatch cost considering traffic jam or not is 41.1540 yuan and 55.0888 yuan, respectively. Through 20 calculations, it can be found that the system dispatch cost under congestion is always greater than that without considering of traffic jam. When considering the road congestion, the delivery cost of some delivery paths increases, so we have to choose congested roads or suboptimal routes for dispatching, which result in the increase of system dispatching cost.This paper calculates 20 times for simple examples and large-scale numerical experiments, respectively, the core program of the algorithm can be obtained fromhttps://github.com/Guofeng-SUN/Takeaway-algorithm-core-program/tree/master, and the computing time of two scale and four cases is shown in Table 8.Table 8
Comparison of numerical test calculation time.
Type of road network congestionTotal computing time (s)Average computing time per order (s)Simple exampleRegardless of road network congestion20.15Consider road network congestion20.15Large-sized numerical experimentsRegardless of road network congestion1122.8Consider road network congestion1142.85It can be found that the computing time is almost the same for the same scale cases. For the average computing time of each order, the one of large-scale examples is significantly longer than that of simple examples. With the increase of the number of couriers and tasks, the scale of the road network is correspondingly expanded, resulting in the sharp increase of the feasible delivery routes. Therefore, the search efficiency of the algorithm in each iteration is also reduced. Although the computing time of large-scale examples has increased, it can still basically meet the application needs in practical according to this scale. In the design of this paper, the connection between nodes is simplified, and all nodes are all connected, which leads to the delivery route obtained by the algorithm being far larger than the actual problem. In practical application, when the number of paths in physical network is reduced, whereas the performance of large-scale commercial computing server is higher, the efficiency of the algorithm will be greatly improved.


## 6. Conclusions

In this paper, order dispatching and route coordination optimization of the take-out system is studied. A route optimization model based on the minimum cost of system dispatch is established to deal with the complexity of space-time network of the take-out dispatch system. Considering the real-time dynamic characteristic of order distribution and route optimization, the coupling relationship between order allocation and route optimization is established based on the delivery process. The main algorithm designed in this paper includes two core parts, one of which is the order allocation algorithm based on the highest efficiency of system dispatch and the other is the route optimization algorithm based on the improved genetic algorithm. A numerical experiment is constructed to verify the effectiveness of the model and the algorithm, and the result of two different traffic status are calculated. The computing results show that the algorithm not only has a better operation efficiency but also can reduce the dispatching cost of the delivery system, therefore has great practical significance.Our current research studies from the perspective of system optimization, which is very necessary in some emergency scenarios, such as the epidemic of COVID-19. In the further research, we will pay more attention to the equilibrium of the order allocation, and continue to study the interactive solution strategies of order allocation and route optimization to realize the real-time optimization of large-scale dispatch problem in the urban system.



---

*Source: 7248492-2020-07-23.xml*