Cross -Reference to Related Applications

The present application claims priority from Australian Provisional Patent Application No 2015900274 filed on 30 January 2015, the content of which is incorporated herein by reference.

Technical field

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.

Background

Natural and man-made disasters, such as hurricanes, floods, and bushfires, affect numerous populated areas and may endanger the lives and welfare of entire populations. 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). At a tactical level, the goal is to design evacuation plans for an area facing an incoming threat (e.g., evacuation of a flood plain following high precipitations). Finally, at the operational level, the goal is to schedule an evacuation, possibly adjusting the evacuation plan in real-time as the disaster unfolds.

When disasters strike over a large and populated area, large numbers of persons need to be evacuated over a transport network. The road network is typically changing by the influence of the disaster and the evacuation itself, with for instance flooded roads or accidents. Due to these dynamic changes, the evacuation plan ideally needs to be continuously re-evaluated during the disaster within tight time constraints. However, the number of paths from one node to another in a transport network grows exponentially with the number of edges, that is, roads. Any method that scales linearly with the number of possible paths, such as enumerating each possible path, quickly becomes infeasible as a result of the large number of paths. In addition, existing methods rely on the simplifying assumption that evacuees can flow freely in the network, which is not applicable in practice.

Further, the actual evacuation often deviates from the evacuation plan. As a result, the goals of the evacuation that are achieved according to the plan are not achieved when the evacuation is actually performed. This means that lives are put at risk.

Any discussion of documents, acts, materials, devices, articles or the like which has been included in the present specification is not to be taken as an admission that any or all of these matters form part of the prior art base or were common general knowledge in the field relevant to the present disclosure as it existed before the priority date of each claim of this application.

Throughout this specification the word "comprise", or variations such as "comprises" or "comprising", will be understood to imply the inclusion of a stated element, integer or step, or group of elements, integers or steps, but not the exclusion of any other element, integer or step, or group of elements, integers or steps.

Disclosure of Invention

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.

Since 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.

It is an advantage to consider a variety of response characteristics. In practice, different movement order procedures will lead to different response characteristic. As such, selecting a response characteristic is equivalent to selecting a movement order procedure, which can then be implemented when executing the movement plan.

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:

determining a new candidate movement plan based on the movement plan selected by solving the master problem; and

adding the new movement plan to the multiple candidate movement plans. 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:

an input port to receive data related to the transport network;

a processor to determine 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; and

and an output port to output data in relation to the route, the starting time and the response characteristic,

wherein the response characteristic represents for each of multiple points in time a number of individuals that initiate movement at that point in time.

Brief Description of Drawings

An example will be described with reference to

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. In one example, 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.

It is to be understood that 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.

For example, 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.

After the actual computation, 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. It is to be understood that throughout this disclosure unless stated otherwise, 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. Further, for the sake of brevity when reference is made to particular 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. The terms "path" and "route" are used interchangeably unless stated otherwise.

In some examples, 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. In this scenario, the evacuation zone or group of the town of Windsor, for example, may be addressed by the respective postcode, such as 'zone 2765' . In this example, 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.

In other examples, the scenario is a movement of troops or movement of groups of vehicles over a transport network. In yet another example, the scenario is an evacuation of a building, such as a high riser. In this example, the levels of the building may define the groups such that all evacuees of one level form one group. In these examples, 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.

In one example of the proposed evacuation planning method, there is a dependency between paths in a time-expanded network as will be explained later with reference to Fig. 4. More precisely, a commodity (i.e., all evacuees from a specific evacuated node) can only follow paths that correspond to the same physical path (sequence of edges in the transport network). Therefore multi-commodity network flow approaches cannot be applied directly, as they assume that each flow unit (evacuee) can flow freely in the graph.

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.

It is noted that 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. Again, 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/.

While the term "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). By solving 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. In this example, 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 Q = (λί = £ T S, Λ) where 8 , T , and S are the set of evacuated, transit, and safe nodes respectively, and Λ 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. 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. This graph 400 Q ^d = (Af ^d = £ ^d jS ^d , A ^d ) is constructed by duplicating each node from Af for each time step. For each edge (i, j) e A and for each time step t in which edge (1, 7) is available, an edge is created modelling the transfer of evacuees from node at time t to node j at time t + s _{(i j}} . In addition, edges with infinite capacity are added to model the evacuees waiting at evacuated and safe nodes. Finally, all evacuated nodes (resp. safe nodes) are connected to a virtual super-source v _s (super- sink v _t ), modelling the inflow (outflow) of evacuees. Note that 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.

