Robust flows with losses and improvability in evacuation planning

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 in...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Marc Goerigk, IsmailaAbderhamane Ndiaye
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2016
Materias:	90B15 90B80 90C15 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/5b3cb303da874f5f8f615a22b27ac479
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:5b3cb303da874f5f8f615a22b27ac479
record_format	dspace
spelling	oai:doaj.org-article:5b3cb303da874f5f8f615a22b27ac4792021-12-02T05:00:54ZRobust flows with losses and improvability in evacuation planning2192-440610.1007/s13675-016-0067-xhttps://doaj.org/article/5b3cb303da874f5f8f615a22b27ac4792016-09-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621000642https://doaj.org/toc/2192-4406We 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.Marc GoerigkIsmailaAbderhamane NdiayeElsevierarticle90B1590B8090C15Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 4, Iss 3, Pp 241-270 (2016)
institution	DOAJ
collection	DOAJ
language	EN
topic	90B15 90B80 90C15 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	90B15 90B80 90C15 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Marc Goerigk IsmailaAbderhamane Ndiaye Robust flows with losses and improvability in evacuation planning
description	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.
format	article
author	Marc Goerigk IsmailaAbderhamane Ndiaye
author_facet	Marc Goerigk IsmailaAbderhamane Ndiaye
author_sort	Marc Goerigk
title	Robust flows with losses and improvability in evacuation planning
title_short	Robust flows with losses and improvability in evacuation planning
title_full	Robust flows with losses and improvability in evacuation planning
title_fullStr	Robust flows with losses and improvability in evacuation planning
title_full_unstemmed	Robust flows with losses and improvability in evacuation planning
title_sort	robust flows with losses and improvability in evacuation planning
publisher	Elsevier
publishDate	2016
url	https://doaj.org/article/5b3cb303da874f5f8f615a22b27ac479
work_keys_str_mv	AT marcgoerigk robustflowswithlossesandimprovabilityinevacuationplanning AT ismailaabderhamanendiaye robustflowswithlossesandimprovabilityinevacuationplanning
_version_	1718400829503832064

Robust flows with losses and improvability in evacuation planning

Ejemplares similares