An Integer Linear Programming Approach to the Travelling Salesman Problem for Optimizing Self-Drive Tourist Routes in Kuala Lumpur
DOI:
https://doi.org/10.24191/mij.v5i1.916Keywords:
Integer programming, Routing problem, Optimization, TSP, Itinerary planningAbstract
Problem: Self-drive tourism offers tourists the flexibility to explore destinations at their own pace, utilizing private transport. However, it is essential to underscore the significance of thorough planning for a successful and enjoyable experience.
Aims/Objectives: The objective of this research is to explore the concept of travelling salesman problem and its application in optimizing travel routes for self-drive tourists visiting Kuala Lumpur.
Methodology/approach: The study employed an integer linear programming (ILP) model to propose efficient routes that connect all seven notable points of interest in Kuala Lumpur, including the Petronas Twin Towers, Batu Caves, Central Market, Merdeka Square, Bukit Bintang, KL Tower, and Titiwangsa Lake Garden.
Results/finding: Implementation of ILP for suggested routes results in reduction of approximately 36.86% in transportation distance, ultimately leading to a decrease in transportation costs. This demonstrates the effectiveness and efficiency of the proposed approach, enabling tourists to maximize their experience while minimizing time and energy spent navigating congested or inefficient roads.
Implication/impact: This research emphasizes the importance of self-drive tourism and the application of an ILP model in optimizing travel routes for tourists in Kuala Lumpur. By following the suggested routes, visitors can efficiently navigate the city's diverse neighborhoods and transportation options, while enjoying its notable attractions. The significant reduction in transportation distance achieved through this approach highlights its effectiveness in enhancing the travel experience in Kuala Lumpur.
References
W. N. A. W. A. Fatthi, M. H. M. Haris, and H. Kahtan, “Application of travelling salesman problem for minimizing travel distance of a two-day trip in Kuala Lumpur via go kl city bus,” in Advances in Intelligent Systems and Computing, 2019. doi: 10.1007/978-3-030-00979-3_28.
L. Hattingh, “Going out-there: a literature review on drive tourism within the South African context,” African Journal of Hospitality, Tourism and Leisure, vol. 11, no. SpecialEdition, pp. 595–616, 2022, doi: 10.46222/ajhtl.19770720.245.
P. C. Pop, O. Cosma, C. Sabo, and C. P. Sitar, “A comprehensive survey on the generalized traveling salesman problem,” European Journal of Operational Research, vol. 314, no. 3. 2024. doi: 10.1016/j.ejor.2023.07.022.
M. Mosayebi, M. Sodhi, and T. A. Wettergren, “The traveling salesman problem with job-times (TSPJ),” Comput Oper Res, vol. 129, 2021, doi: 10.1016/j.cor.2021.105226.
Z. Hashim and W. R. Ismail, “Applications of travelling salesman problem in optimizing tourist destinations visit in langkawi,” in Regional Conference on Science, Technology and Social Sciences (RCSTSS 2014), 2016. doi: 10.1007/978-981-10-0534-3_25.
Z. Hashim and W. R. Ismail, “Self-drive tourism route in Terengganu: An application of goal programming model,” Sains Humanika, vol. 9, no. 1–5, 2017, doi: 10.11113/sh.v9n1-5.1176.
Z. Hashim, W. L. H. Mat Desa, H. A. Aziz, and N. M. Z. Mohd Zaki, “Greedy method for solving the Langkawi tourist route: A case study,” Journal of Technology and Operations Management, vol. 13, no. 1. 2018, doi: 10.32890/jtom2018.13.1.3.
R. Guo, W. Guan, and W. Zhang, “Route design problem of customized buses: Mixed integer programming model and case study,” J Transp Eng A Syst, vol. 144, no. 11, 2018, doi: 10.1061/jtepbs.0000185.
A. De, M. Gorton, C. Hubbard, and P. Aditjandra, “Optimization model for sustainable food supply chains: An application to Norwegian salmon,” Transp Res E Logist Transp Rev, vol. 161, 2022, doi: 10.1016/j.tre.2022.102723.
A. K. Jha, G. S. Sharma, and N. Kaushik, “Modeling of transport problem in linear programming with python (PULP),” SAMRIDDHI : A Journal of Physical Sciences, Engineering and Technology, vol. 15, no. 01, 2023, doi: 10.18090/samriddhi.v15i01.14.
P. T. Giavarina dos Santos, E. Kretschmann, D. Borenstein, and P. C. Guedes, “Cargo routing and scheduling problem in deep-sea transportation: Case study from a fertilizer company,” Comput Oper Res, vol. 119, 2020, doi: 10.1016/j.cor.2020.104934.
N. Nurdin, T. Taufiq, B. Bustami, M. Marleni, and K. Khairuni, “Optimization model of fishery products supply chain using mixed integer linear programming method,” Journal of Informatics and Telecommunication Engineering, vol. 6, no. 2, 2023, doi: 10.31289/jite.v6i2.8186.
W. Cao and X. Wang, “A multiobjective multiperiod mixed-integer programming optimization model for integrated scheduling of supply chain under demand uncertainty,” IEEE Access, vol. 10, 2022, doi: 10.1109/ACCESS.2022.3183281.
A. Pedram, S. Sorooshian, F. Mulubrhan, and A. Abbaspour, “Incorporating vehicle-routing problems into a closed-loop supply chain network using a mixed-integer linear-programming model,” Sustainability (Switzerland), vol. 15, no. 4, 2023, doi: 10.3390/su15042967.
A. Naeem, S. S. Qurashi, Y. Khan, S. Ahmed, and N. Safwan, “Fiber to the home (FTTH) automation planning, its impact on customer satisfaction & cost-effectiveness,” Wirel Pers Commun, vol. 117, no. 2, 2021, doi: 10.1007/s11277-020-07880-4.
P. Thumrongvut, K. Sethanan, R. Pitakaso, T. Jamrus, and P. Golinska-Dawson, “Application of industry 3.5 approach for planning of more sustainable supply chain operations for tourism service providers,” International Journal of Logistics Research and Applications, vol. 26, no. 11, 2023, doi: 10.1080/13675567.2022.2090529.
V. K. Fedorchenko, O. V. Parubets, L. Y. Krasavtceva, L. V. Hrybova, and O. A. Kruchek, “Mechanisms for the integration of tourism systems: Types, problems, prospects,” Geojournal of Tourism and Geosites , vol. 32, no. 4, 2020, doi: 10.30892/gtg.32406-562.
A. Supithak, W. Supithak, and P. Tosak, “Vehicle scheduling for tourism routing problem,” in 6th International Conference on Business and Industrial Research, ICBIR 2021 - Proceedings, 2021. doi: 10.1109/ICBIR52339.2021.9465844.
S. Li, T. Luo, L. Wang, L. Xing, and T. Ren, “Tourism route optimization based on improved knowledge ant colony algorithm,” Complex and Intelligent Systems, 2022, doi: 10.1007/s40747-021-00635-z.
Y. Zhang, L. Jiao, Z. Yu, Z. Lin, and M. Gan, “A tourism route-planning approach based on comprehensive attractiveness,” IEEE Access, vol. 8, 2020, doi: 10.1109/ACCESS.2020.2967060.
C. E. Silva et al., “Route scheduling system for multiple self-driving cars using k-means and bio-inspired algorithms,” in Communications in Computer and Information Science, 2022. doi: 10.1007/978-3-031-08223-8_3.
R. Carr, R. Ravi, and N. Simonetti, “A new integer programming formulation of the graphical traveling salesman problem,” Math Program, vol. 197, no. 2, 2023, doi: 10.1007/s10107-022-01849-w.
O. Nurdiawan, F. A. Pratama, D. A. Kurnia, Kaslani, and N. Rahaningsih, “Optimization of traveling salesman problem on scheduling tour packages using genetic algorithms,” in Journal of Physics: Conference Series, 2020. doi: 10.1088/1742-6596/1477/5/052037.
S. Zhu, “Multi-objective route planning problem for cycle-tourists,” Transportation Letters, vol. 14, no. 3, 2022, doi: 10.1080/19427867.2020.1860355.
W. L. Winston, Operations Research Applications and Algorithms 4th Edition. 2004.
J. C. Martin, C. Román, P. Moreira, R. Moreno, and F. Oyarce, “Does the access transport mode affect visitors’ satisfaction in a World Heritage City? The case of Valparaiso, Chile,” J Transp Geogr, vol. 91, 2021, doi: 10.1016/j.jtrangeo.2021.102969.
Downloads
Published
Issue
Section
License
Copyright (c) 2024 Nur Azirah Suliman , Noorezatty Mohd Yusop, Nurfaqihah Athirah Mat Janggi , Nur Shamira Shamimi Kamaruddin , Nora Mohd Basir
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
