ALLOCATING EMERGENCY RESPONSE RESOURCES ON URBAN RAIL TRANSIT

Binjun MA，Qinghuai LIANG，Xiaohong LIANG

School of Civil Engineering，Beijing Jiaotong University，Beijing 100044

Abstract：Optimal allocation of emergency resources is a pivotal content of the emergency management on urban rail transit.It is a key step in emergency rescue and assistance.This paper，based on the analysis of feature of emergency in urban rail transit，presents the characteristics of emergency resources allocation of urban rail transit under emergency.They are “time first and consider others”，“many-to-one”，“multi-resources coordination” and “the fuzziness between resource demand and response time” respectively.Based on this analysis，we build the resource allocating model with the earliest emergency rescue starting time as the objective function and with the readiness of all emergency resource as constraint condition.Considering the uncertainty of emergency resource demand and response time，this model expresses the resource demand and response time through interval number.And the solving method is given.Finally the example demonstrates the effectiveness of the model and solving method.Our method and algorithm could provide the theoretical basis for the design of emergency plan and resources allocation under emergency of urban rail transit.

Keywords：urban rail transit，emergency response，resources allocation，optimization，model and algorithm

Email：12115311@bjtu.edu.cn

1　Introduction

As an integral part and essential feature of city transportation，urban rail transit（URT）plays an important role in developed and developing countries.However，different kinds of unexpected events occur occasionally to the urban rail transit（see Figure 1）around the world，which cause the operation interruption of urban rail transit and lead a great threat to people’s life，property safety and social stability[1].In China，the urban rail transit is a separate system with its own emergency system.Research on the emergency resource allocation to urban rail transit under emergency is significant to improve the processing ability and efficiency of rail network and to shorten the recovery time of network to open to traffic after the accident and to ensure the normal and safe operation of the urban rail transit system as well.

This paper built a mathematical model allowing for calculation of an optimized resource schedule to help solve the emergency resource allocation problem.

In former research，there are few studies about the emergency resource allocation of urban rail transit.However，there are a lot of studies referred to the resource allocation under emergency which mainly include two parts-model building and solving algorithm.

The general form of emergency resource allocation model under emergency is：

min f（x1，x2，…，xn）

xj≥0，j=1，2，…，n

On the premise that the emergency resources meet the demand，the objective function is the minimum.The objective function could be the emergency response time[2]，transport cost[3]，death toll[4]，risk[5]and the utility of rescue[6].

The above research is focus on single event，such as the earthquake or the fire disaster.However，the urban rail transit is a complex system integrated by multi-specialty.The emergency is always comprehensive event mixed with various emergencies instead of the single event.Therefore，the above model is not suitable for urban rail transit system.

Resources allocation is a function optimization problem with the objective of minimizing f（x1，x2，xn）while satisfying the constraints posed by the system.In the literature，several algorithmic approaches have been proposed to achieve the optimal resources allocation，which mainly include the dynamic programming[7，8]，integer programming[9，10]，Lagrange multiplier[11，12]，simulated annealing[13，14]，genetic algorithm[15]，branch and bound[16]，game theory[17]，greedy[18]，tabu search[19].

This paper is organized as follows.Section 2describes characteristics of emergency resource allocation of urban rail transit.And we build the model for emergency resource allocation of urban rail transit under unexpected events.Then Section 3 proposes an effective algorithm to solve the model.Section 4 depicts a numerical case of an emergency allocation problem using simulation data，and provides the corresponding results to demonstrate the feasibility and effectiveness of the proposed method.The conclusion and remarks about our research are summarized in Section 5.

2　Model Developments

2.1　Emergency resources allocation characteristics

2.1.1　Optimization objective

The emergency of urban rail transit is a public event and crisis.Under this situation，we have to analyze，judge and make emergency decisions in a remarkably short period of time.The first issue to consider when allocate the resource should be time rather than the cost which is not the most important factor under emergency.Based on the basic rule of “time first and consider others”，the target of model we build in this paper is minimizing the earliest starting time of emergency rescue.

2.1.2　Service mode

In the case of networked urban rail transit system，the possibility of more than two emergencies happening to the whole network at the same time is extremely low.It is commonly considered that emergency happens to a point.Therefore，the emergency resource allocation of the urban rail transit is a relationship of many-to-one，which means multiple emergency resources distributed to one demand point.

2.1.3　Required resources

Under normal circumstances，emergency rescue needs the collaboration use of multiple resources.For example，the fire disaster needs the fire extinction equipment，respirator，fire escape mask and so on.Emergency of urban rail transit is the case needed multiple resources as well.

2.1.4　Demand

The urgency degree of urban rail transit is different as the event changes.Therefore，the demand of emergency resources is constantly changing too.It needs to estimate the demand of emergency resource which has strong fuzziness during the process of allocation.

2.1.5　Response time

The emergency resources could be easily affected by external factors within the transportation that the bad weather or the traffic accident could cause the random fluctuation of traffic flow.As a consequence，the emergency response time is uncertain，which we express through interval number in this paper as well.

2.2　Mathematical formulation

In this section，we build the emergency resource allocating model based on the characteristics analysis.The model is an integer programming model with the earliest emergency rescue starting time as the objective function and the readiness of all emergency resource as constraint condition.

2.2.1　Notation and terminology

We assume the number of one emergency facility is N，expressed in A1，A2，…，An.The set of emergency facility is L.A is the demand point.The set of paths from Ai，the ITH regency facility，to demand point A is Z.W（w>1）is the sum of emergency facility in total，expressed in X1，X2，…，XM.R is the set of emergency resource，R=R1，R2，…，Rd.φ is the set of emergency dispatch schemes including φ1，φ2，…，φd.The definitions of other parameters and variables are expressed as follows：

xij：The amount of storage of jthresource in ithemergency facility，i∈L，j∈R.

yij：The supply of jthresource to demand point from ithemergency facility，i∈L，j∈R；

nj：The demand for jthresource，nj∈[cj，dj]，j∈R .

：The emergency response time of the zthpath from Aito

ti：The minimum of

sj：The starting time of jthresource，j∈R.

min sj：The earliest starting time of jthresource，j∈R.

2.2.2　Model

Combined with the characteristics analysis of emergency resource allocation of urban rail transit，we build the following resource allocating model：

s*=max{min sj}　　（1）

s.t.

εyi≤yij≤xiyi，i ∈L　　（3）

yij≤xij，i∈L，j∈R　　（5）

yi∈{0，1}，i∈L　　（6）

The objective Function（1）is the latest one among the earliest starting time of all emergency resources.The Constraint（2）means that the supply of jthresource from emergency facilities with the total number of m is equal to the demand of jthresource under certain event.The Constraint（2）and（6）ensure that the yi，a0-1 variable，value 1 only whenand theε is the positive number which is small enough.The Constraint（4）means the dispatching time of jthresource to demand point is equal to the time of jthresource transported from the farthest emergency facility pj.The Constraint（5）ensures that the supply of jthresource from ithemergency facility is no more than the amount of storage of jthresource in ithemergency facility.

3　Algorithms

Definition 1：ф={ф1，ф2，…，фm}Tis any feasible solution.

The formulais the emergency dispatching solution for jthresource.The set including d1，d2，…，dkwhich we call an array，is the subsequence combination of series of 1，2，…，n.And the formulashows that the set of d1，d2，…，dkis picked from n retrieval depots to supply jthresource.The corresponding supply of jthresource isLet the set of all solutions is Ω.

3.1　Processing method of interval number

Through the analysis of characteristics of emergency resource allocation，the emergency response time and the resource demand are uncertain，which we express through interval number.The processing method is shown below.

3.1.1　Response time

We adopt the processing method took by literature[21]to express the response time through interval number.We rank the time intervals according to the optimal and worse order.Then all resources are dispatched according to the order.Set the response time

T1∈[a，b]，T2∈[c，d] and a，b，c，d are positive real numbers.The processing method takes the definition of possibility degree，which is set by the following formula：

lab=|[a，b] ∩[c，d ] |　　（8）

Since the shorter the response time the better，the response time is a negative index.Consider[a，b]<[c，d] When p（T1>T2）>0.5.The resource should be firstly dispatched by emergency facility with the response time T1.

Consider [a，b]=[c，d] when p（T1>T2）>0.5.The resource can be dispatched by emergency facility both with the response time T1and T2.Consider [a，b]>[c，d] when p（T1>T2）>0.5.Then the resource should be firstly dispatched by emergency facility with the response time T2.

The solving method of interval number could be described as follows.Since the response time of every emergency facility is interval number，the earliest response time we find is also an interval number.We take [a，b] if a>d when[a，b] ∩[c，d]=ф and take [c，d] if c>b.When[a，b] ∩[c，d]=[e，f ]≠ф，then we take e as the left point of the earliest response time and take f=max{b，d} as the right point.The operation nature and algorithms of other interval numbers could be found in literature[20].

3.1.2　Demand

In this paper，we take the maximum of interval number when calculating the model.If the interval number of emergency resource demand is [g，h]，then we take h as the resource demand.

3.2　Framework of algorithm

Intuitively，we should select those retrieval depots with shorter response time forming the emergency solution to make the response time as early as possible.Therefore，we only need to find the response time of each emergency resource and then pick out the maximum to the multiple emergency resource allocation issue of urban rail transit.

According to the above analysis，the retrieval depots set of A1，A2，…，Anis in ascending order of emergency response time ti.SetThe dispatching solution with earliest rescue starting time of jthresource could be described by the following formula：

The earliest starting time is the maximum of response time of emergency facility A1，A2，…，Since the emergency facilities are in ascending order of emergency response time，the response timeof emergency facilityis the earliest rescue starting time.For the optimization goal，the earliest rescue starting time is the maximum of response time of all required emergency resources.

3.3　Details of algorithm

Step 1：compare the priority of response time interval of every emergency facility and rank them according to the priority；

Step 2：find the demand of emergency facility pjfor jthresource.Based on the demand of every resource xjand the supply of every emergency facility，we dispatch resources according to the sequence solved by Step 1，which could be described by the following formula：

Step 3：find the dispatching time interval sjof jthresource，which is equal to the response time of jthresource transported from the farthest emergency facility among pjfacilities to demand point.

Step 4：find the earliest rescue starting time：

s*=max{s1，s2，…，sM}.

4　Case Studies

In this section，we take the emergency rescue of a certain urban rail transit for example to test the model.The supply and demand of emergency facility（4 facilities nearby）and emergency resources（relevant）see Table 1 and the response time of emergency facility to demand point see Table 2.

Step 1：according to the processing method of interval number shown in 3.1，the subsequence of response time of emergency facility to demand point is：t1< t2< t3< t4.The demand of every resource is 32，37，34，3，32，7，10，27 and 66 respectively.

Step 2：for the resource X1，set the demand of emergency facility p1=3.The emergency facility include A1，A2，A3.Then the earliest response time of this resource is s1∈[15，20].Similarly，the amount and the earliest starting time of emergency facility other resources require see Table 3.

Therefore，the earliest rescue starting time of this case is s*∈[15，20]，which means we can run rescue in the interval[15，20].In this case，if the resource storage of emergency facility is more than the demand of demand point，then the emergency solution is not unique which means there could be a lot of optimal solutions.For example，there are tree emergency facilities which could supply the resource R1and the supply ceiling is 33 while the demand is 32.The solution of R1dispatched to demand point is shown in Table 4.

If the storage of emergency facility is equal to the demand of demand point，then the dispatching solution is unique.For example，for the required resource R4，we have to take use of all resources from both A1and A2.Therefore，there is room to adjust the dispatching solution here on the occasion of meeting the demand.Even if there is capacity limitation of rescue vehicles，we could take the solution {（A1，10）（A2，11），（A2，11）} when the capacity limits is 11for the resource X1to reduce the number of vehicles to reduce the cost correspondingly.

Last but not least，the demands of emergency resources of the demand point have been responded successfully.The objective functions value is s*∈[15，20] by the algorithm.The algorithm is finally terminated.

In an Acer PC（2.0 GHz CPU，2.0 GB memory，Win 7 OS），we implement our algorithm with MATLAB.The results of our algorithm，branch-and-bound and enumeration algorithm are compared in Table 5.We find that our method is better than the other in the computing time.In addition，enumeration algorithm occur “combination explosion” of data，it is a hard task to get the optimal solutions according to the growing scale of practical application，Our algorithm has more advantages and will perform much better.

Compared with the branch-and-bound and enumeration algorithm，the computing time of our algorithm is saved by 11.8％ and 43.9％.The simulation study shows the effectiveness and efficiency of our proposed algorithm.It is a real-time algorithm and can be used to solve large-scale practical problem.Urban rail transit operation companies will benefit to make the reasonable emergency response decisions.

5　Conclusions

We conclude by analyzing the characteristics that the emergency resources allocation of urban rail transit under emergency is a multiple resources allocation issue based on “many to one” rescue mode，which needs to consider the response time and demand fuzziness.The basic rule is “time first and consider others”.We then formulate the model of urban rail transit emergency resource allocation under unexpected events.The emergency resource allocation is an effective way to minimize the response time and loss of disasters.There are many different kinds and amounts of demands of emergency resource in a short-period time during emergency response.In the former studies，the available algorithms are often based on the heuristic algorithms and enumeration algorithm.It is hard for them to provide the accurate solution and the real-time response to emergencies.The decision needs be improved to fit the practical situations and provides more effective and flexible strategies for emergency response.The results of the example provide more evidence for the effectiveness and efficiency of our proposed method.It is a real-time algorithm and can be implemented to solve large-size practical problems comprehensively.This paper could provide the theoretical basis for the design of emergency plan and resources allocation under emergency of urban rail transit.

