Optimasi Rute Rencana Perjalanan Pesawat Menggunakan Algoritma Late Acceptance Hill Climbing (Studi Kasus : Travelling Salesman Challenge 2.0)
DOI:
https://doi.org/10.25126/jtiik.20241046842Abstrak
Permasalahan Traveling Salesman Problem (TSP) merupakan permasalahan klasik yang popular diteliti dalam bidang optimasi kombinatorika. Permasalahan ini bertujuan menentukan rute perjalanan terpendek untuk mengunjungi setiap lokasi tepat satu kali dan diakhir perjalanan harus kembali ke lokasi awal perjalanan dimulai. Permasalahan ini telah digolongkan sebagai permasalahan NP-Hard, sehingga membutuhkan algoritma non-deterministic untuk dapat menyelesaikan permasalahan ini. Dalam permasalahan nyata, salah satu penerapan TSP ada pada permasalahan untuk menentukan rute perjalanan termurah untuk mengunjungi beberapa kota di beberapa negara. Kompetisi Travelling Salesman Challenge 2.0 (TSC 2.0) mengangkat permasalahan ini dalam sebuah kompetisi pada tahun 2018. Untuk menyelesaikan studi kasus tersebut, penelitian ini menyembangkan algoritma Late Acceptance Hill Climbing (LAHC) menggunakan metode hiper-heuristik. Algoritma LAHC merupakan algoritma yang sederhana namun telah terbukti mampu mengoptimasi dengan baik pada beberapa permasalahan TSP. Algoritma LAHC diuji coba pada 14 dataset dari TSC 2.0. Hasil penelitian menunjukan algoritma LAHC menghasilkan solusi yang kompetitif dengan mampu menurunkan biaya perjalanan dengan rata-rata 58% dan menghasilkan hasil yang lebih baik dengan rata-rata 9% dari algoritma Threshold Acceptance (TA) yang digunakan sebagai algoritma pembanding.
Abstract
The Traveling Salesman Problem (TSP) is a classic problem that is popularly researched in the field of combinatorics optimization. This problem aims to determine the shortest travel route to visit each location exactly once and, at the end of the trip, must return to where the trip started. This problem has been classified as an NP-Hard problem. Therefore it requires a non-deterministic algorithm to solve it. In the real world, one of the applications of TSP is the problem of determining the cheapest travel routes to visit several cities in several countries. The Traveling Salesman Challenge 2.0 (TSC 2.0) competition raised this issue in a competition in 2018. This study developed the Late Acceptance Hill Climbing (LAHC) algorithm using the hyper-heuristic method to complete the case study from TSC 2.0. The LAHC algorithm is simple but has been proven to optimize well for several TSP problems. The LAHC algorithm was tested on 14 datasets from TSC 2.0. The results show that the LAHC algorithm produces competitive solutions by reducing travel costs by an average of 58% and making better results by an average of 9% than the Threshold Acceptance (TA) algorithm used as a comparison algorithm.
Downloads
Referensi
AKHAND, M.A.H., AYON, S.I., SHAHRIYAR, S.A., SIDDIQUE, N. and ADELI, H., 2020. Discrete Spider Monkey Optimization for Travelling Salesman Problem. Applied Soft Computing Journal, 86. https://doi.org/10.1016/j.asoc.2019.105887.
Al-FURHUD, M.A. and HUSSAIN, Z., 2020. Genetic Algorithms for the Multiple Travelling Salesman Problem. International Journal of Advanced Computer Science and Applications, [online] 11(7). https://doi.org/10.14569/IJACSA.2020.0110768.
BOLAJI, A.L. ARO, BAMIGBOLA, A.F. and SHOLA, P.B., 2018. Late acceptance hill climbing algorithm for solving patient admission scheduling problem. Knowledge-Based Systems, 145, pp.197–206. https://doi.org/10.1016/J.KNOSYS.2018.01.017.
BURKE, E.K. and BYKOV, Y., 2017. The late acceptance Hill-Climbing heuristic. European Journal of Operational Research, [online] 258(1), pp.70–78. https://doi.org/10.1016/j.ejor.2016.07.012.
BURKE, E.K., HYDE, M.R., KENDALL, G., OCHOA, G., ÖZCAN, E. and WOODWARD, J.R., 2019. A classification of hyper-heuristic approaches: Revisited. In: International Series in Operations Research and Management Science. https://doi.org/10.1007/978-3-319-91086-4_14.
CHEIKHROUHOU, O. and KHOUFI, I., 2021. A comprehensive survey on the Multiple Traveling Salesman Problem: Applications, approaches and taxonomy. Computer Science Review, 40, p.100369. https://doi.org/10.1016/J.COSREV.2021.100369.
CHOONG, S.S., WONG, L.P. and LIM, C.P., 2019. An artificial bee colony algorithm with a Modified Choice Function for the traveling salesman problem. Swarm and Evolutionary Computation, 44. https://doi.org/10.1016/j.swevo.2018.08.004.
CINAR, A.C., KORKMAZ, S. and KIRAN, M.S., 2020. A discrete tree-seed algorithm for solving symmetric traveling salesman problem. Engineering Science and Technology, an International Journal, [online] 23(4), pp.879–890. https://doi.org/10.1016/j.jestch.2019.11.005.
CLAY, S., MOUSIN, L., VEERAPEN, N. and JOURDAN, L., 2021. CLAHC - Custom late acceptance hill climbing: First results on TSP. In: GECCO 2021 Companion - Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion. Association for Computing Machinery, Inc. pp.1970–1973. https://doi.org/10.1145/3449726.3463129.
FONSECA, G.H.G., SANTOS, H.G. and CARRANO, E.G., 2016. Late acceptance hill-climbing for high school timetabling. Journal of Scheduling, [online] 19(4), pp.453–465. https://doi.org/10.1007/s10951-015-0458-5.
KHEIRI, A., GRETSISTA, A., KEEDWELL, E., Lulli, G., Epitropakis, M.G. and Burke, E.K., 2021. A hyper-heuristic approach based upon a hidden Markov model for the multi-stage nurse rostering problem. Computers and Operations Research, 130. https://doi.org/10.1016/j.cor.2021.105221.
KHEIRI, A., ÖZCAN, E. and PARKES, A.J., 2016. A stochastic local search algorithm with adaptive acceptance for high-school timetabling. Annals of Operations Research, [online] 239(1), pp.135–151. https://doi.org/10.1007/s10479-014-1660-0.
PANDIRI, V. and SINGH, A., 2019. An artificial bee colony algorithm with variable degree of perturbation for the generalized covering traveling salesman problem. Applied Soft Computing Journal, 78. https://doi.org/10.1016/j.asoc.2019.03.001.
PREMANANDA, I.G.A., TJAHYANTO, A. and MUKLASON, A., 2022. Hybrid Whale Optimization Algorithm for Solving Timetabling Problems of ITC 2019. In: 2022 IEEE International Conference on Cybernetics and Computational Intelligence (CyberneticsCom). IEEE. pp.317–322. https://doi.org/10.1109/CyberneticsCom55287.2022.9865647.
QIM, W., ZHUANG, Z., HUANG, Z. and HUANG, H., 2021. A novel reinforcement learning-based hyper-heuristic for heterogeneous vehicle routing problem. Computers & Industrial Engineering, 156, p.107252. https://doi.org/10.1016/J.CIE.2021.107252.
Unduhan
Diterbitkan
Terbitan
Bagian
Lisensi
Artikel ini berlisensi Creative Common Attribution-ShareAlike 4.0 International (CC BY-SA 4.0)
Penulis yang menerbitkan di jurnal ini menyetujui ketentuan berikut:
- Penulis menyimpan hak cipta dan memberikan jurnal hak penerbitan pertama naskah secara simultan dengan lisensi di bawah Creative Common Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) yang mengizinkan orang lain untuk berbagi pekerjaan dengan sebuah pernyataan kepenulisan pekerjaan dan penerbitan awal di jurnal ini.
- Penulis bisa memasukkan ke dalam penyusunan kontraktual tambahan terpisah untuk distribusi non ekslusif versi kaya terbitan jurnal (contoh: mempostingnya ke repositori institusional atau menerbitkannya dalam sebuah buku), dengan pengakuan penerbitan awalnya di jurnal ini.
- Penulis diizinkan dan didorong untuk mem-posting karya mereka online (contoh: di repositori institusional atau di website mereka) sebelum dan selama proses penyerahan, karena dapat mengarahkan ke pertukaran produktif, seperti halnya sitiran yang lebih awal dan lebih hebat dari karya yang diterbitkan. (Lihat Efek Akses Terbuka).
