2653Accesses
Abstract
In humanitarian aid, emergency relief routing optimization needs to consider equity and priority issues. Different from the general path selection optimization, this paper builds two models differentiated by considerations on the identical and diverse injured degrees, where the relative deprivation cost is proposed as one of the decision-making objectives to emphasize equity, and the in-transit tolerable suffering duration is employed as a type of time window constraint to highlight rescue priority. After proving the NP-hardness of our models, we design a meta-heuristic algorithm based on the ant colony optimization to accelerate the convergence speed, which is more efficient than the commonly-used genetic algorithm. Taking 2017 Houston Flood as a case, we find results by performing the experimental comparison and sensitivity analysis. First, our models have advantages in the fairness of human sufferings mitigation. Second, the role of the in-transit tolerable suffering time window cannot be ignored in humanitarian relief solutions. Various measures are encouraged to extend this type of time window for achieving better emergency relief. Finally, our proposed hybrid transportation strategy aiming at diverse injured degrees stably outperforms the separated strategy, both in operational cost control and psychological sufferings alleviation, especially when relief supplies are limited.
This is a preview of subscription content,log in via an institution to check access.
Access this article
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
Price includes VAT (Japan)
Instant access to the full article PDF.
Similar content being viewed by others
Explore related subjects
Discover the latest articles and news from researchers in related subjects, suggested using machine learning.References
Ariyasingha, I. D. I. D., & Fernando, T. G. I. (2015). Performance analysis of the multi-objective ant colony optimization algorithms for the travelling salesman problem.Swarm and Evolutionary Computation,23, 11–26.
Balcik, B., & Beamon, B. M. (2008). Performance measurement in humanitarian relief chains.International Journal of Public Sector Management,21(1), 4–25.
Balcik, B., Beamon, B. M., & Smilowitz, K. (2008). Last mile distribution in humanitarian relief.Journal of Intelligent Transportation Systems,12(2), 51–63.
Bell, J. E., & McMullen, P. R. (2004). Ant colony optimization techniques for the vehicle routing problem.Advanced Engineering Informatics,18(1), 41–48.
Boonmee, C., Arimura, M., & Asada, T. (2017). Facility location optimization model for emergency humanitarian logistics.International Journal of Disaster Risk Reduction.https://doi.org/10.1016/j.ijdrr.2017.01.017.
Bräysy, O., & Gendreau, M. (2005). Vehicle routing problem with time windows, part II: Metaheuristics.Transportation Science,39(1), 119–139.
Bullnheimer, B., Hartl, R. F., & Strauss, C. (1999). An improved ant system algorithm for the vehicle routing problem.Annals of Operations Research,89, 319–328.
Cable News Network. (2017). Harvey aftermath: Houston open for business; other cities suffering.http://www.cnn.com/2017/08/31/us/harvey-houston-texas-flood/index.html. Accessed 31 August 2017.
Campbell, A. M., Vandenbussche, D., & Hermann, W. (2008). Routing for relief efforts.Transportation Science,42(2), 127–145.
Cantillo, V., Serrano, I., Macea, L. F., & Holguín-Veras, J. (2017). Discrete choice approach for assessing deprivation cost in humanitarian relief operations.Socio-Economic Planning Sciences.https://doi.org/10.1016/j.seps.2017.06.004.
Chen, H. K., Hsueh, C. F., & Chang, M. S. (2009). Production scheduling and vehicle routing with time windows for perishable food products.Computers & Operations Research,36(7), 2311–2319.
Croes, G. A. (1958). A method for solving travelling salesman problems.Operations Research,6(6), 791–812.
Deb, K. (2001).Multi-objective optimization using evolutionary algorithms. New York, NY: Wiley.
Dorigo, M., & Gambardella, L. M. (1997). Ant colony system: A cooperative learning approach to the travelling salesman problem.IEEE Transactions on Evolutionary Computation,1(1), 53–66.
Dorigo, M., & Stützle, T. (2004).Ant colony optimization. Cambridge, MA: The MIT Press.
Elluru, S., Gupta, H., Kaur, H., & Singh, S. P. (2017). Proactive and reactive models for disaster resilient supply chain.Annals of Operations Research.https://doi.org/10.1007/s10479-017-2681-2.
Erera, A. L., Morales, J. C., & Savelsbergh, M. (2010). The vehicle routing problem with stochastic demand and duration constraints.Transportation Science,44(4), 474–492.
Federal Emergency Management Agency. (2017). FEMA Flood Map Service Center.https://msc.fema.gov/portal. Accessed 24 September 2017.
Govindan, K., Jafarian, A., Khodaverdi, R., & Devika, K. (2014). Two-echelon multiple-vehicle location-routing problem with time windows for optimization of sustainable supply chain network of perishable food.International Journal of Production Economics,152, 9–28.
Gralla, E., Goentzel, J., & Fine, C. (2014). Assessing trade-offs among multiple objectives for humanitarian aid delivery using expert preferences.Production and Operations Management,23, 978–989.
Gutjahr, W. J., & Fischer, S. (2018). Equity and deprivation costs in humanitarian logistics.European Journal of Operational Research,270(1), 185–197.
Gutjahr, W. J., & Nolz, P. C. (2016). Multicriteria optimization in humanitarian aid.European Journal of Operational Research,252, 351–366.
Harks, T., König, F. G., Matuschke, J., Richter, A. T., & Schulz, J. (2016). An integrated approach to tactical transportation planning in logistics networks.Transportation Science,50(2), 439–460.
Jabbour, C. J. C., Sobreiro, V. A., Jabbour, A. B. L. S., Campos, L. M. S., Mariano, E. B., & Renwick, D. W. S. (2017). An analysis of the literature on humanitarian logistics and supply chain management: Paving the way for future studies.Annals of Operations Research,5/6, 1–19.
Harris County Flood Control District. (2017). Harris County has never seen a storm like Harvey.https://www.hcfcd.org/hurricane-harvey/. Accessed 2 October 2017.
Holguín-Veras, J., Jaller, M., Van Wassenhove, L. N., Pérez, N., & Wachtendorf, T. (2012). On the unique features of post-disaster humanitarian logistics.Journal of Operations Management,30(7–8), 494–506.
Holguín-Veras, J., Pérez, N., Jaller, M., Van Wassenhove, L. N., & Aros-Verac, F. (2013). On the appropriate objective function for post-disaster humanitarian logistics models.Journal of Operations Management,31(5), 262–280.
Hsu, C. I., Hung, S. F., & Li, H. C. (2007). Vehicle routing problem with time-windows for perishable food delivery.Journal of Food Engineering,80(2), 465–475.
Hu, Z. H., & Sheu, J. B. (2013). Post-disaster debris reverse logistics management under psychological cost minimization.Transportation Research Part B: Methodological,55, 118–141.
Huang, K., Jiang, Y., Yuan, Y., & Zhao, L. (2015). Modeling multiple humanitarian objectives in emergency response to large-scale disasters.Transportation Research Part E: Logistics and Transportation Review,75, 1–17.
Huang, M., Smilowitz, K., & Balcik, B. (2012). Models for relief routing: Equity, efficiency and efficacy.Transportation Research Part E: Logistics and Transportation Review,48(1), 2–18.
Itani, M. N. (2014).Dynamics of deprivation cost in last mile distribution: The integrated resource allocation and vehicle routing problem. Fargo: North Dakota State University.
Jacobson, E. U., Argon, N. T., & Ziya, S. (2012). Priority assignment in emergency response.Operations Research,60(4), 813–832.
Jin, S., Jeong, S., Kim, J., & Kim, K. (2015). A logistics model for the transport of disaster victims with various injuries and survival probabilities.Annals of Operations Research,230(1), 17–33.
Karsu, Ö., & Morton, A. (2015). Inequity averse optimization in operational research.European Journal of Operational Research,245(2), 343–359.
Maniezzo, V. (1999). Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem.INFORMS Journal on Computing,11(4), 358–369.
Matl, P., Hartl, R. F., & Vidal, T. (2018). Workload equity in vehicle routing problems: A survey and analysis.Transportation Science,52(2), 239–260.
Merkle, D., Middendorf, M., & Schmeck, H. (2002). Ant colony optimization for resource-constrained project scheduling.IEEE Transactions on Evolutionary Computation,6(4), 333–346.
Miranda, D. M., & Conceição, S. V. (2016). The vehicle routing problem with hard time windows and stochastic travel and service time.Expert Systems with Applications,64, 104–116.
Özdamar, L., Ekinci, E., & Küçükyazici, B. (2004). Emergency logistics planning in natural disasters.Annals of Operations Research,129(1), 217–245.
Özdamar, L., & Ertem, M. A. (2015). Models, solutions and enabling technologies in humanitarian logistics.European Journal of Operational Research,244(1), 55–65.
Parker, R. G., & Rardin, R. L. (1983). The traveling salesman problem: An update of research.Naval Research Logistics Quarterly,30(1), 69–96.
Pérez, N., & Holguín-Veras, J. (2015). Inventory-Allocation distribution models for post disaster humanitarian logistics with explicit consideration of deprivation cost.Transportation Science,50(4), 1261–1285.
Potvin, J. Y. (2009). State-of-the art review: Evolutionary algorithms for vehicle routing.INFORMS Journal on Computing,21(4), 518–548.
Rahman, M. S., & Kaykobad, M. (2005). On Hamiltonian cycles and Hamiltonian paths.Information Processing Letters,94(1), 37–41.
Ransikarbum, K., & Mason, S. J. (2016). Goal programming-based post-disaster decision making for integrated relief distribution and early-stage network restoration.International Journal of Production Economics,182, 324–341.
Rawls, C. G., & Turnquist, M. A. (2010). Pre-positioning of emergency supplies for disaster response.Transportation Research Part B: Methodological,44(4), 521–534.
Rezaei-Malek, M., Tavakkoli-Moghaddam, R., Cheikhrouhou, N., & Taheri-Moghaddam, A. (2016). An approximation approach to a trade-off among efficiency, efficacy, and balance for relief pre-positioning in disaster management.Transportation Research Part E: Logistics and Transportation Review,93, 485–509.
Sabouhi, F., Bozorgi-Amiri, A., Moshref-Javadi, M., & Heydari, M. (2018). An integrated routing and scheduling model for evacuation and commodity distribution in large-scale disaster relief operations: A case study.Annals of Operations Research.https://doi.org/10.1007/s10479-018-2807-1.
Saghafian, S., Hopp, W. J., Oyen, M. P. V., Desmond, J. S., & Kronick, S. L. (2014). Complexity augmented triage: A tool for improving patient safety and operational efficiency.Manufacturing & Service Operations Management,16(3), 329–345.
Schyns, M. (2015). An ant colony system for responsive dynamic vehicle routing.European Journal of Operational Research,245(3), 704–718.
Sheu, J. B. (2007). An emergency logistics distribution approach for quick response to urgent relief demand in disasters.Transportation Research Part E: Logistics and Transportation Review,43(6), 687–709.
Sheu, J. B. (2010). Dynamic relief-demand management for emergency logistics operations under large-scale disasters.Transportation Research Part E: Logistics and Transportation Review,46(1), 1–17.
Sheu, J. B. (2014). Post-disaster relief-service centralized logistics distribution with survivor resilience maximization.Transportation Research Part B: Methodological,68, 288–314.
Sheu, J. B., & Pan, C. (2014). A method for designing centralized emergency supply network to respond to large-scale natural disasters.Transportation Research Part B: Methodological,67, 284–305.
Sung, I., & Lee, T. (2016). Optimal allocation of emergency medical resources in a mass casualty incident: Patient prioritization by column generation.European Journal of Operational Research,252(2), 623–634.
Swamy, R., Kang, J. E., Batta, R., & Chung, Y. (2017). Hurricane evacuation planning using public transportation.Socio-Economic Planning Sciences,59, 43–55.
Talarico, L., Meisel, F., & Sörensen, K. (2015). Ambulance routing for disaster response with patient groups.Computers & Operations Research,56, 120–133.
Tofighi, S., Torabi, S. A., & Mansouri, S. A. (2016). Humanitarian logistics network design under mixed uncertainty.European Journal of Operational Research,250(1), 239–250.
Üster, H., & Kewcharoenwong, P. (2011). Strategic design and analysis of a relay network in truckload transportation.Transportation Science,45(4), 505–523.
Van Wassenhove, L. N. (2006). Humanitarian aid logistics: Supply chain management in high gear.Journal of Operations Research Society,47(5), 475–489.
Vitoriano, B., Ortuno, M., Tirado, G., & Montero, J. (2011). A multi-criteria optimization model for humanitarian aid distribution.Journal of Global Optimization,51(2), 189–208.
Wang, X., Liang, L., Yue, X., & Van Wassenhove, L. (2017). Estimation of deprivation level functions using a numerical rating scale.Production and Operations Management,26(11), 2137–2150.
Wex, F., Schryen, G., Feuerriegel, S., & Neumann, D. (2014). Emergency response in natural disaster management: Allocation and scheduling of rescue units.European Journal of Operational Research,235, 697–708.
Yi, W., & Özdamar, L. (2007). A dynamic logistics coordination model for evacuation and support in disaster response activities.European Journal of Operational Research,179(3), 1177–1193.
Yuan, Y., & Wang, D. (2009). Path selection model and algorithm for emergency logistics Management.Computers & Industrial Engineering,56(3), 1081–1094.
Zheng, Y., Ling, H., Xue, J., & Chen, S. (2014). Population classification in fire evacuation: A multi-objective particle swarm optimization approach.IEEE Transactions on Evolutionary Computation,18(1), 70–81.
Zhu, E., Crainic, T. G., & Gendreau, M. (2014). Scheduled service network design for freight rail transportation.Operations Research,62(2), 383–400.
Funding
This study was funded by NSFC (Grant Nos. 71571103 and 71620107002), China Scholarship Council (Grant No. 201709040001), and NSSFC (Grant No. 16ZDA013).
Author information
Authors and Affiliations
School of Management Science and Engineering & China Institute of Manufacturing Development, Nanjing University of Information Science & Technology, Nanjing, China
Li Zhu, Yishui Xu & Jun Gu
EMLYON Business School, Écully, France
Yeming Gong
- Li Zhu
You can also search for this author inPubMed Google Scholar
- Yeming Gong
You can also search for this author inPubMed Google Scholar
- Yishui Xu
You can also search for this author inPubMed Google Scholar
- Jun Gu
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toYeming Gong.
Appendices
Appendix A: NP-hardness proof of Models I and II
By the following proposition, we prove the relationship between our Models (VRPTW) and the travelling salesman problem (TSP).
Proposition A.1
The VRPTW is at least as hard as TSP.
Proof
VRPTW is considered as a problem with additional time window constraints based on the general vehicle routing problem (VRP). VRPTW is equivalent to VRP in the case of unlimited time windows. In this sense, VRP is a special case of VRPTW.
Then, we review the definitions of VRP and TSP. VRP tries to answer “what are the optimal routes for a group of vehicles when serving a given set of customers, where vehicles initially-located at a depot are dispatched to customers and return to the origin depot?”, while TSP refers to “given a list of customers and a starting depot, what is the optimal route for one vehicle when services each customer exactly once and returns to the origin depot?”. So, VRP can be treated as a generalization of TSP. When the number of vehicles is 1, VRP becomes TSP. In other words, TSP is a special case of VRP.
Therefore, if TSP is NP-hard, both VRPTW and VRP are naturally NP-hard. That is to say, VRPTW and VRP are at least as hard as TSP.□
It is well-known that TSP is NP-hard, since the Hamiltonian Cycle (HC) that is NP-complete can be reducible to TSP in polynomial time (Rahman and Kaykobad2005). Thereby, we prove that Models I and II are NP-hard according to PropositionA.1.
Appendix B: Comparison analysis based on Model I and Model II
The optimal paths of traditional path selection models.a No deprivation cost objective.b No tolerable suffering time constraint
The optimal paths under different transportation strategies.a1 The 1st stage paths in separated strategy.a2 The 2nd stage paths in separated strategy.b1 The 1st stage paths in hybrid strategy.b2 The 2nd stage paths in hybrid strategy
Appendix C: Sensitivity analysis based on Model I and Model II
The optimal paths under different changes of\( u_{i} \) and\( b_{i} \) in Model I.a1 Both\( u_{i} \) and\( b_{i} \) decreased by 20%.a2 Both\( u_{i} \) and\( b_{i} \) increased by 20%.b1 Only\( u_{i} \) decreased by 20%.b2 Only\( u_{i} \) increased by 30%.c1 Only\( b_{i} \) decreased by 20%.c2 Only\( b_{i} \) increased by 30%
The optimal paths under different changes of\( u_{i} \) and\( b_{i} \) using two transportation strategies in Model II.a1 The 1st stage paths in separated strategy with 20% decrease of\( u_{i} \) and\( b_{i} \).a2 The 2nd stage paths in separated strategy with 20% decrease of\( u_{i} \) and\( b_{i} \).b1 The 1st stage paths in separated strategy with 20% increase of\( u_{i} \) and\( b_{i} \).b2 The 2nd stage paths in separated strategy with 20% increase of\( u_{i} \) and\( b_{i} \).c1 The 1st stage paths in hybrid strategy with 20% decrease of\( u_{i} \) and\( b_{i} \).c2 The 2nd stage paths in hybrid strategy with 20% decrease of\( u_{i} \) and\( b_{i} \).d1 The 1st stage paths in hybrid strategy with 20% increase of\( u_{i} \) and\( b_{i} \).d2 The 2nd stage paths in hybrid strategy with 20% increase of\( u_{i} \) and\( b_{i} \)
Rights and permissions
About this article
Cite this article
Zhu, L., Gong, Y., Xu, Y.et al. Emergency relief routing models for injured victims considering equity and priority.Ann Oper Res283, 1573–1606 (2019). https://doi.org/10.1007/s10479-018-3089-3
Published:
Issue Date:
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative