Efficient contraflow algorithms for quickest evacuation planning

The optimization models and algorithms with their implementations on flow over time problems have been an emerging field of research because of largely increasing human-created and natural disasters worldwide. For an optimal use of transportation network to shift affected people and normalize the disastrous situation as quickly and Efficiently as possible, contraflow configuration is one of the highly applicable operations research (OR) models. It increases the outbound road capacities by reversing the direction of arcs towards the safe destinations that not only minimize the congestion and increase the flow but also decrease the evacuation time significantly. In this paper, we sketch the state of quickest flow solutions and solve the quickest contraflow problem with constant transit times on arcs proving that the problem can be solved in strongly polynomial time O(nm²(log n)²), where n and m are number of nodes and number of arcs, respectively in the network. This contraflow solution has the same computational time bound as that of the best min-cost flow solution. Moreover, we also introduce the contraflow approach with load dependent transit times on arcs and present an Efficient algorithm to solve the quickest contraflow problem approximately. Supporting the claim, our computational experiments on Kathmandu road network and on randomly generated instances perform very well matching the theoretical results. For sufficiently large number of evacuees, about double flow can be shifted with the same evacuation time and about half time is sufficient to push the given flow value with contraflow reconfiguration.     

Locating Active Sensors on Traffic Networks

Sensors are used to monitor traffic in networks. For example, in transportation networks, they may be used to measure traffic volumes on given arcs and paths of the network. This paper refers to an active sensor when it reads identifications of vehicles, including their routes in the network, that the vehicles actively provide when they use the network. On the other hand, the conventional inductance loop detectors are passive sensors that mostly count vehicles at points in a network to obtain traffic volumes (e.g., vehicles per hour) on a lane or road of the network.This paper introduces a new set of network location problems that determine where to locate active sensors in order to monitor or manage particular classes of identified traffic streams. In particular, it focuses on the development of two generic locational decision models for active sensors, which seek to answer these questions: (1) “How many and where should such sensors be located to obtain sufficient information on flow volumes on specified paths?”, and (2) “Given that the traffic management planners have already located count detectors on some network arcs, how many and where should active sensors be located to get the maximum information on flow volumes on specified paths?”The problem is formulated and analyzed for three different scenarios depending on whether there are already count detectors on arcs and if so, whether all the arcs or a fraction of them have them. Location of an active sensor results in a set of linear equations in path flow variables, whose solution provide the path flows. The general problem, which is related to the set-covering problem, is shown to be NP-Hard, but special cases are devised, where an arc may carry only two routes, that are shown to be polynomially solvable. New graph theoretic models and theorems are obtained for the latter cases, including the introduction of the generalized edge-covering by nodes problem on the path intersection graph for these special cases. An exact algorithm for the special cases and an approximate one for the general case are presented.     

Concave cost minimization on networks

The paper deals with the problem of finding a minimum cost multicommodity flow on an uncapacitated network with concave link costs. Problems of this type are the optimal design of a network in the presence of scale economies and the telpack problem.Two different definitions of local optimality are given and compared both from the point of view of the computational complexity and from the point of view of the goodness of the solution they may provide.A vertex following algorithm to find a local optimum is proposed. The computational complexity of each iteration of the algorithm is O(n³), where n is the number of nodes of the network, and is independent of the differentiability of the objective function.Experimental results obtained from a set of test problems of size ranging from 11 nodes and 23 arcs to 48 nodes and 174 arcs, with number of commodities up to 5, are given.     

Algorithms for the quickest path problem and the reliable quickest path problem

The quickest path problem consists of finding a path in a directed network to transmit a given amount of items from an origin node to a destination node with minimal transmission time, when the transmission time depends on both the traversal times of the arcs, or lead time, and the rates of flow along arcs, or capacity. In telecommunications networks, arcs often also have an associated operational probability of the transmission being fault free. The reliability of a path is defined as the product of the operational probabilities of its arcs. The reliability as well as the transmission time are of interest. In this paper, algorithms are proposed to solve the quickest path problem as well as the problem of identifying the quickest path whose reliability is not lower than a given threshold. The algorithms rely on both the properties of a network which turns the computation of a quickest path into the computation of a shortest path and the fact that the reliability of a path can be evaluated through the reliability of the ordered sequence of its arcs. Other constraints on resources consumed, on the number of arcs of the path, etc. can also be managed with the same algorithms.     

Network simplex algorithm for the general equal flow problem

