# Integrated Online Order Picking and Vehicle Routing of Food Cold Chain with Demand Surge

Authors: Youhua Chen; Hongjie Lan; Chuan Wang; Xiaoqiong Jia
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

This paper focuses on the effect of demand surge on the food cold chain, where orders arrive online. The demand surge has successively affected the order batching, batch sequencing, and route planning, compared to regular demand. This research studies the integrated optimization of food cold chain order picking and vehicle routing of online orders, where mixed integer programming model is formulated to minimize time-consuming and cost. We firstly useK-means++ algorithm to cluster all customers, and then an online batch processing algorithm is designed in each region. Finally, a genetic algorithm is used to complete the joint optimization of the picking and delivery. We use X enterprise’s e-commerce platform as a case to collect actual operating data to verify the effectiveness of the model and algorithm. And comparing the analysis results between phased optimization and integrated optimization, reasonable suggestions are put forward for management decisions.


---

## Body

## 1. Introduction

With the continuous development of social economy and the continuous improvement of people’s material living standards, people’s demand for cold chain food has gradually increased, and cold chain logistics has developed rapidly. “2021 China Fresh Food e-commerce Data Report” shows that the transaction scale of country’s fresh food e-commerce in 2021 is 465.81 billion yuan, a year-on-year increase of 27.92%, compared with 364.13 billion yuan in 2020.In recent years, e-commerce has developed rapidly, and competition in e-commerce industries such as JD.com, Tmall, and SF Express has become increasingly fierce. Online shopping has become the main force of consumption, and the demand for food has grown exponentially. Due to the perishability, high storage, and delivery costs of cold chain food, frequent online promotions, network broadcast, and other business promotions are operating, and the situation of demand surge often occurs [1].The demand surge has also brought about problems such as warehouse bursting, delayed delivery, and high complaint rates [2]. With demand surge, the most important for merchants are the delivery cost and the fulfillment time of the order. Delivery costs are directly related to the merchant’s interest, while order fulfillment time is directly related to customer satisfaction. For merchants, both are equally important and need to be considered first.Specifically, with demand surge, the types of orders and batches increased. In the case of a surge in the order arrival rate, more orders need to be processed at the same time compared to regular demand, so the processing time of each order is shortened. In addition, the receiving time required by each consumer is inconsistent, which makes it more difficult to coordinate the delivery time window. The occurrence of a demand surge often leads to changes in the entire process. Therefore, the research scope of this paper is set from the order processing stage of customer orders arriving in warehouse to delivery to customers, and we comprehensively consider the order batch picking, time window, and other requirements and conduct research on order picking and route optimization.Unlike regular demand, the order volume changes in real time with special case of demand surge, requiring enterprises to conduct real-time online analysis due to the uncertainty brought by promotional activities. Moreover, when the demand is greater than the highest point of demand fluctuation in a short period of time, it will lead to a shortage of resources in this period, such as limited number of delivery vehicles, limited vehicle, and limited medical resources [3], which will have a greater impact on the delivery route. Compared with the normal demand situation, the demand surge will result in an increase in the number of vehicle deliveries and the number of manual deliveries. The problem of surging demand translates into restricted resource allocation problem.Taking the above issues into consideration, promotions by online retailers often lead to a surge in demand for package delivery during the shopping festival [4]. How to coordinate the order processing and routing optimization of cold chain food and deliver orders to customers on time is very important for merchants. In the process of real-time order arrival, the order is sequenced in batches according to certain rules as the consumer order arrives. If a new order arrives, the newly arrived order is inserted into the appropriate batch, and the online batching is checked in real time. Then, the factors about routing are considered together to achieve the purpose of joint optimization.This paper focuses on the situation of online arrival of orders with demand surge and conducts integrated optimization on the order picking and route planning of cold chain food. On the basis of considering the lowest cost and the shortest time, optimization model is established, and an online algorithm is designed. Through data analysis, the corresponding management implications for the cold chain food distribution of enterprises are given. The contributions of this paper are as follows:To the best of our knowledge, the demand surge is caused by cold chain food promotions and other activities. The demand surge caused by promotion is often uncertain. This paper considers the online arrival of cold chain food orders and carries out joint optimization of order picking and vehicle routing.This article obtains the actual data of merchants for numerical analysis, compares and analyzes the results of offline orders and online orders, joint optimization, and phased optimization, and brings corresponding management inspiration to merchants.The remainder of the paper is organized as follows. In Section2, we briefly review the related literature. In Section 3, we describe in detail the problem we are investigating, and we also formulate it mathematically. Section 4 introduces the main idea we propose in an algorithm for the problem. Section 5 reports on the results of a series of computational experiments performed to assess the methodological contribution of our work. The paper ends with an overview of the work done.


## 2. Literature Review

The demand surge is mostly caused by emergencies, which are man-made events and natural disasters, such as terrorist attacks, earthquakes, disease outbreaks, volcanoes, floods, and storms [5]. These disasters can trigger a massive demand for humanitarian products such as medicines, food, and water.Existing studies mostly attribute demand surge to emergency. Chen et al. [6] proposed a capacity-sharing emergency management model. This model is to deal with demand surge caused by emergencies and build a capacity-oriented strategic alliance to solve the current situation where the current operating system capacity is insufficient and cannot be dealt with. Emphasis is placed on building an emergency management model for horizontal strategic alliance enterprises. Some researchers believe that online retailers face rush orders, which is similar to demand surge [7]. Cui et al. [1] studied the emergency commodity distribution problem under the blowout demand of e-commerce promotion, divided commodities into time response type and time delay type, and carried out two-stage distribution optimization, respectively. Bao [8] studied the two-level vehicle routing optimization problem under the condition of demand blowout, helping enterprises improve distribution efficiency and customer satisfaction and then reduce costs.In recent years, there have been related studies on demand surge caused by promotional activities. Juliang et al. [9] studied the problem of demand surge caused by low-price promotions and optimized pricing and carrier capacity expansion of online retailer with coordination of supply chains. Li et al. [10], Snyder et al. [11], and Lu et al. [12] also conducted research on supply chain coordination. Liu et al. [4] used capacity sharing, which is the collaboration of unmanned vehicles and vehicles, to cope with the demand surge. There are also studies on issues such as resource allocation under emergencies [13], which will not be introduced here.Demand surge in this article refers to the sudden increase in the number of orders placed under promotions and other activities, resulting in insufficient distribution capacity, which in turn causes changes in order picking and routing.From the receipt of order information in the warehouse to the delivery to consumers, it needs to go through multiple stages of optimization, such as order batching, order picking, and route planning. For studies on a single stage, online order picking can be found in Bukchin et al. [14]; Henn [15]; Giannikas et al. [16]; Leung et al. [17]. Studies on online routing planning include Bent and Hentenryck [18]; Flatberg et al. [19]; Hvattum et al. [20]; Ghiani et al. [21]; Ulmer et al. [22]; Wang et al. [23]. There are Osvald and Stirn [24] and Yao et al. [25] about the routing of food cold chain.In recent years, research has gradually shifted from single order batching, order picking, or route optimization to joint research on warehouse processes. Chen [26] pointed out that greater cost savings can be achieved by integrating research rather than improving single stage.Sebastian and Henn [27] studied the joint order batch allocation and sorting problem, obtained the initial solution through the earliest start date rule, and solved it with a variable neighborhood descent and search algorithm, but they did not further joint the picking path problem. Cheng et al. [28] applied the hybrid algorithm of particle swarm optimization algorithm and ant colony algorithm to study the joint order batch and picking path problem and proved that the hybrid algorithm is more effective in terms of solution quality and computational efficiency.Daniel et al. [29] considered order picking and routing optimization at the same time. The difference is that, considering the order feature of due date, the designed iterative local search algorithm shows that the proposed method can generate high quality solutions even for large instances.Moons et al. [30] proposed a record-to-record travel algorithm to solve the integrated order picking-vehicle routing problem that integration can improve service levels; that is, it can shorten the time between order placement and delivery. It is further demonstrated that the ensemble approach provides an average cost savings of 1.8%.However, there are relatively few studies on online joint optimization. Li et al. [31] aimed at the joint optimization of order batching and picker routing based on a famous and typical online retailer of China, which mainly focuses on fast-moving consumer goods, and improved local search ant colony optimization algorithm. Zhang et al. [32] studied the joint optimization of online order picking and distribution, with the goal of minimizing the makespan and distribution cost and designing an online algorithm to solve it. Zhang et al. [33] aimed at the lowest cost and shortest time, studied the online integrated order picking and distribution problem, and proposed an online algorithm to solve the online problem.The above articles only study two of the different stages and did not consider the joint optimization of the three stages at the same time. Kuhn et al. [34] optimized the batching, picking, and routing of orders for the distribution of small items in micro stores and petrol station shops. An extension of the Adaptive Large Neighborhood Search (ALNS) metaheuristic was presented. Managerial insights from general problem data and a case study with a large German grocery retailer support the applicability of the modeling and solution approach suggested in retail practice.Further, most of the research is carried out on ordinary products, and a small part is based on perishable food and cold chain food. Devapriya et al. [35] carried out joint scheduling optimization of production and routing for the practical problems of perishable products. Hai and Zhang considered the routing problem of perishable food, in which picking and distribution were considered in routing planning [36]. Li et al. [37] studied the impact of carbon emissions on the optimization of cold chain integrated inventory routing problem. Four green cold chain inventory routing optimization models for total cost minimization were constructed, and Genetic Simulated Annealing Algorithm was developed. The effectiveness of the algorithm and model is verified by numerical comparison experiments.It is clear from the reviewed literature that many researchers have developed the following factors: single-stage studies, joint studies, study subjects, and online and demand surge. Nonetheless, all these studies consider factors such as partial joint optimization and online optimization in isolation. This study is the first attempt to conduct a joint study of order batching, order picking, and routing optimization, and it includes the impact of demand surge on the fresh cold chain for online optimization. Table1 presents a comparison between the problems raised in this paper and other literature.Table 1
Comparison of the major attributes in this paper against similar literature.
LiteratureIntegrated optimizationResearch objectOnlineDemand surgeOrder batchingOrder pickingRoutingProductsPerishable productsFood cold chainCui et al. [1]√√√Sebastian and Henn [27]√√√Cheng et al. [28]√√√Li et al. [31]√√√√Moons et al. [30]√√√Bao [8]√√√Zhang et al. [32]√√√√Li et al. [37]√√√Ju-Hai and Zhang [36]√√√Kuhn et al. [34]√√√√√Zhang et al. [33]√√√√This paper√√√√√√


