[go: up one dir, main page]

WO2016119007A1 - Mobilisation et planification d'évacuation combinées - Google Patents

Mobilisation et planification d'évacuation combinées Download PDF

Info

Publication number
WO2016119007A1
WO2016119007A1 PCT/AU2015/050716 AU2015050716W WO2016119007A1 WO 2016119007 A1 WO2016119007 A1 WO 2016119007A1 AU 2015050716 W AU2015050716 W AU 2015050716W WO 2016119007 A1 WO2016119007 A1 WO 2016119007A1
Authority
WO
WIPO (PCT)
Prior art keywords
movement
time
solving
evacuation
response characteristic
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/AU2015/050716
Other languages
English (en)
Inventor
Victor PILLAC
Pascal Van Hentenryck
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Data61
Original Assignee
National ICT Australia Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Priority claimed from AU2015900274A external-priority patent/AU2015900274A0/en
Application filed by National ICT Australia Ltd filed Critical National ICT Australia Ltd
Publication of WO2016119007A1 publication Critical patent/WO2016119007A1/fr
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G08—SIGNALLING
    • G08B—SIGNALLING OR CALLING SYSTEMS; ORDER TELEGRAPHS; ALARM SYSTEMS
    • G08B7/00—Signalling systems according to more than one of groups G08B3/00 - G08B6/00; Personal calling systems according to more than one of groups G08B3/00 - G08B6/00
    • G08B7/06—Signalling systems according to more than one of groups G08B3/00 - G08B6/00; Personal calling systems according to more than one of groups G08B3/00 - G08B6/00 using electric transmission, e.g. involving audible and visible signalling through the use of sound and light sources
    • G08B7/066—Signalling systems according to more than one of groups G08B3/00 - G08B6/00; Personal calling systems according to more than one of groups G08B3/00 - G08B6/00 using electric transmission, e.g. involving audible and visible signalling through the use of sound and light sources guiding along a path, e.g. evacuation path lighting strip

Definitions

  • This disclosure relates to planning movement of multiple groups over a transport network, for example, but not limited to, the evacuation of persons from geographical zones.
  • Evacuation orders are some of the most important decisions performed by emergency services: they ensure the safety of people at risk by instructing them to evacuate the threatened region, be it a building (e.g., fire), a neighbourhood (e.g., industrial hazard), or a whole region (e.g., flood).
  • Evacuation planning also arises at strategic, tactical, and operational levels. At a strategic level, the goal is to design evacuation plans for specific areas and possible threats (e.g., evacuation plans for the surroundings of a nuclear power plant).
  • the goal is to design evacuation plans for an area facing an incoming threat (e.g., evacuation of a flood plain following high precipitations).
  • the goal is to schedule an evacuation, possibly adjusting the evacuation plan in real-time as the disaster unfolds.
  • a method for planning movement of multiple groups over a transport network comprises determining for each group of the multiple groups a route of the movement through the transport network, a starting time for initiating the movement, and a response characteristic to optimise a quantity of movement, wherein the response characteristic represents for each of multiple points in time a number of individuals that initiate movement at that point in time.
  • the method determines a response characteristic and the response characteristic models the time it will take individuals to start their movement depending on the time at which the group movement is initiated, the result more accurately reflects the actual movement when the plan is implemented. This is an advantage over other methods that do not determine response characteristics but assume that the departure time of each individual can be controlled. As a result, the above method considers the human nature of arbitrarily delaying the actual time of departure.
  • the movement may be an evacuation and the transport network may be a road network.
  • Determining the response characteristic may comprise selecting for each group of the multiple groups one of multiple candidate response characteristics, each of the multiple candidate response characteristic being associated with a procedure to mobilise the individuals of that group, and the method may further comprise outputting the procedure associated with the selected response characteristic.
  • Each of the multiple response characteristics may be associated with an amount of resources for initiating the movement and determining the response characteristic comprises selecting for each group one of multiple response characteristics such that the resources of the selected response characteristics together are less than or equal to a maximum available amount of resources.
  • Determining for each group the route, starting time and response characteristic may comprise solving an optimisation problem that is based on the number of individuals that initiate movement at each point in time according to multiple candidate response characteristics.
  • Solving the optimisation problem may comprise maximising a quantity of movement over the transport network.
  • Solving the optimisation problem may comprise performing a column generation method, and performing the column generation method comprises solving a master problem and solving a subproblem.
  • Solving the master problem may comprise selecting one of multiple candidate movement plans, each of the multiple candidate movement plans being associated with a route through the transport network, a starting time and a response characteristic to thereby determine for each group the route, the starting time and the response characteristic.
  • Solving the master problem comprises optimising a linear program or a mixed integer program.
  • the linear problem may comprise a selection variable associated with each of the multiple candidate movement plans.
  • Solving the master problem may comprise optimising a cost function to maximize the number of individuals that complete the movement within a time period for completing the movement and to minimise the time period for completing the movement.
  • Solving the subproblem may comprise:
  • Solving the subproblem may comprise optimising a mixed integer program based on a flow of individuals at each of the multiple points in time according to the response characteristic.
  • the mixed integer program may comprise a binary variable to select one of multiple response curves, and binary variables to select a path in the transportation network.
  • Solving the subproblem may comprise solving a least-cost path problem based on a time-expanded graph of the transport network.
  • Solving the least-cost path problem way comprise aggregating a cost of an entire movement along an edge over time into a single cost for a first traversal of that edge.
  • Solving the subproblem may be performed in parallel for each originating node.
  • Solving the optimisation problem may comprise performing a branch and price algorithm.
  • Software when executed by a computer causes the computer to perform the above method.
  • a computer system for planning movement of multiple groups over a transport network comprises:
  • a processor to determine for each group of the multiple groups
  • response characteristic represents for each of multiple points in time a number of individuals that initiate movement at that point in time.
  • Fig. 1 illustrates a computer system for planning movement of multiple groups over a transport network.
  • Fig. 2a illustrates a method for planning movement of multiple groups over a transport network.
  • Fig. 2b illustrates a method that performs the steps of method in Fig. 2a in a non-sequential order.
  • Fig. 3a illustrates a general evacuation scenario.
  • Fig. 3b illustrates a graph representing the evacuation scenario in Fig. 3a.
  • Fig. 4 illustrates a temporal discretisation of the graph in Fig. 3b over a time horizon.
  • Figs. 5a and 5b illustrate examples of response curves.
  • Fig. 6 illustrates the key intuition behind the least-cost-path formulation of the sub-problem.
  • Fig. 7 illustrates data memory of Fig. 1 storing five response curves.
  • Fig. 8 illustrates a map of a geographical area of interest.
  • Fig. 9 illustrates an evacuation planner computer system.
  • Fig. 10 illustrates a web interface. Best Mode for Carrying Out the Invention
  • Fig. 1 illustrates a computer system 100 for planning movement of multiple groups over a transport network.
  • the computer system 100 includes a processor 102 connected to a program memory 104, a data memory 106, first data port 108 and second data port 110.
  • the first data port 108 and the second data port 110 may be the same data port.
  • the processor is also connected to a user port 112 that interfaces the processor 102 with a display 114 operated by a central decision maker 116.
  • the program memory 104 is a non-transitory computer readable medium, such as a hard drive, a solid-state disk or CD-ROM.
  • Software that is an executable program comprising computer executable instructions, stored on program memory 104 causes the processor 102 to perform the method in Fig. 2a or Fig. 2b, that is, the processor 102 determines for each group of the multiple groups a route of the movement through the transport network, a starting time for initiating the movement and a response characteristic to optimise a quantity of movement.
  • the software stored on program memory 104 turns the computer system 100 into a practical movement-planning tool.
  • any kind of data port may be used to receive and send data, such as a network connection, a memory interface, a pin of the chip package of processor 106, or logical ports, such as IP sockets or parameters of functions stored on program memory 104 and executed by processor 102. These parameters may be handled by-value or by-reference in the source code.
  • the processor 102 may receive data through all these interfaces, which includes memory access of volatile memory, such as cache or RAM, or non-volatile memory, such as an optical disk drive, hard disk drive, storage server or cloud storage.
  • the processor 102 may pre-determine multiple candidate response characteristics, such as response curves, such as by analysing historical data, and store the candidate response curves on data store 106, such as in a database or on a RAM. The processor 102 can then request the candidate response curves from the datastore 106 and receives the candidate response curves via a memory interface.
  • candidate response characteristics such as response curves, such as by analysing historical data
  • data store 106 such as in a database or on a RAM.
  • the processor 102 can then request the candidate response curves from the datastore 106 and receives the candidate response curves via a memory interface.
  • the processor 102 stores the result on a RAM, database or processor register and then receives the data directly afterwards or at a later stage via a memory interface.
  • nodes, edges, graphs, solutions, variables, movement plans, response curves and the like refer to data structures, which are physically stored on data memory 106 or processed by processor 102.
  • variable names such as "period of time” or “quantity of movement” this is to be understood to refer to values of variables stored as physical data in computer system 100.
  • path and “route” are used interchangeably unless stated otherwise.
  • processor 102 generates a graphical user interface 118, such as a map view, and causes the graphical user interface 118 to be displayed on display device 114 by sending appropriate commands and data to the display device 114.
  • the central decision maker 116 can view the user interface and plan the movement accordingly.
  • the following examples relate to an evacuation scenario where the groups are defined by geographical zones and comprise evacuees that are located in the respective geographical zone. Geographical zones may be postcode areas, settlements or defined by a segmentation of an entire evacuation area, such as by an overlying grid.
  • An example of a natural disaster could be a flooding event of the Hawkesbury-Nepean river northwest of Sydney, Australia, triggering a large scale evacuation.
  • the evacuation zone or group of the town of Windsor for example, may be addressed by the respective postcode, such as 'zone 2765' .
  • the transport network is the road network defined by the roads in the evacuation area as displayed on a road map. A 'path' or 'route' for this group starts at this geographical zone and ends at a safe node or zone.
  • the scenario is a movement of troops or movement of groups of vehicles over a transport network.
  • the scenario is an evacuation of a building, such as a high riser.
  • the levels of the building may define the groups such that all evacuees of one level form one group.
  • each group has multiple members, such as military personnel, evacuees, or vehicles. People, cars, troop cohorts or soldiers may all be referred to as individuals.
  • Fig. 2a illustrates a method 200 for planning evacuation movement of multiple groups from respective geographical zones over a transport network.
  • Fig. 2 is to be understood as a blueprint for the evacuation planning software program and may be implemented step-by-step, such that each step in Fig. 2 is represented by a function in a programming language, such as C++ or Java.
  • the resulting source code is then compiled and stored as computer executable instructions on program memory 104.
  • Processor 102 performs method 200. That is, for each group k of multiple groups 202 processor 102 determines 204 a route of movement through the transport network. This route of movement is denoted ⁇ in the mathematical explanation below. The processor 102 further determines 206 a starting time ⁇ , which is the time when the movement commences for group k. Importantly, the processor 102 also determines 208 a response characteristic /, which represents for each of multiple points in time a number of individuals that initiate movement at that point in time. The processor 102 determines these three elements to optimise a quantity of movement, such as to maximise the number of individuals reaching a destination node within a given planning horizon.
  • Fig. 2a illustrates the steps 202, 204, 206 and 208 as distinct steps. From Fig. 2a it may appear as processor 102 performs an iteration over the multiple groups. However, in some examples described below, the entire optimisation may be formulated as a single linear program or a master problem and a sub-problem of a column generation process. As a result, processor 102 does not determine these elements sequentially for each group but simultaneously by optimising the linear program. That is, the steps 202, 204, 206 and 208 may be combined and Fig. 2a merely indicates an arbitrary order for illustration purposes.
  • Fig. 2b illustrates a method 205 that performs the steps of method 200 but in a nonsequential order.
  • processor 102 performs method 250.
  • Processor 102 generates 252 initial response plans and then solves 254 a master problem of a column generation process.
  • the processor 102 then generates 256 new response plans by solving a sub- problem.
  • the master problem may be formulated as a linear program and processor 102 selects one response plan per evacuated area such that this selection satisfies global resource constraints and takes into account non-compliance to evacuation routes.
  • Each response plan comprises a route of movement ⁇ , a starting time ⁇ and a response characteristic/. This means that by selecting a response plan in step 254 processor 102 determines the route of movement ⁇ , starting time ⁇ and response characteristic/.
  • response plan is used in these examples relating to evacuation scenarios, the term “movement plan” may also be used instead as a more general expression.
  • Processor 102 determines 258 whether a termination criterion is met and if that criterion is not met, processor 102 starts again. The mathematical details of this process will be explained further below.
  • the sub-problem may be a pricing problem that is formulated as a least-cost path formulation (non-trivial).
  • the pricing problem processor 102 finds one or more response plans that will improve the solution and considers multiple response curves. This approach can guarantee the optimality of the solution.
  • Fig. 3a illustrates a general evacuation scenario 300.
  • Fig. 3a presents an evacuation scenario with one evacuated node 302 and two safe nodes 304 and 306.
  • the evacuated node 302 has to be evacuated by 13:00, considering that certain links become unavailable at different times (for instance, 2-3 edge 308 is cut at 9:00).
  • Fig. 3b illustrates how the evacuation scenario of Fig. 3a can be represented as a graph 350
  • 8 , T , and S are the set of evacuated, transit, and safe nodes respectively
  • ⁇ is the set of edges.
  • Each evacuated node is characterized by a number of evacuees d i and an evacuation deadline (e.g., 20 and 13:00 for node 0 (reference numeral 352) respectively), while each edge e is associated with a triple (s e ,u e , f e ) , where s e is the travel time, u e is the capacity, and f e is the time at which the edge becomes unavailable.
  • Fig. 4 illustrates a temporal discretisation graph 400 of a period of time, such as a planning horizon.
  • processor 102 One way to deal with the space-time aspects of evacuation problems is for processor 102 to discretise the planning horizon into time steps of identical length, and to work on a time-expanded graph 400, as illustrated in Fig. 4.
  • edges with infinite capacity are added to model the evacuees waiting at evacuated and safe nodes.
  • all evacuated nodes resp. safe nodes
  • v s super- sink v t
  • some nodes may not be connected to either the super- source or super- sink (with dotted border in this example), and can therefore be removed to reduce the graph size.
  • the problem is then to find a flow from v s to v t that models the movements of evacuees in space and time.
  • a central decision maker 116 instructs each evacuated area when to start the evacuation, which safe node to go to, and which path to follow in the evacuation graph;
  • a single threat scenario is known at decision time
  • the central decision maker's 116 objective is to evacuate as many individuals as possible in the minimum amount of time
  • Each evacuated area should be assigned to a single evacuation path
  • the mobilization process can be modelled with response characteristics, such as response curves.
  • Assumption 1 relates to examples where the proposed approach is targeted toward emergency or safety services that design evacuation plans for buildings or regional areas.
  • Assumption 2 and 3 correspond to threats for which forecast or scenarios are available in advance and for which a whole regional area needs to be evacuated. Examples of such threats include hurricanes, forest fires, floods, or industrial hazards.
  • Assumption 4 is a practical consideration and reflects the practice in emergency services operations.
  • Assumption 5 is a simplification to solve the models efficiently, and it is compensated by the fact that edge capacities are set to ensure non-congested traffic conditions.
  • the problem is to design an evacuation plan that assigns a single evacuation path to each evacuated node, and to schedule the evacuation over the planning horizon, with the objective of first maximizing the number of evacuees reaching a safe node, and then optimizing the quality of the evacuation schedule, such as by minimizing the time required to evacuate all evacuees.
  • an evacuation plan produces three outputs: (1) a traffic management plan, including detailed evacuation routes, (2) an evacuation schedule, specifying when residential zones should evacuate and the total duration of the evacuation, and (3) an allocation of resources to communicate the evacuation orders.
  • processor 102 solves the model using a column generation algorithm that jointly decides the evacuation route, evacuation time, and the resource allocation for each evacuated area in order to maximize the number of evacuees reaching safety and minimize the total duration of the evacuation.
  • the disclosed solution integrates evacuation planning and mobilization by incorporating the behavioural response of the evacuees.
  • This methodological contribution is implemented through the integration of response characteristics, also referred to as response curves, into a column-generation algorithm, where processor 102 can solve the subproblem in polynomial time as a least-cost path.
  • the quality of the resulting evacuation plans remains reasonably close to earlier approaches which assume full control of evacuation timing.
  • Each evacuation node / is characterized by a number of evacuees d i , while each arc e is associated with a triple (s e ,u e ,b e ) , where s e is the travel time, u e is the capacity, and b e is the time at which the arc becomes unavailable.
  • the problem is defined over a time horizon ⁇ discretised into time steps as shown in Fig. 4.
  • the objective is to optimise a quantity of movement, such as (1) to maximize the total number of evacuees reaching a safe node and (2) to minimize the time at which the last evacuee reaches safety.
  • the evacuation is carried out using private vehicles, which are then referred to as 'individuals' .
  • Other examples may relate to other contexts, such as building evacuation.
  • This disclosure extends the EPP to the Joint Mobilization and Evacuation Planning Problem (JMEPP).
  • JMEPP Joint Mobilization and Evacuation Planning Problem
  • the orchestrator may be able to influence the actual departure time of evacuees in two ways:
  • the amount of resources invested in the mobilization e.g., how many volunteers are sent to door-knock.
  • the mobilization process may be modelled with response characteristics, such as response curves. These curves are an abstraction to reflect evacuee compliance to the timing of their departure time.
  • each evacuated area k is associated with a set of response curves k stored on data memory 106 as lists of time and value pairs.
  • One of the curves will be selected in evacuation planning.
  • Processor 102 selects, for each evacuation area k , a single evacuation path ⁇ , a response curve / e k , and a departure time ⁇ e ⁇ in order to maximize the total number of evacuees reaching a safe node and to minimize the time at which the last evacuee reaches safety.
  • the flow of evacuees ⁇ leaving area k at time step t for a departure time ⁇ is defined by the chosen response curve / as follows:
  • Figs. 5a and 5b illustrate examples of response curves.
  • Fig. 5a illustrates the rate of evacuees departing and
  • Fig. 5b illustrates the cumulated number of evacuees having departed over time for four response curves, assuming an evacuation order issued at 60 minutes.
  • the constant rate response curve considers a lead time of 60 min before evacuees start departing and then assumes a constant rate until all evacuees have departed.
  • the Rayleigh response curve is defined l + e
  • Processor 102 assigns a response curve to each evacuation area. This response curve captures both the mobilization process and the evacuee behaviour. Moreover, the same mobilization process can give rise to different response curves for distinct evacuation areas, capturing various features of the population.
  • CG Column generation
  • MP Master Problem
  • SP pricing subproblem
  • solving the master problem (MP) processor 102 selects response plans, which are a combination of an evacuation path, a response curve, and an evacuation time. Solving the subproblem (SP) processor 102 generates columns of negative reduced costs, each representing a response plan associated with a single evacuated area. Processor 102 leverages the response curve to solve the SP efficiently by finding a least-cost path for each evacuated node in a time-expanded graph.
  • ⁇ be the current set of response plans
  • x be a binary variable which takes the value of 1 if and only if plan p is selected
  • c be the cost of selecting plan p
  • ⁇ ⁇ be the subset of plans corresponding to evacuated node k
  • co ⁇ e be the subset of plans that use edge e
  • a' be the flow of evacuees on edge e at time t induced by plan p
  • Q be the resource availability for mobilization.
  • the MP is formulated as source code, compiled and stored on program memory 104 and executed by processor 102 as follows:
  • Constraints (19) is a convexity constraint
  • Constraints (20) enforce the capacity on edges
  • constraint (21) ensures that the total number of resources required does not exceed the availability.
  • variables x p are defined as continuous, which means that a post-processing is performed to obtain a solution to the original problem.
  • the cost c p is a function of the flow of evacuees in plan p , which highly penalizes evacuees that cannot reach a safe node and introduce a linear penalty for the arrival time of evacuees reaching safety.
  • Solving the SP processor 102 aims to generate a column p of negative reduced cost r p defined as:
  • [a] is a vector containing the coefficients of column p and w is the vector of dual variables from the MP model (18-22).
  • processor 102 can solve the SP independently for each evacuated node k and available response curve / e J ⁇ , allowing for a size reduction of each SP and a parallelization of the algorithm.
  • q p is a parameter that depends on the selected response curve / .
  • x e be a binary variable that takes the value 1 iff edge e is selected in the evacuation path of k
  • ⁇ be a continuous variable representing the number of evacuees traveling on edge e at time t
  • y t be a binary variable equal to 1 if the evacuation starts at time t .
  • the SP is formulated as source code, compiled and stored on program memory 104 and executed by processor 102 as follows:
  • Model (28-35) the flow departing the evacuated node at each time step is completely defined by variables y t .
  • the model also comprises a flow variable for each edge and each time step to keep track of the flow of evacuees along the selected path.
  • a x j(s, v f ) I s e ⁇ S X
  • (e, t) denotes the edge of Q corresponding to edge e e A at time t .
  • Fig. 6 illustrates the key intuition behind the least-cost-path formulation of the SP.
  • the evacuation node (0) is connected to a transit node (1), itself connected to two transit nodes (2 and 3), with further levels omitted for clarity.
  • edges represent a connection in space and time
  • the node (2,3) represents the node 2 at time step 3.
  • the bar chart at the top represents the number of vehicles departing over time following an arbitrary response curve.
  • the hatched bars correspond to the flow of vehicles if the evacuation is started at time 0, while the solid white bars corresponds to an evacuation started at time 2.
  • the labels on the edges correspond to the number of vehicles that will flow on them if they are part of the evacuation path and depending on the start of the evacuation.
  • the edge ⁇ (1 ; 3); (3; 4)> has two labels: the hatched label indicates that if the evacuation is started at 0, 2 vehicles will flow on that edge, and the solid white label indicates that 1 vehicle will traverse that edge if the evacuation is started at 2. From this we observe that the path followed by the first group of evacuees in the time-expanded graph completely defines the flow of evacuees. For instance, if the first group of evacuees 1002 traverses edge ⁇ (1 ; 3); (3; 4)>, necessarily the second group 1004 will traverse ⁇ (1 ; 4); (3; 5)>, and the third group 1006 will traverse ⁇ (1 ; 5); (3; 6)>.
  • a path in the time expanded graph corresponds to a response plan, in which the start of the evacuation is defined by the first non- waiting edge exiting the evacuation node.
  • the least-cost-path formulation aggregates the cost of the entire evacuation along an edge e over time into a single cost for the first traversal of that edge (i.e., the first group of evacuees).
  • the cost vector c sp for edges in Q x is formulated as source code, compiled and stored on program memory 104 and executed by processor 102 as follows:
  • Equation (37) aggregates all future costs along e , while Equation (39) captures the cost of individuals, such as vehicles, unable to evacuate.
  • Finding a column of negative reduced cost for evacuated node k and response curve / is equivalent to finding the shortest path between k 0 and v t in the graph Q x with the cost vector c sp .
  • ⁇ ⁇ ((e 0 ,t ),( ⁇ 3 ⁇ 4, ⁇ .),..., (e ,t )> be a path between k 0 and v in the time-expanded graph Q x .
  • ⁇ ⁇ can be interpreted as the path in time followed by the first group of evacuees from evacuated node k .
  • t corresponds to the departure time from k . Note that the edge
  • Equation (42) can be rewritten as:
  • a column of minimal reduced cost corresponds to a shortest path in the graph Q x .
  • the evacuation comprises 61 evacuated nodes, 162 transit nodes, 5 safe nodes, and 517 edges, and a planning horizon of lOh (600 minutes).
  • the available response curves for the evacuation areas follow a step function with a rate ⁇ e ⁇ 2, 6,10, 25,50 ⁇ vehicles per 5 minutes which corresponds to a number q e ⁇ 2,6,10, 25, 50 ⁇ of two-persons teams carrying out the door knocking.
  • Fig. 7 illustrates data memory 106 in more detail.
  • Data memory 106 stores 5 response curves 702, 704, 706, 708 and 710 with associated number of teams 712, 714, 716, 718 and 720, respectively. These response curves show the cumulative number of individuals that have left at a particular point in time.
  • the data may be stored in different formats, such as "2*50" (curve 502) for 50 time steps of 5 minutes and two individuals leaving in each time step or "25*4" for 4 time steps of 5 minutes and 25 individuals leaving in each time step or [10,10,10,10,10,10,10,10,10] for 10 time steps of 5 minutes and 10 individuals leaving in each time step. Since the total number in each example is 100, processor 102 may use the values of the curves as a percentage and multiply that value by the number of individuals in each area k.
  • processor 102 selects for each area k one response curve. Since each response curve is associated with an order or warning procedure, processor 102 implicitly selects an order or warning procedure by selecting one response curve. This order or warning procedure can then be provided to the evacuation controller 116 or police forces on display 114, printed, sent by email, included onto a website, communicated automatically by radio, etc.
  • processor selects curve 506 for postcode area 2765 from starting time 3pm.
  • the procedure output may then be a text string or audio message "10 teams required to distribute immediate evacuation orders in postcode area 2765 starting at 3pm".
  • Processor 102 may also provide these instructions to the 10 individual team leaders, such as "distribute evacuation orders in postcode area 2765 starting at 3pm".
  • processor 102 initializes the MP with an empty evacuation plan for each evacuated area, which model that the area is not evacuated, and a plan corresponding to the shortest evacuation path at the earliest time.
  • Processor 102 solves the linear relaxation of the MP using a linear optimization solver, while processor 102 solves the SP with the Bellman-Ford algorithm.
  • processor 102 obtains an integer solution by solving the integer MP at the last iteration with a mixed integer programming solver.
  • the CG approach may be terminated early when an arbitrary convergence criterion is met, and the final MIP may be terminated early to reduce computational times, or intermediary solutions may be reported to the user while the solver is still running.
  • the column generation method is implemented as a branch-and- price approach, possibly combined with a Lagrangian relaxation approach where edge capacities are relaxed in order to improve the scheduling of the evacuation.
  • Fig. 8 illustrates a map 800 of the HN geographical area of interest displayed on screen 114.
  • Fig. 9 presents an evacuation planner computer system 900, an intelligent system for integrated evacuation planning.
  • Computer system 900 pulls information from raw databases 902 containing the detailed road network (e.g., via Open Street Maps), population census, threat scenarios, and preprocesses the data to display it to the planners via a web interface 904.
  • Planners are able to manipulate the data and define the evacuation network (which can be a simplified or reduced version of the road network). Planners can then specify the areas that need to be evacuated, as well as the safe areas and shelters. This information is saved in a second database 906 and can be combined to produce an evacuation instance which is then used as input to the evacuation optimization module 908.
  • Fig. 10 illustrates a web interface 1000 which allows planners to work with multiple scenarios simultaneously.
  • a left panel 1002 presents the different layers (e.g., road network, population, evacuated areas), while a right panel 1004 provides editing functionalities.
  • Suitable computer readable media may include volatile (e.g. RAM) and/or non-volatile (e.g. ROM, disk) memory, carrier waves and transmission media.
  • Exemplary carrier waves may take the form of electrical, electromagnetic or optical signals conveying digital data steams along a local network or a publically accessible network such as the internet.

Landscapes

  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)

