# Round-Trip Emergency Supply Distribution Model Based on Nonfixed Routes

Authors: Yanli Tang; Ying Xiong; Ying Chen
Journal: Journal of Advanced Transportation
 (2022)

---

## Abstract

In the face of increasing natural or man-made disasters, rapid and effective emergency dispatch and organization are of great significance to ensure the life safety of people and reduce social losses. In view of the long duration, strong demand urgency, and relatively limited transportation capacity after catastrophic events, this paper proposes a round-trip emergency supply distribution model based on nonfixed routes. This model includes two main features: (1) round trip: emergency vehicles can travel back and forth to distribute supplies; (2) unfixed routes: distribution routes of the same emergency vehicle could be variable in different trips. In order to ensure the timeliness and fairness of the supply distribution scheme, the model objective function is set to minimize the total supplies’ waiting time at all demand points. According to model features, 4 constraints are set, including flow balance, capacity, vehicle scheduling, and time window. On this basis, a compound algorithm combining 2-opt and tabu search is designed to obtain the optimal plan of the model. To verify the effectiveness and superiority of the model and solution method, a case study based on the Sioux Falls network is carried out. Compared with the traditional method, the objective function is optimized by 11.92%. In fact, under the control of multiple constraint conditions, the model well fits the actual application scenarios, which can provide theoretical guidance and decision support for the distribution of relevant emergency supplies.


---

## Body

## 1. Introduction

As the human society continues to develop, natural or man-made catastrophic events have become increasingly frequent. In the face of these events, rapid and effective emergency rescue is of great significance for reducing disaster damage and ensuring the safety of people’s lives. Supply distribution is the basic premise of emergency rescue, which includes emergency supply allocation and route planning [1]. In fact, scientific and reasonable distribution of emergency supplies can improve the effectiveness of emergency rescue, thereby achieving social benefits.In recent years, the emergency supply distribution problem has attracted more and more attention and been widely studied. In terms of research object, it is a typical vehicle routing planning problem (VRP). Most previous studies assume that emergency vehicle transportation is a one-way trip. In other words, emergency vehicles deliver supplies from the distribution centers to demand points and will not return to the distribution centers after completing their tasks. In addition, each emergency vehicle only serves one demand point, significantly reducing the complexity of the model. Based on the above assumptions, Li et al. [2] established a supply distribution model considering the timeliness and fairness and proposed a hybrid genetic algorithm to solve this problem. Xing et al. [3] constructed a comprehensive emergency scheduling model. They obtained the resource allocation plan based on multiobjective path planning. Meanwhile, Wei et al. [4] introduced the constraint conditions of resources and time windows into their model construction to improve the practicability of the model, which can output emergency supply allocation and vehicle routing plans at the same time. Based on the same one-way travel assumption, Xiong et al. [5] constructed a multimodal emergency supply distribution model integrating vehicles and helicopters. In addition, Yingli [6] added a penalty function based on time delay to the emergency supply distribution model to achieve a balanced distribution of supplies between demand points.With the assumption of one-way trip, the model does not need to consider the return of vehicles, which could help simplify the model effectively, but the assumption is not completely consistent with the actual situation [7]. Because the total number of emergency vehicles is limited, it is difficult to complete all supply distribution at one time based on the assumption of one-way trip. Therefore, in most cases, emergency vehicles need to travel back and forth between distribution centers and disaster sites many times to distribute supplies gradually. Therefore, some studies proposed a round-trip distribution plan or a multipoint distribution plan, where an emergency vehicle can serve multiple demand points in the same trip. Jun et al. [8] studied the emergency supply distribution problem with a single depot and fuzzy demand. They constructed a dynamic scheduling model and designed a particle swarm optimization algorithm to solve this problem. Based on the multitraveling salesman problem, Ming and Peiyong [9] aimed to minimize the total travel cost of the vehicles, conducting emergency supply scheduling. Zhuo et al. [10] considered the mixed transportation of self-owned and rented vehicles in the distribution center and constructed a multiobjective emergency supply distribution model. Chen et al. [11] introduced the reliability of supplies as a factor into the emergency logistics network to solve the emergency supply distribution problem under risk propagation. Furthermore, considering that, in the postdisaster rescue, the number of supplies and transportation capacity of each rescue site may be unbalanced, Han et al. [12] set the supply transfer site in their model to effectively transfer supplies.In this study, a round-trip emergency supply distribution model based on nonfixed routes is proposed. The main features of the model include round trips, where emergency vehicles can travel back and forth to distribute supplies, and nonfixed routes, where different from the traditional method, the emergency vehicle can deliver supplies to multiple demand points in the same trip, and its distribution routes may vary in different trips. By adding these two features, the rationality and efficiency of the obtained supply distribution plan can be improved. In addition, four types of constraint conditions are set, that is, flow balance, capacity, vehicle scheduling, and time window. In order to solve the model, a compound algorithm based on 2-opt and tabu search is designed to obtain the optimal emergency supply distribution plan of the model.Figure 1
A trip of an emergency vehiclev.


