Network Flow with Intermediate Storage: Models and Algorithms
- PDF / 2,309,595 Bytes
- 23 Pages / 439.642 x 666.49 pts Page_size
- 119 Downloads / 197 Views
Network Flow with Intermediate Storage: Models and Algorithms Urmila Pyakurel1
· Stephan Dempe2
Received: 31 March 2020 / Accepted: 2 October 2020 / Published online: 17 November 2020 © Springer Nature Switzerland AG 2020
Abstract Various network flow models, such as a flow maximization, a time minimization, a cost minimization, or a combination of them, have already been investigated. In most of the cases, they are considered subject to the flow conservation constraints. Here, we investigate the network flow models with intermediate storage, i.e., the inflow may be greater than the outflow at intermediate nodes. We introduce a maximum static and a maximum dynamic flow problem where an intermediate storage is allowed. Then, polynomial time algorithms are presented to solve these problems in two terminal general networks. We also study the earliest arrival property of the maximum dynamic flow in two terminal series-parallel networks and present its efficient solution procedure with intermediate storage. Moreover, we introduce a dynamic contraflow model with intermediate storage and present a polynomial time algorithm to solve the maximum dynamic contraflow problem in two terminal networks. We also solve an earliest arrival contraflow problem with intermediate storage. Our investigation is focused to solve the evacuation planning problem where the intermediate storage is permitted. Keywords Network flow · Intermediate storage · Algorithms · Contraflow · Evacuation planning
1 Introduction The contributions in network flow models for last six decades can be found very interesting and important to solve many real-life problems. Ford and Fulkerson [12] introduced a network flow model to solve the maximum dynamic flow problem
Urmila Pyakurel
[email protected] 1
Central Department of Mathematics, Tribhuvan University, P.O.Box 13143, Kathmandu, Nepal
2
Fakult¨at f¨ur Mathematik und Informatik, TU Bergakademie Freiberg, Freiberg, Germany
37
Page 2 of 23
SN Operations Research Forum (2020) 1: 37
(MDFP), where the flow value leaving a source and entering a sink is maximized within a given time horizon without intermediate storage. If the flow is maximized at every time point, then a solution to the earliest arrival flow problem (EAFP) is obtained [13]. Wilkinson [33] solved the EAFP in a two terminal network by computing a maximum flow–minimum cut on its time-expanded network. Minieka [20] also solved the EAFP presenting a pseudo-polynomial time algorithm that computes the successive shortest paths as in Ford and Fulkerson [12] on the residual network and shifts flow along the paths in temporally repeated way. If the flow is maximized according to a given priority ordering of sources and sinks, then a lexicographically maximum flow problem arises. Minieka [20] introduced the lex-max static flow problem (LMSFP) and presented a polynomial time algorithm to solve it. Hoppe and Tardos [15] modeled the evacuation problems as flow problems in dynamic networks. They presented a polynomial time algorithm to solv
Data Loading...
