Temporally Repeated Maximum Dynamic Flow with Intermediate Storage

Durga Prasad Khanal (), Urmila Pyakurel () and Stephan Dempe ()
Additional contact information
Durga Prasad Khanal: Tribhuvan University
Urmila Pyakurel: Tribhuvan University
Stephan Dempe: TU Bergakademie Freiberg

SN Operations Research Forum, 2025, vol. 6, issue 3, 1-27

Abstract: Abstract The maximum dynamic flow problem intends to send the maximum amount of flow from a fixed node (source) to another fixed node (sink/destination) within the given time horizon. The storage of flow at intermediate shelters that do not reach the destination for some reason is one of the important issues in the network flow problem. Similarly, in the case of a two-way network, flow improvement by reversing the direction of arcs towards the destination is another widely accepted technique. Flow with intermediate storage and contraflow are very relevant issues for the evacuation planning, which can shift the maximum number of evacuees from danger zones to safe places. In this paper, we introduce a novel technique of temporally repeated flow to solve the maximum dynamic flow problem with intermediate storage for general network topology. We present a polynomial time algorithm to solve the problem. We discuss the earliest arrival flow problem with intermediate storage and its solution procedure on the series-parallel graph by holding the excess flow at intermediate nodes. We also introduce a maximum dynamic contraflow problem with intermediate storage and solve the problem by using temporal repetition of flows in polynomial time. We extend these problems in continuous time settings by using natural transformation. For the case illustration, we apply our algorithm to find maximum flow with intermediate storage using Python codes by taking the data of the Kathmandu road network.

Keywords: Maximum flow; Intermediate storage; Earliest arrival flow; Temporally repeated flow; Contraflow (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s43069-025-00474-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:snopef:v:6:y:2025:i:3:d:10.1007_s43069-025-00474-5

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/43069

DOI: 10.1007/s43069-025-00474-5

Access Statistics for this article

SN Operations Research Forum is currently edited by Marco Lübbecke

More articles in SN Operations Research Forum from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().