## 2. Model Formulation

### 2.1. Hypotheses

(1)
Through the information collection before emergency dispatching, the demands of supplies of each demand point and the supply reserves of each distribution center can be determined as known conditions. In addition, the total supply reserves should exceed the total demand of supplies of all demand points.(2)
According to specific conditions, different methods can be used to obtain the travel time of emergency vehicles. If there are emergency lanes on the road section, it could be considered that the emergency vehicles travel at a free-flow speed; otherwise, the travel time of the emergency vehicle should be obtained according to the function of the Bureau of Public Roads (BPR) [13].(1)ti,j=ti,j0,if the bus lane is set,ti,j01+βCtCi,jα,otherwise,wheret(i,j) represents the actual travel time of the road section (i, j), ti,j0 represents the travel time under free flow, Ct represents the traffic volume, C(i,j) represents the normal road capacity, and α and β represent the parameters (α = 4 and β = 0.15).(3)
The travel of emergency vehicles from the distribution center to the demand points and back to the distribution center is defined as a trip. As shown in Figure1, during each trip, the emergency vehicle departs from the corresponding distribution center with a full load and returns to the distribution center after completing the supply distribution.


### 2.2. Objective Function

The objective function of the model is set to minimize the total waiting time at all demand points to ensure the timeliness and fairness of the supply distribution plan.(2)MinTwait=∑v∈V∑k=1K∑i∈Eθviktvikqvik,(3)tvik=∑n=1k∑x,y∈AvikδvxynTxy+∑n=1K∑z∈Nvikθvznd.Equation (2) is to obtain the total waiting time for supplies of all demand points, that is, the product sums of waiting time and waiting quantity of supplies at all demand points. Equation (3) is used to calculate the time for emergency vehicles to arrive at the demand point in each trip, that is, the waiting time for supplies at the demand point.


### 2.3. Constraint Conditions

(1)
Flow balance constraint:(4)∑i∈Nδvihk=∑j∈Nδvhjk,h∈N,∀v∈V,k≤K.(2)
Capacity constraint:(5)m⋅CAPv≤∑i∈Eθvikqvik≤CAPv,∀v∈V,k≤K,(6)∑v∈V∑k∈1kθvikqvik=DEMi,∀i∈E,(7)∑v∈V∑k=1K∑i∈Eqvik≤∑j∈SQj.(3)
Vehicle scheduling constraint:(8)∑v∈V∑k=0Kθvik≥1,∀i∈E,(9)∑v∈V∑i∈Eδvjik≤NV,∀j∈S,k≤K,(10)K−1≤∑kK∑i∈Eδvjik≤K,∀j∈S,v∈V.(4)
Time window constraint:(11)δvijktvik+d+Tij≤tvjk≤Ti,∀i,j∈N,v∈V,k∈K.The four constraint conditions of the model are the flow balance, capacity, vehicle scheduling, and time window. Constraint (4) ensures the flow balance, that is, for any distribution center or demand point, the inflow and outflow of vehicles must be equal. Constraint (5) indicates that emergency vehicles can serve different demand points in the same trip. Constraint (6) requires that the demands of supplies of all demand points in the network be met. Constraint (7) ensures that the total demands of supplies at all demand points should not exceed the total reserve of supplies of all distribution centers. Constraint (8) indicates that emergency vehicles pass through all demand points and distribute supplies. Constraint (9) ensures that the number of scheduled vehicles cannot exceed the number of emergency vehicles available. Constraint (10) indicates that the emergency vehicles will not stop delivering supplies before completing the supply distribution, which limits the number of trips of the vehicle. At the same time, constraint (11) ensures that emergency vehicles must arrive at demand points on time or in advance.