In this paper the general equal flow problem is considered. This is a minimum cost network flow problem with additional side constraints requiring the flow of arcs in some given sets of arcs to take on the same value. This model can be applied to approach water resource system management problems or multiperiod logistic problems in general involving policy restrictions which require some arcs to carry the same amount of flow through the given study period. Although the bases of the general equal flow problem are no longer spanning trees, it is possible to recognize a similar structure that allows us to take advantage of the practical computational capabilities of network models. After characterizing the bases of the problem as good (r+1)-forests, a simplex primal algorithm is developed that exploits the network structure of the problem and requires only slight modifications of the well-known network simplex algorithm.     

A new method for constructing a minimal PERT network

A project is an enterprise consisting of several activities which are to be carried out in some specific order. The activities and the order in which they need to be carried out can be represented by a PERT network. The PERT technique is a traditional, well-known approach to the expert of project management. When networks are used, it often becomes necessary to draw dummy activities. Since the computation of project completion time is proportional to the number of arcs, including dummy arcs, it is desirable to draw a network with as few dummy activities as possible.In this paper, we propose a new method for constructing, for a given project scheduling problem, a PERT network having as small as possible the number of dummy arcs by using some results on line graphs. This algorithm deals with the existence of transitive arcs. The paper contains illustrative examples, proofs of some theoretical results as well as a comparative study with a similar algorithm known in the literature. Computational results showed the superiority of our algorithm.     

Generate upper boundary vectors meeting the demand and budget for a p-commodity network with unreliable nodes

The system capacity for a single-commodity flow network is the maximum flow from the source to the sink. This paper discusses the system capacity problem for a p-commodity limited-flow network with unreliable nodes. In such a network, arcs and nodes all have several possible capacities and may fail. Different types of commodity, which are transmitted through the same network simultaneously, competes the capacities of arcs and nodes. In particular, the consumed capacity by different types of commodity varies from arcs and nodes. We first define the system capacity as a vector and then a performance index, the probability that the upper bound of the system capacity is a given pattern subject to the budget constraint, is proposed. Such a performance index can be easily computed in terms of upper boundary vectors meeting the demand and budget. A simple algorithm based on minimal cuts is thus presented to generate all upper boundary vectors. The manager can apply this performance index to measure the system capacity level for a supply-demand system.     

Influence Digraphs Induced by Time-Stamped Graphs (Extended Abstract)

A time-stamped graph is an undirected graph with a real number on each edge. Vertex u influences vertex v if there is an increasing path from u to v. The induced influence digraph of a time-stamped graph is the directed graph that records the influences. In this paper we study the realizability problem: Given a parameter value, does there exist a time-stamped graph whose induced influence digraph has the given parameter value? In particular, we solve this problem when the parameter is the number of arcs. Moreover, if the candidates for the time-stamped graphs are restricted to trees, then every realizable value can be achieved by a tree homeomorphic to K₂ or K_1,3. A number of other questions are also explored. The full version of this paper is submitted to a referreed journal.     

Space-time tradeoffs in negative cycle detection - An empirical analysis of the Stressing Algorithm

This paper discusses space-time tradeoffs associated with algorithms for the problem of detecting negative cost cycles in networks (NCCD). NCCD is one of the more ubiquitous problems in computer science and operations research, with applications ranging from program verification and real-time scheduling to image segmentation and shortest path identification. Typical algorithmic analysis, whether theoretical or empirical, focuses almost exclusively on the running time of the algorithm. However, there exist applications in which space is just as important a parameter as time is. This is especially true when the problem instances are very large, as is the case in program verification. Consequently, an algorithm that minimizes running time while ignoring the space overhead may be impractical. In this paper, we analyze a number of the more common algorithms for NCCD from the perspectives of both time and space, with a view towards providing a space-time tradeoff for the practitioner. All the algorithms discussed in this paper (with the exception of Network Simplex) run in O(m·n) time on a network with m arcs and n vertices; however, their space requirements range from O(1) (Stressing Algorithm) to Ω(n) (all the Bellman-Ford and Network Simplex variants). Our empirical results demonstrate that in the cases where space is paramount, the Stressing Algorithm is a useful alternative to the Bellman-Ford variants.     

A compact hash function for paths in PERT networks

This paper presents a method of identifying all directed paths from the source to the sink (called ‘paths’ in this paper) in a directed acyclic network with one source and one sink. Let L be the set of all the paths in this network and N = |L|. A hash function H:L → {0, 1, …, N ? 1} is constructed having the following properties: it is one-to-one and onto, the algorithms to compute H and its inverse are linea in the number of arcs in the network, it has the smallest possible range and produces no collisions. All these properties make it a very useful hash function in writing computer programs which involve storing information about all paths in the network. The techniques described in this paper can be used to construct hash functions for walks in cyclic graphs. An application to simulation of stochastic networks is described and an illustrative example is included.     