## 3. Model Construction of Integrated Optimization

This paper studies the construction of the model for the online real-time arrival of orders under the self-built distribution mode of enterprises. In the case of a surge demand, real-time dynamic optimal delivery time and delivery route are found, considering the online arrival of orders and vehicle conditions and allocating the orders to the most suitable batch and the most suitable batch at the correct and appropriate time.


### 3.1. Problem Statement and Model Assumption

The problem described in this paper is the joint optimization problem of order processing and route planning of online arrival. The research phase includes order distribution scheduling and delivery. The main difference lies in the order batching and batch sequencing of phaseI. In the stage of order picking and batch sequencing, the problems that need to be solved are as follows:(1)
How to allocate online orders according to dynamic batching rules and insert them into different batches;(2)
Online sequencing of batches.The problems that need to be solved in stage of delivery are as follows:(1)
The delivery time and service time of the vehicle;(2)
The set of orders belonging to the same batch and set of orders batches belonging to the same vehicle;(3)
Route planning of vehicles in each area according to different customer orders.In order to meet the above problems, this article makes the following assumptions:The order information considered in this paper is unknown, and it is allocated dynamically in real time;There is more than one vehicle in each delivery area to provide service;Assuming that each customer has only one order and order splitting is not allowed; that is, the same order is serviced by one vehicle;Assuming that only when the capacity is insufficient during demand surge, vehicles can be rented, and the types of rented vehicles can be different. Except for the rented vehicles, the owned vehicles are all of the same type;The capacity of batching is less than the capacity of vehicle, a batch of orders is served by one vehicle, one batch has multiple orders, and one vehicle has multiple batches.


### 3.2. Parameter Settings

Settings:Set of orders:N=1,2,…,n, representing all orders at time t∈0,+∞;Set of orders with DC:No=0,1,2,…,n;Set of vehicles:V=1,2,…,u,u+1,…,w; 1,u are enterprise-owned vehicles, u+1,w are rented vehicles.Set of order batching:H=1,2,…,h;Set of delivery routing:R=1,2,…,r;Set of delivery regions:O=1,2,…,o;Parameters:qi: The number of items included in order i, i∈N;Qh: The maximum number of items that each batch h can hold, h∈H;Qv: Maximum load capacity of vehicle v, v∈V;Mv: Total delivery times of vehicle v, v∈V;tij: The time it takes for a vehicle from customer i to customer j, i,j∈N0;Ti: Average service time required for customer i;tiearliest: The earliest time that customer i can receive the order to be delivered;tilatest: The latest time that customer i can receive the order to be delivered;tiarrive: Arriving time of customer order i;dij: The distance between customer i and customer j;lvmax: The farthest mileage of vehicle v;cipick: Unit picking cost of order i;cufixed: Fixed cost u per using of own vehicle;cwfixed: Fixed cost w per using of rented vehicle;cup: Unit delivery cost of own vehicle u;cwp: Unit delivery cost of rented vehicle w;ciearliest: The unit penalty cost placed earlier than the earliest acceptable time by the customer;cilatest: The unit penalty cost placed later than the latest acceptable time by the customer;α: Proportion of stock-out loss during delivery;β: Proportion of stock-out loss during loading and unloading;θ: Average cost of stock-out loss of the order;Decision variables:thstart: Start picking time of batch h,h∈H;thsevice: The time required for the batch h picking to complete, h∈H;ticomplete: Picking completion time of order i (the batching);tmvleave: Time when vehicle v left the distribution center for the m th time;tmvend: Time for vehicle v to complete the m th delivery;ri: Flow of customer i;xih=1,if orderiis allocated to order batchingh;0,otherwise;i=1,…,n, h=1,…,H.yimv=1,if orderiis allocated to themth delivery of vehiclevincluding own vehiclesuand rented vehiclesw;0,otherwise;h=1,…,H, v=1,…,w.zijmv=1,if themth delivery of vehiclevis delivered from customerito customer pointj;0,otherwise;i=1,…,n, j=1,…,n, v=1,…,w.τio=1,if the service address of orderibelong to delivery areao;0,otherwise;i=1,…,n, o=1,…,O.δhr=1,if order batchinghis allocated to delivery router;0,otherwise;h=1,…,H, r=1,…,R.σor=1,if delivery routerbelong to delivery areao;0,otherwise;r=1,…,R, o=1,…,O.


### 3.3. Model Construction

To build a model for the integrated optimization of food cold chain order picking and route planning under demand surge, the online order model processes orders in real time and dynamic. This paper is based on minimizing order fulfillment time and total cost to establish a mathematical model.


#### 3.3.1. Time Function

(1)minf1=minmv∈MVtmvend,(2)tmvend=tmvleave+∑i∈Nzoimvtoi+∑i∈N∑j∈Nzijmvtij+∑j∈Nzjomvtjo+∑i∈N∑j∈NzijmvTi.Equation (1) is one of the objective functions, representing the order fulfillment time. Equation (2) refers to the end time when the vehicle leaves the distribution center and then returns to the distribution center.


#### 3.3.2. Cost Function

