Continuous Time Dynamic Contraflow Models and Algorithms

Abstract

The research on evacuation planning problem is promoted by the very challenging emergency issues due to large scale natural or man-created disasters. It is the process of shifting the maximum number of evacuees from the disastrous areas to the safe destinations as quickly and efficiently as possible. Contraflow is a widely accepted model for good solution of evacuation planning problem. It increases the outbound road capacity by reversing the direction of roads towards the safe destination. The continuous dynamic contraflow problem sends the maximum number of flow as a flow rate from the source to the sink in every moment of time unit. We propose the mathematical model for the continuous dynamic contraflow problem. We present efficient algorithms to solve the maximum continuous dynamic contraflow and quickest continuous contraflow problems on single source single sink arbitrary networks and continuous earliest arrival contraflow problem on single source single sink series-parallel networks with undefined supply and demand. We also introduce an approximation solution for continuous earliest arrival contraflow problem on two-terminal arbitrary networks.

Academic Editor:Konstantina Skouri

Central Department of Mathematics, Tribhuvan University, P.O. Box 13143, Kathmandu, Nepal

Received 10 September 2015; Accepted 6 March 2016

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

In normal understanding, an evacuation planning problem is the procedure of shifting residents from disastrous zones to safety areas as successfully as possible with maximum reliability. For an evacuation network, contraflow is a widely accepted model for a good solution rather than an optimal one for practical cases. It increases the outbound road capacity by reversing the direction of arcs. It is a challenging problem of finding a network reconfiguration with ideal lane directions satisfying the given constraints that optimizes the given objective. With the aim of responding to different large scale disasters, many contraflow evacuation plans have been developed that seek to remove traffic jams and make the traffic systematic and smooth. In the literature, we find various mathematical models, heuristics, optimization, and simulation techniques with contraflow for the transportation networks, [1, 2].

There are only some analytical optimization techniques in the literature handling discrete dynamic contraflow problems. The first analytical solution for two-terminal maximum dynamic contraflow (MDCF) problem has been presented in [2] with efficient algorithm. The MDCF problem on multiterminal networks is NP-hard in the strong sense even with two sources and one sink or vice versa. The proofs follow by reductions from the problems 3-SAT and PARTITION [1, 2]. Author in [2] also solved the quickest contraflow (QCF) problem on two-terminal networks polynomially. Its solution is based on parametric search algorithms of [3]. They proved that the multiterminal QCF problems are harder than 3-SAT and PARTITION. An optimal solution to the [figure omitted; refer to PDF] MDCF (and [figure omitted; refer to PDF] EACF) problem on a two-terminal series-parallel graph (TTSP-graph) has been obtained in [4]. Authors in [5] showed that the EACF problem for general graphs always exists with relaxation of arc reversal capability at a number of times when an EAF solution demands this property. For two-terminal network [figure omitted; refer to PDF] , an approximate EACF solution has been presented in [6]. For multiterminal networks with given supply and demand, lexicographically maximum dynamic contraflow (LMDCF) problem has been solved in polynomial time complexity [5]. Moreover, the earliest arrival transshipment contraflow problem in different particular networks has been solved in [7].

In this paper, we introduce a continuous contraflow model and present some efficient algorithms to solve it. We mainly focus on the analytical solution for the problem. However, its importance from the practical point of view would also be interesting.

The organization of the paper is as follows. In Section 2, we study briefly the continuous network flow problems and explain the terminology used in the rest of the paper. A polynomial time algorithm with contraflow configuration is introduced for the maximum continuous dynamic contraflow problem in Section 3. In contrast to the maximum continuous dynamic contraflow, we solve the quickest continuous contraflow problem that finds minimal time required to shift given integral value of flow in Section 4. By sending the maximum amount of flow from the beginning of time, we solve the continuous earliest arrival contraflow problem presenting strongly polynomial time algorithm on two-terminal series-parallel networks in Section 5.1. Section 5.2 presents an approximate solution for the continuous earliest arrival contraflow problem on two-terminal arbitrary networks. Section 6 concludes the paper.

2. Basic Denotations and Models

