Rights statement: The final publication is available at Springer via http://dx.doi.org/ 10.1007/s13675-016-0067-x
Accepted author manuscript, 2.58 MB, PDF document
Available under license: CC BY-NC: Creative Commons Attribution-NonCommercial 4.0 International License
Final published version
Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - Robust flows with losses and improvability in evacuation planning
AU - Goerigk, Marc
AU - Ndiaye, Ismaila Abderhamane
N1 - The final publication is available at Springer via http://dx.doi.org/ 10.1007/s13675-016-0067-x
PY - 2016/9
Y1 - 2016/9
N2 - We consider a network flow problem, where the outgoing flow is reduced by a certain percentage in each node. Given a maximum amount of flow that can leave the source node, the aim is to find a solution that maximizes the amount of flow which arrives at the sink. Starting from this basic model, we include two new, additional aspects: On the one hand, we are able to reduce the loss at some of the nodes; on the other hand, the exact loss values are not known, but may come from a discrete uncertainty set of exponential size. Applications for problems of this type can be found in evacuation planning, where one would like to improve the safety of nodes such that the number of evacuees reaching safety is maximized. We formulate the resulting robust flow problem with losses and improvability as a two-stage mixed-integer program with uncertain recourse for finitely many scenarios and present an iterative scenario-generation procedure that avoids the inclusion of all scenarios from the beginning as well as several heuristic solution methods. In a computational study using both randomly generated instances and realistic data based on the city of Nice, France, we compare our solution algorithms.
AB - We consider a network flow problem, where the outgoing flow is reduced by a certain percentage in each node. Given a maximum amount of flow that can leave the source node, the aim is to find a solution that maximizes the amount of flow which arrives at the sink. Starting from this basic model, we include two new, additional aspects: On the one hand, we are able to reduce the loss at some of the nodes; on the other hand, the exact loss values are not known, but may come from a discrete uncertainty set of exponential size. Applications for problems of this type can be found in evacuation planning, where one would like to improve the safety of nodes such that the number of evacuees reaching safety is maximized. We formulate the resulting robust flow problem with losses and improvability as a two-stage mixed-integer program with uncertain recourse for finitely many scenarios and present an iterative scenario-generation procedure that avoids the inclusion of all scenarios from the beginning as well as several heuristic solution methods. In a computational study using both randomly generated instances and realistic data based on the city of Nice, France, we compare our solution algorithms.
KW - Network flow
KW - Flow with losses
KW - Robust optimization
KW - Adjustable robustness
KW - Random recourse
KW - Network design
U2 - 10.1007/s13675-016-0067-x
DO - 10.1007/s13675-016-0067-x
M3 - Journal article
VL - 4
SP - 241
EP - 270
JO - EURO Journal on Computational Optimization
JF - EURO Journal on Computational Optimization
SN - 2192-4406
IS - 3-4
ER -