Optimal dispatching method of traffic incident rescue resource for freeway network

Chai Gan Ran Xu Xia Jingxin

(1Intelligent Transportation System Research Center， Southeast University， Nanjing 210096， China)(2Changzhou Research Institute， Southeast University， Changzhou 213014， China)

T raffic incident response plays an important role in traffic management for maximizing freeway efficiency.A traffic incident is a non-recurrent event that can lead to traffic flow disruptions and capacity reductions［1］， and the resource dispatching methods are required to reduce the decision-making time by separately analyzing various factors that contribute to incident responses.Especially， the potential incidents that may occur at the same locations will affect the resource dispatching decisions.Therefore，it is necessary to develop a model for optimizing the resource dispatching under the demand of potential incidents.

Targeting the methods for traffic rescue resource dispatching， Zografos et al.［2-5］studied rescue resources in an area with dispatching events.These methods fit the dispatching type according to the sequence of events for local sections along the road，but they are limited in that an incident corresponds to only one response vehicle.Subsequently， Zografos et al.［6-7］studied the dispatching types based on the shortest distance from various rescue dispatching points to the current incident point.However， because of time-varying traffic congestion levels，the shortest distance does not mean the shortest travel time for the closest response vehicles to reach the incident point.In regard to the resource dispatching under potential incidents，Sherali et al.［1，8］defined the rescue cost of potential incidents as an opportunity cost and developed an opportunity cost-based dispatching model.When there are potential incidents in a freeway network，the dispatching of the closest rescue point for a current incident does not necessarily achieve global optimization.This method incorporates the rescue cost of potential incidents into the total rescue cost and attempts to solve the problem of resource dispatching on the freeway network.

Focusing on the resource dispatching under the freeway sections characteristics，both domestic and international researches still lack the ability to tackle the following issues.First， current methods do not consider the differences in dispatching the response vehicles.Practically，the relationships between the types and driving characteristics of the response vehicles are not considered.Secondly，current methods usually use a constant dispatching decision-making time for a response vehicle and do not reflect the impacts of different incident levels and different types of response vehicles.Finally， according to the conflicts among the performance indicators for dispatching optimization， e.g.， the conflict between response time and rescue cost，the conventional method cannot meet the requirements for optimized multi-incidents and multi-response dispatching problems［9］.

In summary，the minimum travel time or the minimum distance from the rescue point to the incident point cannot comprehensively reflect the impact of the incident level on the dispatching time and the differences among the driving speeds of different response vehicles［10］.By using the minimized summation of the dispatching time and the travel time as the objective function，this paper first proposes a method to estimate the decision time for different incident levels and the travel time of different response vehicles.Then，a genetic algorithm is presented to solve the problem of optimized response vehicle dispatching for potential incidents with multi-rescue points in the freeway network.

1 Modeling of Incident Rescue Resource Dispatching for Freeway Network

1.1 Conventional incident rescue resource model

LetLdenote the set of the rescue points;Fdenotes the set of the current incident points;Ndenotes the set of network nodes;ridenotes the response vehicles that are arranged for road rescue points wherei∈L;nfdenotes the number of response vehicles that are required for a current incident point wheref∈FandF?N; λifdenotes the minimum section weight that is calculated as the distance from rescue pointito the incident pointf;xifdenotes the number of response vehicles that are dispatched fromitof;Hdenotes the set of potential incident points whereH?N;Phdenotes the probability of potential incidents at nodehwhereh∈H;λihdenotes the minimum section weight that is calculated as the distance from rescue pointito potential incident pointh， λh≡minλih;andyrepresents an arbitraryyih.If the response vehicles are dispatched fromitoh， thenyih=1;otherwise，yih=0.Letsidenote the number of the remaining vehicles that can be dispatched for potential incident points after the dispatching of the vehicles fromitof，and the conventional rescue resource model［1］can be formulated as

The objective function(Eq.(1))is to minimize the total cost of incident rescues，including the direct cost of current incidents and the opportunity cost of potential incidents.Eq.(2)ensures that the number of vehicles dispatched from any depot does not exceed the number of service vehicles that are available at the depot.Eq.(3)stipulates that the number of vehicles dispatched to any current incident node should meet the service vehicle requirements at that node.Eq.(4)states that a service vehicle should be ready for dispatching rescue resources to potential incidents at any node in the network，whereas Eq.(5)states that such an additional vehicle in Eq.(4)can be dispatched from a depot only if it is available at that depot.Eq.(6)imposes the integrality and binary restrictions of the decision variables.

