Cross-Reference to Related Applications

The present application claims priority from Australian Provisional Patent Application No 2014905110 filed on 17 December 2014, 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. It is therefore difficult to design an evacuation plan for a substantial area using existing methods.

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:

receiving a period of time associated with the movement;

performing one or more iterations of

determining a set of convergent routes through the transport network based on the period of time,

determining a quantity of movement over the set of convergent routes, and adjusting the period of time based on the quantity of movement over the set of convergent routes; and

determining a schedule of movement based on the set of convergent routes.

Since the period of time that is used to determine the convergent routes is adjusted, it is not necessary to pre-define a realistic period of time before performing the method. Instead, a conservative or arbitrary estimate can be used and this estimate is adjusted, which is an advantage over methods where a realistic period of time has to be provided although such an estimate is generally not known. Evidence from actual evacuations highlights that diversions and crossing of evacuation routes lead to significant congestion as drivers slow down at a fork to consider the alternatives ahead of them. Additionally, the presence of forks makes it harder to guarantee that evacuees will actually follow the evacuation plan. It is an advantage that the method produces evacuation routes that are convergent, which means that there are no diversions and crossings, reducing congestion and simplifying traffic management.

Simulations of the evacuation demonstrate that convergent evacuation plans outperform existing approaches for realistic driver behaviours. The benefits of the two-stage approach materialize as soon as a delay of 0.75 second is introduced at a fork when simulating the results of state-of-the-art evacuation planning tools on a mesoscopic simulator. The benefits become substantial when the delay increases: The clearance time doubles when the delay is about 4 seconds.

The method may comprise receiving data related to the transport network and determining the set of convergent routes may be based on the data related to the transport network.

The movement may be an evacuation and the transport network may be a road network.

Each of the multiple groups may comprise multiple group members and the quantity of movement is related to the total number of group members that can move over the set of convergent routes within the period of time.

For each of the multiple groups the initial path and updated path may be the same for all members of that group.

Each of the multiple groups may be associated with a geographical zone and the initial path and the updated path may start from the geographical zone of the respective group.

Determining the set of convergent routes and determining the quantity of movement may comprise aggregating the quantity of movement over the time period.

It is an advantage to aggregate the quantity of movement over the whole time period, since it suppresses the need to discretise time and to create the time-expanded graph. As a result, the complexity of the two determining steps is reduced compared to solving the complete Mixed Integer Program (MIP) routing and scheduling model at once. Aggregating the quantity of movement may comprise allowing movement over each of the set of convergent routes at any point in time within the time period.

Determining the set of convergent routes and determining the quantity of movement may comprise maximising the quantity of movement.

Maximising the quantity of movement may comprise solving a mixed integer programming problem based on the set of convergent routes, the quantity of movement and multiple binary variables, each of the multiple binary variables being indicative of a selection of one edge of the transport network.

Performing the one or more iterations may comprise performing multiple iterations to iteratively refine the set of convergent routes and to iteratively optimise the period of time.

Determining a schedule of movement may comprise based on the quantity of movement selectively solving a scheduling problem for the set of convergent routes.

Experimental results on a real case study show that the two-stage approach of first determining convergent routes and then selectively solving a scheduling problem for the set of convergent routes produces better primal bounds than the MIP model and is two orders of magnitude faster. It also produces dual bounds stronger than the linear relaxation of the MIP model for the entire problem. It is an advantage that the method provides stronger dual bounds than the linear relaxation of the MIP model of the entire problem, since bounds provide a quality guarantee on the results of the method.

The two-stage approach provides high-quality solutions with average and worst-case optimality gaps of 0.2% and 0.7% in less than a minute of CPU Time. In contrast, the MIP model of the entire problem provides solutions with average and worst-case optimality gaps of 1.7% and 7.9% in 24 hours.

Solving a scheduling problem may comprise storing the schedule of movement on a data store or generating a display representing the schedule of movement. The method may further comprise based on the quantity of movement selectively using the period of time as an upper bound or a lower bound of an evacuation completion time. The method may further comprise:

determining whether the quantity of movement is equal to a predetermined value;

upon determining that the quantity of movement is equal to a predetermined value setting the upper bound to the period of time; and