Acknowledgments

This paper is partly supported by graduate innovation fund of Beijing Jiaotong University（2015）.

References

[1]Zhang M.，Wang F.Z.，LI P.，2012.The Platform of Network Operation Assistant Decision Making and Emergency for Urban Rail Transit[J].China Railway Science，1：113-120.

[2]Dai G.X.，Da Q.L.，2000.The Study of Combinatorial Scheduling Problem in Emergency Systems[J].Systems Engineering-Theory & Practice，9：52-55.

[3]Knott R.，1988.The Logistics of Bulk Relief Supplies[J].Disasters，11：113-115.

[4]Fiedrich F.，Gehbauer F.，Rickers U.，2000.Optimized Resource Allocation for Emergency Response after Earthquake Disasters[J].Safety Science，35：41-57.

[5]Sherali H.D.，Desal J.D.，Theodore S.，2004.Allocating Emergency Response Resources to Minimize Risk with Equity Considerations[J].American Journal of Mathematical and Management Sciences，3（24）：367-410.

[6]Rashmi S.S.，2004.An Event Driven Single Game Solution for Resource Allocation in a Multi-crisis Environment[D].Tampa：University of South Florida.

[7]Meltzin S.，Zlotnikov Y.，Shklyar B.Z.，1996.Optimal Allocation of ATM Networks Resources by Using a Dynamic Programming Approach[C].Nineteenth Convention of Electrical and Electronics Engineers in Israel，paper 1-4.

[8]Pronzato L.，Optimal L.，2001.Asymptotically Optimal Decision Rules for Sequential Screening and Resource Allocation[J].IEEE Transactions on Automatic Control，46：687-697.

[9]Rajkumar R.，Lee C.，Lehoczky J.P.，Siewiorek D.P.，1998.Practical Solutions for QoS-based Resource Allocation Problems[C].Proceedings of the 19th IEEE Real-Time Systems Symposium，paper 296-306.

[10]Gertphol S.，Prasanna V.K.，2003.MIP Formulation for Robust Resource Allocation in Dynamic Real-time Systems[C].Proceedings of the International Parallel and Distributed Processing Symposium，paper 8.

[11]Huang C.Y.，Lo J.H.，Kuo S.Y.，Lyu M.R.，2002.Optimal Allocation of Testing Sources for Modular Software Systems[C].Proceedings of the 13th International Symposium on Software Reliability Engineering，paper 129-138.

[12]Huang C.Y.，Lo J.H.，Kuo S.Y.，Lyu M.R.，2004，Optimal Allocation of Testing Sources Considering Cost，Reliability，and Testing-effort[J].Proceedings of the 10th IEEE Pacific Rim International Symposium on Dependable Computing，3：103-112.

[13]Puget J.F.，1993.Object Oriented Constraint Programming for Transportation Problems[C].Advanced Software Technologies for Scheduling，IEE Colloquium on.IET，paper 1-413.

[14]Hao Q.，Song B.H.，Gunawan E.，Ong J.T.，Soh C.B.，Zheng L.，1997.A Low-cost Cellular Mobile Communication System：A Hierarchical Optimization Network Resource Planning Approach[J].IEEE Journal on Selected Areas in Communications，15：1315-1326.

[15]Papavassiliou S.，Puliafito A.，Tomarchio O.，Ye J.，2002.Mobile agent-based Approach for Efficient Network Management and Resource Allocation：Framework and Applications[J].IEEE Journal on Selected Areas in Communications，20：858-872.

[16]Attiya G.，Hamam Y.，2004.Two Phase Algorithm for Load Balancing in Heterogeneous Distributed Systems[C].Parallel，Distributed and Network-Based Processing，Proceedings.12th Euromicro Conference on.IEEE，paper 434-439.

[17]Galati D.，Liu Y.，Simaan M.A.，2003.A Fast Algorithm for Unit Level Team Resource Allocation in a Game Environment[J].Proceedings of the 42nd IEEE Conference on Decision and Control，3：2872-2877.

[18]Kivanc D，Li G.Q.，Liu，H.，2003.Computationally Efficient Bandwidth Allocation and Power Control for OFDMA[J].Wireless Communications IEEE Transactions，2（6）：1150-1158.

[19]Al-Mahmeed A.S.，1998.Commercial Applications of Tabu Search Heuristics[J].IEEE International Conference on Systems，Man and Cybernetics，3：2391-2395

[20]Zhou D.Q.，Zhang Q.，Chen C.，2011.Resource Scheduling Problem in Emergency Systems with Un-known Emergency Time[J].Technoeconomics &Management Research，5：3-5.

ICRE2016-International Conference on Railway Engineering