The cost function includes order picking cost, vehicle fixed cost, delivery cost, stock-out loss cost, and time penalty cost.(1) Order Picking Cost. The demand surge will lead to increased order picking time and picking costs. In addition to the inevitable increase in picking time, picking costs such as labor costs will also increase. Therefore, the order picking cost function is(3)C1=∑i=1N∑h=1Hticompletecipickxih.(2) Vehicle Fixed Cost. The fixed cost of a vehicle is the relatively fixed consumption in the delivery process, regardless of the loading capacity. In the case of a demand surge, it is difficult for its own production capacity to meet the delivery requirements, and it is often necessary to rent vehicles. Therefore, the total fixed cost of a vehicle is divided into two parts: one is the fixed cost of owning vehicles, and the other is the fixed cost of rented vehicles. Whether or not to use a rented vehicle is determined by the 0–1 variable zijmv. Therefore, the fixed cost of the vehicle is(4)C2=∑j=1N∑u=1U∑mu=1Mucufixedzojmv+∑j=1N∑w=u+1W∑mw=1Mwcwfixedzojmw.(3) Delivery Cost. The delivery cost is related to the vehicle delivery distance and delivery time caroused by the vehicle te and generally has a positive correlation with vehicle delivery distance or delivery time. This paper adopts an expression that is positively correlated with delivery time. The same as C2, the cost of delivery vehicles is divided into two parts: one is the delivery cost of the company’s own vehicles, and the other is the delivery cost of the rented vehicles:(5)C3=∑i=0N∑j=1N∑u=1U∑mu=1Mucuptijzijmv+∑i=0N∑j=1N∑w=u+1W∑mw=1Mwcwptijzijmw.(4) Stock-Out Loss Cost. Considering changes in the external environment such as temperature and humidity, especially in the process of delivery and loading and unloading, it is very easy to cause loss due to the particularity of fresh food, which needs to be reflected in the model. This paper considers the unit loss of fresh food and the proportion of stock-out loss in delivery and loading and unloading. Therefore, the total loss cost of fresh food is(6)C4=∑i=0N∑j=1N∑v=1V∑mv=1Mvzijmvθαtij+βqi.(5) Time Penalty Cost. Due to the demand surge, it is inevitable that there will be delays in delivery or early arrival, no matter in any process of order picking, batch sequencing, and delivery. The time penalty cost is(7)C5=∑i=0N∑j=1N∑v=1V∑mv=1Mvciearliestzijmvmaxtiearliest−tiarrive,o,+∑i=0N∑j=1N∑v=1V∑mv=1Mvcilatestzijmvmaxtilatest−tiarrive,o.In summary, the cost part of objective function is(8)minf2=C1+C2+C3+C4+C5,=∑i=1N∑h=1Hticompletecipickxih+∑j=1N∑u=1U∑mu=1Mucufixedzojmv+∑j=1N∑w=u+1W∑mw=1Mwcwfixedzojmw+∑i=0N∑j=1N∑u=1U∑mu=1Mucuptijzijmv+∑i=0N∑j=1N∑w=u+1W∑mw=1Mwcwptijzijmw+∑i=0N∑j=1N∑v=1V∑mv=1Mvzijmvθαtij+βqi+∑i=0N∑j=1N∑v=1V∑mv=1Mvciearliestzijmvmaxtiearliest−tiarrive,o+∑i=0N∑j=1N∑v=1V∑mv=1Mvcilatestzijmvmaxtilatest−tiarrive,o.Since the functionf1 and the function f2 have different dimensions, f1 is a time function, and f2 is a cost function. The model is normalized:(9)minF=minηf1+min1−ηf2=minηtvleave+∑i∈Nzojmvtoj+∑i∈N∑j∈Nzijmvtij+∑i∈Nziomvtio+∑i∈N∑j∈NzijmvTi+min1−η∑i=1N∑h=1Hticompletecipickxih=∑j=1N∑u=1U∑mu=1Mucufixedzojmv+∑j=1N∑w=u+1W∑mw=1Mwcwfixedzojmw+∑i=0N∑j=1N∑u=1U∑mu=1Mucuptijzijmv+∑i=0N∑j=1N∑w=u+1W∑mw=1Mwcwptijzijmw+∑i=0N∑j=1N∑v=1V∑mv=1Mvzijmvθαtij+βqi+∑i=0N∑j=1N∑v=1V∑mv=1Mvciearliestzijmvmaxtiearliest−tiarrive,o+∑i=0N∑j=1N∑v=1V∑mv=1Mvcilatestzijmvmaxtilatest−tiarrive,o,(10)s.t.:∑h∈Hxih=1,∀i∈N,(11)∑i∈Nxihqi≤Qh,∀h∈H,(12)thpick=thstart+thservice∀h∈H,(13)ticomplete=∑h∈Hxihthpick,∀i∈N,(14)tmvleave=maxticompleteyimv,∀v∈V,∀mv∈Mv,∀i∈N,(15)∑i∈N∑j∈Nqizijmv≤Qv,∀v∈V,∀mv∈Mv,(16)∑v∈V∑mv=1Mvyimv=∑vMv,i=01,i∈N,(17)∑i∈N∑v∈V∑mv=1Mvzijmv=∑vMv,j=01,j∈N,(18)∑j∈N0zijmv=yimv,∀i∈N0,v∈V,∀mv∈Mv,(19)∑j∈Nz0jmv=1,∀v∈V,∀mv∈Mv,(20)r0=0,(21)rj−ri≥qi+Qv∑v∈V∑mv=1Mvzijmv−Qv,∀i∈N0,j∈N,(22)rj≤∑i∈N∑v∈V∑mv=1MvzijmvQV,∀j∈N,(23)∑i=0N0∑j=1Nzijmvdij≤lvmax,∀i,j∈N,∀v∈V,∀mv∈Mv,(24)tij≥0,i,j∈N,(25)tmv+1leave≥tmvend,∀mv≤Mv−1,(26)cwfixed≥cufixed,(27)cwp≥cup.Constraint (10) ensures that each order can only be allocated to one order batch. Constraint (11) ensures that the maximum amount of items that can be accommodated in each batch does not exceed Qh. Constraint (12) represents the entire time including the start picking time and service time for order batch h to complete the picking. Constraint (13) represents the picking completion time of the order. Constraint (14) indicates the time when the vehicle leaves the distribution center after the batch picking of all orders belonging to vehicle v is completed in the m th delivery. Constraint (15) represents that the numbers of orders cannot exceed vehicles’ maximum capacity in the m th delivery. Constraint (16) represents that customer i is only served by one vehicle v in its’ m th delivery. Constraint (17) represents that the vehicle departs from distribution center and finally returns to distribution center in the m th delivery. Constraint (18) represents that if the vehicle service is at the customer i, it must leave from customer i in the m th delivery. Constraint (19) represents that the m th delivery of vehicle v leaves once from the distribution center. Constraints (20)–(22) represent the flow restriction of the customer. Constraint (23) represents that the total mileage cannot exceed the maximum mileage of the vehicle. Constraint (24) represents that the delivery time of the vehicle is not less than zero. Constraint (25) ensures that the m+1 th departure time of the v th car is later than the end time of the m th time. Constraint (26) represents that the fixed cost of rented vehicle w is greater than the fixed cost of own vehicles u for each use. Constraint (27) represents that the delivery cost of rented vehicle w per unit time is greater than that of owning a vehicle u per unit time.


## 3.1. Problem Statement and Model Assumption

The problem described in this paper is the joint optimization problem of order processing and route planning of online arrival. The research phase includes order distribution scheduling and delivery. The main difference lies in the order batching and batch sequencing of phaseI. In the stage of order picking and batch sequencing, the problems that need to be solved are as follows:(1)
How to allocate online orders according to dynamic batching rules and insert them into different batches;(2)
Online sequencing of batches.The problems that need to be solved in stage of delivery are as follows:(1)
The delivery time and service time of the vehicle;(2)
The set of orders belonging to the same batch and set of orders batches belonging to the same vehicle;(3)
Route planning of vehicles in each area according to different customer orders.In order to meet the above problems, this article makes the following assumptions:The order information considered in this paper is unknown, and it is allocated dynamically in real time;There is more than one vehicle in each delivery area to provide service;Assuming that each customer has only one order and order splitting is not allowed; that is, the same order is serviced by one vehicle;Assuming that only when the capacity is insufficient during demand surge, vehicles can be rented, and the types of rented vehicles can be different. Except for the rented vehicles, the owned vehicles are all of the same type;The capacity of batching is less than the capacity of vehicle, a batch of orders is served by one vehicle, one batch has multiple orders, and one vehicle has multiple batches.


## 3.2. Parameter Settings

Settings:Set of orders:N=1,2,…,n, representing all orders at time t∈0,+∞;Set of orders with DC:No=0,1,2,…,n;Set of vehicles:V=1,2,…,u,u+1,…,w; 1,u are enterprise-owned vehicles, u+1,w are rented vehicles.Set of order batching:H=1,2,…,h;Set of delivery routing:R=1,2,…,r;Set of delivery regions:O=1,2,…,o;Parameters:qi: The number of items included in order i, i∈N;Qh: The maximum number of items that each batch h can hold, h∈H;Qv: Maximum load capacity of vehicle v, v∈V;Mv: Total delivery times of vehicle v, v∈V;tij: The time it takes for a vehicle from customer i to customer j, i,j∈N0;Ti: Average service time required for customer i;tiearliest: The earliest time that customer i can receive the order to be delivered;tilatest: The latest time that customer i can receive the order to be delivered;tiarrive: Arriving time of customer order i;dij: The distance between customer i and customer j;lvmax: The farthest mileage of vehicle v;cipick: Unit picking cost of order i;cufixed: Fixed cost u per using of own vehicle;cwfixed: Fixed cost w per using of rented vehicle;cup: Unit delivery cost of own vehicle u;cwp: Unit delivery cost of rented vehicle w;ciearliest: The unit penalty cost placed earlier than the earliest acceptable time by the customer;cilatest: The unit penalty cost placed later than the latest acceptable time by the customer;α: Proportion of stock-out loss during delivery;β: Proportion of stock-out loss during loading and unloading;θ: Average cost of stock-out loss of the order;Decision variables:thstart: Start picking time of batch h,h∈H;thsevice: The time required for the batch h picking to complete, h∈H;ticomplete: Picking completion time of order i (the batching);tmvleave: Time when vehicle v left the distribution center for the m th time;tmvend: Time for vehicle v to complete the m th delivery;ri: Flow of customer i;xih=1,if orderiis allocated to order batchingh;0,otherwise;i=1,…,n, h=1,…,H.yimv=1,if orderiis allocated to themth delivery of vehiclevincluding own vehiclesuand rented vehiclesw;0,otherwise;h=1,…,H, v=1,…,w.zijmv=1,if themth delivery of vehiclevis delivered from customerito customer pointj;0,otherwise;i=1,…,n, j=1,…,n, v=1,…,w.τio=1,if the service address of orderibelong to delivery areao;0,otherwise;i=1,…,n, o=1,…,O.δhr=1,if order batchinghis allocated to delivery router;0,otherwise;h=1,…,H, r=1,…,R.σor=1,if delivery routerbelong to delivery areao;0,otherwise;r=1,…,R, o=1,…,O.


## 3.3. Model Construction

To build a model for the integrated optimization of food cold chain order picking and route planning under demand surge, the online order model processes orders in real time and dynamic. This paper is based on minimizing order fulfillment time and total cost to establish a mathematical model.


### 3.3.1. Time Function

(1)minf1=minmv∈MVtmvend,(2)tmvend=tmvleave+∑i∈Nzoimvtoi+∑i∈N∑j∈Nzijmvtij+∑j∈Nzjomvtjo+∑i∈N∑j∈NzijmvTi.Equation (1) is one of the objective functions, representing the order fulfillment time. Equation (2) refers to the end time when the vehicle leaves the distribution center and then returns to the distribution center.


### 3.3.2. Cost Function