## 2.1. Hypotheses

(1)
Through the information collection before emergency dispatching, the demands of supplies of each demand point and the supply reserves of each distribution center can be determined as known conditions. In addition, the total supply reserves should exceed the total demand of supplies of all demand points.(2)
According to specific conditions, different methods can be used to obtain the travel time of emergency vehicles. If there are emergency lanes on the road section, it could be considered that the emergency vehicles travel at a free-flow speed; otherwise, the travel time of the emergency vehicle should be obtained according to the function of the Bureau of Public Roads (BPR) [13].(1)ti,j=ti,j0,if the bus lane is set,ti,j01+βCtCi,jα,otherwise,wheret(i,j) represents the actual travel time of the road section (i, j), ti,j0 represents the travel time under free flow, Ct represents the traffic volume, C(i,j) represents the normal road capacity, and α and β represent the parameters (α = 4 and β = 0.15).(3)
The travel of emergency vehicles from the distribution center to the demand points and back to the distribution center is defined as a trip. As shown in Figure1, during each trip, the emergency vehicle departs from the corresponding distribution center with a full load and returns to the distribution center after completing the supply distribution.


## 2.2. Objective Function

The objective function of the model is set to minimize the total waiting time at all demand points to ensure the timeliness and fairness of the supply distribution plan.(2)MinTwait=∑v∈V∑k=1K∑i∈Eθviktvikqvik,(3)tvik=∑n=1k∑x,y∈AvikδvxynTxy+∑n=1K∑z∈Nvikθvznd.Equation (2) is to obtain the total waiting time for supplies of all demand points, that is, the product sums of waiting time and waiting quantity of supplies at all demand points. Equation (3) is used to calculate the time for emergency vehicles to arrive at the demand point in each trip, that is, the waiting time for supplies at the demand point.


## 2.3. Constraint Conditions

(1)
Flow balance constraint:(4)∑i∈Nδvihk=∑j∈Nδvhjk,h∈N,∀v∈V,k≤K.(2)
Capacity constraint:(5)m⋅CAPv≤∑i∈Eθvikqvik≤CAPv,∀v∈V,k≤K,(6)∑v∈V∑k∈1kθvikqvik=DEMi,∀i∈E,(7)∑v∈V∑k=1K∑i∈Eqvik≤∑j∈SQj.(3)
Vehicle scheduling constraint:(8)∑v∈V∑k=0Kθvik≥1,∀i∈E,(9)∑v∈V∑i∈Eδvjik≤NV,∀j∈S,k≤K,(10)K−1≤∑kK∑i∈Eδvjik≤K,∀j∈S,v∈V.(4)
Time window constraint:(11)δvijktvik+d+Tij≤tvjk≤Ti,∀i,j∈N,v∈V,k∈K.The four constraint conditions of the model are the flow balance, capacity, vehicle scheduling, and time window. Constraint (4) ensures the flow balance, that is, for any distribution center or demand point, the inflow and outflow of vehicles must be equal. Constraint (5) indicates that emergency vehicles can serve different demand points in the same trip. Constraint (6) requires that the demands of supplies of all demand points in the network be met. Constraint (7) ensures that the total demands of supplies at all demand points should not exceed the total reserve of supplies of all distribution centers. Constraint (8) indicates that emergency vehicles pass through all demand points and distribute supplies. Constraint (9) ensures that the number of scheduled vehicles cannot exceed the number of emergency vehicles available. Constraint (10) indicates that the emergency vehicles will not stop delivering supplies before completing the supply distribution, which limits the number of trips of the vehicle. At the same time, constraint (11) ensures that emergency vehicles must arrive at demand points on time or in advance.


