OPTIMIZING BI-OBJECTIVE MULTIPLE TRAVELING SALESMEN ROUTES FOR DISASTER RELIEF LOGISTICS USING GENETIC ALGORITHM

  • Amos Hatoguan Sihombing Department of Mathematics, Faculty of Science and Mathematics, Universitas Diponegoro, Indonesia https://orcid.org/0009-0008-7406-4142
  • Ratna Herdiana Department of Mathematics, Faculty of Science and Mathematics, Universitas Diponegoro, Indonesia https://orcid.org/0000-0001-8624-6543
  • Jovian Dian Pratama Department of Mathematics, Faculty of Science and Mathematics, Universitas Diponegoro, Indonesia https://orcid.org/0000-0003-3761-3479
DOI: https://doi.org/10.30598/barekengvol19iss4pp2507-2520
Keywords: Disaster Relief Logistics, Genetic Algorithm, Multiple Traveling Salesman Problem, Route Optimization

Abstract

Handling natural disasters such as floods requires efficient logistics distribution to minimize the negative impact on victims. Distribution route optimization becomes very important in this process. This paper applies a metaheuristic method using Genetic Algorithm to the Bi-objective Multiple Traveling Salesman Problem (BMTSP) to obtain a solution that minimizes the distance and time to deliver disaster relief logistics. Multiple vehicles are used in this study to represent delivery agents with two main objectives, namely minimizing total distance and travel time. Genetic Algorithm is applied by considering these two main objectives through the process of selection, crossover, mutation, and produces an effective Pareto solution. The results indicate that applying the Genetic Algorithm to the Bi-Objective Multiple Traveling Salesman Problem yields more efficient delivery routes—reducing both distance and time—compared to the Nearest Neighbor Algorithm. The simulation and testing in this study utilize data on distances and travel times among Central Java Regional Disaster Management Agency offices in 19 regencies—including a central depot—located in flood-prone areas of Central Java Province. The scenario involves two vehicles with identical load capacities.

Downloads

Download data is not yet available.

References

R. Matai, S. Singh, and M. Lal, “TRAVELING SALESMAN PROBLEM: AN OVERVIEW OF APPLICATIONS, FORMULATIONS, AND SOLUTION APPROACHES,” in Traveling Salesman Problem, Theory and Applications, InTech, 2010. doi: https://doi.org/10.5772/12909.

S. Linganathan and P. Singamsetty, “GENETIC ALGORITHM TO THE BI-OBJECTIVE MULTIPLE TRAVELLING SALESMAN PROBLEM,” Alexandria Engineering Journal, vol. 90, pp. 98–111, Mar. 2024, doi: https://doi.org/10.1016/j.aej.2024.01.048.

X. Zan, Z. Wu, C. Guo, and Z. Yu, “A PARETO-BASED GENETIC ALGORITHM FOR MULTI-OBJECTIVE SCHEDULING OF AUTOMATED MANUFACTURING SYSTEMS,” Advances in Mechanical Engineering, vol. 12, no. 1, Jan. 2020, doi: https://doi.org/10.1177/1687814019885294.

S. Geetha, P. T. Vanathi, and G. Poonthalir, “METAHEURISTIC APPROACH FOR THE MULTI-DEPOT VEHICLE ROUTING PROBLEM,” Applied Artificial Intelligence, vol. 26, no. 9, pp. 878–901, Oct. 2012, doi: https://doi.org/10.1080/08839514.2012.727344.

F. Mone and J. E. Simarmata, “APLIKASI ALGORITMA GENETIKA DALAM PENJADWALAN MATA KULIAH,” BAREKENG: Jurnal Ilmu Matematika dan Terapan, vol. 15, no. 4, pp. 615–628, Dec. 2021, doi: https://doi.org/10.30598/barekengvol15iss4pp615-628.

Q. M. Ha, Y. Deville, Q. D. Pham, and M. H. Hà, “A HYBRID GENETIC ALGORITHM FOR THE TRAVELING SALESMAN PROBLEM WITH DRONE,” Journal of Heuristics, vol. 26, no. 2, pp. 219–247, Apr. 2020, doi: https://doi.org/10.1007/s10732-019-09431-y.

J. Xu, L. Pei, and R. Zhu, “APPLICATION OF A GENETIC ALGORITHM WITH RANDOM CROSSOVER AND DYNAMIC MUTATION ON THE TRAVELLING SALESMAN PROBLEM,” Procedia Comput Sci, vol. 131, pp. 937–945, 2018, doi: https://doi.org/10.1016/j.procs.2018.04.230.

F. Rafique and H. Cui, “AN EFFICIENT GENETIC ALGORITHM FOR SOLVING THE TRAVEL SALESMAN PROBLEM,” Dec. 14, 2023. doi: https://doi.org/10.21203/rs.3.rs-3739487/v1.

R. I. Bolaños, E. M. Toro O, and M. Granada E, “A POPULATION-BASED ALGORITHM FOR THE MULTI TRAVELLING SALESMAN PROBLEM,” International Journal of Industrial Engineering Computations, pp. 245–256, 2016, doi: https://doi.org/10.5267/j.ijiec.2015.10.005.