Abstract

La présente invention concerne l'évacuation de personnes à partir de zones géographiques. Un processeur détermine pour chaque groupe un itinéraire à travers un réseau de transport, une heure de départ pour initier le déplacement, et une caractéristique de réponse pour optimiser une quantité de déplacement. La caractéristique de réponse représente, pour chacun de multiples instants, un certain nombre d'individus qui initient un déplacement à cet instant. Ceci modélise le temps qu'il faudra aux individus pour commencer leur déplacement en fonction de l'heure à laquelle le déplacement de groupe est initié. Par conséquent, le résultat reflétera plus précisément le déplacement réel lorsque le plan est mis en œuvre. Ceci est un avantage par rapport aux autres procédés qui ne déterminent pas des caractéristiques de réponse mais supposent que l'heure de départ de chaque individu peut être contrôlée. En conséquence, le procédé ci-dessus considère la nature humaine comme retardant arbitrairement l'heure réelle de départ.
PCT/AU2015/050716 2015-01-30 2015-11-16 Mobilisation et planification d'évacuation combinées Ceased WO2016119007A1 (fr)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
AU2015900274 2015-01-30
AU2015900274A AU2015900274A0 (en) 2015-01-30 Joint mobilization and evacuation planning

Publications (1)

Publication Number Publication Date
WO2016119007A1 true WO2016119007A1 (fr) 2016-08-04

