.png)
The Cumulative Capacitated Vehicle Routing Problem with Time-dependent on Humanitarian Logistics for Disaster Management
Abstract
This study addresses the challenges of optimizing humanitarian logistics during disaster management by developing a Cumulative Capacitated Vehicle Routing Problem with Time-Dependent factors (CCVRP-TD) model. The primary objective is to enhance delivery efficiency by incorporating time-dependent variables such as fluctuating traffic and service durations into route planning. The research contributes a novel Mixed Integer Nonlinear Programming (MINLP) framework that dynamically adapts to real-world conditions like road closures and shifting priorities. Using the MINLP approach, the model was validated through numerical experiments involving four delivery vehicles serving six customers across five routes. Results demonstrated a significant improvement in routing efficiency, with a total cumulative travel distance of 110 km and adherence to specified delivery windows, such as 9:30 AM and 10:30 AM for Customer 1. Additionally, vehicle capacity constraints were effectively managed, with individual route lengths ranging from 20 to 35 km. These findings showcase the model’s ability to balance cost minimization, service reliability, and logistical adaptability. The novelty lies in the integration of time-dependent costs and service benefits into a multi-depot framework, enabling flexible yet precise route optimization under constrained conditions. This research provides a robust tool for enhancing disaster logistics and offers practical implications for improving the responsiveness and effectiveness of humanitarian aid delivery.
Keywords
Full Text:
PDFReferences
S. Negi and G. Negi, “Framework to manage humanitarian logistics in disaster relief supply chain management in India,” Int. J. Emerg. Serv., vol. 10, no. 1, pp. 40–76, 2021, doi: 10.1108/IJES-02-2020-0005.
M. A. Salam and S. A. Khan, “Lessons from the humanitarian disaster logistics management: A case study of the earthquake in Haiti,” Benchmarking, vol. 27, no. 4, pp. 1455–1473, 2020, doi: 10.1108/BIJ-04-2019-0165.
N. U. Handayani, G. Basyir, D. Puspitasari, and Y. Widharto, “Designing inventory information system for humanitarian logistics in the merapi disaster management in sleman, yogyakarta,” Proceedings of the International Conference on Industrial Engineering and Operations Management, no. August. 2020.
S. Velastegui, R. Galleguillos-Pozo, C. Rosero, and M. V. Garcia, “Management of Humanitarian Logistics in the Stages Prior to Natural Disasters in Canton Ambato, Ecuador,” Advances in Intelligent Systems and Computing, vol. 1099. pp. 97–108, 2020. doi: 10.1007/978-3-030-35740-5_7.
E. Henrique de Moura, T. Bruno Rocha e Cruz, and D. M. De Genaro Chiroli, “A framework proposal to integrate humanitarian logistics practices, disaster management and disaster mutual assistance: A Brazilian case,” Saf. Sci., vol. 132, 2020, doi: 10.1016/j.ssci.2020.104965.
N. Loree and F. Aros-Vera, “Points of distribution location and inventory management model for Post-Disaster Humanitarian Logistics,” Transp. Res. Part E Logist. Transp. Rev., vol. 116, pp. 1–24, 2018, doi: 10.1016/j.tre.2018.05.003.
O. Rodríguez-Espíndola, P. Albores, and C. Brewster, “Disaster preparedness in humanitarian logistics: A collaborative approach for resource management in floods,” Eur. J. Oper. Res., vol. 264, no. 3, pp. 978–993, 2018, doi: 10.1016/j.ejor.2017.01.021.
F. Fallucchi, M. Tarquini, and E. W. De Luca, “Knowledge management for the support of logistics during Humanitarian Assistance and Disaster Relief (HADR),” Lecture Notes in Business Information Processing, vol. 265. pp. 226–233, 2016. doi: 10.1007/978-3-319-47093-1_19.
B. S. Sahay, N. V. C. Menon, and S. Gupta, “Humanitarian Logistics and Disaster Management: The Role of Different Stakeholders,” Springer Proceedings in Business and Economics. pp. 3–21, 2016. doi: 10.1007/978-81-322-2416-7_1.
B. R. Raghukumar, A. Agarwal, and M. K. Sharma, “An Agile and Flexible Supply Chain for Efficient Humanitarian Logistics in a Disaster Management System,” Springer Proceedings in Business and Economics. pp. 129–139, 2016. doi: 10.1007/978-81-322-2416-7_9.
J. Andharia, “Humanitarian logistics in asia: A missing link in disaster management and practice,” Strategic Disaster Risk Management in Asia. pp. 179–192, 2015. doi: 10.1007/978-81-322-2373-3_12.
J. Montero and B. Vitoriano, “Humanitarian logistics and information management for natural disaster response,” Intelligent Systems and Decision Making for Risk Analysis and Crisis Response - Proceedings of the 4th International Conference on Risk Analysis and Crisis Response, RACR 2013. pp. 15–21, 2013. doi: 10.1201/b16038-6.
G. Kovács and K. M. Spens, Relief supply chain management for disasters: Humanitarian, aid and emergency logistics. 2011. doi: 10.4018/978-1-60960-824-8.
R. P. KNOTT, “Vehicle Scheduling for Emergency Relief Management: A Knowledge‐Based Approach,” Disasters, vol. 12, no. 4, pp. 285–293, 1988, doi: 10.1111/j.1467-7717.1988.tb00678.x.
W. K. Anuar, L. S. Lee, S. Pickl, and H. V. Seow, “Vehicle routing optimisation in humanitarian operations: A survey on modelling and optimisation approaches,” Appl. Sci., vol. 11, no. 2, pp. 1–70, 2021, doi: 10.3390/app11020667.
E. Grass and K. Fischer, “Two-stage stochastic programming in disaster management: A literature survey,” Surv. Oper. Res. Manag. Sci., vol. 21, no. 2, pp. 85–100, 2016, doi: 10.1016/j.sorms.2016.11.002.
U. Srilakshmi, S. A. Alghamdi, V. A. Vuyyuru, N. Veeraiah, and Y. Alotaibi, “A Secure Optimization Routing Algorithm for Mobile Ad Hoc Networks,” IEEE Access, vol. 10, pp. 14260–14269, 2022, doi: 10.1109/ACCESS.2022.3144679.
D. Cattaruzza, N. Absi, D. Feillet, and J. González-Feliu, “Vehicle routing problems for city logistics,” EURO J. Transp. Logist., vol. 6, no. 1, pp. 51–79, 2017, doi: 10.1007/s13676-014-0074-0.
J. R. Montoya-Torres, J. López Franco, S. Nieto Isaza, H. Felizzola Jiménez, and N. Herazo-Padilla, “A literature review on the vehicle routing problem with multiple depots,” Computers and Industrial Engineering, vol. 79. pp. 115–129, 2015. doi: 10.1016/j.cie.2014.10.029.
G. B. DANTZIG and J. H. RAMSER, “Truck Dispatching,” Encyclopedia of Operations Research and Management Science. pp. 1579–1579, 2013. doi: 10.1007/978-1-4419-1153-7_200874.
G. Laporte, Y. Nobert, and D. Arpin, “An exact algorithm for solving a capacitated location-routing problem,” Ann. Oper. Res., vol. 6, no. 9, pp. 291–310, 1986.
İ. Kara, B. Y. Kara, and M. K. Yetiş, “Cumulative Vehicle Routing Problems,” Veh. Routing Probl., no. June, pp. 84–98, 2008, doi: 10.5772/5812.
S. U. Ngueveu, C. Prins, and R. W. Calvo, “Lower and upper bounds for the m-peripatetic vehicle routing problem,” 4or, vol. 8, no. 4, pp. 387–406, 2010, doi: 10.1007/s10288-010-0148-2.
N. A. Kyriakakis, M. Marinaki, N. Matsatsinis, and Y. Marinakis, “A cumulative unmanned aerial vehicle routing problem approach for humanitarian coverage path planning,” Eur. J. Oper. Res., vol. 300, no. 3, pp. 992–1004, 2022, doi: 10.1016/j.ejor.2021.09.008.
T. Vidal, G. Laporte, and P. Matl, “A concise guide to existing and emerging vehicle routing problem variants,” Eur. J. Oper. Res., vol. 286, no. 2, pp. 401–416, 2020, doi: https://doi.org/10.1016/j.ejor.2019.10.010.
K. C. Tan, L. H. Lee, Q. L. Zhu, and K. Ou, “Heuristic methods for vehicle routing problem with time windows,” Artif. Intell. Eng., vol. 15, no. 3, pp. 281–295, 2001.
I. Hamdi, “Solving the cumulative capacitated vehicle routing problem with drones,” J. Ind. Prod. Eng., vol. 41, no. 4, pp. 344–361, 2024, doi: 10.1080/21681015.2024.2304570.
M. N. Kritikos, T. Metzidakis, and G. Ioannou, “The cumulative vehicle routing problem with arc time windows,” Expert Syst. Appl., vol. 240, p. 122447, 2024, doi: https://doi.org/10.1016/j.eswa.2023.122447.
A. Fernández Gil, E. Lalla-Ruiz, M. Gómez Sánchez, and C. Castro, “The cumulative vehicle routing problem with time windows: models and algorithm,” Ann. Oper. Res., 2023, doi: 10.1007/s10479-022-05102-7.
N. A. Kyriakakis, I. Sevastopoulos, M. Marinaki, and Y. Marinakis, “A hybrid Tabu search – Variable neighborhood descent algorithm for the cumulative capacitated vehicle routing problem with time windows in humanitarian applications,” Comput. Ind. Eng., vol. 164, 2022, doi: 10.1016/j.cie.2021.107868.
R. Liu and Z. Jiang, “A hybrid large-neighborhood search algorithm for the cumulative capacitated vehicle routing problem with time-window constraints,” Appl. Soft Comput. J., vol. 80, pp. 18–30, 2019, doi: 10.1016/j.asoc.2019.03.008.
B. Tüű-Szabó, P. Földesi, and L. T. Kóczy, “Experiments with the Discrete Bacterial Memetic Evolutionary Algorithm for Solving the Cumulative Capacitated Vehicle Routing Problem,” Stud. Comput. Intell., vol. 1040, pp. 87–92, 2023, doi: 10.1007/978-3-031-07707-4_11.
F. Ramadhan and A. Imran, “An Adaptation of the Record-to-Record Travel Algorithm for the Cumulative Capacitated Vehicle Routing Problem,” IEEE Int. Conf. Ind. Eng. Eng. Manag., pp. 238–242, 2019, doi: 10.1109/IEEM44572.2019.8978511.
M. E. Bruni, S. Nucamendi-Guillén, S. Khodaparasti, and P. Beraldi, “The Cumulative Capacitated Vehicle Routing Problem with Profits Under Uncertainty,” AIRO Springer Ser., vol. 3, pp. 311–322, 2019, doi: 10.1007/978-3-030-34960-8_28.
S. Nucamendi-Guillén, F. Angel-Bello, I. Martínez-Salazar, and A. E. Cordero-Franco, “The cumulative capacitated vehicle routing problem: New formulations and iterated greedy algorithms,” Expert Syst. Appl., vol. 113, pp. 315–327, 2018, doi: 10.1016/j.eswa.2018.07.025.
J. F. Sze, S. Salhi, and N. Wassan, “The cumulative capacitated vehicle routing problem with min-sum and min-max objectives: An effective hybridisation of adaptive variable neighbourhood search and large neighbourhood search,” Transp. Res. Part B Methodol., vol. 101, pp. 162–184, 2017, doi: 10.1016/j.trb.2017.04.003.
J. C. Rivera, H. M. Afsar, and C. Prins, “A multistart iterated local search for the multitrip cumulative capacitated vehicle routing problem,” Comput. Optim. Appl., vol. 61, no. 1, pp. 159–187, 2015, doi: 10.1007/s10589-014-9713-5.
L. Ke and Z. Feng, “A two-phase metaheuristic for the cumulative capacitated vehicle routing problem,” Comput. Oper. Res., vol. 40, no. 2, pp. 633–638, 2013, doi: 10.1016/j.cor.2012.08.020.
S. U. Ngueveu, C. Prins, and R. Wolfler Calvo, “An effective memetic algorithm for the cumulative capacitated vehicle routing problem,” Comput. Oper. Res., vol. 37, no. 11, pp. 1877–1885, 2010, doi: 10.1016/j.cor.2009.06.014.
J. C. Rivera, H. Murat Afsar, and C. Prins, “Mathematical formulations and exact algorithm for the multitrip cumulative capacitated single-vehicle routing problem,” Eur. J. Oper. Res., vol. 249, no. 1, pp. 93–104, 2016, doi: 10.1016/j.ejor.2015.08.067.
K. Bestuzheva, A. Chmiela, B. Müller, F. Serrano, S. Vigerske, and F. Wegscheider, “Global optimization of mixed-integer nonlinear programs with SCIP 8,” J. Glob. Optim., 2023, doi: 10.1007/s10898-023-01345-1.
P. D. Dai, “An Efficient Mixed Integer Nonlinear Program Model for Optimal Positions of Pressure Reducing Valves in Water Distribution Systems,” 15th International Conference on Electronics, Computers and Artificial Intelligence, ECAI 2023 - Proceedings. 2023. doi: 10.1109/ECAI58194.2023.10193914.
Y. Kim, J. Cho, S. Han, and N. Cho, “Weapon Target Assignment Model for Small Unit Ground Combat Using Mixed Integer Nonlinear Program and Lagrangian Relaxation,” Math. Probl. Eng., vol. 2022, 2022, doi: 10.1155/2022/9228993.
B. Dasović and U. Klanšek, “Integration of mixed-integer nonlinear program and project management tool to support sustainable cost-optimal construction scheduling,” Sustain., vol. 13, no. 21, 2021, doi: 10.3390/su132112173.
DOI: https://doi.org/10.47738/jads.v6i1.481
Refbacks
- There are currently no refbacks.
Journal of Applied Data Sciences
| ISSN | : | 2723-6471 (Online) |
| Publisher | : | Bright Publisher |
| Website | : | http://bright-journal.org/JADS |
| : | taqwa@amikompurwokerto.ac.id (principal contact) | |
| support@bright-journal.org (technical issues) |
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0