An Extended Continuous-time Model for Network Flows Over Time

Deutsche Forschungsgemeinschaft Technische Universität Berlin
Duration: January 2010 -
Project director: Prof. Dr. Martin Skutella
Institut für Mathematik, Technische Universität Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany.
Tel: +49 (0)30 - 314 78 654
email: skutella 'at' math.tu-berlin.de
Researcher: Ebrahim Nasrabadi
address as above
Tel: +49 (0)30 - / 314 78 650 
email: nasrabadi 'at' math.tu-berlin.de
Support: Deutsche Forschungsgemeinschaft (DFG)


Project description.

Background and Motivation.

Network flows over time (also called dynamic flows in the literature) are an interesting and challenging area of research. In contrast to classical static flows, they include a temporal dimension and consequently provide a more realistic modeling tool for a wide variety of applications. In general, there are two aspects which distinguish flows over time from static flows. Firstly, flow values on arcs are not constant but may change over time due to seasonally altering demands, supplies, and arc capacities. Secondly, flow does not travel instantaneously through a network but requires a certain amount of time to travel through each arc.

The research on network flows over time has been pursued in two different and mainly independent directions with respect to time modeling: discrete and continuous time models. In the discrete model, time is discretized into intervals of unit length, whereas in the continuous model, time is modeled as a continuum. For the case that the network parameters (e.g., costs, capacities, supplies, and demands) are independent of time and the transit times as well as the time horizon are integral, there is a one-to-one correspondence between discrete and continuous flows over time. In fact, in this case every continuous flow over time problem can be formulated as a discrete flow over time problem. But this does not remain true for the more general setting where network parameters are subject to fluctuation over time.

Both discrete and continuous models have their advantages and disadvantages. Discrete flow over time problems are considerably easier to solve computationally, but they suffer from a serious drawback: the times at which decisions are being made are fixed in advance before the problem is solved. For many applications, this is by no means a necessary feature of the problem. This is where the continuous-time model comes into play which allows decisions to be made at arbitrary points in time. Although this approach is, in theory, suitable to model various applications such as pipeline systems for transportation (e.g., the problem of pumping water through a water distribution network), it fails to capture the discrete nature of typical applications such as vehicle routing and scheduling (e.g., the scheduling of trains in a railway network).

A precise description of many real-world problems requires a combination of discrete- and continuous-time models. One such example is a crude oil distribution system. There are several methods that are used to transport crude oil: pipelines, tank trucks, railroad tank cars, barges, and tankers. Here, pumping crude oil into pipes naturally requires a continuous time model, whereas scheduling the transport of crude oil by tank trucks, railroad tank cars, barges, and tankers must be done in a discrete time model. As a consequence, it is worthwhile to capture both discrete and continuous aspects of real-world scenarios by means of only one single model. Our approach is based on measure theory. Actually, the flow on each arc can be modeled as a measure on the real line (time axis) which assigns to each suitable subset a real value, interpreted as the amount of flow entering the arc over the subset. Hence, it is natural to extend the notion of flows over time from the point of measure theory.

Research program.

The aim of this project is to generalize important parts of the theory of static network flows to the case of measure-based flows over time. In particular, we study the Minimum Cost Flow Over Time Problem (MCFOTP) where the flow on each arc is modeled as a Borel measure and storage might be permitted at the nodes of the network for later transportation. Here, flow on arcs and storage at nodes are subject to upper bounds given by Borel measures and right-continuous functions of bounded variation, respectively. There are four main ingredients in static minimum cost flows that we might hope to generalize to MCFOTP:

  1. A characterization of extreme points of the set of feasible solutions
  2. The notion of extreme points plays a central role in the theory of linear programming, specifically for the simplex algorithm. Fundamental to this algorithm is that, whenever the problem has an optimum solution, then one can be found among the extreme points of the feasible region. We can make use of techniques from functional analysis to prove that the same result remains true for MCFM under some mild assumptions. Consequently we can restrict our attention to the set of all extreme points of the feasible region when looking for an optimum feasible solution for MCFOTP and hence it is important to characterize the extreme point solutions. In the context of static network flows, extreme points of the feasible region correspond to flows which do not admit cycles, that is, the arcs with flow strictly between their bounds form a forest. We want to derive a similar characterization of the extreme points for MCFOTP.
  3. A theory of the relationship between the problem and its dual problem
  4. The concept of duality also plays a central role in the theory of linear programming and is at the heart of the network simplex algorithm for static network flows. Thus, to generalize this algorithm to solve the MCFM problem, it is necessary to establish a similar duality theory for the minimum cost flow measure problem. In this project, we want to develop a duality theory for minimum cost flow measures. In particular, we will introduce a dual problem in an analogous manner to that described for static minimum cost flows and give sufficient conditions to ensure that the strong duality result holds between MCFOTP and its dual problem.
  5. A development of network-related optimality conditions
  6. Optimality conditions form the cornerstones of static minimum cost flow algorithms. Hence it is important to develop network based optimality conditions for MCFOTP. We want to develop several network based optimality conditions analogous to that found in static network flows for MCFOTP such as a reduced cost optimality condition and a negative cycle optimality condition.
  7. A pivot step to move from any suboptimal extreme point solution to a better one
  8. One of our objectives is to develop an algorithm to move from one extreme point to another extreme point whose objective function value is no worse. As with the simplex method for static network flows, degeneracy may frequently occur here and generate some problems. Hence we will also investigate how to overcome degeneracy.

The extreme point characterization and the development of optimality conditions as well as duality theory will allow us to come up with algorithms for MCFOTP analogous to that known for the static minimum cost flow problem. Hence, we might hope to develop several solution algorithms such as a network simplex algorithm and a negative cycle-canceling algorithm for solving MCFOTP.

The initial step in developing any algorithm for solving MCFOTP is to check whether or not there exists a feasible flow over time. Moreover, if such a flow exists, then the question arises how to compute it. This can always be done by solving a maximum flow over time problem which is among the objectives of the project. We expect to achieve the following general goals for the maximum flow over time problem:

  1. Prove a MaxFlow-MinCut Theorem.
  2. Develop algorithms for computing a maximum flow over time.

We also discuss the continuous-time dynamic shortest path problem which is an extension of the static shortest path problem to networks with time-dependent arc costs. Moreover, it takes a certain amount of time to traverse an arc and waiting at a node is allowed but causes also a time-dependent cost. This problem appears as a subproblem when we want to test, via an algorithm for dynamic shortest paths, the presence of negative dynamic cycles in the residual network in order to develop network-based optimality conditions for MCFOTP. Our aim is to achieve the following general goals for the continuous-time dynamic shortest path problem:

  1. Characterizing extreme point solutions.
  2. Establishing a duality theory.
  3. Developing solution algorithms.

Publications.

[1] S. M. Hashemi, E. Nasrabadi, and M. Skutella. On solving continuous-time dynamic network flows. Technical Report 13-2008, TU Berlin, 2008.
[2] R. Koch, E. Nasrabadi, and M. Skutella. Continuous and discrete flows over time: A general model based on measure theory. Technical Report 16-2009, TU Berlin, 2009.
[3] R. Koch, E. Nasrabadi. Continuous-time dynamic shortest paths with negative transit times. Technical Report 6-2010, TU Berlin, 2010.
[4] E. Nasrabadi. Dynamic Flows in Time-Varying Networks . PhD thesis, Amirkabir University of Technology (Iran) and TU Berlin (Germany), 2009.