## 3. Solution Algorithms

The round-trip emergency supply distribution model based on nonfixed routes is a capacitated vehicle routing problem with time window (CVRPTW), which is a typical nondeterministic polynomial hard problem [14, 15]. Generally speaking, it is difficult to obtain an accurate and optimal solution for such problems in a short time. In fact, it is more important to quickly obtain a scientific, reasonable, and feasible solution. Therefore, a compound algorithm based on 2-opt and tabu search is designed to solve the model [16, 17].First of all, under the constraints of the time window, a preliminary supply distribution plan can be constructed using the greedy insertion algorithm. Then, a 2-opt search is performed for emergency vehicle trips serving multiple demand points to optimize the distribution order of different demand points. Following this, based on the tabu search algorithm, the supply distribution plan is globally optimized through cross-search before the optimal emergency supply distribution plan of the model can be output. The algorithm flowchart and the simplified algorithm flow table are shown in Figure2 and Table 1.Figure 2
Algorithm flowchart.Table 1
Simplified algorithm flow table.
Step0Initialize and import model parametersStep1Form the initial solutionStep2Optimize the solution with 2-optStep3Take the current optimal solution into the tabu listStep4Form candidate solutions with the cross-exchangeStep5Check the time window constraintStep6Calculate the objective functionStep7Check the tabu lengthStep8Check the current optimal solutionStopping ruleIfn ≥ nmax, terminate the algorithmStep 0.
According to the actual situation after disaster, construct the emergency supply distribution network. Initialize, and import model parameters, such as set of distribution centersS, set of disaster sites E, and set of available emergency vehicles V.Step 1.
Based on the time window sequence of each disaster site, insert all disaster sites into the trips of emergency vehicles by the insertion algorithm. In each trip, the emergency vehicle starts from the distribution center, goes to disaster sites in turn to distribute supplies, and finally returns to the distribution center. Form the initial supply distribution scheme in this way, and calculate the objective functionT0. Update the initial supply distribution scheme as the current optimal solution, and set Twait = T0.Step 2.
Perform the intratrip search with 2-opt. According to the current optimal solution, update the set of all tripsR. Select a trip passing by more than one disaster site from R and operate 2-opt on it. Specifically, within the time window constraints, exchange any two disaster sites on the trip, and reverse the direction of routes between these two disaster sites. After each feasible exchange, calculate the current model objective function T. If T＜Twait, accept this exchange, update the current optimal solution, and set Twait = T; otherwise, refuse this exchange. In this way, operate 2-opt on all trips passing by more than one disaster site in R.Step 3.
Take the current optimal solution into the tabu list. Set the tabu lengthL, the maximum number of iterations nmax, l = 0, and n = 0.Step 4.
Perform the intertrip search with the cross-exchange. Update the candidate solution setC and the set of all trips R. Randomly, select two trips (a and b) from R and exchange the supply distribution tasks in trips a and b (remain the starting and ending points unchanged, and exchange the disaster sites and supply distribution). Likewise, search all the same trips as a and b, and perform the exchange operation in pairs. In this way, generate the candidate solution.Step 5.
Based on equation (7), check the time window constraint of each disaster site. If δvijktvik+d+Tij≤tvjk≤Ti,∀i,j∈N,v∈V,k∈K, go to Step 6; otherwise, go to Step 4.Step 6.
Calculate the objective function of the candidate solutionT, and check the aspiration criterion. If T < Twait, replace the current optimal solution with the candidate solution, update the tabu list, set Twait = T, n = n+1, and l = 0, and go to Step 4; otherwise, take the candidate solution into the candidate solution set C, set l = l+1, and go to Step 7.Step 7.
Check the tabu length. Ifl ≥ L, go to Step 8; otherwise, go to Step 4.Step 8.
Based on the model objective function, select the optimal candidate solution in the candidate solution setC, and record the corresponding objective function T. Replace the current optimal solution with the optimal candidate solution, update the tabu list, set Twait = T, n = n+1, and l = 0, and go to Step 4.
Stopping ruleIfn ≥ nmax, terminate the algorithm. Output the current optimal solution as the model optimal emergency supply distribution scheme.