The limitation of the conventional model is that the rescue point and the section weight are fixed.Consequently，the impact of different types of resources on generating plans cannot be reflected.As is known， the dispatching decision-making time should vary with the type and the level of the incident.Therefore， the conventional model needs to be improved.

1.2 Modified incident rescue resource model

Previous studies have shown that the levels of incidents affect the dispatching decision-making time and that the driving characteristics of response vehicles are important factors in determining their travel time.Therefore， the dispatching time in this study is defined as the combination of the dispatching decision-making time and the travel time of response vehicles.The decision-making time refers to the time from the moment of determining the level of an incident to the moment of generating the dispatching plan.The travel time of response vehicles refers to the vehicles used on the rescue path.The dispatching time is given as

whereTifis the dispatching time from rescue pointito current incident pointf;Tihis the dispatching time from rescue pointito potential incident pointh;tfandthare the dispatching decision times determined by the levels of a current incident and a potential incident，respectively;λih/vihis the travel time of response vehicles;andvifandvihare the average driving speeds of the vehicles passing road sections from rescue pointito a current incident pointfand a potential incident pointh， respectively.According to the level of traffic incidents，the reference values of the dispatching decision-making time［11］are given in Tab.1.

Tab.1 Dispatching decision-making time according to levels of incidents min

The average driving speeds of different types of rescue vehicles［12］are given in Tab.2.

Tab.2 Average driving speed of rescue vehicles on road

By replacing the section weights λifand λihin Eqs.(1)to(6)with the dispatching timesTifandTihin Eq.(7)，and definingTh≡minTih， the modified potential demand based model is given as

Compared with the conventional model where the rescue cost is computed as the product of rescue route distance and the number of dispatched vehicles，the proposed model calculates the rescue cost as the product of the dispatching time and the number of dispatched vehicles to reflect the actual situation for dynamic traffic conditions.

2 Dispatching Plan Based on Genetic Algorithm

Response vehicles include traffic police，road patrol cars， wreckers， fire engines， ambulances， etc.In this section， a genetic algorithm(GA)［13］， including chromosome encoding， fitness function， selection， crossover，and mutation，is developed to solve the modified dispatching model for the response vehicle dispatching.The algorithm is coded in Matlab 7 by installing the GATbx(genetic algorithm optimization toolbox)developed by the University of Sheffield.

2.1 Chromosome encoding

In the chromosome encoding，the digit position in a chromosome is defined as the number of response vehicles dispatched from rescue pointLito incident pointFi.The general structure of the chromosome coding is shown in Tab.3.

Tab.3 General structure of chromosome coding

The numerical valueX1on the first position of a chromosome is the number of rescue vehicles dispatched from rescue pointL1to accident pointF1.In a road network with multi-rescue points and multi-accident points，each rescue point has its specific coverage due to the limits of the rescue time，and only the rescue points and accident points within the rescue point coverage are selected for encoding.The number of rescue points contained in a chromosome is determined by the location of the current incident，which means that rescue pointLxwill be included in the process of encoding if the current accident occurs within the coverage of rescue pointLx.According to the encoding characteristics，the encoding constraints are set as follows.

First， for the potential accident point， the total number of rescue vehicles obtained from different rescue points should not exceed the total demand for any given point;i.e.，whereXiis the number of response vehicles dispatched from the rescue point to the incident point andnhis the total number of demand vehicles for the potential incident.

Secondly， for the current accident point， the total number of rescue vehicles obtained from different rescue points should be equal to the number of demand vehicles;i.e.，wherenfis the total number of demand vehicles for the current incident.

Thirdly，the total number of response vehicles dispatched from each rescue point should not exceed the number of response vehicles allocated for this rescue point;i.e.，

whereriis the number of response vehicles equipped at this rescue point.

2.2 Fitness function

The fitness function is the objective function of the algorithm.The key point of dispatching is the formation of dispatching plans rather than the specific value of the rescue costs.Therefore， the fixed variables in the objective function in Eq.(8)can be eliminated， whereas the parameters that vary with the actual situation can be kept.Due to the fact thatyih=1，?h∈H，if the potential incident points are fixed， the term ofPh(－Thyih)=Ph(－Th)can be removed from the objective function in Eq.(8).Therefore， the latter term of Eq.(8)can be simplified asPhTih，whereis the number of response vehicles dispatched fromitoh.Set the occurrence probability of the current incident as 1，and the fitness function will be the product of the probability of the incidents，the dispatching time from the rescue point to the incident point，and the number of vehicles dispatched to the incident point.In this sense， theobjective function is minPiTixi，wherenis the chromosome coding length.When the genetic algorithm is used to calculate the maximum value，the objective func-tion can be converted to the form as max(a－PiTixi)，whereais an arbitrary constant.Considering the impact of the chromosome coding constraints，a penalty function is used.When a chromosome code contains values inconsistent with the constraints，the fitness of the chromosome is reduced to diminish the genetic probability of the chromosome to the next generation，so as to achieve the purpose of phasing out nonconforming chromosomes.The fitness function of the genetic algorithm is finally formed as

