# Two-Sided Matching on Comprehensive Transportation Network Emergency Vehicles’ Allocation

Authors: Kunwei Xie; Heying Xu; Hongxia Lv
Journal: Journal of Advanced Transportation
 (2021)

---

## Abstract

In emergency rescue, the allocation of comprehensive transportation network emergency vehicles often affects the efficiency of the whole rescue process. In the context of disasters, this paper researches the one-to-many two-sided matching problem between the emergency vehicles and the materials to be transported. Firstly, based on the needs of both parties involved in the matching, the satisfaction evaluation systems are constructed; with the goal of maximizing the weighted satisfaction of the affected areas and vehicles, the optimization model of the materials and emergency vehicles matching is established; then, an improved National Intern Matching Program (NIMP) algorithm is designed to solve the model, which is based on thek: 1 experimental pairing and updating ideas, and can take into account the capacity and destination constraints of vehicles in the matching process. Finally, through the calculation of an example, the matching scheme can make the satisfaction of material transportation reach 0.7392, and the simulation analysis proves that the scheme keeps certain stability in risky conditions.


---

## Body

## 1. Introduction

Emergency causes huge losses and social impact because of the suddenness, unpredictability, and diffusion. In the process of emergency response, transportation network often plays an important role in ensuring the transportation of materials and transfer of disaster victims. A scientific and reasonable allocation scheme of emergency vehicles can make limited transportation resources fit the transportation need between the supply point and the affected area to the maximum extent, which is of great significance for the improvement of emergency capacity of the whole society. However, disasters cause different degrees of damage to the road, resulting in one or more transportation networks getting paralyzed, which is not conducive to the emergency work.With the rapid construction of transportation infrastructure and modern comprehensive transportation system, the division of labor among various modes of transportation becomes clearer and closer. Therefore, the formulation of emergency transportation schemes should be based on different needs of affected areas, different characteristics of demand materials, and different modes of transportation, to realize the reasonable and efficient utilization of the emergency vehicles. Comprehensive transportation network emergency vehicles refer to all kinds of comprehensive transportation mobile equipment that can be used in the territory and the whole rescue scope in the process of joint prevention and control, emergency rescue, disaster victims transfer, post disaster recovery, and other work in order to control the disaster and reduce losses under the constraints of certain fixed facilities and channel transport capacity.Existing research on material transportation optimization mainly includes the emergency vehicle route planning, distribution, and scheduling.On the emergency vehicle route planning, Zhang et al. [1] established the shortest path model considering the road conditions and the shortage of demand resources. Hu [2] used a linear programming model to plan the route. Özdamar et al. [3] built a combined transportation path model based on node clustering.On the vehicle distribution, Rawls et al. [4] proposed a two-stage mixed integer programming location model. Bozorgi-Amiri et al. [5] established an emergency material distribution model considering the uncertainty of demand location.On the vehicle scheduling, Afshar et al. [6], Sabouhi et al. [7], and Huang et al. [8] researched the emergency vehicle scheduling model from the perspective of logistics operation. Laporte et al. [9], Arda et al. [10], Duan, et al. [11], and Klibi et al. [12] proposed the multistage model to optimize vehicle scheduling.The above papers mainly solve the problems of emergency vehicle distribution and scheduling, and the limitations are as follows. (1) Existing literature considers the same model of vehicles, and materials are homogeneous. (2) Existing literature usually ignores train, and flight operation is limited by timetable. Actually, in emergency transportation, different vehicles have different loading attributes and some of them may have fixed operating period. These constraints make existing research neither clarify the matching relationship between materials and vehicles nor put into use directly.Considering that the two-sided matching theory can be used to solve the matching problem between two objects and the development of emergency management information platform makes it easier to bring the information of various rescue resources into the unified platform for centralized management, it is possible for us to research how to find a satisfactory matching between materials and vehicles with this theory.Two-sided matching theory was first proposed by Gale and Shapley [13], and Roth [14, 15] clearly defined the concepts of “two-sided” and “two-sided matching.” “Two-sided” refers to the participants in the market who belong to two disjoint sets, and “matching” refers to the two-sided nature of market exchange. Since both parties have the preference to get stable matching, two-sided matching theory is used to study the matching process of disjoint parties with stable preference.The process of emergency vehicles’ allocation is participated by the vehicles and materials that need to be transported, and the core is to find an optimal resource allocation scheme in the context of emergency so that both sides can find the matching objects which meet their own needs. Therefore, combined with the characteristics of strong timeliness, high uncertainty, and weak economy of emergency rescue, this paper proposes an emergency vehicle allocation method based on the two-sided matching theory, which has three main contributions:(1)
The application of two-sided matching theory is extended(2)
A two-sided matching model considering materials’ loading demands is established, which can guide the matching of materials with specific emergency vehicles(3)
An example validates the stability and operability of emergency vehicles’ allocation scheme under certain risksThe remainder of the paper is organized as follows. Section2 introduces the problem and presents an analysis on matching satisfaction. Section 3 formulates a two-side matching model, and an improved Nation Intern Matching Program (NIMP) algorithm is proposed in Section 4. Thereafter, a matching example is conducted in Section 5. Section 6 concludes the paper and provides potential future work.


## 2. Matching Satisfaction Calculation

### 2.1. Problem Presentation

Suppose that there are disaster affected areas and each area needsM materials. We use R to denote the set of materials to transport:(1)R=R1,R2,…,Ri,…,RIT,=r11…r1M⋮⋱⋮rI1…rIM,where Ri denotes the set of materials demand of area i, Ri=ri1,…,rim,…,riM, and rim denotes the material m required for area i, i=1,2,…,I and m=1,2,…M.Emergency vehicle setV is composed of J vehicles, V=V1,…,Vj,…,VJ. Vj denotes vehicle j, j=1,2,…,J.MappingμR∪S⟶R∪S denotes the matching result between rim and Vj. If the rim is transported by Vj, rim∈μVj and Vj∈μrim.


### 2.2. Model Assumptions

Before modeling, we make the following assumptions: (1) the materials needed for one disaster affected area can be transported by different vehicles; (2) each vehicle is only used to meet the transportation demand of one disaster area, but it can transport different materials needed in this area; (3) each material rim cannot be separated or transshipped during transportation; (4) if vehicleVj is also the required material for affected areas, we assume a virtual good rim in set R, and this rim has the following characteristics: rim = Vj; the weight of rim is 0; rim can only be transported by Vj; (5) the number and capacity of available vehicles are limited.Because decision makers can obtain the information of the affected areas’ material demand and comprehensive transportation network emergency vehicles through the emergency management information platform, there is a two-sided matching market between the demand materials and emergency vehicles based on the information platform. According to the model assumptions, this is a one-to-many two-sided matching market. One affected area in this market can be served by multiple vehicles, which forms a one-to-many matching relationship between one area and vehicles; at the same time, one vehicle can transport a variety of materials, so that the matching market between vehicles and materials can be regarded as one-to-many matching relationships restricted by the materials’ destination. The operating mechanism of this matching market is shown in Figure1.Figure 1
Two-sided matching mode of emergency platform.


### 2.3. Matching Satisfaction Index Systems

The premise of establishing the demand materials and emergency transportation vehicles’ matching optimization model is the construction of the evaluation index systems on both sides so that we can evaluate the satisfaction of different matching schemes. The parameters related to evaluation models are given in Table1.Table 1
Notation statement.
SetStatementUSet of demand materials satisfaction evaluation indexSSet of emergency vehicles’ satisfaction evaluation indexlojThe loadable materials set of vehicleVjParameterStatementTimjEstimated arrival time of rim transported byVjTimminMinimum value ofTimj for each rimTimj^Maximum positive deviation ofTimj affected by emergencyTWimmin,TWimmaxSatisfaction arrival time window ofrimξjDelay probability ofVjξjminMinimum value ofξjdimjDeadhead kilometers ofrim transported by Vjdjmin,djmaxMinimum and maximum value ofdimj for each VjtimjHandling time ofrim transported by Vjtjmin,tjmaxMinimum and maximum value oftimj for each VjgimEstimated weight ofrimcjCargo capacity ofVjκControl coefficient of arrival timeWe useU=u1,u2,…,u4 to denote the satisfaction evaluation index set of demand materials and S=s1,s2,…,s4 to denote the satisfaction evaluation index set of comprehensive transportation network emergency vehicles. Combined with the research on the evaluation of emergency material allocation [16–20] and vehicle-material matching problem [21–25] and considering the potential applications of the proposed method in high-speed rail systems [26, 27], the evaluation index systems on both sides are established.For each material to be transported, the optimal scheme is to make the transportation time as short as possible. And, the transportation route should be reliable, so as to avoid the routes damage making the material transportation interruption. Therefore, on the basis of the loading characteristics of materials, we establish the material satisfaction evaluation index system as follows.(1)
Arrival time indexu1im,j: in emergency transportation, higher satisfaction of materials means earlier arrival time transport by vehicles:(2)u1im,j=TimminTimj.(2)
Delay probability indexu2im,j: the delay probability of Vj reflects the reliability of vehicle route. Higher material satisfaction requires higher reliability and lower delay probability:(3)u2im,j=ξjminξj.(3)
Loading condition indexu3im,j: different vehicles have different loading conditions, such as thermal, container, and flat, and materials evaluate different vehicles according to their own requirements:(4)u3im,j∈0,1.(4)
Cargo capacity indexu4im,j: the weight of materials should not exceed the vehicles’ weight limitations:(5)u4im,j=0,gim>cj,1,gim≤cj.The satisfaction value of the materials in relation to vehicles is calculated as follows. In equation (6), ωpim denotes the weight of upim,j, ∑p=14ωpim=1, and the satisfaction value matrix is RV, RV=λjimJ×I×M:(6)λjim=∏p=14upim,jωpim,∀j.The rescue mission of each vehicle is to deliver materials to the respective destinations reliably and effectively. In actual rescue, emergencies usually attack routes thus prolonging the transportation time. So, we introduce control coefficientκ of arrival time, in response to the risk that materials cannot be delivered on schedule. Combined with vehicle loading operation, we establish the vehicle satisfaction evaluation index system as follows.(1)
Satisfaction time window indexs1j,im: the arrival time of emergency transportation is usually uncertain. Therefore, we reserve satisfactory time window and keep a certain time margin to ensure the stability of the scheme:(7)s1j,im=1,Timj+κ⋅Timj^≤TWimmin,1−2Timj+κ⋅Timj^−TWimminTWimmax−TWimmin2,TWimmin<Timj+κ⋅Timj^≤TWimmin+TWimmax2,2Timj+κ⋅Timj^−TWimmaxTWimmax−TWimmin2,TWimmin+TWimmax2<Timj+κ⋅Timj^≤TWimmax,0,Timj+κ⋅Timj^>TWimmax.(2)
Empty driving indexs2j,im: the origin of Vj should be the same as the rim to avoid empty driving:(8)s2j,im=djmax−dimjdjmax−djmin+ε.In order to ensure materials are transported as many as possible, we use minimumε to make s2j,im>0.(3)
Handling time indexs3j,im: the handling time reflects the complexity of handling operations:(9)s3j,im=0,rim∉loj,tjmax−timjtjmax−tjmin+ε,rim∈loj.In addition, in order to ensure materials are transported as much as possible, we use minimumε to make s2j,im=0 if and only if rim∉loj.(4)
Cargo capacity indexs4j,im: the cargo capacity of vehicles should exceed the materials’ weight:(10)s4j,im=0,gim>cj,1,gim≤cj.The satisfaction value of the vehicles in relation to materials is calculated as follows. In equation (11), ωqj denotes the weight of sqj,im, ∑q=14ωqj=1, and the satisfaction value matrix is VR, VR=θjimJ×I×M:(11)θjim=∏p=14spj,imωqj,∀i,m.


## 2.1. Problem Presentation

Suppose that there are disaster affected areas and each area needsM materials. We use R to denote the set of materials to transport:(1)R=R1,R2,…,Ri,…,RIT,=r11…r1M⋮⋱⋮rI1…rIM,where Ri denotes the set of materials demand of area i, Ri=ri1,…,rim,…,riM, and rim denotes the material m required for area i, i=1,2,…,I and m=1,2,…M.Emergency vehicle setV is composed of J vehicles, V=V1,…,Vj,…,VJ. Vj denotes vehicle j, j=1,2,…,J.MappingμR∪S⟶R∪S denotes the matching result between rim and Vj. If the rim is transported by Vj, rim∈μVj and Vj∈μrim.


## 2.2. Model Assumptions

Before modeling, we make the following assumptions: (1) the materials needed for one disaster affected area can be transported by different vehicles; (2) each vehicle is only used to meet the transportation demand of one disaster area, but it can transport different materials needed in this area; (3) each material rim cannot be separated or transshipped during transportation; (4) if vehicleVj is also the required material for affected areas, we assume a virtual good rim in set R, and this rim has the following characteristics: rim = Vj; the weight of rim is 0; rim can only be transported by Vj; (5) the number and capacity of available vehicles are limited.Because decision makers can obtain the information of the affected areas’ material demand and comprehensive transportation network emergency vehicles through the emergency management information platform, there is a two-sided matching market between the demand materials and emergency vehicles based on the information platform. According to the model assumptions, this is a one-to-many two-sided matching market. One affected area in this market can be served by multiple vehicles, which forms a one-to-many matching relationship between one area and vehicles; at the same time, one vehicle can transport a variety of materials, so that the matching market between vehicles and materials can be regarded as one-to-many matching relationships restricted by the materials’ destination. The operating mechanism of this matching market is shown in Figure1.Figure 1
Two-sided matching mode of emergency platform.


## 2.3. Matching Satisfaction Index Systems

The premise of establishing the demand materials and emergency transportation vehicles’ matching optimization model is the construction of the evaluation index systems on both sides so that we can evaluate the satisfaction of different matching schemes. The parameters related to evaluation models are given in Table1.Table 1
Notation statement.
SetStatementUSet of demand materials satisfaction evaluation indexSSet of emergency vehicles’ satisfaction evaluation indexlojThe loadable materials set of vehicleVjParameterStatementTimjEstimated arrival time of rim transported byVjTimminMinimum value ofTimj for each rimTimj^Maximum positive deviation ofTimj affected by emergencyTWimmin,TWimmaxSatisfaction arrival time window ofrimξjDelay probability ofVjξjminMinimum value ofξjdimjDeadhead kilometers ofrim transported by Vjdjmin,djmaxMinimum and maximum value ofdimj for each VjtimjHandling time ofrim transported by Vjtjmin,tjmaxMinimum and maximum value oftimj for each VjgimEstimated weight ofrimcjCargo capacity ofVjκControl coefficient of arrival timeWe useU=u1,u2,…,u4 to denote the satisfaction evaluation index set of demand materials and S=s1,s2,…,s4 to denote the satisfaction evaluation index set of comprehensive transportation network emergency vehicles. Combined with the research on the evaluation of emergency material allocation [16–20] and vehicle-material matching problem [21–25] and considering the potential applications of the proposed method in high-speed rail systems [26, 27], the evaluation index systems on both sides are established.For each material to be transported, the optimal scheme is to make the transportation time as short as possible. And, the transportation route should be reliable, so as to avoid the routes damage making the material transportation interruption. Therefore, on the basis of the loading characteristics of materials, we establish the material satisfaction evaluation index system as follows.(1)
Arrival time indexu1im,j: in emergency transportation, higher satisfaction of materials means earlier arrival time transport by vehicles:(2)u1im,j=TimminTimj.(2)
Delay probability indexu2im,j: the delay probability of Vj reflects the reliability of vehicle route. Higher material satisfaction requires higher reliability and lower delay probability:(3)u2im,j=ξjminξj.(3)
Loading condition indexu3im,j: different vehicles have different loading conditions, such as thermal, container, and flat, and materials evaluate different vehicles according to their own requirements:(4)u3im,j∈0,1.(4)
Cargo capacity indexu4im,j: the weight of materials should not exceed the vehicles’ weight limitations:(5)u4im,j=0,gim>cj,1,gim≤cj.The satisfaction value of the materials in relation to vehicles is calculated as follows. In equation (6), ωpim denotes the weight of upim,j, ∑p=14ωpim=1, and the satisfaction value matrix is RV, RV=λjimJ×I×M:(6)λjim=∏p=14upim,jωpim,∀j.The rescue mission of each vehicle is to deliver materials to the respective destinations reliably and effectively. In actual rescue, emergencies usually attack routes thus prolonging the transportation time. So, we introduce control coefficientκ of arrival time, in response to the risk that materials cannot be delivered on schedule. Combined with vehicle loading operation, we establish the vehicle satisfaction evaluation index system as follows.(1)
Satisfaction time window indexs1j,im: the arrival time of emergency transportation is usually uncertain. Therefore, we reserve satisfactory time window and keep a certain time margin to ensure the stability of the scheme:(7)s1j,im=1,Timj+κ⋅Timj^≤TWimmin,1−2Timj+κ⋅Timj^−TWimminTWimmax−TWimmin2,TWimmin<Timj+κ⋅Timj^≤TWimmin+TWimmax2,2Timj+κ⋅Timj^−TWimmaxTWimmax−TWimmin2,TWimmin+TWimmax2<Timj+κ⋅Timj^≤TWimmax,0,Timj+κ⋅Timj^>TWimmax.(2)
Empty driving indexs2j,im: the origin of Vj should be the same as the rim to avoid empty driving:(8)s2j,im=djmax−dimjdjmax−djmin+ε.In order to ensure materials are transported as many as possible, we use minimumε to make s2j,im>0.(3)
Handling time indexs3j,im: the handling time reflects the complexity of handling operations:(9)s3j,im=0,rim∉loj,tjmax−timjtjmax−tjmin+ε,rim∈loj.In addition, in order to ensure materials are transported as much as possible, we use minimumε to make s2j,im=0 if and only if rim∉loj.(4)
Cargo capacity indexs4j,im: the cargo capacity of vehicles should exceed the materials’ weight:(10)s4j,im=0,gim>cj,1,gim≤cj.The satisfaction value of the vehicles in relation to materials is calculated as follows. In equation (11), ωqj denotes the weight of sqj,im, ∑q=14ωqj=1, and the satisfaction value matrix is VR, VR=θjimJ×I×M:(11)θjim=∏p=14spj,imωqj,∀i,m.


## 3. Two-Sided Matching Model

Since different disaster affected areas have different urgency and materials play various roles in different areas,αim denoting demand urgency weight of rim is used to make the matching scheme satisfy the total material demand to the maximum extent. We aim at optimal satisfaction on both sides and establish a one-to-many two-sided matching model:(12)maxF1=∑i=1I∑m=1Mαim⋅∑j=1Jλjim⋅xjim,(13)maxF2=∑i=1I∑m=1M∑j=1Jθjim⋅xjim,(14)s.t.∑j=1Jxjim≤1,∀i,m,(15)∑m=1Mxjim⋅∑m=1Mxji′m=0,∀j,i,i′;i≠i′,(16)∑i=1I∑m=1Mgim⋅xjim≤cj,∀j,(17)λjim−λ′⋅xjim≥0,∀j,i,m,(18)θjim−θ′⋅xjim≥0,∀j,i,m,(19)xjim=1,∀j,i;rim=Sj,(20)xjim∈0,1,∀j,i,m.Equations (12) and (13) are the object of the optimization model. Equation (12) means maximum satisfaction of affected areas. Equation (13) represents the optimal object of vehicles. Equation (14) limits one material matches at most one vehicle. Equation (15) indicates that one vehicle is only used to meet the transportation demand of one disaster area. Equation (16) gives the cargo capacity constraint, in which the cargo capacity of the vehicle should exceed the weight of matching materials. Equations (17) and (18) are the minimum matching satisfaction constraint: if and only if rim and θjim>θ′, matching between rim and Vj is possible. Equation (19) denotes if rim=Vj, xjim=1. Equation (20) denotes the range of decision variable xjim. xjim=1 denotes rim matches Vj. xjim=0 denotes rim does not match Vj.


## 4. Algorithm Design

National Intern Matching Program (NIMP) algorithm is an efficient algorithm which has been applied in one-to-many matching problem and successfully served many markets. The NIMP is consisted of a matching phase and a tentative assignment and update phase. In thekth step of the matching phase (which is called k: 1 step), the demander-supplier pairs such that the demander is top ranked on the supplier’s ranking and the supplier is kth ranked by the demander are sought to find (here we assume one supplier serves multiple demanders). If such matches are found, the algorithm proceeds to tentatively assign and update [28]. It is proved that NIMP algorithm can generate stable matching in given preference and obtain the optimal stable matching of one party under strict preference sequence.Because there are two matching markets in the model: one vehicle matches multiple materials and one affected area matches multiple vehicles, and NIMP algorithm is used to solve only one matching market problem. This paper proposes an improved NIMP algorithm to solve the model. The definition of algorithm parameters is as follows.n denotes iteration variable; R1n denotes unmatched set of materials in the nth iteration, R2n denotes matched set of materials, R1n∩R2n=∅, R1n∪R2n=R; PVjnis the set that Vj is nth ranked by rim∈PVjn, and λjim′>λ′, θjim>θ′; PVj,in⊆PVjn, each rim∈PVj,in meets ∑rim∈PVj,inλjim′=max∑rim∈PVjn∩Riλjim′, ∑rim∈PVj,ingim≤cj, and belongs to the same Ri; μn denotes the matching scheme in the nth iteration; cjn denotes the remaining cargo capacity of Vj before nth iteration.Step 1: calculate the satisfaction matrixVR=θjimJ×I×M and RV′=λJ′×I×M=λjimJ⋅αimI×M, and obtain the preference order lists submitted by the demand materials and vehicles.Step 2: initialize variablesn = 1. Determine whether rim = Vj is present; if yes, μ1rim=Vj, μ1Vj=rim, R11=R−rim, and R21=R21∪rim, and turn to step 3; else, R11=R, R21=∅, PVj1=∅, μ1rim=∅, μ1Vj=∅, and turn to step 3.Step 3: find thenth choice Vj of each rim. Identify the set PVjn of Vj, PVjn⊆R1n. If one material has the same satisfaction for different vehicles, take a random method to determine a virtual strict preference order. Match Vj and rim as the following steps.(1)j = 1.(2) Determine whetherPVjn=∅ is true; if yes, turn to step 3.8; else, turn to step (3).(3) Determine whetherμnVj=∅ is true; if yes, turn to step (4); else, turn to step (3).(a) Determine whetherPVjn=1 is true; if yes, let μn+1rim=Vj, μn+1Vj=rim, R1n+1=R1n−PVjn, R2n+1=R2n∪PVjn, and cjn+1=cjn−gim, and turn to step (8); else, turn to step (b).(b) Determine whether there are different material need to be transported in the same direction in setPVjn; if yes, turn to step (c); else, only if λjim′=maxλjim′, let μn+1rim=Vj, μn+1Vj=rim, R1n+1=R1n−PVjn, R2n+1=R2n∪PVjn, and cjn+1=cjn−gim, and turn to step (8).(d) Letμn+1Vj=PVj,in, μn+1rim=Vjrim∈PVj,in, R1n+1=R1n−PVj,in, R2n+1=R2n∪PVj,incjn+1=cjn−∑mgim, and turn to step (8).(4) Find the setPVj,in; determine whether PVj,in is empty; if yes, turn to step (8); else turn to step (5).(5) Determine whetherPVj,in and μnVj belong to the same Ri, if not, turn to step (6); if yes, let μn+1Vj=μnVj∪PVj,in, μn+1rim=Vjrim∈PVj,in, R1n+1=R1n−PVj,in, R2n+1=R2n∪PVj,in, cjn+1=cjn−∑mgim, and turn to step (8).(6) Determine whether∑rim∈PVj,inλjim′>∑rim∈μnVjλjim′ is true; if yes, turn to step (7); if not, determine whether there is rim∈PVjn with the same destination as rim∈μnVj; if yes, let μn+1Vj=μnVj∪PVj,μnVjn, μn+1rim=Vjrim∈PVj,in, R1n+1=R1n−PVj,μnVjn, R2n+1=R2n∪PVj,μnVjncjn+1=cjn−∑mgim, turn to step (8); else, turn to step (8).(7) LetR1n+1=R1n∪μnVj, R2n+1=R2n−μnVj, PVj′n=PVj′n∪μnVj (Vj is the nth choice of rim), recalculate μnVj; let μn+1rim=Vjrim∈PVj,in,R1n+1=R1n+1−PVj,in, R2n+1=R2n+1∪PVj,in, and cjn+1=cj1−∑mgim, and turn to step (8).(8) Determine whetherj≥J is true; if yes, turn to step 4; else, j=j+1 and turn to step (2).Step 4: determine whetherR1n≠∅ is true; if yes, end the loop and turn to step 5; if not, determine whether n≥J is true; if not, n=n+1 and repeat steps 3-4; else, end the loop and turn to step 5.Step 5: determine whether there areμn+1Vj1, μn+1Vj2, and μn+1Vj3 which satisfy that①
μn+1Vj1 and μn+1Vj2 belong to the same Ri different from μn+1Vj3.②
cj1n+1≥∑rim∈μn+1Vj2gim.③
∑rim∈μn+1Vj3λj2im′−∑rim∈μn+1Vj3λj3im′>∑rim∈μn+1Vj2λj2im′−∑rim∈μn+1Vj2λj1im′. If yes, μn+2rim=Vj1rim∈μn+1Vj2, μn+2Vj1=μn+1Vj1∪​μn+1Vj2, μn+2Vj2=μn+1Vj3, μn+2rim=Vj2rim∈μn+1Vj3, μn+2Vj3=∅, and output, else, output.


## 5. Simulation Results and Analysis

To verify the validity of the two-sided matching model, we use the data of 4 affected locationsR1,R2,R3,R4, and each location needs 4 materials r11,r12,…,r44. At the same time, we collect information about 12 vehicles V1,V2,…,V12 used for emergency transportation. Information on materials and vehicles is shown in Tables 2 and 3.Table 2
Information on materials.
MaterialsWeight (t)Time window (h)TWimmin,TWimmaxαimωpimω1imω2imω3imω4imr1136[6, 24]0.1370.50.30.050.15r12188[24, 48]0.0980.30.30.20.2r13940[48, 72]0.0590.30.20.20.3r1416[12,48]0.0190.30.20.20.3r1520[6, 24]0.0270.50.30.050.15r1680[24, 48]0.0190.30.30.20.2r171200[48, 72]0.0040.30.20.20.3r248[12, 52]0.0120.40.20.10.3r3134[6, 24]0.1910.50.30.050.15r32150[24, 48]0.0820.30.30.20.2r331600[48, 72]0.0270.30.20.20.3r340r34=V4[12, 36]0.1370.50.40.050.05r4122[6, 24]0.0820.50.30.050.15r42130[24, 48]0.0350.30.30.20.2r431500[48, 72]0.0120.30.20.20.3r4410[12, 36]0.0590.40.30.20.1Table 3
Information on vehicles.
VehiclesCargo capacity (t)Loadable materials setξjVehicle typeωqjω1jω2jω3jω4jV120R-r34, r340.6Truck0.30.20.250.25V220R-r340.6Truck0.30.20.250.25V320R-r340.5Truck0.30.20.250.25V42r11,r21,r31,r34,r410.5Ambulance0.70.10.10.1V52000R0.2Freight train0.20.40.20.2V62000R0.2Freight train0.20.40.20.2V72000R0.22Freight train0.20.40.20.2V82000R0.22Freight train0.20.40.20.2V950R0.1Helicopter0.30.40.150.15V1050R0.1Helicopter0.30.40.150.15V1150R0.1Helicopter0.30.40.150.15V1250R0.1Helicopter0.30.40.150.15In addition, we calculate the estimated arrival time as follows:(21)Timj=21.821.8923.7921.712221.7926.1621.9935.9335.4642.14+∞34.5435.2640.5135.0921.422.4623.9221.912222.3226.1822.2935.5836.0241.92+∞34.7435.8140.4135.3423.823.8726.6423.6627.0526.7731.8427.1417.6417.4024.64+∞31.4332.1737.9431.923.424.2426.2923.8627.0527.2131.2627.4417.2917.8023.5216.4131.6332.5837.0932.1528.4128.3828.6028.5628.7828.5730.528.946.6646.0749.3147.1335.4836.0038.3236.1330.7730.3830.7930.6830.9830.5732.7430.984948.0751.6749.1337.638.0040.6238.2330.9131.2732.0731.2435.6735.5837.7436.0321.9922.0825.0122.9341.3642.0744.1841.9333.7334.2935.1634.1838.5738.5840.8638.9924.8225.1028.1925.9344.345.0847.3344.889.159.5011.978.89.209.0614.489.0515.1314.9822.8815.5410.7211.7418.1511.16.176.519.235.87.227.0612.637.117.036.9814.927.487.728.7615.228.0710.1510.4813.259.88.208.0513.848.0511.1310.9719.4211.545.726.7313.66.110.1710.5013.149.87.227.0512.517.119.038.9716.749.485.726.7413.076.07.The maximum positive deviation ofTimj is as follows:(22)T⌢imj=2020.0619.7520.032121.012121.0334.233434.434.333.943434.0634.1920.520.5620.2520.5321.521.5221.521.5334.7334.534.934.834.4434.534.5634.693333.0933.1932.9639.083939.1139.2623.9123.942413.946.2446.3946.1146.533.7533.8433.9433.7139.8339.7539.8640.0124.6624.6924.7524.6246.9947.1446.8647.2513.4913.5313.3213.513.991413.0014.0122.6522.522.7722.5717.517.5417.5917.6714.4914.5314.3214.514.991514.9915.0123.6523.523.7723.5718.518.5418.5918.6714.9214.941514.917.5417.517.5517.6210.4910.510.5310.4720.520.5720.4420.6216.4216.4616.516.419.041919.0519.1211.991212.0311.972222.0721.9422.122.102.102.072.12.402.42.402.403.933.93.953.9133.013.023.031.201.211.221.21.801.81.811.821.501.51.501.492.12.112.092.822.402.402.372.42.102.12.102.102.732.72.752.711.51.511.521.532.402.412.422.41.801.81.811.822.102.12.102.091.51.511.491.52.The distancesdimj between rim and Vj are as follows:(23)dimj=40452042212221231301121441207075809040452042212221231301121441207075809030354028403642502022251865735879303540284036425020222518657358795863386039403941148130162138889398108586338603940394114813016213888939810850556048605662704042453885937899505560486056627040424538859378998085608261626163170152184160110115120130606570587066728050525548951038810985906587666766681751571891651151201251358080907890869210070727568115123108129.The handlingtimj time is as follows:(24)timj=1.81.824.042.2410.785.160.961.71.467.74+∞1.11.266.450.90.91.903.671.840.50.814.680.760.851.527.02+∞0.551.315.850.651.81.804.512.2410.775.760.961.71.448.64+∞1.11.257.20.90.9+∞+∞+∞0.5+∞+∞+∞0.850.850.8500.55+∞+∞+∞1.441.331.972.080.80.572.520.881.361.073.7820.880.923.150.81.81.332.162.2410.572.760.961.71.074.1421.10.923.450.91.081.352.071.920.60.582.640.81.021.083.9620.660.943.30.70.91.372.161.840.50.582.760.760.851.104.1420.550.953.450.652.162.485.082.41.21.066.481.042.041.989.722.51.321.728.112.162.485.172.41.21.066.61.042.041.989.92.51.321.728.2512.162.465.362.41.21.056.841.042.041.9710.262.51.321.708.5512.162.465.082.41.21.056.481.042.041.979.722.51.321.708.11.And, the loading conditions’ satisfactionu3im,j is as follows:(25)u3im,j=0.50.7510.50.50.7510.50.50.75100.50.7510.5110.51110.51110.50110.510.50.7510.50.50.7510.50.750.75100.50.7510.510001000100110000.75110.750.75110.750.751100.75110.750.75110.750.75110.750.751100.75110.750.75110.750.75110.750.751100.75110.750.75110.750.75110.750.751100.75110.7510.750.5110.750.75110.750.5010.750.5110.750.5110.750.75110.750.5010.750.5110.750.5110.750.75110.750.5010.750.5110.750.5110.750.75110.750.5010.750.51.


### 5.1. Example Results

Settingε=10−8 and κ=10%, we calculate the satisfaction value matrices of RV′=λjim′J×I×M and VR=θjimJ×I×M are as follows:(26)Rv′=0000.00780.0087000.00500000000.01490000.00890.009000.005300000000.0170000.00790.0083000.004700000000.0163000000000000.057100000.05110.05120.03660.00970.01080.01010.00270.00580.05940.03780.016400.02640.01720.00760.02220.04910.05020.03580.00950.01040.00990.00260.00560.05790.03730.016200.02560.01690.00740.02170.04760.04830.03470.00920.00950.00920.00250.00520.0840.04580.019700.02370.01590.00710.02030.04560.0470.03370.0090.00910.0090.00240.0050.07910.04410.019100.02290.01560.0070.01980.1125000.01680.0239000.01090.13020000.0599000.04630.137000.0190.027000.0120.1910000.0706000.05260.1068000.01620.0253000.01140.15180000.082000.05890.1067000.01620.027000.0120.16850000.082000.059,VR=0000.89550000.9367000000000000.89240000.933000000000000.84980000.718700000000000000000000.8821000000.84460.89120.710300.96760.82660.8705000.001000.63140.5541000.830.88850.674800.94390.82410.8341000.001000.57750.5525000.78270.74440.685700.72230.67820.55630.34140.94240.09520.781100.21420.4707000.72470.74020.632400.62480.67440.503400.93570.09520.693800.10850.467300.8928000.90090.971000.98960.3213000.49570.7689000.71710.897000.90730.8303000.74220.966000.97270.5482000.010.8795000.90240.9827000.98960.3868000.50490.8092000.71710.8629000.90680.8302000.74220.9489000.97210.5519000.01.Assumingλ′=10−7 and θ′=10−7 and using improved NIMP algorithm to solve the model, finally, we get the maximum weighted satisfaction of F1 is 0.7392, and the optimal matching result is shown in Table 4.Table 4
Information on vehicles.
AreaVehicle typeResultR1HelicopterV9⟷r11Freight trainV5⟷r12,r13,r14R2HelicopterV12⟷r21,r24Freight trainV8⟷r22,r23R3HelicopterV10⟷r31Freight trainV7⟷r32,r33AmbulanceV4⟷r34R4HelicopterV11⟷r41,r44Freight trainV6⟷r42,r43It can be seen from the result that the loading characteristics are considered in the allocation scheme so that the materials can be matched with particular vehicles. This scheme is more specific than the existing research and plays a more practical guiding role in material emergency transportation.


### 5.2. Example Analysis

Considering the uncertainty of arrival time in emergency transportation, we design the following experiments to show that the matching scheme still has certain reliability under different delay risks.(1)
Firstly, setκ=10%, and the delay probability ξj of Vj is given in Table 3. Assume in actual rescue, the disturbance coefficient κactual is 20%, and the delay time of the delayed vehicle is κactual∗Timj^=20%∗Timj^. In this condition, we calculate the satisfaction of the optimal scheme attacked by disturbance coefficient κactual (κactual-optimal scheme for short) and the scheme in Table 4 (κ-current scheme for short), respectively. Repeat this experiment 2000 times, and the comparison between the κ-current and the κactual-optimal scheme is shown in Figure 2.We use green circle which denotesκ-current scheme satisfaction and blue line which denotes κactual-optimal scheme satisfaction. It can be seen from Figure 2, when κ=10% and disturbance coefficient κactuall is 20%, the gap between the κ-current scheme and the κactual-optimal scheme is not noticeable. This result shows that κ=10% and can make the scheme stable to a certain extent.(2)
On the basis of the above experiment, we still makeκ=10% and change the value of disturbance coefficient κactual from 0 to 70%. Under each value of κactual, we calculate the mean satisfaction value of the κ-current and κactual-optimal schemes. The comparison is shown in Figure 3.We use the green circle which denotes the variation inκ-current scheme satisfaction and the blue line which denotes the variation in κactual-optimal scheme satisfaction. The result shows that, with the increase of the disturbance coefficient κactual, the average satisfaction of the κ-current schemes and the κactual-optimal schemes show a downward trend, and the descent speed of κ-current schemes is faster than κactual-optimal schemes. Even so, when the disturbance coefficient is less than 53.7%, the difference between the satisfaction of the κ-current schemes and the κactual-optimal schemes is still not significant. When the disturbance coefficient exceeds 53.7%, because the overall satisfaction of R3 decrease significantly, the gap between the κ-current schemes and the κactual-optimal schemes has been widened.(3)
The value ofκ not only affects the reliability of the scheme but also affects the satisfaction of the κ-current scheme, so we change κ from 0 to 200% to find a reasonable value. Figure 4 shows the relationship between κ and the satisfaction of the κ-current scheme (green line) and the relationship between κ and stability of matching scheme (blue line) as well.Figure 2
Comparison between theκ-current and the κactual-optimal schemes.Figure 3
Relationship between the gap and the disturbance coefficient.Figure 4
Relationship betweenκ and the satisfaction of schemes, and the relationship between κ and stability of the κ-current schemes.The green line expresses ifκ≤49.7%, and the satisfaction of the κ-current schemes remains unchanged. Once κ>49.7%, the satisfaction of κ-current schemes falls rapidly.The blue line shows the value of disturbance coefficientκactual that the satisfaction of the κ-current scheme is lower than that of the optimal scheme for the first time. Whenκ≤49.7%, the value remains almost unchanged. Whenκ>49.7%, because of the nonideal κ-current scheme, all the optimal schemes are better than the κ-current ones.Based on the above analysis, the value ofκ should not exceed 49.7%.In practical application, the value ofκ can also be analyzed according to the specific situation of vehicles and materials to let the scheme have better stability and operability.


## 5.1. Example Results

