Connectivity after disasters has become a critical problem in the management of modern cities. This comes from the need of the decision-makers to ensure urgent medical attention by providing access to health facilities and to other relevant services needed by the population. Managing congestion could help maintain some routes operative even in complex scenarios such as natural disasters, terrorist attacks, protests, or riots. Recent advances in Humanitarian Logistics have handled this problem using different modeling approaches but have principally focused on the response phase. In this paper, firstly, we propose a penalized variant of an existing mathematical model for the robust s–t path problem with investments. With the aim of solving the robust several-to-one path problem with investments, and due to the high complexity of this new problem, a heuristic is proposed. Moreover, this approach allows us to improve travel times in both specific paths and in a set of routes in a systemic framework. The new problem and the proposed heuristic are illustrated by an example, which corresponds to a typical city network, that provides a concrete vision of the potential application of the framework. Lastly, some managerial insights are given by the analysis of results exhibited in the example network.
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2021086
Keywords: Traffic network design, humanitarian logistics, robust optimization, minmax regret path problem with investments, travel times, critical links
@article{RO_2021__55_3_1865_0,
author = {P\'erez-Galarce, Francisco and Candia-V\'ejar, Alfredo and Maculan, Guido and Maculan, Nelson},
title = {Improved robust shortest paths by penalized investments},
journal = {RAIRO. Operations Research},
pages = {1865--1883},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
number = {3},
doi = {10.1051/ro/2021086},
mrnumber = {4275486},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2021086/}
}
TY - JOUR AU - Pérez-Galarce, Francisco AU - Candia-Véjar, Alfredo AU - Maculan, Guido AU - Maculan, Nelson TI - Improved robust shortest paths by penalized investments JO - RAIRO. Operations Research PY - 2021 SP - 1865 EP - 1883 VL - 55 IS - 3 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2021086/ DO - 10.1051/ro/2021086 LA - en ID - RO_2021__55_3_1865_0 ER -
%0 Journal Article %A Pérez-Galarce, Francisco %A Candia-Véjar, Alfredo %A Maculan, Guido %A Maculan, Nelson %T Improved robust shortest paths by penalized investments %J RAIRO. Operations Research %D 2021 %P 1865-1883 %V 55 %N 3 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2021086/ %R 10.1051/ro/2021086 %G en %F RO_2021__55_3_1865_0
Pérez-Galarce, Francisco; Candia-Véjar, Alfredo; Maculan, Guido; Maculan, Nelson. Improved robust shortest paths by penalized investments. RAIRO. Operations Research, Tome 55 (2021) no. 3, pp. 1865-1883. doi: 10.1051/ro/2021086
[1] , and , Humanitarian supply chain performance management: a systematic literature review. Supply Chain Manage. Int. J. 19 (2014) 592–608. | DOI
[2] , and , A humanitarian logistics model for disaster relief operation considering network failure and standard relief time: a case study on San Francisco district. Transp. Res. Part E: Logist. Transp. Rev. 75 (2015) 145–163. | DOI
[3] , and , A survey of healthcare facility location. Comput. Oper. Res. 79 (2017) 223–263. | MR | DOI
[4] , and , Min-max and min-max regret versions of combinatorial optimization problems: a survey. Eur. J. Oper. Res. 197 (2009) 427–438. | MR | Zbl | DOI
[5] , and , A systematic review of humanitarian operations, humanitarian logistics and humanitarian supply chain performance literature 2005 to 2016. Ann. Oper. Res. 2832019 (2005) 71–86. | MR
[6] , , , and , Minmax-regret evacuation planning for cycle networks. In: International Conference on Theory and Applications of Models of Computation. Springer (2019) 42–58. | MR | DOI
[7] , , and , Robust optimization for emergency logistics planning: risk mitigation in humanitarian relief supply chains. Transp. Res. Part B Methodol. 45 (2011) 1177–1189. | DOI
[8] and , Improved algorithms for computing minmax regret sinks on dynamic path and tree networks. Theor. Comput. Sci. 607 (2015) 411–425. | MR | DOI
[9] , , and , Minmax regret 1-sink for aggregate evacuation time on path networks. Preprint arXiv:1806.00814 (2018).
[10] , and , Facility location optimization model for emergency humanitarian logistics. Int. J. Disaster Risk Reduct. 24 (2017) 485–498. | DOI
[11] , and , A multi-objective robust stochastic programming model for disaster relief logistics under uncertainty. OR Spectr. 35 (2013) 905–933. | MR | Zbl | DOI
[12] , and , Minmax regret combinatorial optimization problems: an algorithmic perspective. RAIRO: OR 45 (2011) 101–129. | MR | Zbl | Numdam | DOI
[13] , and , Optimization models in emergency logistics: a literature review. Socio-Econ. Plan. Sci. 46 (2012) 4–13. | DOI
[14] , , , , and , Transport network design problem under uncertainty: a review and new developments. Transp. Rev. 31 (2011) 743–768. | DOI
[15] and , Optimization of transportation-infrastructure-system protection considering weighted connectivity reliability. J. Infrastruct. Syst. 22 (2015) 04015008. | DOI
[16] and , Minmax regret combinatorial optimization problems with investments. Comput. Oper. Res. 85 (2017) 1–11. | MR | DOI
[17] , A note on two problems in connexion with graphs. Numer. Math. 1 (1959) 269–271. | MR | Zbl | DOI
[18] and , A stochastic optimization model to reduce expected post-disaster response time through pre-disaster investment decisions. Networks Spatial Econ. 14 (2014) 271–295. | MR | DOI
[19] and , A robust optimization model for distribution and evacuation in the disaster response phase. J. Ind. Eng. Int. 13 (2017) 117–141. | DOI
[20] , and , Recent advances in robust optimization: an overview. Eur. J. Oper. Res. 235 (2014) 471–483. | MR | Zbl | DOI
[21] , Multi-criteria spatial decision support system for identifying strategic roads in disaster situations. Int. J. Crit. Infrastruct. Prot. 24 (2019) 23–36. | DOI
[22] and , Multicriteria optimization in humanitarian aid. Eur. J. Oper. Res. 252 (2016) 351–366. | MR | DOI
[23] , and , A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4 (1968) 100–107. | DOI
[24] , and , All minutes are not equal: travel time and the effects of congestion on commute satisfaction in Canadian cities. Transportation 45 (2018) 1249–1268. | DOI
[25] , , , and , On the appropriate objective function for post-disaster humanitarian logistics models. J. Oper. Manage. 31 (2013) 262–280. | DOI
[26] , and , Or models with stochastic components in disaster operations management: a literature survey. Comput. Ind. Eng. 82 (2015) 183–197. | DOI
[27] , , , , and , An analysis of the literature on humanitarian logistics and supply chain management: paving the way for future studies. Ann. Oper. Res. 283 (2019) 289–307. | MR | DOI
[28] , and , A bi-objective stochastic optimization model for humanitarian relief chain by using evolutionary algorithms. Int. J. Eng. Trans. A: Basics 30 (2017) 1526–1537.
[29] , Discrete Optimization with Interval Data. In: Vol. 228 of Studies in Fuzziness and Soft Computing. Springer Berlin Heidelberg, Berlin, Heidelberg (2008). | Zbl
[30] and , Robust Discrete Optimization and its Applications. Kluwer Academic Publishers (1997). | MR | Zbl | DOI
[31] and , A roadmap for higher research quality in humanitarian operations: a methodological perspective. Eur. J. Oper. Res. 276 (2019) 395–408. | MR | DOI
[32] and , Disaster relief routing under uncertainty: a robust optimization approach. IISE Trans. 51 (2019) 869–886. | DOI
[33] , , and , The robust shortest path problem for multimodal transportation considering timetable with interval data. Syst. Sci. Control Eng. 6 (2018) 68–78. | DOI
[34] and , An exact algorithm for the robust shortest path problem with interval data. Comput. Oper. Res. 31 (2004) 1667–1680. | MR | Zbl | DOI
[35] , and , A branch and bound algorithm for the robust shortest path problem with interval data. Oper. Res. Lett. 32 (2004) 225–232. | MR | Zbl | DOI
[36] , and , Emergency transportation network design problem: identification and evaluation of disaster response routes. Int. J. Disaster Risk Reduct. 27 (2018) 7–20. | DOI
[37] , , , , , and , Decision aid models and systems for humanitarian logistics. A survey. In: Decision Aid Models for Disaster Management and Emergencies. Springer (2013) 17–44. | DOI
[38] and , Models, solutions and enabling technologies in humanitarian logistics. Eur. J. Oper. Res. 244 (2015) 55–65. | MR | DOI
[39] , , and , Pre-disaster investment decisions for strengthening a highway network. Comput. Oper. Res. 37 (2010) 1708–1719. | Zbl | DOI
[40] , , and , Humanitarian logistics and disaster relief research: trends, applications, and future research directions. In: Proceedings of the 4th International Conference on Information Systems, Logistics and Supply Chain (2012) 26–29.
[41] , , and , An optimization model for the location of disaster refuges. Socio-Econ. Plan. Sci. 59 (2017) 56–66. | DOI
[42] , , and , Algorithms for the minmax regret path problem with interval data. Inf. Sci. 462 (2018) 218–241. | MR | DOI
[43] and , Stochastic programming models. In: Vol. 10 of Handbooks in Operations Research and Management Science (2003) 1–64. | MR | Zbl | DOI
[44] , and , Estimation of travel time distributions in urban road networks using low-frequency floating car data. ISPRS Int. J. Geo-Inf. 6 (2017) 253. | DOI
[45] , and , Humanitarian logistics network design under mixed uncertainty. Eur. J. Oper. Res. 250 (2016) 239–250. | MR | DOI
[46] , , and , Two-stage multi-objective location-routing-inventory model for humanitarian logistics network design under uncertainty. Int. J. Disaster Risk Reduct. 27 (2018) 290–306. | DOI
[47] , Minmax regret 1-facility location on uncertain path networks. Eur. J. Oper. Res. 239 (2014) 636–643. | MR | DOI
[48] and , A stochastic programming model for emergency supply planning considering traffic congestion. IISE Trans. 51 (2019) 910–920. | DOI
Cité par Sources :