## 4. Case Study

In order to verify the effectiveness of the proposed model and algorithm, a case study based on the Sioux Falls network is employed [18]. According to the location of demand points, the network topology has been processed. As shown in Figure 3, the positions and adjacent distances of all demand points in the network are determined. The setting of an emergency distribution center is generally related to storage capacity, facility conditions, and transportation convenience. In this case, emergency distribution centers I and II are set up at nodes 7 and 13, respectively. In addition, it is assumed that each road section is equipped with an emergency lane. The travel time of emergency vehicles on each road section is shown in Table 2.Figure 3
Sioux Falls network.Table 2
Network information.
LinkTime cost (min)LinkTime cost (min)LinkTime cost (min)LinkTime cost (min)1222083965842621840105912322224418602446234426611256248431062866254448631078264458648862784666569828104746681082984886761183010496681012831850869613432851107081463365267161583410534728164358544736178366558746184372256247581943822578766In this case, medical masks are taken as an example to conduct emergency supply distribution. The corresponding parameters are set as follows. Emergency distribution centers I and II reserve 200 and 250 cases of medical masks, respectively. Four emergency vehicles (A, B, C, and D) are set at I and II. The value ofm is set to 0.75. The capacity of emergency vehicles is 40 cases. The loading and unloading time at the node is 2 minutes.On this basis, the proposed model is applied to case solving. The optimal emergency supply distribution plan of the model is shown in Table3. It can be found that the optimal solution of the model satisfies all constraint conditions, and each demand point can effectively obtain supplies within the time window, ensuring the time reliability of the plan. The total waiting time of supplies is 25,822 minutes, and the unit supply waiting time is 64.56 minutes.Table 3
Optimal model of the emergency supply distribution plan.
Emergency vehiclePlanTrip 1Trip 2Trip 3ARoute7⟶10⟶77⟶9⟶5⟶6⟶2⟶77⟶17⟶19⟶7Timetable (min)0⟶22⟶4444⟶62⟶68⟶78⟶86⟶106106⟶126⟶132⟶156Supply (case)0⟶40⟶00⟶18⟶7⟶4⟶4⟶00⟶26⟶14⟶0BRoute7⟶10⟶4⟶3⟶1⟶77⟶18⟶16⟶8⟶7Timetable (min)0⟶22⟶40⟶48⟶56⟶9898⟶104⟶114⟶120⟶130Supply (case)0⟶10⟶13⟶3⟶10⟶00⟶5⟶16⟶18⟶0CRoute13⟶22⟶15⟶1313⟶24⟶23⟶14⟶13Timetable (min)0⟶22⟶30⟶5858⟶66⟶74⟶82⟶102Supply (case)0⟶17⟶23⟶00⟶12⟶16⟶12⟶0DRoute13⟶21⟶20⟶1313⟶14⟶1313⟶12⟶11⟶13Timetable (min)0⟶16⟶26⟶5050⟶70⟶9090⟶114⟶122⟶152Supply (case)0⟶12⟶21⟶00⟶30⟶00⟶15⟶25⟶0In order to verify the effectiveness of the proposed model, an emergency supply distribution plan based on traditional methods is obtained as a control plan [9]. This method divides the subgraphs (the service range of each emergency distribution center) based on the multitraveling salesman problem (MTSP) and obtains the supply distribution plan in each subgraph. Under the same model constraint conditions, the obtained control plans are shown in Tables 4 and 5. The total waiting time of supplies is 29,316 minutes, and the unit supply waiting time is 73.29 minutes.Table 4
Subgraph division in the control solution.
Distribution centerService rangeDemands of supply (case)I2, 4, 5, 6, 7, 8, 9, 10, 16, 17, 18, 19188II1, 3, 11, 12, 13, 14, 15, 20, 21, 22, 23, 24212Table 5
Control plan.
Emergency vehiclePlanTrip 1Trip 2Trip 3ARoute7⟶10⟶77⟶18⟶17⟶19⟶77⟶6⟶9⟶7Timetable (min)0⟶22⟶4444⟶50⟶66⟶72⟶9696⟶110⟶124⟶142Supply (case)0⟶40⟶00⟶4⟶18⟶7⟶11⟶00⟶4⟶18⟶0BRoute7⟶16⟶10⟶4⟶77⟶8⟶2⟶5⟶17⟶7Timetable (min)0⟶14⟶24⟶42⟶7272⟶82⟶94⟶110⟶130⟶150Supply (case)0⟶10⟶16⟶13⟶00⟶5⟶15⟶14⟶0CRoute13⟶22⟶15⟶1313⟶24⟶23⟶21⟶1313⟶14⟶1⟶13Timetable (min)0⟶22⟶30⟶5858⟶66⟶74⟶90⟶106106⟶126⟶158⟶196Supply (case)0⟶17⟶23⟶00⟶12⟶12⟶16⟶00⟶23⟶10⟶0DRoute13⟶24⟶12⟶3⟶1313⟶14⟶20⟶1313⟶11⟶13Timetable (min)0⟶8⟶38⟶48⟶8080⟶100⟶126⟶150150⟶180⟶210Supply (case)0⟶3⟶15⟶12⟶00⟶21⟶19⟶00⟶25⟶0It is obvious that these two plans meet the flow balance constraint, capacity constraint, vehicle scheduling constraint, and time window constraint. However, compared with the control plan, the total supply waiting time of the optimized solution of the model is reduced by 11.92%, showing better timeliness. At the same time, the total number of vehicle trips in the optimized solution of the model is reduced by 1, indicating that its vehicle transportation utilization rate has been improved. Therefore, it can be concluded that the proposed model more effectively solves the problem of emergency supply distribution.