A directed graph [figure omitted; refer to PDF] where [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , with a set of nodes [figure omitted; refer to PDF] and a set of [figure omitted; refer to PDF] , represents an evacuation scenario. We have considered the contraflow problem, so two-way network configuration is allowed. Let [figure omitted; refer to PDF] and [figure omitted; refer to PDF] be a set of source nodes, that is, initial location of evacuees, and a set of sink nodes, that is, safe location for evacuees with enough capacity, respectively. Nodes [figure omitted; refer to PDF] and [figure omitted; refer to PDF] represent the single source and single sink. Let [figure omitted; refer to PDF] on an [figure omitted; refer to PDF] be an upper bound on the amount of flow actually on that arc. Let [figure omitted; refer to PDF] be the rate of flow that is the amount of flow entering the particular arc per time unit. It is bounded by arc capacity of that arc; that is, [figure omitted; refer to PDF] . The time needed to transfer one unit of flow on [figure omitted; refer to PDF] from node [figure omitted; refer to PDF] to [figure omitted; refer to PDF] is the transit time [figure omitted; refer to PDF] . Here we consider the constant transit time; that is, if we send one unit of flow from node [figure omitted; refer to PDF] at time [figure omitted; refer to PDF] with flow rate one, then it will reach the node [figure omitted; refer to PDF] at time [figure omitted; refer to PDF] with flow rate one. We assume that [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] and [figure omitted; refer to PDF] for the node [figure omitted; refer to PDF] . The group of evacuees is modeled as a flow which passes through the network over time.

With predetermined time [figure omitted; refer to PDF] , we represent the transportation network as the collection of all data [figure omitted; refer to PDF] . We assume a finite time horizon [figure omitted; refer to PDF] that means everything must happen before a given stop time [figure omitted; refer to PDF] . Time can increase in discrete increments or continuously. In discrete time approach, we appear at the networks with a suitable time unit like at times [figure omitted; refer to PDF] and all time related parameters are integers. But, in continuous approach, [figure omitted; refer to PDF] can take any value in [figure omitted; refer to PDF] . By converting the continuous flow models into discrete ones, time can be discretized in practical models. The choice of time unit affects the problem directly; that is, if the time unit is shorter, then the problem is more complex. Let [figure omitted; refer to PDF] be the domain of time that can be valid for both discrete and continuous approaches; that is, [figure omitted; refer to PDF] in a discrete model and [figure omitted; refer to PDF] in a continuous model.

Let the reversal of an [figure omitted; refer to PDF] be [figure omitted; refer to PDF] . For a contraflow configuration of a network [figure omitted; refer to PDF] with symmetric transit times, the auxiliary network [figure omitted; refer to PDF] consists of the modified arc capacities and transit times as [figure omitted; refer to PDF] where an edge [figure omitted; refer to PDF] in [figure omitted; refer to PDF] if [figure omitted; refer to PDF] in [figure omitted; refer to PDF] . The remaining graph structure and data are unaltered.

2.1. Natural Transformation of Discrete into Continuous Model

Let [figure omitted; refer to PDF] and [figure omitted; refer to PDF] be the amount of flow on an [figure omitted; refer to PDF] and the rate of flow on an [figure omitted; refer to PDF] , respectively. Thus, [figure omitted; refer to PDF] is the amount of flow on [figure omitted; refer to PDF] at discrete time [figure omitted; refer to PDF] and [figure omitted; refer to PDF] is the amount of flow that enters [figure omitted; refer to PDF] at continuous time [figure omitted; refer to PDF] . These two functions are closely related in continuous and discrete models, respectively [8]: [figure omitted; refer to PDF]

The distinguish between the discrete time approach and continuous time approach depends upon the flow that entering an [figure omitted; refer to PDF] at time [figure omitted; refer to PDF] has already arrived at the head node by [figure omitted; refer to PDF] or is still on the arc at that moment. In the discrete approach, we assume that such a flow is already at the head node at time [figure omitted; refer to PDF] .

Let [figure omitted; refer to PDF] be a feasible discrete flow entering [figure omitted; refer to PDF] at time [figure omitted; refer to PDF] for [figure omitted; refer to PDF] and set the continuous flow rate [figure omitted; refer to PDF] to [figure omitted; refer to PDF] for [figure omitted; refer to PDF] . We assume that the arc capacities do not change. Then, from this natural transformation, we obtain a feasible continuous flow and the flow value in any integral interval [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , will be same for both [figure omitted; refer to PDF] and [figure omitted; refer to PDF] . Authors in [9] presented this natural transformation for many discrete dynamic flows based on chain decomposable flows to transform into continuous dynamic flows and proved its optimality.

Suppose that [figure omitted; refer to PDF] is a static flow and it has a standard decomposition into a set of chains [figure omitted; refer to PDF] with [figure omitted; refer to PDF] that satisfies [figure omitted; refer to PDF] where all chains in [figure omitted; refer to PDF] start and end at the terminal nodes and use the arcs in the same direction as [figure omitted; refer to PDF] does in discrete time approach. The lengths of all chains [figure omitted; refer to PDF] satisfy [figure omitted; refer to PDF] for standard chain decomposition [figure omitted; refer to PDF] . Then, [figure omitted; refer to PDF] computes a feasible dynamic flow obtained by summing the dynamic flows induced by each chain flow.

For the integral time horizon [figure omitted; refer to PDF] , the natural transformation of chain decomposable flows is feasible. If [figure omitted; refer to PDF] is not integral, then we have a discrete [figure omitted; refer to PDF] time. Due to the integral transit time, all the chain flows have integral length. This results in that the chain flows used with time horizon [figure omitted; refer to PDF] can also be used with time bound [figure omitted; refer to PDF] . A chain flow is not affected by the time it starts to use an arc. But it reduces the time when the chain flow uses the arc. Thus, a discrete [figure omitted; refer to PDF] -horizon chain decomposable flow can be transformed naturally into a continuous [figure omitted; refer to PDF] -horizon flow and stop sending flow along each chain flow [figure omitted; refer to PDF] at time [figure omitted; refer to PDF] instead of time [figure omitted; refer to PDF] . In dynamic flow, a chain induces the same amount of flow at each chain flow. Hence if the discrete chain decomposable flow is feasible, then the continuous chain decomposable flow is also feasible.

2.2. Continuous Dynamic Flow Model

The static flow [figure omitted; refer to PDF] is defined on [figure omitted; refer to PDF] that satisfies the capacity constraint [figure omitted; refer to PDF] and flow conservation constraints: [figure omitted; refer to PDF] If a static flow satisfies the flow conservation constraints at terminals also, then it is a static circulation. The residual network [figure omitted; refer to PDF] of a static flow [figure omitted; refer to PDF] with respect to capacity [figure omitted; refer to PDF] is the same network with redefined residual capacities as [figure omitted; refer to PDF] for forward arc and [figure omitted; refer to PDF] for backward arc.

A discrete dynamic flow is a function [figure omitted; refer to PDF] that represents a flow to each arc at each time step [figure omitted; refer to PDF] satisfying the capacity constraint [figure omitted; refer to PDF] for all time steps [figure omitted; refer to PDF] and flow conservation constraints with allowing holdover at nodes: [figure omitted; refer to PDF]

Let [figure omitted; refer to PDF] be a continuous dynamic flow with the capacity constraints as flow rate constraint and the flow conservation constraints similar as for the discrete dynamic flow, with the sum over time replaced by an integral as follows: [figure omitted; refer to PDF] For a given time [figure omitted; refer to PDF] , the maximum continuous dynamic flow (MCDF) problem maximizes [figure omitted; refer to PDF] in (7) satisfying the constraints (5) and (6): [figure omitted; refer to PDF] The continuous earliest arrival flow (CEAF) problem maximizes [figure omitted; refer to PDF] in (8) satisfying the constraints (5) and (6) for all [figure omitted; refer to PDF] : [figure omitted; refer to PDF]

3. Maximum Continuous Dynamic Contraflow

In this section, we discuss the maximum continuous dynamic contraflow (MCDCF) problem. Recall that the maximum dynamic flow (MDF) problem was solved in [10] by solving a minimum cost flow (MCF) problem with the arc costs as travel times on arcs. A MDF has been obtained by the temporally repeated flows (TRFs). The static optimal flow is decomposed into paths which are TRF over time [figure omitted; refer to PDF] , yielding the MDF. With a static flow [figure omitted; refer to PDF] and a chain decomposition [figure omitted; refer to PDF] , authors in [10, 11] calculated the MDF value associated with a TRF for given time horizon [figure omitted; refer to PDF] as in (9). The sum on the right depends on only the static flow and not on the particular [figure omitted; refer to PDF] : [figure omitted; refer to PDF]

The temporally repeated flow expressed in (9) can be extended to continuous time. For the networks with fixed arc capacities, authors in [12] showed that the maximum continuous dynamic flow in time [figure omitted; refer to PDF] has been obtained with the temporally repeated flow as in Theorem 1.

Theorem 1 (see [12]).

The MCDF in time [figure omitted; refer to PDF] in a network [figure omitted; refer to PDF] has value [figure omitted; refer to PDF] where [figure omitted; refer to PDF] is a minimum cost circulation flow (MCCF) in the network with an additional [figure omitted; refer to PDF] arc with cost [figure omitted; refer to PDF] and infinite capacity.

In this section, we first study the single source and single sink MCDCF problem. We assume that the arc is reversed at time zero without any processing cost. That means, if we choose to reverse an arc, it remains reversed from time [figure omitted; refer to PDF] to [figure omitted; refer to PDF] . We assume that the network is allowed to be asymmetric with respect to the arc capacities. However, if both directions of an arc are included in the network, then transit time of these two arcs must be the same. Thus, reversing an arc only changes the capacity of the arc but does not alter its transit time.

Problem 2.

Given a dynamic network [figure omitted; refer to PDF] , the MCDCF problem is to find a maximum continuous flow by maximizing Objective (7) with respect to constraints (5) and (6) that can be sent from [figure omitted; refer to PDF] to [figure omitted; refer to PDF] in time [figure omitted; refer to PDF] , if the direction of arcs can be reversed at time zero.

Recall that authors in [2] solved the maximum dynamic contraflow (MDCF) problem in discrete time [figure omitted; refer to PDF] . The philosophy of the MDCF solution is that every MDCF solution in original network [figure omitted; refer to PDF] is equivalent to the MDF solution on corresponding auxiliary network [figure omitted; refer to PDF] . In continuous dynamic contraflow model with arc reversal at time zero, the capacity of the reversed arc is obtained by adding two-way arcs capacities but the transit time remains the same. Thus, the flow rate on arc increases but does not exceed the reversed capacities. This proves that the optimal MCDF obtained on auxiliary network [figure omitted; refer to PDF] with natural transformation of [9] is similar to a feasible MCDCF on original network [figure omitted; refer to PDF] as in Lemma 3.

Lemma 3.

Every MCDCF in original network [figure omitted; refer to PDF] is equivalent to the MCDF on the corresponding auxiliary network [figure omitted; refer to PDF] .

To solve the MCDCF problem, first we adopt the discrete MDCF algorithm of [2] on two-terminal network [figure omitted; refer to PDF] . By reversing the direction of arcs towards the sinks, we compute an auxiliary network [figure omitted; refer to PDF] . Then, apply the MCF algorithm for continuous time as presented in [9] that obtains the MCDF on the auxiliary network. The obtained MCDF is decomposed into paths and removable cycles. An [figure omitted; refer to PDF] is reversed if and only if the flow on [figure omitted; refer to PDF] is greater than [figure omitted; refer to PDF] or if there is a nonnegative flow along [figure omitted; refer to PDF] .

Algorithm 4 (maximum continuous dynamic contraflow (MCDCF)).

(1) Given a network [figure omitted; refer to PDF] .

(2) Obtain the auxiliary network [figure omitted; refer to PDF] .

(3) On network [figure omitted; refer to PDF] , we apply MCF algorithm of [9] with flow rate [figure omitted; refer to PDF] , capacity [figure omitted; refer to PDF] , and transit time [figure omitted; refer to PDF] .

(4) Perform flow decomposition into chain and cycle flows of the maximum flow resulting from Step (3) and the cycle flow is removed.

(5) [figure omitted; refer to PDF] is reversed, if and only if the flow along [figure omitted; refer to PDF] is greater than [figure omitted; refer to PDF] or if there is a nonnegative flow along [figure omitted; refer to PDF] and the resulting flow is MCDF with the arc reversals for the network [figure omitted; refer to PDF] .

(6) Obtain the maximum continuous dynamic contraflow solution.

To show the feasibility of Algorithm 4, it is enough to show that only Step (5) is well defined. The flow is decomposed into paths and cycles with positive flows in Step (4). The positive flow along all cycles is canceled and there is no flow along any cycle. Therefore, there is a flow along either [figure omitted; refer to PDF] or [figure omitted; refer to PDF] but never in both arcs. This proves that the flow is not greater than the reversed capacities on all the arcs at all time units. This proves that the flow is bounded by the capacities on all reversed arcs at all time units.

Theorem 5.

Algorithm 4 solves the MCDCF problem on two-terminal network optimally.

Proof.

By reversing the direction of arcs in linear time, we obtain the auxiliary network [figure omitted; refer to PDF] . On [figure omitted; refer to PDF] we run the continuous dynamic temporally repeated flow algorithm of [9] that gives the MCDF solution by using Theorem 1. The obtained continuous flow is decomposed into chains and cycles. The cycles are removed. The flow obtained in Step (3) of the algorithm does not change in Steps (4) and (5). Thus, this flow is optimal in auxiliary network [figure omitted; refer to PDF] . Moreover, any optimal flow in auxiliary networks is equivalent to the optimal contraflow in original networks (cf. Lemma 3). That is, the MCDF in [figure omitted; refer to PDF] is equivalent to the MCDCF in [figure omitted; refer to PDF] .

Corollary 6.

The MCDCF solution can be obtained in [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] and [figure omitted; refer to PDF] are the time required to solve the flow decomposition and the minimum cost flow problem, respectively.

Proof.

By the natural transformation, the MDF obtained by solving temporally repeated minimum cost flow (MCF) problem of [10] is a MCDF on [figure omitted; refer to PDF] . Thus, the complexity to solve the MCDF problems remains the same as in discrete solution since the complexity of Algorithm 4 is dominated by Steps (3) and (4).

4. Quickest Continuous Contraflow

In contrast to the MCDCF problem, the quickest continuous contraflow (QCCF) problem shifts the given integral value [figure omitted; refer to PDF] of flow from source [figure omitted; refer to PDF] to sink [figure omitted; refer to PDF] in minimal time by reversing the direction of arcs towards the sink without any processing cost.

Problem 7.

Given a dynamic network [figure omitted; refer to PDF] , the QCCF problem is to find the minimum time [figure omitted; refer to PDF] satisfying the constraints (5) and (6) required to send a given integral flow value [figure omitted; refer to PDF] from [figure omitted; refer to PDF] to [figure omitted; refer to PDF] having arc reversal capability at time zero.

In discrete time setting, quickest contraflow problem has been polynomially solved in [2] on two-terminal networks. This solution has been based on the parametric search algorithms of [3]. First an upper bound on the quickest time has been obtained in polynomial time by computing a path from source to sink. Then a binary search has been applied repeatedly to obtain MDCF along the path until all supply at the source is sent to the sink.

In continuous time setting, using the natural transformation of [9], the QCCF problem on two-terminal networks for given integral supply [figure omitted; refer to PDF] can be solved polynomially. First, we convert given network [figure omitted; refer to PDF] into its auxiliary network [figure omitted; refer to PDF] . In auxiliary network, we solve the quickest continuous flow (QCF) problem using natural transformation of [9] in Step (3) of Algorithm 4. As in [9], for integral supply [figure omitted; refer to PDF] and integral transit times, the time of the quickest flow is a rational number with a denominator bounded by the size of a minimum cut in the network. This time can also be obtained by binary search algorithms of [3] as in discrete solution. By Lemma 3, the obtained QCF in [figure omitted; refer to PDF] is a feasible QCCF in [figure omitted; refer to PDF] .

Theorem 8.

For given two-terminal network [figure omitted; refer to PDF] with integer supply [figure omitted; refer to PDF] , the QCCF problem can be solved polynomially.

Notice that the construction of auxiliary network [figure omitted; refer to PDF] can be done in polynomial time. Moreover, the quickest continuous flow can be obtained in polynomial time using the methodology of [9]. From Lemma 3, the obtained QCF solution in auxiliary network is equal to the QCCF solution in original network. As the QCF solution in auxiliary network can be computed in polynomial time, the overall complexity required to solve the QCCF problem is polynomial.

5. Continuous Earliest Arrival Contraflow

We initiate the continuous earliest arrival contraflow (CEACF) problem in this section. It is also known as universal continuous maximum contraflow (UCMCF) problem. It is an extension of the maximum continuous dynamic contraflow problem with an additional property: the cumulative amount of flow having reached the sink in every considered time and all preceding times of the considered one have to be maximal. This property is called the earliest arrival property.

Problem 9.

Let [figure omitted; refer to PDF] be a two-terminal network. The CEACF problem is to find a feasible continuous dynamic flow from source [figure omitted; refer to PDF] to sink [figure omitted; refer to PDF] which is maximum for all times [figure omitted; refer to PDF] by maximizing Objective (8) satisfying constraints (5) and (6) if the direction of arcs can be reversed at time zero.

In general there is no efficient solution in the literature for the two-terminal earliest arrival contraflow problem (EACF) with arbitrary supply and demand on the terminals even in discrete time approach. Authors in [4] studied the problem on two-terminal series-parallel graphs (TTSP-graphs) and presented strongly polynomial time algorithm to solve it. Their algorithm has been obtained by a modification of MDCF algorithm in [2] using the MCCF algorithm of [13]. The main advantage in series-parallel networks is that every cycle in the residual networks has nonnegative cycle length. This solves the MCCF problem introduced in [11] for the MDF problem in the auxiliary network [figure omitted; refer to PDF] . The temporally repeated flow thus obtained is an optimal solution to the [figure omitted; refer to PDF] EACF problem on a two-terminal series-parallel graph in time [figure omitted; refer to PDF] .

A single [figure omitted; refer to PDF] is series-parallel with starting terminal [figure omitted; refer to PDF] and end terminal [figure omitted; refer to PDF] . Let [figure omitted; refer to PDF] and [figure omitted; refer to PDF] be two series-parallel graphs with starting terminals [figure omitted; refer to PDF] and [figure omitted; refer to PDF] and the end terminals [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , respectively. Then, the graph [figure omitted; refer to PDF] obtained by identifying [figure omitted; refer to PDF] as [figure omitted; refer to PDF] in the series combination is a series-parallel graph with [figure omitted; refer to PDF] and [figure omitted; refer to PDF] as its terminals. The graph [figure omitted; refer to PDF] obtained by identifying [figure omitted; refer to PDF] as [figure omitted; refer to PDF] and also [figure omitted; refer to PDF] as [figure omitted; refer to PDF] in the parallel combination is a series-parallel graph with [figure omitted; refer to PDF] and [figure omitted; refer to PDF] as its terminals.

Moreover, authors in [6] studied the approximate solution for EACF on two-terminal arbitrary network [figure omitted; refer to PDF] with undefined supply and demand. They also presented a fully polynomial time approximation algorithm that computes an approximate solution for EACF by reversing the direction of arcs at time zero. This solution is based on the MDCF algorithm in [2] and the approximate EAF algorithm in [14].

In special TTSP networks, we solve the CEACF problem in strongly polynomial time (cf. Section 5.1). We also establish a polynomial time algorithm that gives an approximate solution for the CEACF problem on two-terminal arbitrary networks within a factor of [figure omitted; refer to PDF] for any [figure omitted; refer to PDF] (cf. Section 5.2).

5.1. Continuous Earliest Arrival Flow on TTSP Networks

At first we reconsider Algorithm 4 in TTSP networks. It is modified by replacing Step (3) with the minimum cost circulation flow (MCCF) algorithm of [13]. The MCCF algorithm solves the MCDF problem having earliest arrival property in strongly polynomial time. We use only forward arcs to make flow in TTSP networks. Thus, every cycle in the residual networks has nonnegative cycle length. This solves the MCCF problem introduced in [11] with natural transformation of [9] for the MCDF problem in the auxiliary network [figure omitted; refer to PDF] .

Algorithm 10 (continuous time EACF on TTSP networks).

(1) In Step (3) of Algorithm 4, we run the minimum cost circulation flow algorithm of [13] with natural transformation of [9] having flow rate [figure omitted; refer to PDF] , capacity [figure omitted; refer to PDF] , and transit time [figure omitted; refer to PDF] .

(2) Obtain the continuous earliest arrival contraflow solution on TTSP networks.

The MCDCF solution obtained by Algorithm 4 does not have earliest arrival property. It is unable to find the CEACF solution with arc reversal capability. Because in the network given in Figure 1(b) there may be two orientations [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , it is hard to decide which is the best orientation in continuous time. But in series-parallel network as shown in Figure 1(a), there is not any orientation between the nodes [figure omitted; refer to PDF] and [figure omitted; refer to PDF] . Hence, Algorithm 4 could not find the CEACF solution unless the network is series-parallel. A complication of the CEACF problem arises because of the flipping requirements of such intermediate arcs with respect to the time as in discrete solution of [4].

Figure 1: (a) Series-parallel network. (b) Arbitrary network.

(a) [figure omitted; refer to PDF]

(b) [figure omitted; refer to PDF]

Algorithm 10 is feasible due to the feasibility of Algorithm 4. This algorithm computes the MCDCF solution in TTSP networks. Due to the minimum cost circulation flow algorithm of [13] with natural transformation of [9], the obtained MCDCF solution always has the earliest arrival flow property.

Theorem 11.

Algorithm 10 solves the CEACF in TTSP networks optimally.

Proof.

By creating auxiliary network [figure omitted; refer to PDF] of given network [figure omitted; refer to PDF] , we apply the MCCF algorithm of [13] that uses only forward arcs to send flow but not backward arcs. As the MCCF algorithm gives temporally repeated flow, by natural transformation of [9] as in Theorem 1, the obtained flow from Algorithm 10 is the MCDF in auxiliary network [figure omitted; refer to PDF] having earliest arrival property. By Lemma 3, the MCDF in [figure omitted; refer to PDF] is a feasible MCDCF in original network [figure omitted; refer to PDF] with earliest arrival property. As a result, the CEACF is solved in TTSP-graph.

Corollary 12.

The CEACF problem on TTSP networks can be solved in [figure omitted; refer to PDF] time complexity.

Proof.

The complexity of Algorithm 10 is dominated by MCCF algorithm of [13]. The complexity of the MCCF algorithm is [figure omitted; refer to PDF] in discrete time. By natural transformation of [9], this can be extended into continuous time that follows the result.

5.2. Approximate CEACF

As there is not any polynomial time algorithm to solve the CEACF problem on two-terminal arbitrary networks with unknown supply and demand, we discuss its approximation solution in this section. Authors in [6] have presented an polynomial approximation algorithm that obtains a discrete time flow value within [figure omitted; refer to PDF] of the EACF problem on two-terminal arbitrary networks with unknown supply and demand. Recall that Algorithm 4 does not give the CEACF solution without any modification. Thus, we present a polynomial approximate solution for the CEACF on this network.

Problem 13.

Let [figure omitted; refer to PDF] be a two-terminal network. Let [figure omitted; refer to PDF] be given. Then, the problem is to find an approximation solution for CEACF from source [figure omitted; refer to PDF] to sink [figure omitted; refer to PDF] within a factor of [figure omitted; refer to PDF] , for [figure omitted; refer to PDF] in time [figure omitted; refer to PDF] if the direction of the arcs can be reversed at time zero without any cost.

We replace Step (3) of Algorithm 4 by fully polynomial time approximate algorithm of [14] in discrete time with natural transformation of [9] into continuous time. Other steps remain as they are. Set the initial flow [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] . The algorithm of [14] combines capacity scaling with the shortest augmenting paths algorithm. In their dynamic networks, all capacities are evenly divisible by [figure omitted; refer to PDF] . Initially they obtained the static flow using shortest augmenting paths algorithm until the flow value exceeds [figure omitted; refer to PDF] where the residual capacities are rounded down to the nearest even number [figure omitted; refer to PDF] . The flow computed from each augmentation is added to a set of chain flows [figure omitted; refer to PDF] that will give the final dynamic flow. Thus, each successive phase uses the residual networks obtained from previous phase that is divisible by [figure omitted; refer to PDF] , multiple of [figure omitted; refer to PDF] , augments flow along shortest paths until the flow value of the new augmentation exceeds [figure omitted; refer to PDF] , adds the augmenting chain flows on [figure omitted; refer to PDF] , and finally rounds the residual capacities down so that they are evenly divisible by [figure omitted; refer to PDF] . This process continues until there is no augmenting path of length less than or equal to [figure omitted; refer to PDF] .

Algorithm 14 (approximate continuous earliest arrival contraflow).

(1) In Step (3) of Algorithm 4, we solve the CEAF problem on [figure omitted; refer to PDF] using fully polynomial time approximate algorithm of [14] with natural transformation of [9].

(2) Obtain [figure omitted; refer to PDF] -approximation solution of CEACF problem for the network [figure omitted; refer to PDF] .

Due to the feasibility of Algorithm 4, our algorithm, Algorithm 14, is also feasible. Now we prove the correctness of the algorithm as follows.

Theorem 15.

Algorithm 14 computes the approximation solution for the CEACF problem on two-terminal arbitrary networks efficiently.

Proof.

Recall that we first convert the given network into auxiliary network at time zero without processing cost. On the auxiliary network, we solve the [figure omitted; refer to PDF] -approximate continuous EAF problem. According to [9], the natural transformation of the approximate discrete EAF gives a continuous dynamic flow of value within [figure omitted; refer to PDF] of the CEAF for any interval. It is true for both integral [figure omitted; refer to PDF] and real [figure omitted; refer to PDF] . Thus, obtained [figure omitted; refer to PDF] -approximate CEAF on auxiliary networks is equivalent to the [figure omitted; refer to PDF] -approximation for CEACF on original networks.

Corollary 16.

Algorithm 14 computes [figure omitted; refer to PDF] -approximation for CEACF in [figure omitted; refer to PDF] time.

Proof.

As the fully polynomial time approximation algorithm for EAF of [14] requires [figure omitted; refer to PDF] time, the complexity of Algorithm 14 requires the similar complexity to compute the approximation of CEACF.

6. Conclusions

We studied the continuous dynamic flow and discrete dynamic contraflow problems. Then, we introduced continuous contraflow model for the MCDCF, QCCF, and CEACF problems with natural transformation. We presented polynomial time algorithms to solve the MCDCF and QCCF problems on two-terminal arbitrary networks with undefined supply and demand. In particular networks, that is, TTSP, we solved the CEACF problem with strongly polynomial time complexity. Moreover, in the arbitrary two-terminal networks, we presented an approximation solution for CEACF problem in polynomial time complexity.

We solved these problems with the same complexity as without contraflow but, according to discrete dynamic contraflow with natural transformation into continuous dynamic contraflow, the flow value may be doubled. In contraflow, we can transship the given flow value two times faster than without contraflow.

To the best of our knowledge, these problems we introduced are for the first time in the continuous network contraflow approach. Furthermore, we are interested to develop the continuous contraflow models and algorithms for the network flow problems in multiterminal networks with the flexibility of arc reversals at any time. Moreover, we are also interested in implementing the continuous contraflow techniques with a case study in our future work.

Acknowledgments

Tanka Nath Dhamala would like to thank Alexander von Humboldt Foundation for the research support on evacuation planning.

References

[1] S. Kim, S. Shekhar, M. Min, "Contraflow transportation network reconfiguration for evacuation route planning," IEEE Transactions on Knowledge and Data Engineering , vol. 20, no. 8, pp. 1115-1129, 2008.

[2] S. Rebennack, A. Arulselvan, L. Elefteriadou, P. M. Pardalos, "Complexity analysis for maximum flow problems with arc reversals," Journal of Combinatorial Optimization , vol. 19, no. 2, pp. 200-216, 2010.

[3] R. E. Burkard, K. Dlaska, B. Klinz, "The quickest flow problem," Zeitschrift für Operations Research , vol. 37, no. 1, pp. 31-58, 1993.

[4] T. N. Dhamala, U. Pyakurel, "Earliest arrival contraflow problem on series-parallel graphs," International Journal of Operations Research , vol. 10, no. 1, pp. 1-13, 2013.

[5] U. Pyakurel, T. N. Dhamala, "Models and algorithms on contraflow evacuation planning network problems," International Journal of Operations Research , vol. 12, no. 2, pp. 36-46, 2015.

[6] R. C. Dhungana, U. Pyakurel, S. R. Khadka, T. N. Dhamala, "Universally maximum contraflow for evacuation planning," International Journal of Operations Research , vol. 4, pp. 67-78, 2015.

[7] U. Pyakurel, T. N. Dhamala, "Evacuation planning by earliest arrival contraflow," Journal of Industrial and Management Optimization , 2015.

[8] B. Kotnyek An Annotated Overview of Dynamic Network Flows , INRIA, Sophia Antipolis, France, 2004.

[9] L. K. Fleischer, E. Tardos, "Efficient continuous-time dynamic network flow algorithms," Operations Research Letters , vol. 23, no. 3-5, pp. 71-80, 1998.

[10] F. R. Ford, D. R. Fulkerson Flows in Networks , Princeton University Press, Princeton, NJ, USA, 1962.

[11] L. R. Ford Jr., D. R. Fulkerson, "Constructing maximal dynamic flows from static flows," Operations Research , vol. 6, pp. 419-433, 1958.

[12] E. J. Anderson, P. Nash, A. B. Philpott, "A class of continuous network flow problems," Mathematics of Operations Research , vol. 7, no. 4, pp. 501-514, 1982.

[13] S. Ruzika, H. Sperber, M. Steiner, "Earliest arrival flows on series-parallel graphs," Networks , vol. 57, no. 2, pp. 169-173, 2011.

[14] B. E. Hoppe Efficient dynamic network flow algorithms [Ph.D. thesis] , Cornell University, 1995.