The cost function includes order picking cost, vehicle fixed cost, delivery cost, stock-out loss cost, and time penalty cost.(1) Order Picking Cost. The demand surge will lead to increased order picking time and picking costs. In addition to the inevitable increase in picking time, picking costs such as labor costs will also increase. Therefore, the order picking cost function is(3)C1=∑i=1N∑h=1Hticompletecipickxih.(2) Vehicle Fixed Cost. The fixed cost of a vehicle is the relatively fixed consumption in the delivery process, regardless of the loading capacity. In the case of a demand surge, it is difficult for its own production capacity to meet the delivery requirements, and it is often necessary to rent vehicles. Therefore, the total fixed cost of a vehicle is divided into two parts: one is the fixed cost of owning vehicles, and the other is the fixed cost of rented vehicles. Whether or not to use a rented vehicle is determined by the 0–1 variable zijmv. Therefore, the fixed cost of the vehicle is(4)C2=∑j=1N∑u=1U∑mu=1Mucufixedzojmv+∑j=1N∑w=u+1W∑mw=1Mwcwfixedzojmw.(3) Delivery Cost. The delivery cost is related to the vehicle delivery distance and delivery time caroused by the vehicle te and generally has a positive correlation with vehicle delivery distance or delivery time. This paper adopts an expression that is positively correlated with delivery time. The same as C2, the cost of delivery vehicles is divided into two parts: one is the delivery cost of the company’s own vehicles, and the other is the delivery cost of the rented vehicles:(5)C3=∑i=0N∑j=1N∑u=1U∑mu=1Mucuptijzijmv+∑i=0N∑j=1N∑w=u+1W∑mw=1Mwcwptijzijmw.(4) Stock-Out Loss Cost. Considering changes in the external environment such as temperature and humidity, especially in the process of delivery and loading and unloading, it is very easy to cause loss due to the particularity of fresh food, which needs to be reflected in the model. This paper considers the unit loss of fresh food and the proportion of stock-out loss in delivery and loading and unloading. Therefore, the total loss cost of fresh food is(6)C4=∑i=0N∑j=1N∑v=1V∑mv=1Mvzijmvθαtij+βqi.(5) Time Penalty Cost. Due to the demand surge, it is inevitable that there will be delays in delivery or early arrival, no matter in any process of order picking, batch sequencing, and delivery. The time penalty cost is(7)C5=∑i=0N∑j=1N∑v=1V∑mv=1Mvciearliestzijmvmaxtiearliest−tiarrive,o,+∑i=0N∑j=1N∑v=1V∑mv=1Mvcilatestzijmvmaxtilatest−tiarrive,o.In summary, the cost part of objective function is(8)minf2=C1+C2+C3+C4+C5,=∑i=1N∑h=1Hticompletecipickxih+∑j=1N∑u=1U∑mu=1Mucufixedzojmv+∑j=1N∑w=u+1W∑mw=1Mwcwfixedzojmw+∑i=0N∑j=1N∑u=1U∑mu=1Mucuptijzijmv+∑i=0N∑j=1N∑w=u+1W∑mw=1Mwcwptijzijmw+∑i=0N∑j=1N∑v=1V∑mv=1Mvzijmvθαtij+βqi+∑i=0N∑j=1N∑v=1V∑mv=1Mvciearliestzijmvmaxtiearliest−tiarrive,o+∑i=0N∑j=1N∑v=1V∑mv=1Mvcilatestzijmvmaxtilatest−tiarrive,o.Since the functionf1 and the function f2 have different dimensions, f1 is a time function, and f2 is a cost function. The model is normalized:(9)minF=minηf1+min1−ηf2=minηtvleave+∑i∈Nzojmvtoj+∑i∈N∑j∈Nzijmvtij+∑i∈Nziomvtio+∑i∈N∑j∈NzijmvTi+min1−η∑i=1N∑h=1Hticompletecipickxih=∑j=1N∑u=1U∑mu=1Mucufixedzojmv+∑j=1N∑w=u+1W∑mw=1Mwcwfixedzojmw+∑i=0N∑j=1N∑u=1U∑mu=1Mucuptijzijmv+∑i=0N∑j=1N∑w=u+1W∑mw=1Mwcwptijzijmw+∑i=0N∑j=1N∑v=1V∑mv=1Mvzijmvθαtij+βqi+∑i=0N∑j=1N∑v=1V∑mv=1Mvciearliestzijmvmaxtiearliest−tiarrive,o+∑i=0N∑j=1N∑v=1V∑mv=1Mvcilatestzijmvmaxtilatest−tiarrive,o,(10)s.t.:∑h∈Hxih=1,∀i∈N,(11)∑i∈Nxihqi≤Qh,∀h∈H,(12)thpick=thstart+thservice∀h∈H,(13)ticomplete=∑h∈Hxihthpick,∀i∈N,(14)tmvleave=maxticompleteyimv,∀v∈V,∀mv∈Mv,∀i∈N,(15)∑i∈N∑j∈Nqizijmv≤Qv,∀v∈V,∀mv∈Mv,(16)∑v∈V∑mv=1Mvyimv=∑vMv,i=01,i∈N,(17)∑i∈N∑v∈V∑mv=1Mvzijmv=∑vMv,j=01,j∈N,(18)∑j∈N0zijmv=yimv,∀i∈N0,v∈V,∀mv∈Mv,(19)∑j∈Nz0jmv=1,∀v∈V,∀mv∈Mv,(20)r0=0,(21)rj−ri≥qi+Qv∑v∈V∑mv=1Mvzijmv−Qv,∀i∈N0,j∈N,(22)rj≤∑i∈N∑v∈V∑mv=1MvzijmvQV,∀j∈N,(23)∑i=0N0∑j=1Nzijmvdij≤lvmax,∀i,j∈N,∀v∈V,∀mv∈Mv,(24)tij≥0,i,j∈N,(25)tmv+1leave≥tmvend,∀mv≤Mv−1,(26)cwfixed≥cufixed,(27)cwp≥cup.Constraint (10) ensures that each order can only be allocated to one order batch. Constraint (11) ensures that the maximum amount of items that can be accommodated in each batch does not exceed Qh. Constraint (12) represents the entire time including the start picking time and service time for order batch h to complete the picking. Constraint (13) represents the picking completion time of the order. Constraint (14) indicates the time when the vehicle leaves the distribution center after the batch picking of all orders belonging to vehicle v is completed in the m th delivery. Constraint (15) represents that the numbers of orders cannot exceed vehicles’ maximum capacity in the m th delivery. Constraint (16) represents that customer i is only served by one vehicle v in its’ m th delivery. Constraint (17) represents that the vehicle departs from distribution center and finally returns to distribution center in the m th delivery. Constraint (18) represents that if the vehicle service is at the customer i, it must leave from customer i in the m th delivery. Constraint (19) represents that the m th delivery of vehicle v leaves once from the distribution center. Constraints (20)–(22) represent the flow restriction of the customer. Constraint (23) represents that the total mileage cannot exceed the maximum mileage of the vehicle. Constraint (24) represents that the delivery time of the vehicle is not less than zero. Constraint (25) ensures that the m+1 th departure time of the v th car is later than the end time of the m th time. Constraint (26) represents that the fixed cost of rented vehicle w is greater than the fixed cost of own vehicles u for each use. Constraint (27) represents that the delivery cost of rented vehicle w per unit time is greater than that of owning a vehicle u per unit time.


## 3.3.1. Time Function

(1)minf1=minmv∈MVtmvend,(2)tmvend=tmvleave+∑i∈Nzoimvtoi+∑i∈N∑j∈Nzijmvtij+∑j∈Nzjomvtjo+∑i∈N∑j∈NzijmvTi.Equation (1) is one of the objective functions, representing the order fulfillment time. Equation (2) refers to the end time when the vehicle leaves the distribution center and then returns to the distribution center.


## 3.3.2. Cost Function