upon determining that the quantity of movement is unequal to the predetermined value setting the lower bound to the period of time.

An example of determining whether the quantity of movement is equal to a predetermined value is provided with reference to line 7 of Algorithm 3 in Fig. 6.

An example of upon determining that the quantity of movement is equal to a predetermined value setting the upper bound to the period of time is provided with reference to line 12 of Algorithm 3 in Fig. 6. An example of upon determining that the quantity of movement is unequal to the predetermined value setting the lower bound to the period of time is provided with reference to line 14 of Algorithm 3 in Fig. 6.

Adjusting the period of time may comprise adjusting the period of time based on the upper bound and the lower bound.

An example of adjusting the period of time based on the upper bound and the lower bound is provided with reference to line 5 of Algorithm 3 in Fig. 6. Adjusting the period of time may comprise setting the period of time to a value in the interval defined by the lower bound and the upper bound. Adjusting the period of time may comprise setting the period of time to a value that is equidistant from lower bound and the upper bound. An example of setting the period of time to a value in the interval defined by the lower bound and the upper bound and for setting the period of time to a value that is equidistant from lower bound and the upper bound. is provided with reference to line 5 of Algorithm 3 in Fig. 6.

The method may further comprise outputting one or more of the upper bound and the lower bound on an outputting device.

The method may further comprise:

determining whether the quantity of movement is equal to a predetermined value;

upon determining that the quantity of movement is equal to a predetermined value decreasing the period of time; and

upon determining that the quantity of movement is unequal to the predetermined value increasing the period of time. The method may further comprise optimising a clearance time based on the set of convergent paths. Optimising the clearance time may comprise using the clearance time as a variable in an objective function of a tree-design problem.

The method may further comprise:

receiving events related to the transport network;

determining an updated transport network based on the events; and

performing the method of any one of the preceding claims based on the updated transport network. Software, when installed on a computer, causes the computer to perform the method of any one of the preceding claims.

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 and a period of time associated with the movement;

a processor

to perform one or more iterations of

determining a set of convergent routes through the transport network based on the period of time,

an output port to output the schedule of movement.

Optional features described of one of the above aspects of method, software or system, where appropriate, similarly apply to the other aspects also described here.

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. 2 illustrates a method for planning movement of multiple groups over a transport network.

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.

Fig. 5 illustrates an algorithm that implements a two-stage approach.

Fig. 6 illustrates an algorithm of a tree design and flow scheduling procedure. Fig. 7 illustrates an algorithm of a heuristic to optimise a clearance time.

Fig. 8 illustrates a more detailed procedure to optimise the clearance time.

Fig. 9 illustrates a map of a geographical area of interest.

Fig 10 illustrates an evacuation graph of a transport network.

Fig. 11 illustrates an evacuation tree computed with the procedure of Fig. 8. Fig. 12 illustrates an evacuation planner computer system.

Fig. 13 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. 2, that is, the processor 102 determines a set of convergent routes based on a period of time and a quantity of movement over the set of convergent routes. Processor 102 then adjusts the period of time based on the 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 the period of time associated with the movement, such as by a previous iteration of the method, and store the period of time on data store 106, such as in a database or on a RAM. The processor 102 can then request the period of time from the datastore 106 and receives the period of time via a memory interface.

