Metode Hybrid-DPSO dan Clustering untuk Rekomendasi Rute Perjalanan Wisata Berbasis Mobile Android
DOI:
https://doi.org/10.26418/jp.v10i2.72014Keywords:
metode heuristik, metode clustering, metode hybrid, VRP, DPSO, GAAbstract
Di dalam suatu tur perjalanan wisata terdapat beberapa lokasi wisata yang akan dikunjungi. Penentuan urutan lokasi wisata yang akan dikunjungi akan menentukan total waktu lamanya perjalanan wisata yang ditempuh dan akan semakin kompleks apabila jumlah lokasi wisata yang akan dikunjungi semakin banyak dan dilakukan selama beberapa hari. Pengelola perjalanan wisata harus menentukan rencana perjalanan wisata dengan matang agar dapat memaksimalkan waktu di tempat wisata. Di sisi lain, metode heuristik particle discrete swarm optimization (DPSO) dan genetic algorithm (GA) merupakan metode yang sering digunakan menyelesaikan kasus vehicle routing problem (VRP) yang identik dengan pencarian solusi rute perjalanan terpendek. Sedangkan, metode clustering K-Means dapat digunakan untuk mengelompokkan titik-titik lokasi wisata menjadi beberapa kelompok berdasarkan jumlah hari berwisata. Oleh karena itu, dengan menggunakan metode heuristik dan metode clustering tersebut, maka pengelompokan tempat wisata dan waktu yang ditempuh dalam perjalanan wisata dapat diminimalkan sehingga waktu yang dihabiskan di tempat wisata menjadi lebih panjang. Metode hybrid tersebut kemudian diimplementasikan ke dalam aplikasi mobile android sebagai media rekomendasi rute perjalanan. Hasil pengujian menunjukkan bahwa metode hybrid-DPSO dapat merekomendasikan rute yang lebih optimal jika dibandingkan dengan rute wisata yang sering digunakan oleh agen wisata dengan nilai 2-13%.References
G. B. Dantzig and J. H. Ramser, “The Truck Dispatching Problem,†Manage. Sci., 1959, doi: 10.1287/mnsc.6.1.80.
J. Ouenniche, P. K. Ramaswamy, and M. Gendreau, “A dual local search framework for combinatorial optimization problems with TSP application,†J. Oper. Res. Soc., vol. 68, no. 11, 2017, doi: 10.1057/s41274-016-0173-4.
M. Prates, P. H. C. Avelar, H. Lemos, L. C. Lamb, and M. Y. Vardi, “Learning to solve NP-Complete problems: A graph neural network for decision TSP,†in 33rd AAAI Conference on Artificial Intelligence, AAAI 2019, 31st Innovative Applications of Artificial Intelligence Conference, IAAI 2019 and the 9th AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, 2019. doi: 10.1609/aaai.v33i01.33014731.
J. Al-Ghamdi, J. A. Al-Ghamdi, and E. R. Al, “Heuristics and Meta-Heuristics optimization methods in solving Traveling Salesman Problem TSP,†Int. J. Adv. Res., no. July, 2020.
M. F. Tasgetiren, P. N. Suganthan, and Q. K. Pan, “A discrete particle swarm optimization algorithm for the generalized traveling salesman problem,†Proc. GECCO 2007 Genet. Evol. Comput. Conf., no. 2, pp. 158–167, 2007, doi: 10.1145/1276958.1276980.
A. L. Chen, G. K. Yang, and Z. M. Wu, “Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem,†J. Zhejiang Univ. Sci., vol. 7, no. 4, pp. 607–614, 2006, doi: 10.1631/jzus.2006.A0607.
A. Kovacs, Solving the Vehicle Routing Problem with Genetic Algorithm and Simulated Annealing in Computer Engineering, no. May. 2008.
D. Cattaruzza, N. Absi, and D. Feillet, “Vehicle routing problems with multiple trips,†Ann. Oper. Res., vol. 271, no. 1, 2018, doi: 10.1007/s10479-018-2988-7.
W. Li, Y. Wu, P. N. R. Kumar, and K. Li, “Multi-trip vehicle routing problem with order release time,†Eng. Optim., vol. 52, no. 8, 2020, doi: 10.1080/0305215X.2019.1642880.
K. Zhang, F. He, Z. Zhang, X. Lin, and M. Li, “Multi-vehicle routing problems with soft time windows: A multi-agent reinforcement learning approach,†Transp. Res. Part C Emerg. Technol., vol. 121, 2020, doi: 10.1016/j.trc.2020.102861.
J. Ochelska-Mierzejewska, A. Poniszewska-Marańda, and W. Marańda, “Selected genetic algorithms for vehicle routing problem solving,†Electron., vol. 10, no. 24, 2021, doi: 10.3390/electronics10243147.
H. Zhou, M. Song, and W. Pedrycz, “A comparative study of improved GA and PSO in solving multiple traveling salesmen problem,†Appl. Soft Comput. J., 2018, doi: 10.1016/j.asoc.2017.12.031.
A. Izzah, I. A. Kusuma, Y. Irawan, and T. A. Cinderatama, “Developing an Android-Based City Tour App using Evolutionary Algorithm,†Int. J. Interact. Mob. Technol., vol. 15, no. 14, pp. 193–203, 2021, doi: 10.3991/ijim.v15i14.20275.
“Solve Traveling Salesman Problem Using Particle Swarm Optimization Algorithm,†Int. J. Comput. Sci. Issues, 2012.
J. Kennedy and R. C. Eberhart, “A discrete binary version of the particle swarm al gorithm.,†Proc. IEEE Int. Conf. Syst. Man, Cybern., vol. 5, pp. 4104–4108, 1997.
R. C. Eberhart and Y. Shi, “Comparison between genetic algorithms and particle swarm optimization,†Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 1447, pp. 611–616, 1998, doi: 10.1007/bfb0040812.
J. Kennedy and R. Eberhart, “Particle swarm optimization,†in IEEE International Conference on Neural Networks - Conference Proceedings, 1995. doi: 10.4018/ijmfmp.2015010104.
M. Clerc, “From Theory to Practice in Particle Swarm Optimization,†2011. doi: 10.1007/978-3-642-17390-5_1.
M. Clerc, “Particle swarms,†in Metaheuristics, 2016. doi: 10.1007/978-3-319-45403-0_8.
B. Korte and J. Vygen, “The Traveling Salesman Problem,†2018. doi: 10.1007/978-3-662-56039-6_21.
M. Jünger, G. Reinelt, and G. Rinaldi, “Chapter 4 The traveling salesman problem,†Handbooks in Operations Research and Management Science. 1995. doi: 10.1016/S0927-0507(05)80121-5.
J. H. Holland, Adaptation in Natural and Artificial Systems. 2019. doi: 10.7551/mitpress/1090.001.0001.
A. Fahim, “K and starting means for k-means algorithm,†J. Comput. Sci., vol. 55, 2021, doi: 10.1016/j.jocs.2021.101445.
T. Phienthrakul, “Clustering Evolutionary Computation for Solving Traveling Salesman Problems,†Int. J. Adv. Comput. Sci. Inf. Technol., vol. 3, no. 3, pp. 243–262, 2014.
G. Developers, “Google Maps Android API | Google Developers,†Google Developers, 2015.
H. Wei, H. Huang, Z. F. Hao, Q. Q. Chen, W. Pedrycz, and G. Li, “A real adjacency matrix-coded evolution algorithm for highly linkage-based routing problems,†Int. J. Bio-Inspired Comput., vol. 18, no. 1, 2021, doi: 10.1504/IJBIC.2021.117426.
R. J. Hijmans, E. Williams, and C. Vennes, “geosphere: Spherical Trigonometry,†Cran, 2019.