The cost function includes order picking cost, vehicle fixed cost, delivery cost, stock-out loss cost, and time penalty cost.(1) Order Picking Cost. The demand surge will lead to increased order picking time and picking costs. In addition to the inevitable increase in picking time, picking costs such as labor costs will also increase. Therefore, the order picking cost function is(3)C1=∑i=1N∑h=1Hticompletecipickxih.(2) Vehicle Fixed Cost. The fixed cost of a vehicle is the relatively fixed consumption in the delivery process, regardless of the loading capacity. In the case of a demand surge, it is difficult for its own production capacity to meet the delivery requirements, and it is often necessary to rent vehicles. Therefore, the total fixed cost of a vehicle is divided into two parts: one is the fixed cost of owning vehicles, and the other is the fixed cost of rented vehicles. Whether or not to use a rented vehicle is determined by the 0–1 variable zijmv. Therefore, the fixed cost of the vehicle is(4)C2=∑j=1N∑u=1U∑mu=1Mucufixedzojmv+∑j=1N∑w=u+1W∑mw=1Mwcwfixedzojmw.(3) Delivery Cost. The delivery cost is related to the vehicle delivery distance and delivery time caroused by the vehicle te and generally has a positive correlation with vehicle delivery distance or delivery time. This paper adopts an expression that is positively correlated with delivery time. The same as C2, the cost of delivery vehicles is divided into two parts: one is the delivery cost of the company’s own vehicles, and the other is the delivery cost of the rented vehicles:(5)C3=∑i=0N∑j=1N∑u=1U∑mu=1Mucuptijzijmv+∑i=0N∑j=1N∑w=u+1W∑mw=1Mwcwptijzijmw.(4) Stock-Out Loss Cost. Considering changes in the external environment such as temperature and humidity, especially in the process of delivery and loading and unloading, it is very easy to cause loss due to the particularity of fresh food, which needs to be reflected in the model. This paper considers the unit loss of fresh food and the proportion of stock-out loss in delivery and loading and unloading. Therefore, the total loss cost of fresh food is(6)C4=∑i=0N∑j=1N∑v=1V∑mv=1Mvzijmvθαtij+βqi.(5) Time Penalty Cost. Due to the demand surge, it is inevitable that there will be delays in delivery or early arrival, no matter in any process of order picking, batch sequencing, and delivery. The time penalty cost is(7)C5=∑i=0N∑j=1N∑v=1V∑mv=1Mvciearliestzijmvmaxtiearliest−tiarrive,o,+∑i=0N∑j=1N∑v=1V∑mv=1Mvcilatestzijmvmaxtilatest−tiarrive,o.In summary, the cost part of objective function is(8)minf2=C1+C2+C3+C4+C5,=∑i=1N∑h=1Hticompletecipickxih+∑j=1N∑u=1U∑mu=1Mucufixedzojmv+∑j=1N∑w=u+1W∑mw=1Mwcwfixedzojmw+∑i=0N∑j=1N∑u=1U∑mu=1Mucuptijzijmv+∑i=0N∑j=1N∑w=u+1W∑mw=1Mwcwptijzijmw+∑i=0N∑j=1N∑v=1V∑mv=1Mvzijmvθαtij+βqi+∑i=0N∑j=1N∑v=1V∑mv=1Mvciearliestzijmvmaxtiearliest−tiarrive,o+∑i=0N∑j=1N∑v=1V∑mv=1Mvcilatestzijmvmaxtilatest−tiarrive,o.Since the functionf1 and the function f2 have different dimensions, f1 is a time function, and f2 is a cost function. The model is normalized:(9)minF=minηf1+min1−ηf2=minηtvleave+∑i∈Nzojmvtoj+∑i∈N∑j∈Nzijmvtij+∑i∈Nziomvtio+∑i∈N∑j∈NzijmvTi+min1−η∑i=1N∑h=1Hticompletecipickxih=∑j=1N∑u=1U∑mu=1Mucufixedzojmv+∑j=1N∑w=u+1W∑mw=1Mwcwfixedzojmw+∑i=0N∑j=1N∑u=1U∑mu=1Mucuptijzijmv+∑i=0N∑j=1N∑w=u+1W∑mw=1Mwcwptijzijmw+∑i=0N∑j=1N∑v=1V∑mv=1Mvzijmvθαtij+βqi+∑i=0N∑j=1N∑v=1V∑mv=1Mvciearliestzijmvmaxtiearliest−tiarrive,o+∑i=0N∑j=1N∑v=1V∑mv=1Mvcilatestzijmvmaxtilatest−tiarrive,o,(10)s.t.:∑h∈Hxih=1,∀i∈N,(11)∑i∈Nxihqi≤Qh,∀h∈H,(12)thpick=thstart+thservice∀h∈H,(13)ticomplete=∑h∈Hxihthpick,∀i∈N,(14)tmvleave=maxticompleteyimv,∀v∈V,∀mv∈Mv,∀i∈N,(15)∑i∈N∑j∈Nqizijmv≤Qv,∀v∈V,∀mv∈Mv,(16)∑v∈V∑mv=1Mvyimv=∑vMv,i=01,i∈N,(17)∑i∈N∑v∈V∑mv=1Mvzijmv=∑vMv,j=01,j∈N,(18)∑j∈N0zijmv=yimv,∀i∈N0,v∈V,∀mv∈Mv,(19)∑j∈Nz0jmv=1,∀v∈V,∀mv∈Mv,(20)r0=0,(21)rj−ri≥qi+Qv∑v∈V∑mv=1Mvzijmv−Qv,∀i∈N0,j∈N,(22)rj≤∑i∈N∑v∈V∑mv=1MvzijmvQV,∀j∈N,(23)∑i=0N0∑j=1Nzijmvdij≤lvmax,∀i,j∈N,∀v∈V,∀mv∈Mv,(24)tij≥0,i,j∈N,(25)tmv+1leave≥tmvend,∀mv≤Mv−1,(26)cwfixed≥cufixed,(27)cwp≥cup.Constraint (10) ensures that each order can only be allocated to one order batch. Constraint (11) ensures that the maximum amount of items that can be accommodated in each batch does not exceed Qh. Constraint (12) represents the entire time including the start picking time and service time for order batch h to complete the picking. Constraint (13) represents the picking completion time of the order. Constraint (14) indicates the time when the vehicle leaves the distribution center after the batch picking of all orders belonging to vehicle v is completed in the m th delivery. Constraint (15) represents that the numbers of orders cannot exceed vehicles’ maximum capacity in the m th delivery. Constraint (16) represents that customer i is only served by one vehicle v in its’ m th delivery. Constraint (17) represents that the vehicle departs from distribution center and finally returns to distribution center in the m th delivery. Constraint (18) represents that if the vehicle service is at the customer i, it must leave from customer i in the m th delivery. Constraint (19) represents that the m th delivery of vehicle v leaves once from the distribution center. Constraints (20)–(22) represent the flow restriction of the customer. Constraint (23) represents that the total mileage cannot exceed the maximum mileage of the vehicle. Constraint (24) represents that the delivery time of the vehicle is not less than zero. Constraint (25) ensures that the m+1 th departure time of the v th car is later than the end time of the m th time. Constraint (26) represents that the fixed cost of rented vehicle w is greater than the fixed cost of own vehicles u for each use. Constraint (27) represents that the delivery cost of rented vehicle w per unit time is greater than that of owning a vehicle u per unit time.


## 4. Algorithm

The main idea of this part is first to batch all orders that have arrived but not picked in batches at the current moment; then, check the current number of orders, which have been assigned on the vehicle. If it is less than a certain number, wait for a period of time. After reaching a certain value, the vehicle will be dispatched. If it is more than a certain quantity, it is necessary to judge whether its own capacity is sufficient. If the own capacity is not enough to support the delivery of all orders, then external forces, such as vehicle renting, will be required. Finally, optimization of route planning will be done. Therefore, the algorithm in this paper uses three steps to solve the problem. The first step usesK-means++ clustering to classify customer areas, and the historical orders are used as the clustering standard; the second step is online batching and picking of orders; the third step is to optimize the route planning.


### 4.1. Customer Clustering

According to all the historical orders and the regional situation of vehicles, the following calculations are carried out for each divided region.K-means++ algorithm can be used for classification.


### 4.2. Online Batching Algorithm

In order to simplify the model, it is set as a single picking channel, and the following points are mainly considered in the online batching algorithm.(1)
Set the upper limit of the delay time ast=mintihlatest−thsevice−toi, the maximum delay time of each picking batch, mintihlatest is the latest delivery time allowed for the order i with the earliest time window in one of the batches, thsevice is the completion time of pick batching, and toi is the distance time from the distribution center to the customer;(2)
If the batch quantity is 1, and the time does not reach the upper limit of the delay time, wait for the arrival of next order;(3)
If the batch quantity is greater than 1, and the time does not reach the upper limit of the delay time, the batch with the smallest service time will be selected.The specific steps of the algorithm are as follows:(1)
Initialization: sett=0, and Ut is the current set of orders that have arrived but not picked, U0=i|tiarrive=0;(2)
ConvertUt order set to Ht batch set. Batching is to divide the orders in each area separately, where Qb represents the maximum capacity that can be accepted by pickers or machines. Ht is the cardinality of the set Ht, if Ht=0, it means that no order arrives at the current moment; go to step (4); if Ht≥1 and t≥mintihlatest−thsevice−toi, the batch with the longest service time at the current moment is allocated to the earliest idle picker or machine, and the order is inserted into the appropriate order batch. It is the time when the picking is completed and the region to which the order belongs are determined. In addition, set the value of t to the earliest idle time of the picker or machine, and return to step (2). If t≤mintihlatest−thsevice−toi, go to step (3);(3)
IfHt1, set the value of t to minmintihlatest−thsevice−toi,ti+1arrive, and ti+1arrive is the arrival time of the i+1th order, which is the arrival time of the next order. Assign the current batch to the earliest idle picker or machine, set the value of t to the earliest idle time of the picker or machine, and return to step (2). If Ht>1 and the batch with the shortest service time at the current moment is assigned to the earliest idle picker or machine, and the value of t is set to the earliest idle time of the picker or machine, return to step (2);(4)
If there are still orders arriving, sett=ti+1arrive and return to step (2); otherwise, end.


### 4.3. Optimization of Route Planning