Family

ID=56542039

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/AU2015/050716 Ceased WO2016119007A1 (fr) 2015-01-30 2015-11-16 Mobilisation et planification d'évacuation combinées

Country Status (1)

Country Link
WO (1) WO2016119007A1 (fr)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN114386660A (zh) * 2021-12-06 2022-04-22 西安交通大学 核电厂场外应急疏散路径规划方法

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20100161370A1 (en) * 2008-12-18 2010-06-24 Motorola, Inc. Pass through for improved response time
US20130253889A1 (en) * 2012-03-06 2013-09-26 Mid-Atlantic Technology, Research & Innovation Center, Inc. Modeling and simulation capability for resource consumption and consequence management
US8738276B1 (en) * 2010-04-27 2014-05-27 International Business Machines Corporation Emergency routing within a controllable transit system
US8787871B2 (en) * 2008-12-02 2014-07-22 International Business Machines Corporation System and method for calculating and disseminating intelligent evacuation routes based on location awareness and integrated analytics

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8787871B2 (en) * 2008-12-02 2014-07-22 International Business Machines Corporation System and method for calculating and disseminating intelligent evacuation routes based on location awareness and integrated analytics
US20100161370A1 (en) * 2008-12-18 2010-06-24 Motorola, Inc. Pass through for improved response time
US8738276B1 (en) * 2010-04-27 2014-05-27 International Business Machines Corporation Emergency routing within a controllable transit system
US20130253889A1 (en) * 2012-03-06 2013-09-26 Mid-Atlantic Technology, Research & Innovation Center, Inc. Modeling and simulation capability for resource consumption and consequence management

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN114386660A (zh) * 2021-12-06 2022-04-22 西安交通大学 核电厂场外应急疏散路径规划方法