Settingε=10−8 and κ=10%, we calculate the satisfaction value matrices of RV′=λjim′J×I×M and VR=θjimJ×I×M are as follows:(26)Rv′=0000.00780.0087000.00500000000.01490000.00890.009000.005300000000.0170000.00790.0083000.004700000000.0163000000000000.057100000.05110.05120.03660.00970.01080.01010.00270.00580.05940.03780.016400.02640.01720.00760.02220.04910.05020.03580.00950.01040.00990.00260.00560.05790.03730.016200.02560.01690.00740.02170.04760.04830.03470.00920.00950.00920.00250.00520.0840.04580.019700.02370.01590.00710.02030.04560.0470.03370.0090.00910.0090.00240.0050.07910.04410.019100.02290.01560.0070.01980.1125000.01680.0239000.01090.13020000.0599000.04630.137000.0190.027000.0120.1910000.0706000.05260.1068000.01620.0253000.01140.15180000.082000.05890.1067000.01620.027000.0120.16850000.082000.059,VR=0000.89550000.9367000000000000.89240000.933000000000000.84980000.718700000000000000000000.8821000000.84460.89120.710300.96760.82660.8705000.001000.63140.5541000.830.88850.674800.94390.82410.8341000.001000.57750.5525000.78270.74440.685700.72230.67820.55630.34140.94240.09520.781100.21420.4707000.72470.74020.632400.62480.67440.503400.93570.09520.693800.10850.467300.8928000.90090.971000.98960.3213000.49570.7689000.71710.897000.90730.8303000.74220.966000.97270.5482000.010.8795000.90240.9827000.98960.3868000.50490.8092000.71710.8629000.90680.8302000.74220.9489000.97210.5519000.01.Assumingλ′=10−7 and θ′=10−7 and using improved NIMP algorithm to solve the model, finally, we get the maximum weighted satisfaction of F1 is 0.7392, and the optimal matching result is shown in Table 4.Table 4
Information on vehicles.
AreaVehicle typeResultR1HelicopterV9⟷r11Freight trainV5⟷r12,r13,r14R2HelicopterV12⟷r21,r24Freight trainV8⟷r22,r23R3HelicopterV10⟷r31Freight trainV7⟷r32,r33AmbulanceV4⟷r34R4HelicopterV11⟷r41,r44Freight trainV6⟷r42,r43It can be seen from the result that the loading characteristics are considered in the allocation scheme so that the materials can be matched with particular vehicles. This scheme is more specific than the existing research and plays a more practical guiding role in material emergency transportation.


## 5.2. Example Analysis

Considering the uncertainty of arrival time in emergency transportation, we design the following experiments to show that the matching scheme still has certain reliability under different delay risks.(1)
Firstly, setκ=10%, and the delay probability ξj of Vj is given in Table 3. Assume in actual rescue, the disturbance coefficient κactual is 20%, and the delay time of the delayed vehicle is κactual∗Timj^=20%∗Timj^. In this condition, we calculate the satisfaction of the optimal scheme attacked by disturbance coefficient κactual (κactual-optimal scheme for short) and the scheme in Table 4 (κ-current scheme for short), respectively. Repeat this experiment 2000 times, and the comparison between the κ-current and the κactual-optimal scheme is shown in Figure 2.We use green circle which denotesκ-current scheme satisfaction and blue line which denotes κactual-optimal scheme satisfaction. It can be seen from Figure 2, when κ=10% and disturbance coefficient κactuall is 20%, the gap between the κ-current scheme and the κactual-optimal scheme is not noticeable. This result shows that κ=10% and can make the scheme stable to a certain extent.(2)
On the basis of the above experiment, we still makeκ=10% and change the value of disturbance coefficient κactual from 0 to 70%. Under each value of κactual, we calculate the mean satisfaction value of the κ-current and κactual-optimal schemes. The comparison is shown in Figure 3.We use the green circle which denotes the variation inκ-current scheme satisfaction and the blue line which denotes the variation in κactual-optimal scheme satisfaction. The result shows that, with the increase of the disturbance coefficient κactual, the average satisfaction of the κ-current schemes and the κactual-optimal schemes show a downward trend, and the descent speed of κ-current schemes is faster than κactual-optimal schemes. Even so, when the disturbance coefficient is less than 53.7%, the difference between the satisfaction of the κ-current schemes and the κactual-optimal schemes is still not significant. When the disturbance coefficient exceeds 53.7%, because the overall satisfaction of R3 decrease significantly, the gap between the κ-current schemes and the κactual-optimal schemes has been widened.(3)
The value ofκ not only affects the reliability of the scheme but also affects the satisfaction of the κ-current scheme, so we change κ from 0 to 200% to find a reasonable value. Figure 4 shows the relationship between κ and the satisfaction of the κ-current scheme (green line) and the relationship between κ and stability of matching scheme (blue line) as well.Figure 2
Comparison between theκ-current and the κactual-optimal schemes.Figure 3
Relationship between the gap and the disturbance coefficient.Figure 4
Relationship betweenκ and the satisfaction of schemes, and the relationship between κ and stability of the κ-current schemes.The green line expresses ifκ≤49.7%, and the satisfaction of the κ-current schemes remains unchanged. Once κ>49.7%, the satisfaction of κ-current schemes falls rapidly.The blue line shows the value of disturbance coefficientκactual that the satisfaction of the κ-current scheme is lower than that of the optimal scheme for the first time. Whenκ≤49.7%, the value remains almost unchanged. Whenκ>49.7%, because of the nonideal κ-current scheme, all the optimal schemes are better than the κ-current ones.Based on the above analysis, the value ofκ should not exceed 49.7%.In practical application, the value ofκ can also be analyzed according to the specific situation of vehicles and materials to let the scheme have better stability and operability.


## 6. Summary

This paper studies the matching problem between the materials to be transported and the comprehensive transportation network emergency vehicles in the process of rescue, aiming to promote the information sharing of transportation resources and the rational allocation of transportation resources and improve the quality of emergency rescue. We first establish evaluation index systems to measure the satisfaction of both parties. Next, based on the realistic constraints of the materials and vehicles matching, the multiobjective optimization model is established to maximize the satisfaction of the matching parties. Then, an improved NIMP algorithm is designed to solve the model. Finally, through the calculation of an example, it shows that the proposed method can obtain the optimal matching scheme different from the existing literature, which can specify the materials transported by certain vehicles on the basis of loading and arrival time demand. At the same time, repeated experiments show that the obtained matching scheme has excellent stability in the face of the uncertainty of transportation time caused by emergencies.The limitations of the paper are as follows. (1) The situation of multimodal transportation is not considered. (2) It is not applicable that materials can be separated. (3) Discussion about blending loading demand for materials is lacking. Therefore, in the next step of research, it is attemptable to transform the one-to-many matching mode into many-to-many matching mode and improve the satisfaction index extraction based on the characteristics of emergency.



---

*Source: 6817013-2021-07-05.xml*