The route of vehicle is optimized by genetic algorithm. Suppose that the number of rental vehicles in the area isP, and the delivery vehicle in the area is defined as K=1,2,…P,P+1, and P+1 is its own delivery vehicles of the area, and the objective function of the genetic algorithm is(28)minf=min∑v=1P+1ηC1′+C2′+C3′+C4′+C5′+1−ηtvleave+∑jdvojsVv+P1sign1+P2sign2,C1′=∑i=1nkticompletecipickxiP+1,C2′=∑i=1nkcufixedzojP+1+∑j=1nk∑w=1Pcwfixedzojw,C3′=∑i=0nk∑j=1nkcvptijzijP+1+∑i=0nk∑j=1nk∑w=1Pcwptijzijw,C4′=∑i=0nk∑j=1nk∑v=1P+1zijvθαtij+βqi,C5′=∑i=0nk∑j=1nk∑v=1P+1ciearliestzijvmaxtiearliest−tiarrive,o+∑i=0nk∑j=1nk∑v=1P+1cilatestzijvmaxtilatest−tiarrive,o.C1′+C2′+C3′+C4′+C5′ is the corresponding cost function, tvleave+∑jdvojs/Vv is the end time of the vth vehicle, and sign1 represents whether the current plan exceeds the maximum vehicle capacity; if it exceeds, it is 1; otherwise, it is 0. P1 is the corresponding penalty coefficient, and generally the value should be greater than the cost function value. Sign2 indicates whether the current plan meets the customer’s time window requirements, with 0 for satisfaction and 1 for dissatisfaction. P2 is the corresponding penalty coefficient, and generally the value should be greater than the cost function value.The steps of genetic algorithm are as follows:(1)
Initialization.T is the maximum evolutionary algebra; randomly generate delivery routes for all customer coordinates in each type of area, and randomly insert P vehicle positions in each delivery route, indicating that the previous route to the vehicle position is delivered by this vehicle. A total of N individuals are generated as the initial population Pt;(2)
Individual evaluation. Calculate the fitness1/f of each individual in Pt;(3)
Selection operation. Apply the selection operator to the group;The selection strategy that combines the best individual preservation and the selection of the gambling wheel is adopted;(4)
Crossover operation. Apply the crossover operator to the groupUsing the OX-like crossover method, the crossover operation occurs with a certain probability.(5)
Mutation operation. Apply the mutation operator to the groupThe mutation operation also occurs with a certain probability. When the mutation operation is generated, the random method is used to generate the number of exchangesJ, the gene of the individual that needs to be mutated is exchanged J times, the position of the exchange gene is randomly generated, and the next generation population is obtained through (3), (4), and (5) operations Pt+1;(6)
Judgment of termination conditiont≤T:t←t+1, go to step (2); t>T: terminate output solution.


## 4.1. Customer Clustering

According to all the historical orders and the regional situation of vehicles, the following calculations are carried out for each divided region.K-means++ algorithm can be used for classification.


## 4.2. Online Batching Algorithm

In order to simplify the model, it is set as a single picking channel, and the following points are mainly considered in the online batching algorithm.(1)
Set the upper limit of the delay time ast=mintihlatest−thsevice−toi, the maximum delay time of each picking batch, mintihlatest is the latest delivery time allowed for the order i with the earliest time window in one of the batches, thsevice is the completion time of pick batching, and toi is the distance time from the distribution center to the customer;(2)
If the batch quantity is 1, and the time does not reach the upper limit of the delay time, wait for the arrival of next order;(3)
If the batch quantity is greater than 1, and the time does not reach the upper limit of the delay time, the batch with the smallest service time will be selected.The specific steps of the algorithm are as follows:(1)
Initialization: sett=0, and Ut is the current set of orders that have arrived but not picked, U0=i|tiarrive=0;(2)
ConvertUt order set to Ht batch set. Batching is to divide the orders in each area separately, where Qb represents the maximum capacity that can be accepted by pickers or machines. Ht is the cardinality of the set Ht, if Ht=0, it means that no order arrives at the current moment; go to step (4); if Ht≥1 and t≥mintihlatest−thsevice−toi, the batch with the longest service time at the current moment is allocated to the earliest idle picker or machine, and the order is inserted into the appropriate order batch. It is the time when the picking is completed and the region to which the order belongs are determined. In addition, set the value of t to the earliest idle time of the picker or machine, and return to step (2). If t≤mintihlatest−thsevice−toi, go to step (3);(3)
IfHt1, set the value of t to minmintihlatest−thsevice−toi,ti+1arrive, and ti+1arrive is the arrival time of the i+1th order, which is the arrival time of the next order. Assign the current batch to the earliest idle picker or machine, set the value of t to the earliest idle time of the picker or machine, and return to step (2). If Ht>1 and the batch with the shortest service time at the current moment is assigned to the earliest idle picker or machine, and the value of t is set to the earliest idle time of the picker or machine, return to step (2);(4)
If there are still orders arriving, sett=ti+1arrive and return to step (2); otherwise, end.


## 4.3. Optimization of Route Planning

The route of vehicle is optimized by genetic algorithm. Suppose that the number of rental vehicles in the area isP, and the delivery vehicle in the area is defined as K=1,2,…P,P+1, and P+1 is its own delivery vehicles of the area, and the objective function of the genetic algorithm is(28)minf=min∑v=1P+1ηC1′+C2′+C3′+C4′+C5′+1−ηtvleave+∑jdvojsVv+P1sign1+P2sign2,C1′=∑i=1nkticompletecipickxiP+1,C2′=∑i=1nkcufixedzojP+1+∑j=1nk∑w=1Pcwfixedzojw,C3′=∑i=0nk∑j=1nkcvptijzijP+1+∑i=0nk∑j=1nk∑w=1Pcwptijzijw,C4′=∑i=0nk∑j=1nk∑v=1P+1zijvθαtij+βqi,C5′=∑i=0nk∑j=1nk∑v=1P+1ciearliestzijvmaxtiearliest−tiarrive,o+∑i=0nk∑j=1nk∑v=1P+1cilatestzijvmaxtilatest−tiarrive,o.C1′+C2′+C3′+C4′+C5′ is the corresponding cost function, tvleave+∑jdvojs/Vv is the end time of the vth vehicle, and sign1 represents whether the current plan exceeds the maximum vehicle capacity; if it exceeds, it is 1; otherwise, it is 0. P1 is the corresponding penalty coefficient, and generally the value should be greater than the cost function value. Sign2 indicates whether the current plan meets the customer’s time window requirements, with 0 for satisfaction and 1 for dissatisfaction. P2 is the corresponding penalty coefficient, and generally the value should be greater than the cost function value.The steps of genetic algorithm are as follows:(1)
Initialization.T is the maximum evolutionary algebra; randomly generate delivery routes for all customer coordinates in each type of area, and randomly insert P vehicle positions in each delivery route, indicating that the previous route to the vehicle position is delivered by this vehicle. A total of N individuals are generated as the initial population Pt;(2)
Individual evaluation. Calculate the fitness1/f of each individual in Pt;(3)
Selection operation. Apply the selection operator to the group;The selection strategy that combines the best individual preservation and the selection of the gambling wheel is adopted;(4)
Crossover operation. Apply the crossover operator to the groupUsing the OX-like crossover method, the crossover operation occurs with a certain probability.(5)
Mutation operation. Apply the mutation operator to the groupThe mutation operation also occurs with a certain probability. When the mutation operation is generated, the random method is used to generate the number of exchangesJ, the gene of the individual that needs to be mutated is exchanged J times, the position of the exchange gene is randomly generated, and the next generation population is obtained through (3), (4), and (5) operations Pt+1;(6)
Judgment of termination conditiont≤T:t←t+1, go to step (2); t>T: terminate output solution.


## 5. Results

The date comes from the actual operating data ofX company for data analysis. The food cold chain distribution company was established in 2014. Currently, it is mainly based on the front warehouse model. It is a fresh O2O e-commerce platform that operates all categories of vegetables, fruits, meat and eggs, dairy products, and aquatic products. The e-commerce platform often carries out activities such as centralized discounts and promotions. According to statistics, sales increased by 1.7 times year-on-year in the promotion activities of “Double Eleven” in 2019.The case in this paper deals with online processing of customer orders. Firstly, we select 203 customer points within 15 km around one distribution center, and their specific locations are shown in Figure1. Next, we use K-means clustering to classify the regions where customers are located, as shown in Figure 2. It is worth noting that the value of K is usually set by experience. According to the survey and communication with X enterprise, we set K as 5. At the same time, we use sum of the squared errors (SSE) to verify the validity of the K value, which further addresses the validity and reliability of K-means clustering. And then, the online order batching and routing of customer orders in each region are jointly optimized.Figure 1
Customer geographic distribution map.Figure 2
Clustering result of customers.


### 5.1. Case Result Analysis

Considering that orders arrive online for real-time analysis and distribution, it is necessary to meet the distribution needs of customers in real time according to the actual situation of the enterprise. Therefore, the batches and routes of orders in the online situation are increased compared with those in the offline situation. Table2 shows the number of delivery batches and routes in region 1 when the order arrives online.Table 2
Delivery path of region 1.
RegionThe number of routeDelivery route11[179, 114, 138]2[135, 152, 50, 64, 95, 121]3[181, 32, 96, 49, 148, 202, 120]4[145, 52, 153, 102, 16, 61, 22, 23]5[62, 201, 182, 156, 192, 122, 195]6[103, 37, 31, 63]Figure3 shows the convergence diagram obtained by MATLAB running the program. It can be seen that each region is basically in convergence, the initial test population is 2000, and the number of iterations is 80.Figure 3
Convergence diagram of each region.Figure4 shows the path diagram of each region; from top to bottom and from left to right are the path diagrams in areas 1–5. There are a total of 38 paths in the 5 areas, with 6, 9, 4, 9, and 10 paths, respectively.Figure 4
Delivery path diagram of each region.Table2 shows all the specific vehicle delivery routes in region 1 when the order arrives online. The paths in all areas are shown in the appendix. It can be seen that, in the case of online real-time processing of orders, the frequency of delivery will increase because of the consideration of both the time of customer ordering and the timeliness of delivery.Table3 shows the total delivery time, total cost, total mileage, and total load capacity of each route in region 1 jointly optimized when the order arrives online.Table 3
Total time, cost, mileage, and load of region 1.
RouteTotal time (hour)Total cost (yuan)Total mileage (km)Total load (kg)12.2576.0031.3179.4122.35100.2533.8196.5132.57105.0235.0186.8242.59122.3231.49110.4152.91113.4938.9296.7262.1380.8728.6285.97Total14.80597.96199.17555.84Table4 shows the total delivery time, cost, mileage, and load capacity of the joint optimization in each region when the order arrives online.Table 4
Total time, cost, mileage, and load in each region when the order online.
RegionTotal time (hour)Total cost (yuan)Total mileage (km)Total load (kg)114.80597.96199.17555.84217.23706.63227.37448.1337.03337.82118.28219.14417.691038.60258.00614.80526.051314.81304.60871.32Total82.813995.821107.432709.23