On solving continuous-time dynamic network flows

Temporal dynamics is a crucial feature of network flow problems occurring in many practical applications. Important characteristics of real-world networks such as arc capacities, transit times, transit and storage costs, demands and supplies etc. are subject to fluctuations over time. Consequently, also flow on arcs can change over time which leads to so-called dynamic network flows. While time is a continuous entity by nature, discrete-time models are often used for modeling dynamic network flows as the resulting problems are in general much easier to handle computationally. In this paper, we study a general class of dynamic network flow problems in the continuous-time model, where the input functions are assumed to be piecewise linear or piecewise constant. We give two discrete approximations of the problem by dividing the considered time range into intervals where all parameters are constant or linear. We then present two algorithms that compute, or at least converge to optimum solutions. Finally, we give an empirical analysis of the performance of both algorithms.     

Optimal expansion of capacitated transshipment networks

In this paper, we address the problem of allocating a given budget to increase the capacities of arcs in a transshipment network to minimize the cost of flow in the network. The capacity expansion costs of arcs are assumed to be piecewise linear convex functions. We use properties of the optimum solution to convert this problem into a parametric network flow problem. The concept of optimum basis structure is used which allows us to consider piecewise linear convex functions without introducing additional arcs. The resulting algorithm yields an optimum solution of the capacity expansion problem for all budget levels less than or equal to the given budget. For integer data, the algorithm performs almost all computations in integers. Detailed computational results are also presented.     

Inverse minimum cost flow problems under the weighted Hamming distance

Given a network N(V, A, u, c) and a feasible flow x⁰, an inverse minimum cost flow problem is to modify the cost vector as little as possible to make x⁰ form a minimum cost flow of the network. The modification can be measured by different norms. In this paper, we consider the inverse minimum cost flow problems, where the modification of the arcs is measured by the weighted Hamming distance. Both the sum-type and the bottleneck-type cases are considered. For the former, it is shown to be APX-hard due to the weighted feedback arc set problem. For the latter, we present a strongly polynomial algorithm which can be done in O(n · m²).     

The fleet size and mix problem for capacitated arc routing

There have been several attempts to solve the capacitated arc routing problem with m vehicles starting their tours from a central node. The objective has been to minimize the total distance travelled. In the problem treated here we also have the fixed costs of the vehicles included in the objective function. A set of vehicle capacities with their respective costs are used. Thus the objective function becomes a combination of fixed and variable costs. The solution procedure consists of four phases. In the first phase, a Chinese or rural postman problem is solved depending on whether all or some of the arcs in the network demand service with the objective of minimizing the total distance travelled. It results in a tour called the giant tour. In the second phase, the giant tour is partitioned into single vehicle subtours feasible with respect to the constraints. A new network is constructed with the node set corresponding to the arcs of the giant tour and with the arc set consisting of the subtours of the giant tour. The arc costs include both the fixed and variable costs of the subtours. The third phase consists of solving the shortest path problem on this new network to result in the least cost set of subtours represented on the new network. In the last phase a postprocessor is applied to the solution to improve it. The procedure is repeated for different giant tours to improve the final solution. The problem is extended to the case where there can be upper bounds on the number of vehicles with given capacities using a branch and bound method. Extension to directed networks is given. Some computational results are reported.     

Primitive non-powerful symmetric loop-free signed digraphs with given base and minimum number of arcs

In [B.M. Kim, B.C. Song, W. Hwang, Primitive graphs with given exponents and minimum number of edges, Linear Algebra Appl. 420 (2007) 648-662], the minimum number of edges of a simple graph on n vertices with exponent k was determined. In this paper, we completely determine the minimum number, H(n,k), of arcs of primitive non-powerful symmetric loop-free signed digraphs on n vertices with base k, characterize the underlying digraphs which have H(n,k) arcs when k is 2, nearly characterize the case when k is 3 and propose an open problem.     

The convex hull of two core capacitated network design problems