M. Goerigk, K. Deghdak, and P. Heßler, “A COMPREHENSIVE EVACUATION PLANNING MODEL AND GENETIC SOLUTION ALGORITHM,” Transp Res E Logist Transp Rev, vol. 71, pp. 82–97, Nov. 2014, doi: https://doi.org/10.1016/j.tre.2014.08.007

M. Ma and H. Li, “A HYBRID GENETIC ALGORITHM FOR SOLVING BI-OBJECTIVE TRAVELING SALESMAN PROBLEMS,” J Phys Conf Ser, vol. 887, p. 012065, Aug. 2017, doi: https://doi.org/10.1088/1742-6596/887/1/012065.

H. Liu, P. Zhan, and M. Zhou, “OPTIMIZATION OF A LOGISTICS TRANSPORTATION NETWORK BASED ON A GENETIC ALGORITHM,” Mobile Information Systems, vol. 2022, pp. 1–8, Jun. 2022, doi: https://doi.org/10.1155/2022/1271488.

D. Zhang and W. Y. Zhang, “AN OPTIMIZATION DESIGN FOR EVACUATION PLANNING BASED ON FUZZY CREDIBILITY THEORY AND GENETIC ALGORITHM,” IOP Conf Ser Earth Environ Sci, vol. 81, p. 012194, Aug. 2017, doi: https://doi.org/10.1088/1755-1315/81/1/012194.

A. Roy, G. So, and Y. A. Ma, “OPTIMIZATION ON PARETO SETS: ON A THEORY OF MULTI-OBJECTIVE OPTIMIZATION,” 2023, Accessed: Jun. 03, 2025. [Online]. Available: https://arxiv.org/abs/2308.02145

S. D. Immanuel and U. Kr. Chakraborty, “GENETIC ALGORITHM: AN APPROACH ON OPTIMIZATION,” in 2019 International Conference on Communication and Electronics Systems (ICCES), IEEE, Jul. 2019, pp. 701–708. doi: https://doi.org/10.1109/ICCES45898.2019.9002372.

S.N. Sivanandar and S.N. Deepa, INTRODUCTION TO GENETIC ALGORITHMS. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008. doi: 10.1007/978-3-540-73190-0.

Eyal Wirsansky, HANDS-ON GENETIC ALGORITHMS WITH PYTHON. Birmingham: Packt Publishing Ltd, 2020.

A. P. Wibowo, D. Avianto, and I. Imantoko, “PENGEMBANGAN ALGORITMA GENETIKA DENGAN PENDEKATAN REPETITIVE RANDOM UNTUK PENJADWALAN UJIAN PENDADARAN PROYEK TUGAS AKHIR,” Jurnal Nasional Teknologi dan Sistem Informasi, vol. 7, no. 1, pp. 35–43, Jun. 2021, doi: https://doi.org/10.25077/TEKNOSI.v7i1.2021.35-43.

A. Saxena and J. Panday, “REVIEW OF CROSSOVER TECHNIQUES FOR GENETIC ALGORITHMS,” International Journal of Trend in Research and Development, vol. 3, no. 5, 2019.

A. Hassanat, K. Almohammadi, E. Alkafaween, E. Abunawas, A. Hammouri, and V. B. S. Prasath, “CHOOSING MUTATION AND CROSSOVER RATIOS FOR GENETIC ALGORITHMS—A REVIEW WITH A NEW DYNAMIC APPROACH,” Information, vol. 10, no. 12, p. 390, Dec. 2019, doi: https://doi.org/10.3390/info10120390.

R. Ferdiani Harahap and Sawaluddin, “STUDY VEHICLE ROUTING PROBLEM USING NEAREST NEIGHBOR ALGORITHM,” J Phys Conf Ser, vol. 2421, no. 1, p. 012027, Jan. 2023, doi: https://doi.org/10.1088/1742-6596/2421/1/012027.

Published
2025-09-01
How to Cite
[1]
A. H. Sihombing, R. Herdiana, and J. D. Pratama, “OPTIMIZING BI-OBJECTIVE MULTIPLE TRAVELING SALESMEN ROUTES FOR DISASTER RELIEF LOGISTICS USING GENETIC ALGORITHM”, BAREKENG: J. Math. & App., vol. 19, no. 4, pp. 2507-2520, Sep. 2025.
Issue
Vol 19 No 4 (2025): BAREKENG: Journal of Mathematics and Its Application
Section
Articles

Copyright (c) 2025 Ratna Herdiana, Amos Hatoguan Sihombing, Jovian Dian Pratama

Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Authors who publish with this Journal agree to the following terms:

  1. Author retain copyright and grant the journal right of first publication with the work simultaneously licensed under a creative commons attribution license that allow others to share the work within an acknowledgement of the work’s authorship and initial publication of this journal.
  2. Authors are able to enter into separate, additional contractual arrangement for the non-exclusive distribution of the journal’s published version of the work (e.g. acknowledgement of its initial publication in this journal).
  3. Authors are permitted and encouraged to post their work online (e.g. in institutional repositories or on their websites) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published works.