### 5.2. Comparative Analysis of Results

#### 5.2.1. Comparative Analysis of Joint Optimization and Phased Processing Results

Companies generally divide the batch picking and order distribution of orders into two stages to optimize the solution separately. In actual conditions, the company is delivering online, and the order picking and routing are not jointly optimized. Therefore, comparing the individual processing in stages and the joint optimization in Table5, it can be seen that the total time, total cost, and total mileage of delivery have been optimized to a certain extent. In terms of the total delivery time, the batch of orders was reduced by 6.19 hours compared with the original, a reduction of 6.95%; the total delivery cost was reduced by 376.45 yuan after the joint optimization, which was a reduction of 8.61% with the original; in terms of the total mileage of the distribution, it is a reduction of 78.00 kilometers, 6.58% with the original. It can be seen that the cost, time, and mileage, compared with the original phased processing, are greatly reduced, and the result of joint optimization is more obvious. It is more intuitively reflected in Figure 5. Therefore, it is advisable to jointly optimize the order picking and routing, which can effectively reduce the total cost and total time from the perspective of the enterprise.Table 5
Comparison of the results of two optimization methods.
Processing methodTotal time (hour)Total cost (yuan)Total mileage (km)Phased processing88.994372.271185.43Integrated optimization82.813995.821107.43Optimization6.19376.4578.00Optimization percentage6.95%8.61%6.58%Figure 5
Comparison of the results of two optimization methods.


#### 5.2.2. The Comparison between the Offline and Online Arrival of the Order

In Table6, it can be seen that the joint optimization of the online order arrival situation is more than the total time, total cost, and total mileage when the order arrives offline. This is related to the real-time online processing of the order and takes into account the time of the order arrival. Since there are more batches and routes for online orders than offline orders, the delivery cost is slightly higher. This can also be seen in Table 7.Table 6
Comparison of offline and online orders.
OrderTotal time (hour)Total cost (yuan)Total mileage (km)Offline71.383679.12846.81Online82.813995.821107.43Offline optimization compared to online11.42316.70260.62Offline optimization percentage compared to online13.80%7.93%23.53%Table 7
Analysis of delivery cost for offline and online orders.
Cost (Yuan)Offline ordersOnline ordersPercentage of offline orders (%)Percentage of online orders (%)Order picking costC11015.001015.0027.5925.40Vehicle fixed costC2950.001580.0025.8239.54Delivery costC3505.51596.2213.7414.92Stock-out loss costC4799.15597.0321.7214.94Time penalty costC5409.46207.5711.135.19Total cost3679.123995.82100.00100.00In Table7, it can be seen that the fixed cost of the vehicle C2 and the delivery cost C3 are both lower in the offline case than in the online case, from the comparative analysis of the various distribution costs in the two cases where the order arrives online. And the two costs of stock-out loss cost C4 and time penalty cost C5 are smaller when the order arrives online than when it is offline, which can also be seen intuitively from Figures 6 and 7. It can be seen from Figure 6 that C1 and C2 account for a higher proportion of the total delivery cost, while the remaining cost proportions are slightly different. When companies further reduce costs based on the research in this article, they can start from these two aspects. Among them, C5 is the order time penalty cost, which represents customer satisfaction in this article. According to Figure 7, it can be seen that C5 accounts for a smaller proportion of its total distribution cost in the online case than in the offline case. According to the statistics of the route results in each area, among the 23 routes of offline orders, there are 7 routes, with C5 being 0, accounting for 30.43%; among the 38 routes of online orders, and there are 20 routes, with C5 being 0, accounting for 52.63%. It can be seen that, under the surge in demand, when orders arrive online, the rate of delivery on time according to customer requirements is higher, but at the same time, more costs are paid. Therefore, the online situation can better meet the customer’s requirements for delivery time, and customer satisfaction is higher.Figure 6
Comparison of analysis of delivery cost for offline and online orders.Figure 7
Analysis of each cost for offline and online orders.It can be seen from the above that the cost of the joint optimization of offline order arrival processing is 7.93% lower than that of the online arrival joint optimization. If it is not necessary to urgently need food on the same day, or if it is not necessary to arrive on the same day, the company can suggest that the customer choose the next day delivery or the required food after placing the order. Orders can be placed one day in advance, which will reduce costs for the enterprise. On this basis, the enterprise can also provide certain discounts for non-same-day delivery customers to achieve a win-win situation for enterprise customers. According to the different needs of different customers, enterprises can combine the two modules of offline processing and online arrival optimization to combine as many online processing orders as possible to reduce costs. To improve customer satisfaction, customers can also have more flexible time to choose, and enterprises and customers can get the greatest discount at the same time.


## 5.1. Case Result Analysis

Considering that orders arrive online for real-time analysis and distribution, it is necessary to meet the distribution needs of customers in real time according to the actual situation of the enterprise. Therefore, the batches and routes of orders in the online situation are increased compared with those in the offline situation. Table2 shows the number of delivery batches and routes in region 1 when the order arrives online.Table 2
Delivery path of region 1.
RegionThe number of routeDelivery route11[179, 114, 138]2[135, 152, 50, 64, 95, 121]3[181, 32, 96, 49, 148, 202, 120]4[145, 52, 153, 102, 16, 61, 22, 23]5[62, 201, 182, 156, 192, 122, 195]6[103, 37, 31, 63]Figure3 shows the convergence diagram obtained by MATLAB running the program. It can be seen that each region is basically in convergence, the initial test population is 2000, and the number of iterations is 80.Figure 3
Convergence diagram of each region.Figure4 shows the path diagram of each region; from top to bottom and from left to right are the path diagrams in areas 1–5. There are a total of 38 paths in the 5 areas, with 6, 9, 4, 9, and 10 paths, respectively.Figure 4
Delivery path diagram of each region.Table2 shows all the specific vehicle delivery routes in region 1 when the order arrives online. The paths in all areas are shown in the appendix. It can be seen that, in the case of online real-time processing of orders, the frequency of delivery will increase because of the consideration of both the time of customer ordering and the timeliness of delivery.Table3 shows the total delivery time, total cost, total mileage, and total load capacity of each route in region 1 jointly optimized when the order arrives online.Table 3
Total time, cost, mileage, and load of region 1.
RouteTotal time (hour)Total cost (yuan)Total mileage (km)Total load (kg)12.2576.0031.3179.4122.35100.2533.8196.5132.57105.0235.0186.8242.59122.3231.49110.4152.91113.4938.9296.7262.1380.8728.6285.97Total14.80597.96199.17555.84Table4 shows the total delivery time, cost, mileage, and load capacity of the joint optimization in each region when the order arrives online.Table 4
Total time, cost, mileage, and load in each region when the order online.
RegionTotal time (hour)Total cost (yuan)Total mileage (km)Total load (kg)114.80597.96199.17555.84217.23706.63227.37448.1337.03337.82118.28219.14417.691038.60258.00614.80526.051314.81304.60871.32Total82.813995.821107.432709.23


## 5.2. Comparative Analysis of Results

### 5.2.1. Comparative Analysis of Joint Optimization and Phased Processing Results

Companies generally divide the batch picking and order distribution of orders into two stages to optimize the solution separately. In actual conditions, the company is delivering online, and the order picking and routing are not jointly optimized. Therefore, comparing the individual processing in stages and the joint optimization in Table5, it can be seen that the total time, total cost, and total mileage of delivery have been optimized to a certain extent. In terms of the total delivery time, the batch of orders was reduced by 6.19 hours compared with the original, a reduction of 6.95%; the total delivery cost was reduced by 376.45 yuan after the joint optimization, which was a reduction of 8.61% with the original; in terms of the total mileage of the distribution, it is a reduction of 78.00 kilometers, 6.58% with the original. It can be seen that the cost, time, and mileage, compared with the original phased processing, are greatly reduced, and the result of joint optimization is more obvious. It is more intuitively reflected in Figure 5. Therefore, it is advisable to jointly optimize the order picking and routing, which can effectively reduce the total cost and total time from the perspective of the enterprise.Table 5
Comparison of the results of two optimization methods.
Processing methodTotal time (hour)Total cost (yuan)Total mileage (km)Phased processing88.994372.271185.43Integrated optimization82.813995.821107.43Optimization6.19376.4578.00Optimization percentage6.95%8.61%6.58%Figure 5
Comparison of the results of two optimization methods.


### 5.2.2. The Comparison between the Offline and Online Arrival of the Order