where the constraints for Eq.(12)are the same as those in Eqs.(9)， (10)and(11).

2.3 Selection， crossover and mutation

In this paper，the proposed genetic algorithm is coded to find the optimal dispatching decision by using the model built before for simplifying the process of selection， crossover and mutation.The GATbx is used in this process.The population size and genetic algebra can be determined according to the length of the chromosome and the complexity of the road network.The longer the chromosome，the larger the population size and the genetic algebra［14］.As all the chromosomes consist of smaller positive integers or 0， the commonly used “roulette wheel selection”operator can be used as the selection operator;the “single-point crossover”operator can be selected as the crossover operator;and the substantial population mutation function can be adopted.

In general，the occurrence probability of the crossover is several orders of magnitude that are higher than that of the mutation.In this context， a value between 0.6 and 0.95 is usually applied as the crossover probability， and a value between 0.001 and 0.01 is usually taken as the mutation probability.The specific value can be finetuned according to the real situation of the road network.

3 Case Study

In this section，the proposed model is empirically tested using a real world road network in Nanjing， China.

3.1 Description of the background

Fig.1 shows the abstracted topology of the tested road network， in which the nodes represent the hub， interchanges， and toll stations.The arcs between hubs and anodes are abstracted for the two-way road sections.The rescue points are also abstracted as nodes connected with the road network.Tab.4 gives the occurrence probability of potential incidents and Tab.5 shows the types and quantities of response vehicles allocated at various dispatching points.

Fig.1 Abstract diagram of the road network

Tab.4 Occurrence probability of potential incidents Phin network nodes

When a major accident that is 10 km away from Hushu Interchange and 10 km away from Shangfang Interchange occurs in the direction of Hushu Interchange to Shangfang Interchange on Nan-Hang freeway in the road network，the occurrence point of the accident is abstracted as node 0，and the types and quantities of resources required for rescue are determined according to the level of the accident as shown in Tab.6.

Tab.5 Types and quantities of response vehicle at dispatching points

Tab.6 Types and quantities of response vehicles required

3.2 Generation of dispatching plan

The dispatching plan is divided into sev eral independent parts according to the type of rescue vehicles.For example， a dispatching plan can be composed of five parts，i.e.， dispatching of police patrol cars， road patrol cars，48 t-class wreckers， 40 t-class cranes， and 60 t-class cranes.

Taking the dispatching of police patrol cars as an example，the process of obtaining the optimal dispatching plan by using the genetic algorithm is illustrated as below.

3.2.1 Creation of chromosome encoding

According to Fig.1， the incident at point 0 lies within the coverage of dispatching pointsA，CandD.The potential incident points withinA，CandDrescue points and the chromosome coding structure are shown in Tab.7.

Tab.7 Individual coding structure of police patrol vehicles

In the individual coding，Xiis the value of thei-th position corresponding to the number of patrol cars that are dispatched from the dispatching point to the accident point.

3.2.2 Constraint conditions for developing fitness function

The constraint conditions represented in Eqs.(9)，(10)and(11)are required to be determined when applying Eq.(12)for the fitness function.As shown in Tab.6，a total number of three police patrol cars are required to be dispatched for the incident.If rescue pointsA，CandDare equipped with two police patrol cars，respectively，the total number of police patrol cars dispatched by each rescue point cannot exceed 2.Meanwhile， for the potential incident points，it is deemed that the demand of rescue vehicles should not exceed 1.Therefore，the constraint conditions to be met by the dispatching plan are formulated asX1+X9+X18=3，X2+X10≤1，X3+X11≤1，X12+X19≤1，X13+X20≤1，X4+X14+X21≤1，X5+X15+X22≤1，X6+X16≤1，X7+X17≤1，X8+X23≤1，X1+X2+X3+X4+X5+X6+X7+X8≤2，X9+X10+X11+X12+X13+X14+X15+X16+X17≤2，X18+X19+X20+X21+X22+X23≤2.

