Abstract
Every year, natural disasters such as earthquakes, floods, volcanos, etc. cause millions of victims. So a quick response to these disasters is vital to reduce their negative consequences. Vehicle routing models can make important contributions to faster response, and thus, save lives. This paper proposes a vehicle routing problem to deliver relief resources from origins to destinations in response to disasters. For this purpose, a multi-period, multi-depot, multi-trip mixed-integer linear programming model is developed. Minimizing the sum of arrival times is considered as a service-based objective function for the increase of the survival rate. For the first time, the problem is solved using a grouping metaheuristic algorithm. Then its performance is compared with two other grouping algorithms. To evaluate the solution method, the algorithms are implemented on various test problems and compared statistically. Additionally, to show the validity of the model, sensitivity analyses are performed and managerial insights are given.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Al Theeb, N., & Murray, C. (2017). Vehicle routing and resource distribution in postdisaster humanitarian relief operations. International Transactions in Operational Research, 24(6), 1253–1284.
Anuar, W. K., Lee, L. S., Seow, H.-V., & Pickl, S. (2021). A multi-depot vehicle routing problem with stochastic road capacity and reduced two-stage stochastic integer linear programming models for rollout algorithm. Mathematics, 9(13), 1572.
Balcik, B., Beamon, B. M., & Smilowitz, K. (2008). Last mile distribution in humanitarian relief. Journal of Intelligent Transportation Systems, 12(2), 51–63.
Banomyong, R., Varadejsatitwong, P., & Oloruntoba, R. (2019). A systematic review of humanitarian operations, humanitarian logistics and humanitarian supply chain performance literature 2005 to 2016. Annals of Operations Research, 283(1), 71–86.
Barbarosoǧlu, G., & Arda, Y. (2004). A two-stage stochastic programming framework for transportation planning in disaster response. Journal of the Operational Research Society, 55(1), 43–53.
Behl, A., & Dutta, P. (2019). Humanitarian supply chain management: A thematic literature review and future directions of research. Annals of Operations Research, 283(1), 1001–1044.
Berkoune, D., Renaud, J., Rekik, M., & Ruiz, A. (2012). Transportation in disaster response operations. Socio-Economic Planning Sciences, 46(1), 23–32.
Campbell, A. M., Vandenbussche, D., & Hermann, W. (2008). Routing for relief efforts. Transportation Science, 42(2), 127–145.
Çankaya, E., Ekici, A., & Özener, O. Ö. (2019). Humanitarian relief supplies distribution: An application of inventory routing problem. Annals of Operations Research, 283(1–2), 119–141.
Cattaruzza, D., Absi, N., & Feillet, D. (2018). Vehicle routing problems with multiple trips. Annals of Operations Research, 271(1), 127–159.
Centre for Research on the Epidemiology of Disasters CRED. (2020). “Disaster Year in Review.”
Ertem, M. A., İş, M., İşbilir, M., & Arslan, A. Ş. (2017). Review of intermodal freight transportation in humanitarian logistics. European Transport Research Review, 9(1), 10–20.
Farahani, R. Z., Lotfi, M. M., Baghaian, A., Ruiz, R., & Rezapour, S. (2020). Mass casualty management in disaster scene: A systematic review of OR&MS research in humanitarian operations. European Journal of Operational Research, 287(3), 787–819.
Ferrer, J. M., Javier Martín-Campo, F., Teresa Ortuño, M., Pedraza-Martínez, A. J., Tirado, G., & Vitoriano, B. (2018). Multi-criteria optimization for last mile distribution of disaster relief aid: Test cases and applications. European Journal of Operational Research, 269(2), 501–515.
Fleischmann, B. (1990). The Vehicle Routing Problem with Multiple Use of the Vehicles. Technical report, Fachbereich Wirtschaftswissenschaften, Universitaet Hamburg.
Galindo, G., & Batta, R. (2013). Review of recent developments in OR/MS research in disaster operations management. European Journal of Operational Research, 230(2), 201–211.
Hoyos, M. C., Morales, R. S., & Akhavan-Tabatabaei, R. (2015). OR models with stochastic components in disaster operations management: A literature survey. Computers & Industrial Engineering, 82, 183–197.
Huang, K., & Rafiei, R. (2019). Equitable last mile distribution in emergency response. Computers & Industrial Engineering, 127, 887–900.
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.
Huang, X., & Song, L. (2018). An emergency logistics distribution routing model for unexpected events. Annals of Operations Research, 269(1), 223–239.
Jahre, M. (2017). Humanitarian supply chain strategies–a review of how actors mitigate supply chain risks. Journal of Humanitarian Logistics and Supply Chain Management, 7(2), 82–101.
Kashan, A. H., Masoud J., & Mina H. K. (2009). A new solution approach for grouping problems based on evolution strategies. In International conference of soft computing and pattern recognition (pp. 88–93). IEEE.
Kashan, A. H., Tavakkoli-Moghaddam, R., & Gen, M. (2017). A warfare inspired optimization algorithm: The Find-Fix-Finish-Exploit-Analyze (F3EA) metaheuristic algorithm. In Proceedings of the tenth international conference on management science and engineering management (Vol. 366, pp. 393–408).
Khorsi, M., Chaharsooghi, S. K., Bozorgi-Amiri, A., Kashana, A. H., Chaharsooghi, K., Bozorgi-Amiri, A., & Kashan, H. (2020). A multi-objective multi-period model for humanitarian relief logistics with split delivery and multiple uses of vehicles. Journal of System Science and System Engineering, 29, 360–378.
Khorsi, M., Chaharsooghi, S. K., Kashan, A. H., & Bozorgi-Amiri, A. (2021). Pareto-based grouping meta-heuristic algorithm for humanitarian relief logistics with multistate network reliability. Or Spectrum, 43(2), 327–365.
Kunz, N., & Reiner, G. (2012). A meta-analysis of humanitarian logistics research. Journal of Humanitarian Logistics and Supply Chain Management, 2(2), 116–147.
Leiras, A., de Brito, J. I., Peres, E. Q., Bertazzo, T. R., & Yoshizaki, H. T. (2014). Literature review of humanitarian logistics research: Trends and challenges. Journal of Humanitarian Logistics and Supply Chain Management, 4(1), 95–130.
Lin, Y. H., Batta, R., Rogerson, P. A., Blatt, A., & Flanigan, M. (2011). A logistics model for emergency supply of critical items in the aftermath of a disaster. Socio-Economic Planning Sciences, 45(4), 132–145.
Luis, E., Dolinskaya, I. S., & Smilowitz, K. R. (2012). Disaster relief routing: Integrating research and practice. Socio-Economic Planning Sciences, 46(1), 88–97.
Mahootchi, M., & Golmohammadi, S. (2017). Developing a new stochastic model considering bi-directional relations in a natural disaster: A possible earthquake in Tehran (the Capital of Islamic Republic of Iran). Annals of Operations Research, 269(1), 1–35.
Martínez-Salazar, I., Angel-bello, F., & Alvarez, A. (2015). A customer-centric routing problem with multiple trips of a single vehicle. Journal of the Operational Research Society, 66(8), 1312–1323.
Modgil, S., Singh, R. K., & Foropon, C. (2020). Quality management in humanitarian operations and disaster relief management: A review and future research directions. Annals of Operations Research, 1–54.
Molina, J., López-Sánchez, A. D., Hernández-Díaz, A. G., & Martínez-Salazar, I. (2018). A Multi-start Algorithm with Intelligent Neighborhood Selection for solving multi-objective humanitarian vehicle routing problems. Journal of Heuristics, 24(2), 111–133.
Moreno, A., Alem, D., Ferreira, D., & Clark, A. (2018). An effective two-stage stochastic multi-trip location-transportation model with social concerns in relief supply chains. European Journal of Operational Research, 269(3), 1050–1071.
Moshref-Javadi, M., & Lee, S. (2016). The latency location-routing problem. European Journal of Operational Research, 255(2), 604–619.
Najafi, M., Eshghi, K., & de Leeuw, S. (2014). A Dynamic dispatching and routing model to plan/ re-plan logistics activities in response to an earthquake. Or Spectrum, 36(2), 323–356.
Özdamar, L., Ekinci, E., & Küçükyazici, B. (2004). Emergency logistics planning in natural disasters. Annals of Operations Research, 129(1–4), 217–245.
Özdamar, L., & Yi, W. (2008). Greedy neighborhood search for disaster relief and evacuation logistics. IEEE Intelligent Systems, 23(1), 14–23.
Rivera, J. C., Murat Afsar, H., & Prins, C. (2016). Mathematical formulations and exact algorithm for the multitrip cumulative capacitated single-vehicle routing problem. European Journal of Operational Research, 249(1), 93–104.
Ruiz, A., Anaya-Arenas, A. M., & Renaud, J. (2014). Relief distribution networks: A systematic review. Annals of Operations Research, 223(1), 53–79.
Sakiani, R., Seifi, A., & Khorshiddoust, R. R. (2020). Inventory routing and dynamic redistribution of relief goods in post-disaster operations. Computers & Industrial Engineering, 140, 106219.
Salam, M. A., & Khan, S. A. (2020). Lessons from the humanitarian disaster logistics management: A case study of the earthquake in Haiti. Benchmarking an International Journal, 27(4), 1455–1473.
Salcedo-sanz, S., Jiménez-Fernández, S., Del Leopoldo Carro-Calvo, J., Ser, J. A., Portilla-figueras, L. E., Agustı, S.-S., et al. (2012). A new grouping genetic algorithm for clustering problems. Expert Systems with Applications, 39(10), 9695–9703.
Sharif, M. T., & Salari, M. (2015). A GRASP algorithm for a humanitarian relief transportation problem. Engineering Applications of Artificial Intelligence, 41, 259–269.
Shen, Z., Dessouky, M. M., & Ordóñez, F. (2009). A two-stage vehicle routing model for large-scale bioterrorism emergencies. Networks, 54(4), 255–269.
Wang, L., Song, J., & Shi, L. (2015). Dynamic emergency logistics planning: Models and heuristic algorithm. Optimization Letters, 9(8), 1533–1552.
Wolpert, D. H., Nna, D., Road, H., Jose, S., & Macready, W. G. (1997). No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1(1), 67–82.
Wu, Y., Pan, F., Li, S., Pan, F., Chen, Z., & Dong, M. (2020). Peer-induced fairness capacitated vehicle routing scheduling using a hybrid optimization ACO–VNS algorithm. Soft Computing, 24(3), 2201–2213.
Yi, W., & Kumar, A. (2007). Ant colony optimization for disaster relief operations. Transportation Research Part E: Logistics and Transportation Review, 43(6), 660–672.
Zheng, Y.-J., Chen, S.-Y., & Ling, H.-F. (2015). Evolutionary optimization for disaster relief operations: A survey. Applied Soft Computing, 27, 553–566.
Zhu, Li., Gong, Y., Yishui, Xu., & Jun, Gu. (2019). Emergency relief routing models for injured victims considering equity and priority. Annals of Operations Research, 283(1–2), 1573–1606.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Competing interests
The authors declare that they have no competing interests.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendices
Appendix A
Notations are defined below:
Notation | Definition |
|---|---|
Index sets | |
\(N\) | Set of all nodes indexed by \(i,j\in N\) |
\(D\) | Set of demand nodes indexed by \(d, {d}^{\prime}\) |
\(S\) | Set of distribution centers indexed by \(s, {s}^{\prime}\) |
\(V\) | Set of vehicles indexed by \(v\) |
\(C\) | Set of commodity types indexed by \(c\) |
\(T\) | Set of periods indexed by \(t\) |
\(R\) | Set of trips any vehicle makes indexed by \(r\) |
Parameters | |
\({d}_{cdt}\) | Amount of demand for commodity \(c\) in node \(d\) in period \(t\) |
\({t}_{ijt}\) | Travel time from node \(i\) to node \(j\) in period \(t\) |
\(VC\) | Volume capacity of a vehicle |
\(WC\) | Weight capacity of a vehicle |
\({C}_{c}\) | Unit volume of commodity type \(c\) |
\({W}_{c}\) | Unit weight of commodity type \(c\) |
\({\delta }_{ijts}\) | Zero and one matrix that indicates accessibility to arc \((i,j)\) in period \(t\) |
\({t}_{max}\) | Maximum working hours per vehicle per period |
\(M\) | A large positive number |
Notation | Definition | Description |
|---|---|---|
Decision variables | ||
\({Z}_{vrijt}\) | 1 if vehicle \(v\) in trip \(r\) in period \(t\) traverses arc \((i,j)\); otherwise, 0 | This variable helps to determine the sequence of points, which each vehicle meets on each trip and gives the vehicle routing plan. Besides, it can help to determine the goods’ distribution plan |
\({st}_{rvt}\) | Start time of trip \(r\) for vehicle \(v\) in period \(t\) | The departure time of a vehicle from its DC to make a specific trip in a specific time period is determined by this variable |
\({et}_{rvt}\) | End time of trip \(r\) for vehicle \(v\) in period \(t\) | The return time of a vehicle to its DC after making a specific trip in a specific time period is determined by this variable |
\({at}_{ivrt}\) | Arrival time of vehicle \(v\) in trip \(r\) in period \(t\) in node \(i\) | This variable determines when a vehicle meets a node in the network on a given trip and period. With the aid of this variable, we can attain the operations’ scheduling plan |
Appendix B
The steps of the F3EA algorithm are explained in the following.
2.1 The find step
This step is referred to as the selection step that imitates the process of military objects detection by a radar. To generate a new solution in each iteration, it is first assumed that the parent’s solution has a temporary role in a radar. On the other side, all other solutions in the population play the role of the enemy’s military facility and it is possible to detect it by the artificial radar. Identification of individuals is determined by the maximum radar range (\({Rn}_{max}\)).
Detection capability is measured based on the value of the function. The radar equation can be expressed as follows according to the function values:
Let’s assume that the worst and best function values in the population are shown by \({f}_{min}^{t}\) and \({f}_{max}^{t}\), respectively. The function values of the ith individual in the population (the parent solution) and the jth individual are represented by \(f\left({\overrightarrow{F}}_{i}^{t}\right)\) and \(f\left({\overrightarrow{F}}_{j}^{t}\right)\), respectively.
Definition 1
Let \({R}_{ij}^{t}=\left|f\left({\overrightarrow{F}}_{i}^{t}\right)-f\left({\overrightarrow{F}}_{j}^{t}\right)\right|\) be the distance between \({\overrightarrow{F}}_{i}^{t}\) and \({\overrightarrow{F}}_{j}^{t}\) in the function value space. \({\overrightarrow{F}}_{i}^{t}\) detect \({\overrightarrow{F}}_{j}^{t}\) if \({R}_{ij}^{t}\le {Rn}_{max ij}^{t}\).
Observation 1
If \(f\left({\overrightarrow{F}}_{i}^{t}\right)={f}_{min}^{t}\), then \({R}_{max ij}^{t}=0, \forall i\ne j\). In a radar with the best solution, nothing is detected.
Observation 2
If \(f\left({\overrightarrow{F}}_{j}^{t}\right)={f}_{min}^{t}\), then \({R}_{max ij}^{t}=f\left({\overrightarrow{F}}_{i}^{t}\right)-{f}_{min}^{t}={R}_{ij}^{t}\). All other individuals in the population can always detect the best solution in the population.
Observation 3
If \(f\left({\overrightarrow{F}}_{j}^{t}\right)={f}_{max}^{t}\), then \({R}_{max ij}^{t}=0\). No individual can detect the worst solution.
Among all the detected solutions by the radar, one is selected based on any logic to generate the new solution in the Finish step. If no individual is identified, an individual of the population will be selected. Hereafter, we assume that \({\overrightarrow{F}}_{j}^{t}\) is the selected individual.
2.2 The fix step
In this step, which is a type of local search step, the imitation of the aiming process toward the target in order to monitor it is performed. As can be seen in Fig.
A schematic concept of the Fix step
9, when the military tank target has to be hit, the angle by which the rocket is launched has to be acute enough to let the rocket traverses the maximum peak. A single-variable optimization problem is used to obtain the improved solutions locally.
Let \({G}_{0}^{t}\) be defined as an individual that reveals the position of an artificial rocket launcher in the search space and \({S}^{t}\) as a search direction. The Fix step probes for the location of the deepest valley (the minimum of the scalar function) on the line passing through \({G}_{0}^{t}\), and in parallel with \({S}^{t}\), the following equations are used for one-dimensional optimization problem as follows:
where \({G}_{d}^{t}={G}_{d-1}^{t}+{S}_{d}^{t}{e}_{d}\) and components \({S}_{d}^{t}\), \(\forall d=1,\dots ,d\) are obtained consecutively as follows:
where \({e}_{d}\) is the dth coordinate unit vector and \({\gamma }_{d}^{t}\) is every time set randomly selected as 0.05 or 1 to shrink the line search extent for local or global exploration, respectively. According to the \({\lambda }^{*}\) value obtained by Eqs. (30–32), the position of the newly generated solution is \({G}_{0}^{t}+{\lambda }^{*}{S}^{t}\).
2.3 The finish step
Let \({\overrightarrow{F}}_{i}^{t}\) and \({\overrightarrow{F}}_{j}^{t}\) represent the position of a rocket launcher and a target military facility, respectively. The main purpose of this step is to find a new solution based on \({\overrightarrow{F}}_{i}^{t}\) and benefiting from \({\overrightarrow{F}}_{j}^{t}\). It is assumed that an artificial rocket is launched from \({\overrightarrow{F}}_{i}^{t}\) toward \({\overrightarrow{F}}_{j}^{t}\) and the position of the explosion \({\overrightarrow{E}}_{ij}^{t}\) is determined via the projectile motion equations and considered as a new solution in the search space.
Let \({\left[{\overrightarrow{F}}_{i}^{t},u({\overrightarrow{F}}_{i}^{t})\right]}_{1\times (n+1)}\) and \({\left[{\overrightarrow{F}}_{j}^{t},u({\overrightarrow{F}}_{j}^{t})\right]}_{1\times (n+1)}\) be the positions of the rocket launcher and the jth artificial military object selected for devastation in the \(F-u(F)\) coordinate system, respectively (see Fig.
The rocket’s move path is parabolic regardless of the air or wind drag
10).
As shown in Fig. 10, the inclination \({\beta }_{ij}^{t}\) with the horizon is calculated as follows:
Let the artificial rocket be launched from \({\overrightarrow{F}}_{i}^{t}\) toward \({\overrightarrow{F}}_{j}^{t}\) with angle \({\alpha }_{ij}^{t}\). The value of the artificial rocket’s initial velocity (\({v}_{0ij}^{t}\)) can be obtained for a given value of \({\alpha }_{ij}^{t}\) as bellow:
where,
By Eq. (38), the time of the rocket’s flight is determined:
After launching the rocket, it is exposed to two different conditions of an unanticipated air drag force and the wind force, which cause the deviation of explosion position from the predicted position (see Fig.
Air drag and wind force cause the rocket’s move path to be non-parabolic
11). The amount of this diversion depends on the mass of the rocket (\({rm}_{ij}^{t}\)).
It seems logical to assume that the wind force on the X-axis blows in an unswerving direction toward \({\overrightarrow{F}}_{i}^{t}\) to push the artificial rocket toward \({\overrightarrow{F}}_{j}^{t}\), if \(f\left({\overrightarrow{F}}_{j}^{t}\right)<f\left({\overrightarrow{F}}_{i}^{t}\right)\). Otherwise, if \(f\left({\overrightarrow{F}}_{i}^{t}\right)<f\left({\overrightarrow{F}}_{j}^{t}\right)\), it is logical to say that the wind force on the X-axis blows in a direction away from \({\overrightarrow{F}}_{i}^{t}\), and pushes the artificial rocket away from \({\overrightarrow{F}}_{j}^{t}\). No wind component in the z direction is assumed (\({w}_{zij}^{t}=0\)):
If \({E}_{i}^{t}\) is considered as the explosion position of the artificial rocket launched from \({\overrightarrow{F}}_{i}^{t}\) toward \({\overrightarrow{F}}_{j}^{t}\), which is a new solution to the problem, Eqs. 40–41 are used to generate \({E}_{i}^{t}\) as follows (Eq. 40 is the explosion position on the x-axis, and Eq. 41 represents the new solution generated in the Finish step):
2.4 The exploit step
It is necessary that the outcome of the Finish step via the crossover operations be exploited in the Exploit step of the F3EA metaheuristic algorithm. The feasible solution \({E}_{i}^{t}\) differs from \({\overrightarrow{F}}_{i}^{t}\) in all dimensions. By contrast, for many functions, making changes in all directions may not be a good idea. To simulate the number of changes, a truncated geometric distribution is used.
2.5 The analyze step
There are two circumstances in the Analyze step; either when a new solution is generated during the Fix or Exploit step, which is able to provide a better function value, or when it starts to update the global best solution.
An example of a new solution generation
Average RPD value of the algorithms for medium-sized problems
CPU time of the algorithms for medium-sized problems
Average RPD value of the algorithms for large-sized problems
Standard deviation of the algorithms’ RPD for large-sized problems
CPU time of the algorithms for large-sized problems
Rights and permissions
About this article
Cite this article
Khorsi, M., Chaharsooghi, S.K., Husseinzadeh Kashan, A. et al. Solving the humanitarian multi-trip cumulative capacitated routing problem via a grouping metaheuristic algorithm. Ann Oper Res 319, 173–210 (2022). https://doi.org/10.1007/s10479-022-04757-6
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-022-04757-6