In Table6, it can be seen that the joint optimization of the online order arrival situation is more than the total time, total cost, and total mileage when the order arrives offline. This is related to the real-time online processing of the order and takes into account the time of the order arrival. Since there are more batches and routes for online orders than offline orders, the delivery cost is slightly higher. This can also be seen in Table 7.Table 6
Comparison of offline and online orders.
OrderTotal time (hour)Total cost (yuan)Total mileage (km)Offline71.383679.12846.81Online82.813995.821107.43Offline optimization compared to online11.42316.70260.62Offline optimization percentage compared to online13.80%7.93%23.53%Table 7
Analysis of delivery cost for offline and online orders.
Cost (Yuan)Offline ordersOnline ordersPercentage of offline orders (%)Percentage of online orders (%)Order picking costC11015.001015.0027.5925.40Vehicle fixed costC2950.001580.0025.8239.54Delivery costC3505.51596.2213.7414.92Stock-out loss costC4799.15597.0321.7214.94Time penalty costC5409.46207.5711.135.19Total cost3679.123995.82100.00100.00In Table7, it can be seen that the fixed cost of the vehicle C2 and the delivery cost C3 are both lower in the offline case than in the online case, from the comparative analysis of the various distribution costs in the two cases where the order arrives online. And the two costs of stock-out loss cost C4 and time penalty cost C5 are smaller when the order arrives online than when it is offline, which can also be seen intuitively from Figures 6 and 7. It can be seen from Figure 6 that C1 and C2 account for a higher proportion of the total delivery cost, while the remaining cost proportions are slightly different. When companies further reduce costs based on the research in this article, they can start from these two aspects. Among them, C5 is the order time penalty cost, which represents customer satisfaction in this article. According to Figure 7, it can be seen that C5 accounts for a smaller proportion of its total distribution cost in the online case than in the offline case. According to the statistics of the route results in each area, among the 23 routes of offline orders, there are 7 routes, with C5 being 0, accounting for 30.43%; among the 38 routes of online orders, and there are 20 routes, with C5 being 0, accounting for 52.63%. It can be seen that, under the surge in demand, when orders arrive online, the rate of delivery on time according to customer requirements is higher, but at the same time, more costs are paid. Therefore, the online situation can better meet the customer’s requirements for delivery time, and customer satisfaction is higher.Figure 6
Comparison of analysis of delivery cost for offline and online orders.Figure 7
Analysis of each cost for offline and online orders.It can be seen from the above that the cost of the joint optimization of offline order arrival processing is 7.93% lower than that of the online arrival joint optimization. If it is not necessary to urgently need food on the same day, or if it is not necessary to arrive on the same day, the company can suggest that the customer choose the next day delivery or the required food after placing the order. Orders can be placed one day in advance, which will reduce costs for the enterprise. On this basis, the enterprise can also provide certain discounts for non-same-day delivery customers to achieve a win-win situation for enterprise customers. According to the different needs of different customers, enterprises can combine the two modules of offline processing and online arrival optimization to combine as many online processing orders as possible to reduce costs. To improve customer satisfaction, customers can also have more flexible time to choose, and enterprises and customers can get the greatest discount at the same time.


## 5.2.1. Comparative Analysis of Joint Optimization and Phased Processing Results

Companies generally divide the batch picking and order distribution of orders into two stages to optimize the solution separately. In actual conditions, the company is delivering online, and the order picking and routing are not jointly optimized. Therefore, comparing the individual processing in stages and the joint optimization in Table5, it can be seen that the total time, total cost, and total mileage of delivery have been optimized to a certain extent. In terms of the total delivery time, the batch of orders was reduced by 6.19 hours compared with the original, a reduction of 6.95%; the total delivery cost was reduced by 376.45 yuan after the joint optimization, which was a reduction of 8.61% with the original; in terms of the total mileage of the distribution, it is a reduction of 78.00 kilometers, 6.58% with the original. It can be seen that the cost, time, and mileage, compared with the original phased processing, are greatly reduced, and the result of joint optimization is more obvious. It is more intuitively reflected in Figure 5. Therefore, it is advisable to jointly optimize the order picking and routing, which can effectively reduce the total cost and total time from the perspective of the enterprise.Table 5
Comparison of the results of two optimization methods.
Processing methodTotal time (hour)Total cost (yuan)Total mileage (km)Phased processing88.994372.271185.43Integrated optimization82.813995.821107.43Optimization6.19376.4578.00Optimization percentage6.95%8.61%6.58%Figure 5
Comparison of the results of two optimization methods.


## 5.2.2. The Comparison between the Offline and Online Arrival of the Order

In Table6, it can be seen that the joint optimization of the online order arrival situation is more than the total time, total cost, and total mileage when the order arrives offline. This is related to the real-time online processing of the order and takes into account the time of the order arrival. Since there are more batches and routes for online orders than offline orders, the delivery cost is slightly higher. This can also be seen in Table 7.Table 6
Comparison of offline and online orders.
OrderTotal time (hour)Total cost (yuan)Total mileage (km)Offline71.383679.12846.81Online82.813995.821107.43Offline optimization compared to online11.42316.70260.62Offline optimization percentage compared to online13.80%7.93%23.53%Table 7
Analysis of delivery cost for offline and online orders.
Cost (Yuan)Offline ordersOnline ordersPercentage of offline orders (%)Percentage of online orders (%)Order picking costC11015.001015.0027.5925.40Vehicle fixed costC2950.001580.0025.8239.54Delivery costC3505.51596.2213.7414.92Stock-out loss costC4799.15597.0321.7214.94Time penalty costC5409.46207.5711.135.19Total cost3679.123995.82100.00100.00In Table7, it can be seen that the fixed cost of the vehicle C2 and the delivery cost C3 are both lower in the offline case than in the online case, from the comparative analysis of the various distribution costs in the two cases where the order arrives online. And the two costs of stock-out loss cost C4 and time penalty cost C5 are smaller when the order arrives online than when it is offline, which can also be seen intuitively from Figures 6 and 7. It can be seen from Figure 6 that C1 and C2 account for a higher proportion of the total delivery cost, while the remaining cost proportions are slightly different. When companies further reduce costs based on the research in this article, they can start from these two aspects. Among them, C5 is the order time penalty cost, which represents customer satisfaction in this article. According to Figure 7, it can be seen that C5 accounts for a smaller proportion of its total distribution cost in the online case than in the offline case. According to the statistics of the route results in each area, among the 23 routes of offline orders, there are 7 routes, with C5 being 0, accounting for 30.43%; among the 38 routes of online orders, and there are 20 routes, with C5 being 0, accounting for 52.63%. It can be seen that, under the surge in demand, when orders arrive online, the rate of delivery on time according to customer requirements is higher, but at the same time, more costs are paid. Therefore, the online situation can better meet the customer’s requirements for delivery time, and customer satisfaction is higher.Figure 6
Comparison of analysis of delivery cost for offline and online orders.Figure 7
Analysis of each cost for offline and online orders.It can be seen from the above that the cost of the joint optimization of offline order arrival processing is 7.93% lower than that of the online arrival joint optimization. If it is not necessary to urgently need food on the same day, or if it is not necessary to arrive on the same day, the company can suggest that the customer choose the next day delivery or the required food after placing the order. Orders can be placed one day in advance, which will reduce costs for the enterprise. On this basis, the enterprise can also provide certain discounts for non-same-day delivery customers to achieve a win-win situation for enterprise customers. According to the different needs of different customers, enterprises can combine the two modules of offline processing and online arrival optimization to combine as many online processing orders as possible to reduce costs. To improve customer satisfaction, customers can also have more flexible time to choose, and enterprises and customers can get the greatest discount at the same time.


## 6. Conclusions

In this paper, the joint optimization problem of cold chain food online order picking and vehicle delivery is studied by considering both the demand surge and the real-time order arrival. The following problems have been solved:(1)
Fully consider the characteristics of fresh food, analyze the demand surge caused by promotions, and avoid problems such as unreasonable picking arrangements and untimely delivery caused by demand surge.(2)
Aiming at the existing problems, the joint optimization of order picking and routing is studied, and an integer programming model is designed. In the model, both the lowest cost and the shortest time are considered.(3)
The actual operation data of the enterprise is obtained, and the heuristic algorithm is used to solve the problem, and the online and offline, joint optimization, and subsection optimization are compared and analyzed, respectively.Our research results show that it is advisable to jointly optimize the order picking and routing, which can effectively reduce the total cost and total time-consuming. At the same time, it shows that the online situation can better meet the customer’s requirements for delivery time, and the customer satisfaction is higher. Conversely, the cost has also increased. Therefore, enterprises can provide certain discounts for non-same-day delivery customers in advance. At the same time, according to the different needs of different customers, enterprises can combine the two joint optimizations of offline processing and online arrival to convert as many orders processed online as possible to offline processing.Future research can make breakthroughs in constraint setting and algorithm design, aiming to solve such problems more accurately and efficiently. Specifically, the order deterioration rate can be further considered in the constraint setting, due to the shelf life of fresh food. For the simplicity of the calculation, it is assumed that a customer has only one order per day, which is inconsistent with reality. However, the increase of orders will greatly increase the solution scale; it is worth considering how to make it more realistic. An online algorithm with larger instances can be designed. The demand for online food is increasing year by year, and merchants have frequent promotions. Properly increasing production capacity and seeking capacity sharing are also issues that need to be considered.



---

*Source: 4485376-2022-07-08.xml*