## 5. Conclusion

This study proposes an emergency supply distribution model, which is defined by its main features, that is, round trips and nonfixed routes. The objective function of the model is set to minimize the total waiting time of supplies of all demand points, which will help improve the timeliness and fairness of the supply distribution plan. In addition, according to the features of the model, the flow balance constraint, capacity constraint, vehicle scheduling constraint, and time window constraint are set, respectively. A compound algorithm based on 2-opt and tabu search is designed to solve the emergency supply distribution model. In order to verify the effectiveness of the proposed model and algorithm, a case study is carried out in the Sioux Falls network. Compared with the control plan, not only the objective function of the optimal emergency supply distribution plan of the model is reduced by 11.92% but the total number of vehicle trips is also reduced by 1. It significantly indicates that the optimal solution of the model is more effective, which helps reduce system costs and improve rescue efficiency. Through the case study, the superiority of the proposed model and algorithm can be verified.With the control of multiple constraint conditions, the model well fits the actual application scenarios. Compared with the traditional models, it has better applicability and practicability, which can provide theoretical guidance and decision support for the distribution of relevant emergency supplies. However, in some special cases, it may be difficult to obtain accurate supply demands of demand points the first time. Therefore, the author will further study methods to apply the model in the cases of emergency supply distribution with uncertain demands. In addition, the intelligent development of transportation is imperative. For example, smart roads, autonomous vehicles, and unmanned aerial vehicles (UAVs) have been more and more studied and applied, which own the advantages of high efficiency, convenience, and flexibility [19–21]. Hence, the author will also further explore emergency supply distribution methods to combine traditional vehicle transportation with intelligent transportation technology.



---

*Source: 9068442-2022-02-16.xml*