The same applies when the processor 102 determines a route or solves a scheduling problem to determine a departure schedule. 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, evacuation plans 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, the 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. 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. 2 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.

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 G = (N = E VJ T VJ S, A) where S , T , and S are the set of evacuated, transit, and safe nodes respectively, and A is the set of edges. Each evacuated node i is characterized by a number of evacuees d _t and an evacuation deadline f _t (e.g., 20 and 13 :00 for node 0 (reference numeral 352) respectively), while each edge e is associated with a triple (s _e , _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 = S ^{d d} u S ^d , A ^d ) is constructed by duplicating each node from λί for each time step. For each edge (i, j) e A and for each time step t in which edge is available, an edge (i _t , j _t+s ) is created modelling the transfer of evacuees from node i at time t to node j at time t + s _{(1 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 (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 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 evacuee when to leave, 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 persons as possible in the minimum amount of time;

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

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

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. Finally, 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. 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 two outputs: (1) a traffic management plan, including detailed evacuation, and (2) an evacuation schedule, specifying when residential zones should evacuate and the total duration of the evacuation.

In a controlled evacuation each residential zone is assigned a specific route and time to evacuate, leading to an effective utilization of the road network. These approaches significantly improve the quality of evacuation plans, evacuating more people over a given horizon or decreasing the overall evacuation time. However, two evacuation routes can merge, possibly share a few road segments, and then diverge, leaving evacuees with a choice at the fork. Evidence collected during evacuations demonstrates that drivers hesitate when approaching a fork, leading to additional congestion.

To address this limitation, convergent evacuation plans assign an evacuation route to each residential zone and ensure that the overall plan converges to the safe zones. Convergent evacuation plans can be fully controlled by closing the outgoing roads that are not used for evacuation purposes, forcing the flow of evacuees to follow the evacuation plan. They also remove a key source of congestion by ensuring that drivers never face a choice. Optimal convergent plans can be obtained by a Mixed Integer Program (MTP) model using a time-indexed flow formulation.

However, it is difficult with this model to tackle realistic-scale evacuations. To remedy this issue a two-stage approach is disclosed that separates the choice of evacuation routes from the scheduling of the evacuation. More precisely, processor 102 performs the first stage, and solves a tree design problem. During the first stage processor 102 selects a set of convergent routes and produces a quantity of movement, such as an upper bound on the number of people who can reach safety over a time horizon.

The second stage solves a flow scheduling problem that determines how to evacuate the residential zones optimally given the evacuation routes produced in the first stage.

Experimental results on a real case study demonstrate the benefits of the two-stage approach. In particular:

• The tree design problem provides dual bounds that are stronger than the linear relaxation of the MIP model;

• The two-stage approach produces better primal bounds than the MIP model and is two orders of magnitude faster, producing high-quality convergent evacuation plans for 70,000 people in less than a minute.

• Convergent evacuation plans outperform traditional approaches even for minimal driver hesitations at forks.

The input of the Evacuation Planning Problem is an evacuation graph Q = (AT = £ u u (S, ) , where £, T , and S are the set of evacuation, transit, and safe nodes, and A is the set of arcs. Each evacuation node is characterized by a number of evacuees d _i and an evacuation deadline f _i , while each arc 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 arc becomes unavailable. For modeling purposes, we assume that all evacuation (resp. safe) nodes are connected to a super source v _s (resp. sink v,). Note that u _{v I)} = d _i . The goal of the EPP is to find a maximum flow from v _s to v _t which allows to retrace the path and departure time of each evacuee.

Fig. 3a, 3b and 4 illustrate these concepts. Figs. 3a and 3b present an evacuation scenario with one evacuation node (0) and two safe nodes (A and B). The evacuation node 0 must be evacuated by 13 :00 and different arcs become unavailable at different times (for instance, (2, 3) is cut at 9:00). Figure 2 specifies an evacuation graph based on this scenario. Here evacuation node 0 has a demand of 20 and a deadline of 13 :00. The arc (0, 1) has a travel time of 1, a capacity of 10, and becomes unavailable at

11 :00.

In one example, the period of time associated with the movement, also referred to as planning horizon H , is represented by a single number h indicating the end of the period of time assuming that the evacuation starts at the time of calculation. In some examples, however, the threat can be predicted in advance and evacuation is planned before it is started. For example, the landfall of a hurricane can be predicted days in advance. In this case, the time values of the evacuation plan are normalised to the start time, such that the first time value of the evacuation is 'Ο'. This way, the value h of the period of time indicates the time available for planning the evacuation and as well as the point in time when the available time for the evacuation ends. The period of time may be set independently of the evacuation scenario at hand, which means that in many cases the last evacuee is scheduled to arrive at a safe node well before the end of the period of time. The period of time can then be adjusted as described herein.

The Converging Evacuation Planning Problem (CEPP) is a subclass of the EPP in which the evacuation paths form a tree T rooted in v _t . Thus in the CEPP, any subset of paths meeting at an intersection merge into one single exiting path. A flow following a set of merging paths is a converging flow. More formally, the goal of the CEPP is to find a subgraph of the evacuation graph that maximizes the flow of evacuees and is fully controllable. A graph is convergent if, for every node i e λί , the outdegree of is 1. It is connected if, for every evacuation node i e S , there is a path from the source v _s to the sink v _t going through . Observe that if the arcs direction is reversed and v _s is ignored, these paths form a tree rooted at v _t with evacuation nodes as leaves. An evacuation graph that is both connected and convergent is fully controllable from an operational perspective.

Proposition 1 Let Q be a connected evacuation graph. There exists a connected and convergent subgraph T of Q .

Proposition 2 There is a unique path from an evacuation node to the sink in every connected and convergent evacuation graph.

The Convergent Evacuation Planning Problem (CEPP) can now be formally stated.

Definition 1 (CEPP) Given a connected evacuation graph Q as input, the Convergent

Evacuation Planning Problem (CEPP) consists of finding a convergent subgraph Ύ of Q whose associated time-expanded graph T ^d maximizes the flow from v _s to v _r Consider Q a graph and Q ^d the corresponding time-expanded graph. The CEPP consists in finding the maximum flow on Q ^d from a set of source nodes S ^d to a sink node v _t , such that for each source node , the flow to v _t only uses edges from a path p _i defined in Q , and the union of the paths p _i forms a tree rooted at the sink. As background information, the following description provides a MIP model for solving the CEPP. The model uses a binary variable x _e to denote whether arc e e Q is selected and a continuous variable φ _ε for the flow on arc e _t e Q ^d . The MIP model is formulated as follows: max 0) .t.

(p _et < x _e .u _et e e A t e H (4) φ > 0 Me _t e A ^d (5)

where 5 ^~ (i) (resp. S ⁺ (i) ) denotes the set of incoming (resp. outgoing) edges of node . Constraints (2) ensure flow conservation through the network, constraints (3) enforce convergence of the evacuation plan, constraints (4) link the arc and flow variables, while the objective (1) maximizes the total evacuee flow.

Computational experiments show that the MIP formulation quickly becomes intractable for real-sized instances. The following description presents a two-stage approach that separates the choice of the converging paths from the flow scheduling.

Referring back to method 200 in Fig. 2, the first stage of the disclosed approach for planning movement of multiple groups over a transport network is a Tree Design Problem (TDP). Processor 102 receives 202 a period of time associated with the movement, such as a data value indicative of the current planning horizon. As mentioned above, receiving may comprise retrieving the value from the data memory 106 or from a user interface 118. Based on the period of time, processor 102 then determines 204 a tree defined by a set of convergent routes based on a planning horizon. Intuitively, the TDP is an abstraction of the CEPP where the evacuation flow is aggregated over time, avoiding the need to reason about the time-expanded evacuation graph.

Let Q ⁺ be the evacuation graph Q where the arc capacities have been summed over the time horizon. The TDP consists of finding a convergent subgraph of Q ⁺ that maximizes the flow from the source to the sink.

The TDP can be formulated as a MIP model with a binary variable y _e and a continuous flow variable ψ, for each arc e <≡A . The binary variable denotes whether arc e is selected, while the continuous variable represents the aggregated flow on arc e . The TDP can be formulated as follows:

max (7) ε<Ξβ ⁺ (ν

si.

ee<5 (/) ee<5 (/)

∑ y _e < l V/ e A/- (9) e&T ^" (i )

ψ _β ≥0 Ve s A (11) y _e G {0, \ } Ve s A (12) The above formulation does not contain a reference to the time t, which means that for solving the TDP, movement is allowed over each of the set of convergent routes at any point in time within the time period. Constraints (8) and (9) ensure flow conservation and a convergent plan, constraints (10) impose the flow capacity on each arc, and the objective (7) maximizes the flow, that is, the result of the objective function is the total number of group members that can move over the set of convergent routes within the time horizon and that result is used as a quantity of movement.

Theorem 1 The optimal solution of TDP is an upper bound to the CEPP.

Proof. We show that an optimal solution to the CEPP can be transformed into a solution of the TDP with the same objective value. Let Φ = {φ" ^ί χ ₍ ,} be an

optimal solution to the CEPP and ζ(Φ) be its objective value. Consider the following candidate solution to the TDP: Ψ = {i _e - _> y _e ^{= x} e )eeA - By definition of the flows, the objective value of Ψ is equal to ζ(Φ) . We now show that Ψ satisfies all constraints of the TDP. Since Φ is a solution to the CEPP, it satisfies constraints (2) and we have

and Ψ satisfies constraints (8). Since Φ satisfies constraints (3), it follows that Ψ satisfies constraints (9). Finally, since Φ satisfies constraints (3), we have

φ ≤x _e .u \/e <≡ A, Vt <≡ H

and Ψ satisfies (10). The result follows.

As can be seen from the above MIP formulation of the TDP, determining the tree also comprises determining 206 a quantity of movement, such as the flow ψ, over the set of convergent routes. Processor 102 then adjusts 208 the time horizon h based on the quantity of movement ψ over the set of convergent routes. An optimal solution to the TDP defines a connected and convergent evacuation graph T used in the second stage to schedule 210 the flow of evacuees. The second stage may be a Flow Scheduling Problem (FSP) that maximizes the flow in the time- expanded graph ^d associated with T .

The FSP avoids the creation of the time-expanded graph by reasoning about paths from the evacuation nodes to the sink. By Propositions (1) and (2), the TDP produces a convergent and connected subgraph which includes a unique path from each evacuation node to the sink. We denote by Ω this set of paths and use the following notations: T _p ^e is the time taken to reach edge e from the source node using path ρ <≡Ω. ,

O.Ji - τ) is the set of departure times that would allow evacuees to reach safety by using path p , p _t is the path associated with evacuation node i e S in the TDP solution, and w(e) is the set of paths using arc e . The FSP uses a continuous variable χ' for each path ρ <≡Ω. and i H to represent the flow leaving at time t along path p . The FSP can then be specified by the following linear program:

m ^ax Σ Σ (13)

(15) ρ&ω (e)

Constraints (14) ensure that the number of evacuees along path p _k does not exceed the number of evacuees d _k in evacuation node k , while constraints (15) enforce arc capacity by reasoning about the number of evacuees that can reach arc e at time t . The objective (13) maximizes the total flow along all paths and all times in the horizon.

In the following, we denote by TDP(^, 7i) an optimal solution to the stage 1 (TDP) given an input evacuation graph Q and horizon Ή and by Ρ8Ρ(Ψ, 7ΐ) an optimal solution to the stage two (FSP) given a solution Ψ to the TDP and horizon , and CEPP(^, 7i) an optimal solution to the CEPP MIP. We also use ζ{σ) to denote the objective value of a solution σ to the CEPP, TDP, or FSP. Corollary 1 Let Q be a connected evacuation graph, Ή a time horizon. We have

Z(TDP (g, H))≥ Z(CEPP (g, H))≥ Z(FSP (TDP (g, H) , n)y The combination of TDP and FSP provides a solution to the CEPP. In some examples, processor 102 reduces the gap between the FSP flow value φ and the maximum TDP flow value ψ _Ή ^* for a given time horizon Ή . In other words processor 102 determines a tree T such that the FSP maximum flow using T through horizon Ή , φ _{η τ} , is as close as possible to ψ _Ή ^* .

When the time horizon is too large, many convergent evacuation plans would be optimal solutions to the TDP. However, these plans often differ substantially in their ability to deal with congestion. In practice, using optimal solutions to the TDP with a tighter time horizon produces significantly better plans for the FSP. A way to generate different trees with TDP is to pick distinct values for Ή in constraint (10). In one example, processor 102 finds the best solution for FSP when the TDP flow is maximal. The FSP flow may be highest when the horizon for TDP is close to [0, r] with τ such that ψ _[ ^* _{0 T]} = ψ _Η ^* and ψ _[ ^* _{0 T} _ < ψ _η ^* . As a result, the two-stage approach for tree design and flow scheduling (TDFS) computes the smallest time horizon that preserves the optimal solution to the TDP and solves the FSP using the TDP solution obtained for the tightest time horizon.

Fig. 5 illustrates an algorithm 500 stored as program code on program memory 104 and executed by processor 102. Algorithm 500 implements the two-stage approach. The FSP receives the full horizon, since the TDP is an approximation to the CEPP and it may not be possible to schedule the TDP flow in the time-expanded graph for the tightest time horizon. The tightest time horizon can be obtained by dichotomic search over the horizon using the TDP as a subproblem. Fig. 6 illustrates an algorithm 600 of the TDFS procedure stored as program code on program memory 104 and executed by processor 102. First, processor 102 initializes the time horizon bound for TDP to (0, /z) (line 1), stores the time horizon as the period of time associated with the movement on data store 106, receives the period of time from data store 106 and computes an initial TDP solution (line 2), and an initial FSP solution using the tree from TDP (line 3) and stores the resulting values on data memory 106. Processor 102 then performs a dichotomic search on the length of the horizon.

The dichotomic search means that given the upper and lower bounds, the processor 102 selects the time horizon as the point in time that is equidistant from the upper and the lower bounds (line 5 of algorithm 600). For example, processor 102 starts with an initial time horizon of 12 hours and determines the set of convergent paths given 12 hours of available time. In doing so, the processor 102 may multiply the capacity of individuals per hour of each edge by 12 hours to determine the total capacity of that edge.

This initial value of 12 hours is chosen such that it is relatively certain that all individuals can evacuate in that time horizon. As a result, the quantity of movement, that is, the total flow for 12 hours should be equal to the total number of evacuees. This means the upper bound is 12 hours and the lower bound is zero hours. It is noted that doubling the initial value results in only one additional iteration and insignificant computation time. Therefore, the initial value can be set conservatively high. In another example, processor 102 sets the initial value arbitrarily. If the initial value was too low processor 102 doubles the time horizon by performing the described method.

In order to reduce the time horizon, processor 102 sets the time horizon in the middle between the upper and lower bounds, which is 6 hours in this example.

At each iteration of the loop in method 200, processor 102 solves the TDP on the current horizon (line 6), which corresponds to steps 204 and 206 of method 200 in Fig. 2. Based on the flow, that is, the quantity of movement over the set of convergent routes, processor 102 adjusts the time horizon in lines 12 and 14 depending on the flow ψ according to step 208 of method 200. That is, if the flow remains unchanged from the first iteration (line 7), which indicates that all evacuees can be evacuated, processor 102 reduces the upper bound to the time horizon (line 12) and as a result, reduces the time horizon (line 5). On the other hand, if the flow changes, that is, not all evacuees can be evacuated, processor 102 increases the lower bound to the time horizon (line 14) and as a result, increases the time horizon (line 5). If the corresponding static flow ψ is equal to the original bound, processor 102 solves the FSP (line 8), keeping track of the best solution found (line 10) on data memory 106, and decreases the horizon upper bound (line 12). Otherwise processor 102 increases the horizon lower bound (line 14). Finally, processor 102 returns the best solution (evacuation plan) found during the search and may store the solution in data store 106. An evacuation plan may comprise:

- a set of converging evacuation routes, exactly one for each evacuated area; and

- a departure schedule for each evacuated area.

In one example, processor 102 determines as an output of the CEPP a schedule of the actual departure of evacuees. Processor 102 stores this schedule on data store 106 in the form of ASCII characters, an Excel spreadsheet or as a graphical representation.

Processor 102 may also enter the schedule into a calendar tool, such as Outlook or automatically send alert or reminder messages, such as emails or SMS messages to evacuees at the times of the schedule.

The scheduling of the evacuation can take different forms.

In one example processor 102 determines the scheduling of the evacuation by solving the FSP model (13-16), which solves a max flow problem over the time-expanded graph. This model provides an optimal departure time for each vehicle in each evacuated area. This corresponds to the time at which each unit of flow leaves an evacuated node.

In another example, the scheduling of the evacuation is obtained by solving a constraint programming model in which the evacuation of each area through the network is modelled as a scheduling problem in which edges play the role of machines, and evacuees the role of jobs.

In one example, processor 102 stores the evacuation plan as a list of postcodes with associated departure times and routes:

Postcode Departure time Route

2753 10am 1

2758 10:30am 2

2777 1 lam 1

where each of the route numbers identifies a particular sequence of street names. The evacuation plan that is finally presented in a visual representation 118, such as a modified map, on display device 114 comprises the tree T, that is, the set of convergent paths and the solution Φ of the scheduling problem. The solution Φ comprises the selected edges e and the flow on the selected edges during a particular time slot φ _Β . The evacuation plan T and Φ may be stored on data memory 106 or sent to different computer systems, such as smartphones or tablet computers of coordinators and police in the field. Based on the flow variables φ _Β evacuees can be notified of when they are asked to start their respective movements, such as through automatically generated SMS messages, emails, radio announcements, smartphone apps or web sites.

Processor 102 may also output the bounds, such as by displaying them on screen 114. The bounds can be valuable information to the operator 116 to judge the quality of the evacuation plan and assess how much the actual evacuation might deviate from the determined plan.

In evacuation planning, it is often desirable to determine the earliest time by which all evacuees can reach safety. More precisely, the goal is to compute the minimum clearance time h ^* defined as

To that purpose, we adapt the TDP model (7-12) by introducing a new continuous variable h representing the length of the horizon, setting the objective to min z , and adding the following constraints:

By executing the resulting model, namely TDP-CT, processor 102 determines a convergent subgraph and a lower bound on the clearance time.

Fig. 7 illustrates an algorithm 700 of the TDFS-CT heuristic which is executed by processor 102 to find a convergent evacuation plan of minimum clearance time given a solution of TDP-CT. In this example, step 2 uses a dichotomic search initialized with the lower bound provided by TDP-CT. Fig. 8 illustrates a more detailed example 800 of the TDFS-CT procedure. Processor 102 solves TDP-CT (line 1), initializes the lower and upper bound on the clearance time (line 2) and solves the FSP (line 3). Given the tree T, the processor 102 iteratively estimates the minimum clearance time and tightens the minimum clearance time bounds using the secant line (lines 4-11). Finally, processor 102 uses a binary search to find the minimum clearance time (lines 12-21).

One example application is the evacuation of the Hawkesbury-Nepean (FIN) floodplain, located North-West of Sydney. We consider a l-in-200 years flood that would require the evacuation of 70,000 people. The UN evacuation graph defined by data stored on data memory 106 contains 80 evacuated nodes, 5 safe nodes, 184 transit nodes, and 580 edges. The time horizon Ή spans 10 hours discretised into 5 minutes time-steps.

Some examples also consider a class of instances HN80-Ix using the UN evacuation graph but a number of evacuees scaled by a factor x e [1.1, 3.0] to reflect projected population growth over the next decades. The disclosed methods may be implemented using Java 7 and Gurobi 5.6 and the results may be obtained on 64bits machines with 2.8GHz AMD 6-Core Opteron 4184 and 32Gb of RAM.

In one example, the processor 102 has a further input port (not shown) to receive events related to the transport network, such as roads closures, threat scenario updates and traffic information. The processor 102 then updates the road network, such as by adjusting the capacity of affected edges where the speed of travel is reduced or removing edges altogether. The processor 102 then performs the method described above to design an evacuation plan over the changed road network. The processor 102 may start from the previous solution based on the outdated road network as an initial solution or may start from a new initial solution as described above. The re- computation of the evacuation plan in response to changes to the road network may be in real-time, that is, the evacuation plan is continuously adjusted and each adjustment is computed within a set maximum computation time.

Fig. 9 illustrates a map 900 of the HN geographical area of interest displayed on screen 114.

Fig. 10 illustrates the original HN evacuation graph 1000 while Fig. 11 illustrates an evacuation tree 1100 computed with TDP-CT. Both graph 1000 and tree 1100 may be displayed on screen 114 to operator 116. The evacuation tree demonstrates the ability of this algorithm to compute direct paths for each evacuation area.

Fig. 12 presents an evacuation planner computer system 1200, an intelligent system for integrated evacuation planning. Computer system 1200 pulls information from raw databases 1202 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 1204. 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 1206 and can be combined to produce an evacuation instance which is then used as input to the evacuation optimization module 1208. 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. 13 illustrates a web interface 1300 which allows planners to work with multiple scenarios simultaneously. A left panel 1302 presents the different layers (e.g., road network, population, evacuated areas), while a right panel 1304 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.