The network loading problem (NLP) is a specialized capacitated network design problem in which prescribed point-to-point demand between various pairs of nodes of a network must be met by installing (loading) a capacitated facility. We can load any number of units of the facility on each of the arcs at a specified arc dependent cost. The problem is to determine the number of facilities to be loaded on the arcs that will satisfy the given demand at minimum cost.This paper studies two core subproblems of the NLP. The first problem, motivated by a Lagrangian relaxation approach for solving the problem, considers a multiple commodity, single arc capacitated network design problem. The second problem is a three node network; this specialized network arises in larger networks if we aggregate nodes. In both cases, we develop families of facets and completely characterize the convex hull of feasible solutions to the integer programming formulation of the problems. These results in turn strengthen the formulation of the NLP.Research of this author was supported in part by a Faculty Grant from the Katz Graduate School of Business, University of Pittsburgh.     

The multi-terminal maximum-flow network-interdiction problem

This paper defines and studies the multi-terminal maximum-flow network-interdiction problem (MTNIP) in which a network user attempts to maximize flow in a network among K ? 3 pre-specified node groups while an interdictor uses limited resources to interdict network arcs to minimize this maximum flow. The paper proposes an exact (MTNIP-E) and an approximating model (MPNIM) to solve this NP-hard problem and presents computational results to compare the models. MTNIP-E is obtained by first formulating MTNIP as bi-level min-max program and then converting it into a mixed integer program where the flow is explicitly minimized. MPNIM is binary-integer program that does not minimize the flow directly. It partitions the node set into disjoint subsets such that each node group is in a different subset and minimizes the sum of the arc capacities crossing between different subsets. Computational results show that MPNIM can solve all instances in a few seconds while MTNIP-E cannot solve about one third of the problems in 24 hour. The optimal objective function values of both models are equal to each other for some problems while they differ from each other as much as 46.2% in the worst case. However, when the post-interdiction flow capacity incurred by the solution of MPNIM is computed and compared to the objective value of MTNIP-E, the largest difference is only 7.90% implying that MPNIM may be a very good approximation to MTNIP-E.     

Maximization Problems in Single Machine Scheduling

Problems of scheduling n jobs on a single machine to maximize regular objective functions are studied. Precedence constraints may be given on the set of jobs and the jobs may have different release times. Schedules of interest are only those for which the jobs cannot be shifted to start earlier without changing job sequence or violating release times or precedence constraints. Solutions to the maximization problems provide an information about how poorly such schedules can perform. The most general problem of maximizing maximum cost is shown to be reducible to n similar problems of scheduling n?1 jobs available at the same time. It is solved in O(mn+n ²) time, where m is the number of arcs in the precedence graph. When all release times are equal to zero, the problem of maximizing the total weighted completion time or the weighted number of late jobs is equivalent to its minimization counterpart with precedence constraints reversed with respect to the original ones. If there are no precedence constraints, the problem of maximizing arbitrary regular function reduces to n similar problems of scheduling n?1 jobs available at the same time.     

The tricriterion shortest path problem with at least two bottleneck objective functions

The focus of this paper is on the tricriterion shortest path problem where two objective functions are of the bottleneck type, for example MinMax or MaxMin. The third objective function may be of the same kind or we may consider, for example, MinSum or MaxProd. Let p(n) be the complexity of a classical single objective algorithm responsible for this third function, where n is the number of nodes and m be the number of arcs of the graph. An O(m²p(n)) algorithm is presented that can generate the minimal complete set of Pareto-optimal solutions. Finding the maximal complete set is also possible. Optimality proofs are given and extensions for several special cases are presented. Computational experience for a set of randomly generated problems is reported.     

An efficient algorithm for the evacuation problem in a certain class of networks with uniform path-lengths

In this paper, we consider the evacuation problem in a network which consists of a directed graph with capacities and transit times on its arcs. This problem can be solved by the algorithm of Hoppe and Tardos [B. Hoppe, É. Tardos, The quickest transshipment problem, Math. Oper. Res. 25(1) (2000) 36–62] in polynomial time. However their running time is high-order polynomial, and hence is not practical in general. Thus, it is necessary to devise a faster algorithm for a tractable and practically useful subclass of this problem. In this paper, we consider a network with a sink s such that (i) for each vertex v≠s the sum of the transit times of arcs on any path from v to s takes the same value, and (ii) for each vertex v≠s the minimum v-s cut is determined by the arcs incident to s whose tails are reachable from v. This class of networks is a generalization of grid networks studied in the paper [N. Kamiyama, N. Katoh, A. Takizawa, An efficient algorithm for evacuation problem in dynamic network flows with uniform arc capacity, IEICE Trans. Infrom. Syst. E89-D (8) (2006) 2372–2379]. We propose an efficient algorithm for this network problem.