On solving continuous-time dynamic network flows |
| |
Authors: | S. Mehdi Hashemi Ebrahim Nasrabadi |
| |
Affiliation: | 1. Department of Computer Sciences, Amirkabir University of Technology, 424 Hafez Ave., Tehran, Iran 2. Institut f??r Mathematik, Technische Universit?t Berlin, Stra?e des 17. Juni 136, 10623, Berlin, Germany
|
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|