Similar Documents

Publication Publication Date Title
US20160314554A1 (en) Evacuation plan design
Pillac et al. A conflict-based path-generation heuristic for evacuation planning
Kim et al. Evacuation route planning: scalable heuristics
US9047767B2 (en) Traffic impact prediction for multiple event planning
Kulshrestha et al. Robust shelter locations for evacuation planning with demand uncertainty
Yusoff et al. Optimization approaches for macroscopic emergency evacuation planning: a survey
Pillac et al. A column-generation approach for joint mobilization and evacuation planning
US20170046653A1 (en) Planning of transportation requests
Hadas et al. Network design model with evacuation constraints
Fu et al. Optimization of evacuation traffic management with intersection control constraints
Manopiniwes et al. Optimization model for temporary depot problem in flood disaster response
Varia et al. Application of genetic algorithms for joint optimization of signal setting parameters and dynamic traffic assignment for the real network data
CN107220749A (zh) 一种应急资源快速调度的方法及系统
Henry et al. Influence of road network and population demand assumptions in evacuation modeling for distant tsunamis
Shiri et al. Online optimization of first-responder routes in disaster response logistics
Shimamoto et al. Evaluation of tsunami evacuation planning considering vehicle usage and start timing of evacuation
Hasan et al. Large‐scale zone‐based evacuation planning, Part II: Macroscopic and microscopic evaluations
Guo et al. Max-flow rate priority algorithm for evacuation route planning
Danchuk et al. Adaptable dynamic routing system in urban transport logistics problems using GIS data
WO2016119007A1 (fr) Mobilisation et planification d'évacuation combinées
Zhang et al. Coordination of semi‐actuated signals on arterials
Islam et al. Simulation-assisted optimization for large-scale evacuation planning with congestion-dependent delays
WO2016094935A1 (fr) Plans convergents d'évacuations à grande échelle
Moeckel Modeling the impact of communications technologies on travel behavior and land use
Bertero et al. Developing optimization tools for municipal solid waste collection in the Argentine city of Berazategui

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 15879280

Country of ref document: EP

Kind code of ref document: A1

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 15879280

Country of ref document: EP

Kind code of ref document: A1