In one example, the following assumptions are made:

1. 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;

2. A single threat scenario is known at decision time;

3. The central decision maker's 116 objective is to evacuate as many individuals as possible in the minimum amount of time;

4. Each evacuated area should be assigned to a single evacuation path;

5. Edges capacity does not depend on the flow, and no congestion occurs at intersections;

6. 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.

Assumption 6 means that the human behaviour which is sometimes erratic and arbitrary can be modelled by response curves to a reasonable degree of accuracy. If the number of evacuees leaving at any point in time is completely random, for example, this assumption may be less accurate.

In that context, 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. Given a threat or a set of threat scenarios, 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.

During large-scale evacuations authorities decide and stage evacuation routes, mobilize resources, and issue evacuation orders under strict time constraints. These decisions consider both the capacity of the road network and the evolution of the threat (e.g., a bushfire or a flood). There is disclosed herein an optimization model that jointly optimizes the mobilization and evacuation planning, taking into account the behavioural response of evacuees and the allocation of resources for communicating and implementing evacuation orders.

From a technical standpoint, 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.

As described above in relation to Figs. 3a and 3b the Evacuation Planning Problem (EPP) is defined on a graph Q = (J\f = S ^ T U S, A) , where 8 , T , and S are the set of evacuation, transit, and safe nodes respectively, and A is the set of edges. 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. In some examples, 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). The orchestrator may be able to influence the actual departure time of evacuees in two ways:

- the time of the evacuation order; and

- 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.

More formally, 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:

f 0 if t < S

«* = {/(.-*) v <>s ^<17) 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 S-shape used as response curve is described by a logistic function fs (0 ⁼ — ~~~kt where D and k are parameters. The Rayleigh response curve is defined l + e

by the function F _R (t) =—^ -ί'/2σ'

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.

Column generation (CG) is an optimization technique which considers only a subset of columns Ω c: Ω of a Master Problem (MP) and iteratively generates columns of negative reduced costs (for minimization problems) by solving a pricing subproblem (SP).

In the context of the JMEPP, 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.

Solving the MP processor 102 selects response plans from a subset of all the feasible plans stored on data memory 106. Let Ω 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 the number of mobilization resources required to execute plan p , and 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:

s.t. ∑x _p = l Vfc e E (19)

Σ α p' ,e x p < ιί e Ve <= A,t e H (20) pe ( )

≤ Q (21)

p≡Ci

x _p ≥ p e Ω ^' (22)

Constraints (19) is a convexity constraint, Constraints (20) enforce the capacity on edges, and constraint (21) ensures that the total number of resources required does not exceed the availability. Note that 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.

More prec

&p t

where a is the number of non-evacuated vehicles in plan p and if i e E

I H I lOO max Jmax , }. (24)

0 otherwise

This cost essentially produces a lexicographic objective function that first maximizes the number of evacuees reaching safety and then minimize the overall evacuation time. Each column of the MP represents a response plan p = ^,π, /, δ) , where k e 8 is a residential area, π is a (k, s) evacuation path from zone Ho a safe node s e S , e f _t is a response curve, and S G H is a departure time. Solving the SP processor 102 aims to generate a column p of negative reduced cost r _p defined as:

r _p = c _p -[*f _p v (25)

where [a] is a vector containing the coefficients of column p and w is the vector of dual variables from the MP model (18-22).

Let [v _k ] _keg , [W' ^ _A ^- _H , and z be the dual variables associated with Constraints (19), (20), and (21) respectively: We rewrite Equation (25) for evacuated node k as follows:

r _P = ^~v k ^~ zq _p + ca _P +∑∑(c _e ' - w )a _p ' _e (27)

Since time-response plans are independent from each other, 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. Note also that the term q _p is a parameter that depends on the selected response curve / . As a result, solving the SP for an evacuation area k and response curve / is equivalent to finding a departure time δ and an evacuation path π that minimize ca„+ V V (c' - w')aL .

Let 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 , and 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:

s.t. ∑ x _e = 1 (29)

∑ x _e - ∑ x _e = 0 Vi e Γ (30)

' < u _e x _e \/e G A, t G H (32) ∑y, = 1 (35) x _e , y _t G {0, \ } , q>, (p _e '≥0 \fe & A, t & H (36)

Constraints (29-30) ensure that a unique path is selected between the evacuation area and a safe node. Constraints (31) enforce the flow conservation for the variables φ _ε ' , while Constraints (32) enforce that the edge capacity is respected. Constraints (33) ensure that the number of vehicles departing the evacuated area k at time t follows the response curve / for the selected departure time δ (defined by y _s = 1 ). Constraint

(34) accounts for the number φ of vehicles that cannot be evacuated. Constraints (35) ensure that the evacuation starts at a single time step. Finally, the objective (28) minimizes the reduced cost defined in (27).

A least-cost-path formulation of SP will be disclosed in the following description. In

Model (28-35), the flow departing the evacuated node at each time step is completely defined by variables y _t . However, 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 least-cost-path formulation is disclosed that relies on the time expanded graph X = (J\f ^x = S ^X T uS ^x , A ^x ) as described above, to which processor 102 adds edges with infinite capacity to model evacuees waiting at evacuated nodes (denoted as A ). Finally, processor 102 connects all safe nodes to a virtual super-sink v _t by edges

A ^x = j(s, v _f ) I s e <S ^X | , modelling the outflow of evacuees. For convenience, (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. In this example, 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. As before, edges represent a connection in space and time, and 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.

For instance, 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)>.

Consequently, given a response curve, 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).

Given an evacuated node k and a response curve / , 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:

=∑« ^' - ^) (i' - V( _e ,i) e A" \ (A: u (37)

t'=t

(38)

= c (d _k - F (\ H \ -t)) Ve e A; (39)

c = 0 Ve e A (40) 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 ₀ and v _t in the graph Q ^x with the cost vector c ^sp .

Proof (Sketch). Let π ^χ =((e ₀ ,t ),(<¾, ί .),..., (e ,t )> be a path between k ₀ 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 . For simplicity, we ignore waiting edges and assume that t corresponds to the departure time from k . Note that the edge

(e ,t ) connects the safe node to the super sink. The cost of path π ^χ is equal to:

= ∑ ∑(c -w' f(t'-t _e ) ₊ c(d _k -F(\H\-t _m )) (42)

Let π = <<¾,<¾, --,β„,> be a projection of path π ^χ in the static graph Q , p = (k^,f,t ₀ ) the corresponding response plan, and the a _p ' _e coefficients defined as follows: Equation (42) can be rewritten as:

cost{ ^x ) = - w' f (t'-t _e ) + c(d _k -F(\H\ -t)) (44) cost{ ^x ) =∑∑(c _e ' - w )a _p ' _e + ca _P (45) cost(7t ^* ) = r _p +v _k +zq _p (46) It follows that if π ^χ is the shortest (k ₀ v _t ) path in the graph Q ^x then the vector a defines the column of minimal reduced cost r = cost(n ^x )-v _k —zq ■

Conversely, it can be shown that a column of minimal reduced cost corresponds to a shortest path in the graph Q ^x . In one example, 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,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.

As explained above, 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. In one example, 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". In one example, 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. Finally, 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. In another example, 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. The resulting evacuation plans are then presented to the planner who can then iterate the process, refining the selection of residential zones, evacuation roads, contraflow edges, and threat scenarios. 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.

It will be appreciated by persons skilled in the art that numerous variations and/or modifications may be made to the specific embodiments without departing from the scope as defined in the claims.

It should be understood that the techniques of the present disclosure might be implemented using a variety of technologies. For example, the methods described herein may be implemented by a series of computer executable instructions residing on a suitable computer readable medium. 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.

It should also be understood that, unless specifically stated otherwise as apparent from the following discussion, it is appreciated that throughout the description, discussions utilizing terms such as "estimating" or "processing" or "computing" or "calculating", "optimizing" or "determining" or "displaying" or "maximising" or the like, refer to the action and processes of a computer system, or similar electronic computing device, that processes and transforms data represented as physical (electronic) quantities within the computer system's registers and memories into other data similarly represented as physical quantities within the computer system memories or registers or other such information storage, transmission or display devices.

The present embodiments are, therefore, to be considered in all respects as illustrative and not restrictive.