[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Supply planning for shelters and emergency management crews

  • Original paper
  • Published:
Operational Research Aims and scope Submit manuscript

Abstract

This paper addresses the problem of supplying provisions to civilians affected by an emergency and to the intervention groups that provide post emergency relief. We define the Emergency Supply using Heterogeneous Fleet Problem (ESHFP) using a Mixed Integer Linear Programming mathematical model that describes the complexities involved in these operations. Furthermore, we propose a novel heuristic algorithm which constructs a plan comprising a set of efficient vehicle routes in order to minimize the total supply time, respecting constraints concerning timing, demand, capacity and supply. The characteristics of the problem have been studied by solving an extensive set of test cases. The efficiency and practicality of the algorithm has been tested by applying it to a large scale ESHFP instance and to a case study involving a forest fire in the Province of Teruel, Spain.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

References

  • Afsar HM, Prins C, Santos AC (2014) Exact and heuristic algorithms for solving the generalized vehicle routing problem with flexible fleet size. Int Trans Oper Res 21:153–175

    Article  Google Scholar 

  • Anily S, Bramel J (1999) Approximation algorithms for the capacitated traveling salesman problem with pickups and deliveries. Nav Res Logist 46(6):654–670

    Article  Google Scholar 

  • Anily S, Hassin R (1992) The swapping problem. Networks 22(4):419–433

    Article  Google Scholar 

  • Archetti C, Speranza M, Hertz A (2006) A Tabu search algorithm for the split delivery vehicle routing problem. Transp Sci 40(1):64–73

    Article  Google Scholar 

  • Balcik B, Beamon BM, Smilowitz K (2008) Last mile distribution in humanitarian relief. J Intell Transp Syst 12(2):51–63

    Article  Google Scholar 

  • Baou E, Koutras V, Zeimpekis V, Minis I (2018) Emergency evacuation planning in natural disasters under diverse population and fleet characteristics. J Humanit Logist Supply Chain Manag 8(4):447–476

    Article  Google Scholar 

  • Berbeglia G, Cordeau JF, Laporte G (2010) Dynamic pickup and delivery problems. Eur J Oper Res 202(1):8–15

    Article  Google Scholar 

  • Bianchessi N, Righini G (2007) Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery. Comput Oper Res 34(2):578–594

    Article  Google Scholar 

  • Bish DR (2011) Planning for a bus-based evacuation. OR Spectr 33(3):629–654

    Article  Google Scholar 

  • Cetin S, Gencer C (2015) A heuristic algorithm for vehicle routing problems with simultaneous pick-up and delivery and hard time windows. Open J Soc Sci 3:35–41. https://doi.org/10.4236/jss.2015.33008

    Article  Google Scholar 

  • Dikas G, Minis I (2016) Solving the bus evacuation problem and its variants. Comput Oper Res 70:75–86

    Article  Google Scholar 

  • EM-DAT (2017) Emergency Events Database (EM-DAT). The International Disasters Database Available at: http://www.emdat.be/advanced_search/index.html. Accessed 18 Jan 2017

  • Falkiner L (2003) Impact analysis of the Canadian Red Cross Expect the Unexpected Program. Institute for Catastrophic Loss Reduction, Canadian Red Cross Society, Canada

    Google Scholar 

  • Fan J (2011) The vehicle routing problem with simultaneous pickup and delivery based on customer satisfaction. Adv Control Eng Inf Sci Procedia Eng 15:5284–5289

    Google Scholar 

  • FEMA (2017) Disaster Planning Is Up To You. Federal Emergency Management Agancy, Available at: https://www.fema.gov/news-release/2007/03/30/disaster-planning-you. Accessed 15 Jan 2017

  • Fragkos EM (2017a) MELOGIC PROJECT: ESHFP input data and results for the case study in the Province of Teruel, Spain. URL: http://deopsys.aegean.gr/files/MELOGIC%20PROJECT_ESHFP%20input%20data%20and%20results%20for%20the%20case%20study%20in%20the%20Province%20of%20Teruel%2C%20Spain_0.pdf

  • Fragkos EM (2017b) Supply planning in natural disasters: modeling and analysis. Diploma Thesis, Department of Financial and Management Engineering, School of Engineering, University of the Aegean, Chios, Greece. URL: http://deopsys.aegean.gr/files/Michalis%20Fragkos%20Thesis_2017.pdf

  • Fragkos EM (2019a) MELOGIC PROJECT: effects of critical ESHFP characteristics on supply time. URL: http://deopsys.aegean.gr/files/MELOGIC%20PROJECT_Effects%20of%20critical%20ESHFP%20characteristics%20on%20supply%20time_0.pdf

  • Fragkos EM (2019b) MELOGIC PROJECT_ESHFP input data and solution for a large scale problem. URL: http://deopsys.aegean.gr/files/MELOGIC%20PROJECT_ESHFP%20input%20data%20and%20solution%20for%20a%20large%20scale%20problem_0.pdf

  • Gökçe MA, Ercan E (2019) Multi-period vehicle routing & replenishment problem of neighbourhood disaster stations for pre-disaster humanitarian relief logistics. IFAC- Pap Online 52(13):2614–2619

    Article  Google Scholar 

  • Gribkovskaia I, Halskau Ø, Laporte G, Vlček M (2007) General solutions to the single vehicle routing problem with pickups and deliveries. Eur J Oper Res 180(2):568–584

    Article  Google Scholar 

  • Hernández-Pérez H, Salazar-González JJ (2004a) Heuristics for the one-commodity pickup-and-delivery traveling salesman problem. Transp Sci 38(2):245–255

    Article  Google Scholar 

  • Hernández-Pérez H, Salazar-González JJ (2004b) A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery. Discrete Appl Math 145(1):126–139

    Article  Google Scholar 

  • Kanungo T, Mount DM, Netanyahu NS, Piatko CD, Silverman R, Wu AY (2002) An efficient k-means clustering algorithm: analysis and implementation. IEEE Trans Pattern Anal Mach Intell 24(7):881–892

    Article  Google Scholar 

  • Lau HC, Liang Z (2002) Pickup and delivery problem with time windows: algorithms and test case generation. In: Proceedings 13th IEEE international conference on tools with artificial intelligence (ICTAI 2001), Dallas, TX, 2001, pp 333–340. https://doi.org/10.1109/ictai.2001.974481

  • Liu R, Xie X, Augusto V, Rodriguez C (2013) Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care. Eur J Oper Res 230(3):475–486

    Article  Google Scholar 

  • Martinovic G, Aleksi I, Baumgartner A (2008) Single-commodity vehicle routing problem with pickup and delivery service. Math Probl Eng 697981:1

    Article  Google Scholar 

  • Mitrovic-Minic S (1998) Pickup and delivery problem with time windows: A survey. Technical Report. SFU CMPT TR 1998-12. School of Computing Science, Simon Fraser University, Burnaby, BC, Canada

  • Mohamadi A, Yaghoubi S, Pishvaee MS (2019) Fuzzy multi-objective stochastic programming model for diaster relief logistics considering telecommunication infrastructures: a case study. Oper Res Int J 19(1):59–99

    Article  Google Scholar 

  • Montane FAT, Galvao RD (2002) Vehicle routing problems with simultaneous pick-up and delivery service. OPSEARCH 39(1):19–32

    Article  Google Scholar 

  • Nagy G, Salhi S (2005) Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries. Eur J Oper Res 162(1):126–141

    Article  Google Scholar 

  • Parragh S, Doerner K, Hartl R (2008a) A survey on pickup and delivery problems: part I: Transportation between customers and depot. J für Betriebswirtschaft 58(2):21–51

    Article  Google Scholar 

  • Parragh S, Doerner K, Hartl R (2008b) A survey on pickup and delivery problems: part II: Transportation between pickup and delivery locations. J für Betriebswirtschaft 58(2):81–117

    Article  Google Scholar 

  • Penna PHV, Santos AC, Prins C (2017) Vehicle routing problems for last mile distribution after major disaster. J Oper Res Soc 69(8):1254–1268

    Article  Google Scholar 

  • Penna PHV, Subramanian A, Ochi LS, Vidal T, Prins C (2019) A hybrid heuristic for a broad class of vehicle routing problems with heterogeneous fleet. Ann Oper Res 273(1–2):5–74

    Article  Google Scholar 

  • Psarafis H (1980) A dynamic programming solution to the single vehicle, many-to-many immediate request dial-a-ride problem. Transp Sci 14(2):130–154

    Article  Google Scholar 

  • Rezaei-Malek M, Tavakkoli-Mghaddam R, Zahiri B, Bozorgi-Amiri A (2016) An interactive approach for designing a robust disaster relief logistics network with perishable commodities. Comput Ind Eng 94:201–215

    Article  Google Scholar 

  • Safaei AS, Farsad S, Paydar MM (2018) Emergency logistics planning under supply risk and demand uncertainty. Oper Res Int J. https://doi.org/10.1007/s12351-018-0376-3

    Article  Google Scholar 

  • Savelsbergh MW, Sol M (1995) The general pickup and delivery problem. Transp Sci 29(1):17–29

    Article  Google Scholar 

  • Serdan Tasan A, Gen M (2012) A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries. Comput Ind Eng 62:755–761

    Article  Google Scholar 

  • Sheu J (2007) Challenges of emergency logistics management. Transp Res Part E Logist Transp Rev 43(6):655–659

    Article  Google Scholar 

  • Subramanian A, Uchoa E, Pessoa AA, Ochi LS (2013) Branch-cut-and-price for the vehicle routing problem with simultaneous pickup and delivery. Optim Lett 7(7):1569–1581

    Article  Google Scholar 

  • Vidal T, Crainic TG, Gendreau M, Prins C (2013) Heuristics for multi-attribute vehicle routing problems: a survey and synthesis. Eur J Oper Res 231(1):1–21

    Article  Google Scholar 

  • Wassan NA, Nagy G (2014) Vehicle routing problem with deliveries and pickups: modelling issues and meta-heuristics solution approaches. Int J Transp 2(1):95–110

    Article  Google Scholar 

  • Wu J (2012) Advances in K-means clustering: a data mining thinking. Springer, New York

    Book  Google Scholar 

  • Zachariadis EE, Kiranoudis CT (2011) A local search metaheuristic algorithm for the vehicle routing problem with simultaneous pick-ups and deliveries. Expert Syst Appl 38(3):2717–2726

    Article  Google Scholar 

  • Zeimpekis V, Ichoua S, Minis I (2013) Humanitarian and relief logistics. Springer, New York

    Book  Google Scholar 

Download references

Acknowledgements

This research has been co-financed by the European Commission (DG ECHO) under the MELOGIC project (ECHO/SUB/2014/695769). The authors would like to thank the rest of the project partners namely European University Cyprus (EUC), Caritas Diocesana de Teruel, HANKEN School of Economics, and Red Cross Italy (Vicenza Chapter), and especially Professor George Boustras, Professor Gyöngyi Kovács, Mr. Pierandrea Turchetti, and Mr. Jose Guillen.

Funding

The funding was provided by EU Civil Protection Mechanism (Grant No. ECHO/SUB/2014/695769) - MELOGIC project.

Author information

Authors and Affiliations

  1. Department of Financial and Management Engineering, School of Engineering, University of the Aegean, 41 Kountouriotou Str., 82100, Chios, Greece

    Michael E. Fragkos, Vasileios Zeimpekis, Vasilis Koutras & Ioannis Minis

Authors
  1. Michael E. Fragkos
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Vasileios Zeimpekis
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Vasilis Koutras
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Ioannis Minis
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ioannis Minis.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendices

Appendix A

1.1 Input data for the theoretical case study

Table 4, presents the demand points (shelters D1–D10) to be supplied, and the demand (in appropriate units, e.g. boxes) at each shelter per commodity (C1–C6). The demand values were generated from appropriate random distributions. The coordinates of the demand points are generated from the uniform distribution \(U \left( {0,50} \right)\) under the constraint that their Euclidian distance from the origin (0,0) is between 30 and 50.

Table 4 Commodity (C) quantities par demand point (D)
Full size table

Table 5, presents the available vehicles (V1- V15) along with the corresponding capacity in \(m^{3}\) (randomly generated) and their starting locations (S.L.).The coordinates of vehicles’ starting locations are generated from the uniform distribution \(U\left( {0,20} \right)\) under the constraint that their Euclidian distance from the origin (0,0) is between 0 and 20.

Table 5 Vehicle-related input data
Full size table

Table 6 presents the supply points (S1–S16) and the inventory per commodity per supply point. A total inventory of 250 pallets is considered and it is distributed almost equally (\(\sigma^{2}\) = low, see Sect. 5) to the supply points. The coordinates of the supply points are generated from the uniform distribution \(U\left( {0,20} \right)\) under the constraint that their Euclidian distance from (0,0) is between 0 and 20.

Table 6 Supply points-related input data
Full size table

Appendix B

2.1 Output data for the theoretical case study

Table 7 presents the routes operated, the corresponding vehicle per route, the route’s starting and ending times, the sequence of visits to the supply points and the corresponding supplies collected, the sequence of visits at the demand points and the corresponding supplies delivered.

Table 7 Output data of the theoretical case study
Full size table

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Fragkos, M.E., Zeimpekis, V., Koutras, V. et al. Supply planning for shelters and emergency management crews. Oper Res Int J 22, 741–777 (2022). https://doi.org/10.1007/s12351-020-00557-7

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12351-020-00557-7

Keywords

Search

Navigation