3.2.3 Parameter design of genetic operators

Combined with the actual situation in this case，the number of chromosomes in the population is set to be 50;the largest genetic algebra is selected as 150;the generation gap value is set to be 0.9;the probability of a single-point crossover is set to be 0.7;and the mutation probability is set to be 0.004.By using the genetic algorithm，the output of the dispatching result is achieved after an iteration of 150.

3.2.4 Dispatching plan

The dispatching plan obtained through the genetic algorithm is shown in Tab.8.It is observed that the optimal dispatching plan does not necessarily select the rescue point with the shortest dispatching time to the incident point when considering the potential incidents in the road network.As indicated in Fig.1， pointAis the closest rescue point from incident point 0，but there are some potential incident points in the vicinity of pointA.Comparatively，the number of potential incident points is fewer for pointD.In this sense， the preferred dispatching of resources from rescue pointAis obviously not the global optimization dispatching plan.This is also consistent with the results from the improved dispatching model.As shown in Tab.8， the optimal dispatching plan can be quickly found by applying the genetic algorithm.Moreover，the improved dispatching method in this study can reflect the impact of potential accident points in generating the resource dispatching plan.

Tab.8 Comprehensive dispatching plan

4 Conclusion

This paper proposes an improved dispatching model for road network rescue resources for incident response，in which the dispatching decision-making time and the driving speed range of the rescue vehicles are given，and the calculation of the resource dispatching time is designed.The proposed model describes the resource dispatching cost for both current incidents and potential incidents in the road network for fully reflecting the corresponding relationships between the levels of incidents and dispatching decision-making time.In addition， the model considers the impact of different response vehicles on the dispatching time which is more consistent with a realistic rescue dispatching process.

The improved model is solved by the genetic algorithm.First， the real coding is adopted and the objective function is changed.Secondly，the fitness function is designed.Finally， the selection， crossover， and mutation operators are designed for the genetic parameters.In addition，the genetic optimization steps to solve the improved model are given to obtain the optimal resource dispatching plan.

［1］Sherali H D， Subramanian S.Opportunity cost-based models for traffic incident response ［J］.Journal of Transportation Engineering， 1999， 125(3):176-185.

［2］Zografos K G，Nathanail T，Michalopoulos P.Analytical framework for minimizing freeway incident response time［J］.Journal of Transportation Engineering， 1993， 119(4):535-549.

［3］Goldberg J， Dietrich R， Chen J M， et al.Validating and applying a model for locating emergency medical vehicles in Tucson， AZ［J］.European Journal of Operational Research， 1990， 49(3):308-324.

［4］Yamada T.A network flow approach to a city emergency evacuation planning ［J］.International Journal of Systems Science， 1996， 27(10):931-936.

［5］Yuan Qian， Liu Shuyan.Research on the optimum of the Hungarian method［J］.Journal of Wuhan University of Technology，2007，29(3):146-149.(in Chinese)

［6］Zografos K G，Androutsopoulos K N，Vasilakis G M.A real-time decision support system for roadway network incident response logistics［J］.Transportation Research Part C，2002，6(10):1-18.

［7］Haghani A，Tian Q，Hu H J.A simulation model for real-time emergency vehicle dispatching and routing［J］.Transportation Research Board， 2003，1882:176-183.

［8］Carter G M，Chaiken J M，Ignall E.Response areas for two emergency units［J］.Operations Research， 1972，20(3):571-594.

［9］Chai Gan， Zhu Canghui.Decision model and algorithm for traffic rescue resource dispatching on expressway［J］.Journal of Southeast University:Natural Science Edition，2009，25(2):252-256.(in Chinese)

［10］Zhang Ying， Zhou Gang， Huang Xiyue.Simulation of rescue model based on optimal plan［J］.Computer Simulation，2006，23(1):207-209.(in Chinese)

［11］Cheu R L， Huang Y， Huang B.Allocating emergency service vehicles to serve critical transportation infrastructures ［J］.Journal of Intelligent Transportation Systems，2008， 12(1):38-48.

［12］Wang Wei， Guo Xiucheng.Traffic engineering［M］.Nanjing:Southeast University Press， 2000.(in Chinese)

［13］Wang Ling.Intelligent optimization algorithms with applications［M ］.Beijing:Tsinghua University Press，2001.(in Chinese)

［14］Ghoseiri K， Ghannadpour S F.Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm［J］.Applied Soft Computing，2010， 10(4):1096-1107.