Previous Article in event
Previous Article in session
Next Article in event
Next Article in session
Flows on Network with Intermediate Storage Capability: Evacuation Planning Perspective
Published:
20 September 2021
by MDPI
in The 1st Online Conference on Algorithms
session Combinatorial Optimization, Graph and Network Algorithms
https://doi.org/10.3390/IOCA2021-10883
(registering DOI)
Abstract:
Optimization models for evacuation with capability of holding evacuees at intermediate places are of particular interest when all the evacuees cannot be sent to the safe destination. We study the maximum flow evacuation planning problem that aims to lexicographically maximize the evacuees entering a set of capacitated terminals, sink and intermediate vertices, with respect to a given prioritization.
We propose a polynomial time algorithm for the problem modeled on uniform path length (UPL) network. We also apply this algorithm to solve quickest flow evacuation planning problem that lexicographically minimizes the time required to fulfill the demand of evacuees at such terminals. Moreover, we show that the algorithm solves an earliest arrival version of the problem with sufficient vertex capacities for uniform path length two terminal series parallel (UPL-TTSP) network.
Keywords: TTSP network; Uniform path length network; Lexicographically maximum flows; Evacuation planning problem
Comments on this paper
Urmila Pyakurel
7 October 2021
With respect to this paper, I have following comments:
1. Is the intermediate storage always possible ? Is there any necessary condition for the problem ? I would like to suggest the following papers for the clear messages.
-- https://tu-freiberg.de/sites/default/files/media/fakultaet-fuer-mathematik-und-informatik-fakultaet-1-9277/prep/2019-01_fertig.pdf
https://link.springer.com/article/10.1007/s43069-020-00033-0
https://link.springer.com/chapter/10.1007%2F978-3-030-64973-9_14
https://www.hindawi.com/journals/mpe/2021/5063207/
-- http://www.optimization-online.org/DB_HTML/2020/07/7891.html
All the above papers solve the network flow problems with intermediate storage on general two terminal as well as multi-terminal networks (for single commodity and multi-commodity flow problems) with given sufficient node capacities in which priority orderings have not been given but need to find. Moreover, their complexities are polynomial. With respect to the literature, I would like to know the major contributions of this paper. However, there is simple solutions of particular cases.
2. If the priority of nodes are given, than what is the difference than the network considered by authors [ References 17,18]?
1. Is the intermediate storage always possible ? Is there any necessary condition for the problem ? I would like to suggest the following papers for the clear messages.
-- https://tu-freiberg.de/sites/default/files/media/fakultaet-fuer-mathematik-und-informatik-fakultaet-1-9277/prep/2019-01_fertig.pdf
https://link.springer.com/article/10.1007/s43069-020-00033-0
https://link.springer.com/chapter/10.1007%2F978-3-030-64973-9_14
https://www.hindawi.com/journals/mpe/2021/5063207/
-- http://www.optimization-online.org/DB_HTML/2020/07/7891.html
All the above papers solve the network flow problems with intermediate storage on general two terminal as well as multi-terminal networks (for single commodity and multi-commodity flow problems) with given sufficient node capacities in which priority orderings have not been given but need to find. Moreover, their complexities are polynomial. With respect to the literature, I would like to know the major contributions of this paper. However, there is simple solutions of particular cases.
2. If the priority of nodes are given, than what is the difference than the network considered by authors [ References 17,18]?
Phanindra Prasad Bhandari
8 October 2021
Thank you for your concern on our work.
The storage of flow units at intermediate vertex depends upon the network structure, time horizon, etc. We don’t think there is any necessary condition to exist the problem.
Authors in [17, 18] do not consider the fixed vertex capacities. You also realize (….with given sufficient node capacities…..) in your comment that the works mentioned with links do not consider the fixed vertex capacities at intermediate vertices. However, we do . For general network with fixed vertex capacities, flow computed by TRFs for some vertices
The storage of flow units at intermediate vertex depends upon the network structure, time horizon, etc. We don’t think there is any necessary condition to exist the problem.
Authors in [17, 18] do not consider the fixed vertex capacities. You also realize (….with given sufficient node capacities…..) in your comment that the works mentioned with links do not consider the fixed vertex capacities at intermediate vertices. However, we do . For general network with fixed vertex capacities, flow computed by TRFs for some vertices
Urmila Pyakurel
8 October 2021
If the outgoing capacities of a network structure from the sources have less than the capacities of incoming arcs to the sinks, then I would like to know what how much flow will be at intermediate nodes?
Phanindra Prasad Bhandari
8 October 2021
Depends upon network structure--capacities of the arcs which do not link the source or sink.
Urmila Pyakurel
8 October 2021
In other words, if the outgoing arc capacity from source is less than the minimum cut capacity of the netwrok, what will be the amount of flow at intermediate nodes? Is the fixed node capacities of your network structures can hold flow there?
Urmila Pyakurel
8 October 2021
For your kind information, please visit slides number 27-29 in the following link which was discussed at 2012. (I know, the slides are immature but the concept, when the intermediate storage will be possible, was discussed there).
https://www.researchgate.net/publication/342654764_Contraflow_Emergency_Evacuation_by_Earliest_Arrival_Flow
Thank you for our answer but please visit the literature also.
https://www.researchgate.net/publication/342654764_Contraflow_Emergency_Evacuation_by_Earliest_Arrival_Flow
Thank you for our answer but please visit the literature also.
Phanindra Prasad Bhandari
8 October 2021
1. We do not find any matching with the results (neither model of problem) with the work (slides presented in an office) you mentioned.
2. There are some other publications exploring the concept of holding flows at intermediate vertices years before the work (slides presented in an office) you mentioned was made public on July 3, 2020.
3. We hope no one kills someone’s precious time unnecessarily.
2. There are some other publications exploring the concept of holding flows at intermediate vertices years before the work (slides presented in an office) you mentioned was made public on July 3, 2020.
3. We hope no one kills someone’s precious time unnecessarily.
Urmila Pyakurel
8 October 2021
Correction to the previous comment
In other words, if the outgoing arc capacity from source is equal the minimum cut capacity of the network, what will be the amount of flow at intermediate nodes? Is the fixed node capacities of your network structures can hold flow there?
In other words, if the outgoing arc capacity from source is equal the minimum cut capacity of the network, what will be the amount of flow at intermediate nodes? Is the fixed node capacities of your network structures can hold flow there?
Urmila Pyakurel
8 October 2021
1. I am very sorry if I am killing your precious time Dr. Bhandari. But it is necessary to be clear because your work is in public now. As a reader, it is my right to ask you questions.
2. Your contribution is meaningless if the outgoing arc capacity from source is equal the minimum cut capacity of the network because all flows will reach to the sink i.e., similar to maximum flow theory of Ford and Fulkerson 1956. If you can hold please show your answer.
3. If there are already some papers dealing network flow problem with intermediate storage, why you did not mention in your reference ?
4. All the publications mentioned in previous links were published before this conference paper for your kind information.
Thank you very much
2. Your contribution is meaningless if the outgoing arc capacity from source is equal the minimum cut capacity of the network because all flows will reach to the sink i.e., similar to maximum flow theory of Ford and Fulkerson 1956. If you can hold please show your answer.
3. If there are already some papers dealing network flow problem with intermediate storage, why you did not mention in your reference ?
4. All the publications mentioned in previous links were published before this conference paper for your kind information.
Thank you very much
Phanindra Prasad Bhandari
8 October 2021
Extended set of paths mentioned in paper is for the situations like you pointed out.
Discussions on the subject matter are welcome.
Discussions on the subject matter are welcome.
