Optimization of Flight Routes Employing the Simulated Annealing Method in the Context of the Indonesian National Airline Industry

Singgih Juniawan; Uti Roysen; Fachrul Alam; Zafitri Zainuddin; Daruki Daruki; Hermawan Taher

doi:10.22441/ijiem.v5i3.21748

Authors

Singgih Juniawan Industrial Engineering Department, Mercu Buana University, Jl. Meruya Selatan No.1, Jakarta Barat 11650, Indonesia http://orcid.org/0009-0007-3239-2730
Uti Roysen Industrial Engineering Department, Mercu Buana University, Jl. Meruya Selatan No.1, Jakarta Barat 11650, Indonesia
Fachrul Alam Industrial Engineering Department, Mercu Buana University, Jl. Meruya Selatan No.1, Jakarta Barat 11650, Indonesia
Zafitri Zainuddin Industrial Engineering Department, Mercu Buana University, Jl. Meruya Selatan No.1, Jakarta Barat 11650, Indonesia
Daruki Daruki Industrial Engineering Department, Mercu Buana University, Jl. Meruya Selatan No.1, Jakarta Barat 11650, Indonesia
Hermawan Taher Computer Science Department, Pakuan University, Jl. Pakuan No. 1, Bogor, Jawa Barat 16129, Indonesia

DOI:

https://doi.org/10.22441/ijiem.v5i3.21748

Keywords:

Route, Optimization, Simulated annealing, Traveling salesman problem, Indonesian national airline industry

Abstract

This research was conducted in the context of significant air traffic growth in Indonesia, where the increasing number of passengers each year presents an opportunity for airlines to expand their route networks and reach more markets. To seize this opportunity, a national airline based in Jakarta conducted internal research to open new flight routes connecting several important cities in Indonesia, namely Jakarta, Kupang, Pangkal Pinang, Pekanbaru, Makassar, and Banjarmasin.This research aims to obtain an optimal flight route that can enhance the effectiveness and efficiency of the planned airline routes. The research utilizes the Simulated Annealing-Traveling Salesman Problem optimization method to achieve this objective. This method is employed to find the best solution in determining the shortest route that includes visits to each destination city.The initial proposed flight route by the airline was Banjarmasin-Pangkal Pinang-Pekanbaru-Jakarta-Kupang-Makassar, with a total distance of 5,127 km. However, the research yielded a different optimal flight route after conducting the optimization process using the Simulated Annealing-Traveling Salesman Problem method. The discovered optimal flight route is Pekanbaru-Pangkal Pinang-Jakarta-Banjarmasin-Makassar-Kupang, with a total distance of 3,256 km. A comparison between the initial and optimal routes reveals that the new route has a 36.49% shorter distance than the initial route.

Downloads

Download data is not yet available.

References

Applegate, D. L., Bixby, R. E., Chvátal, V., & Cook, W. J. (2007). The Traveling Salesman Problem. Princeton University Press.

Ben Ahmed, M., Ghroubi, W., Haouari, M., & Sherali, H. D. (2017). A hybrid optimization-simulation approach for robust weekly aircraft routing and retiming. Transportation Research Part C: Emerging Technologies, 84, 1–20. https://doi.org/10.1016/j.trc.2017.07.010

Botsali, A. R., & Alaykiran, K. (2020). Analysis of TSP: Simulated Annealing and Genetic Algorithm Approaches. International Journal of Computational and Experimental Science and Engineering, 6(1), 23–28. https://doi.org/10.22399/ijcesen.637445

Drezner, Z., & Hamacher, H. W. (2002). Facility Location: Applications and Theory. Springer-Verlag.

Eltoukhy, A. E. E., Chan, F. T. S., & Chung, S. H. (2017). Airline schedule planning: A review and future directions. Industrial Management and Data Systems, 117(6), 1201–1243. https://doi.org/10.1108/IMDS-09-2016-0358

Eltoukhy, A. E. E., Chan, F. T. S., Chung, S. H., Niu, B., & Wang, X. P. (2017). Heuristic approaches for operational aircraft maintenance routing problem with maximum flying hours and man-power availability considerations. Industrial Management and Data Systems, 117(10), 2142–2170. https://doi.org/10.1108/IMDS-11-2016-0475

Ezugwu, A. E. S., Adewumi, A. O., & Frîncu, M. E. (2017). Simulated annealing based symbiotic organisms search optimization algorithm for traveling salesman problem. Expert Systems with Applications, 77, 189–210. https://doi.org/10.1016/j.eswa.2017.01.053

He, Q., Wu, Y.-L., & Xu, T.-W. (2018). Application of improved genetic simulated annealing algorithm in TSP optimization. Kongzhi Yu Juece/Control and Decision, 33, 219–225. https://doi.org/10.13195/j.kzyjc.2016.1666

Hodi, Hi Umar, S., & Fakhrudin, A. (2017). Prediksi Tingkat Pertumbuhan Penumpang Dan Evaluasi pada Bandar Udara Internasional di Indonesia. Jurnal Manajemen Dirgantara, 10(1), 44–52. https://doi.org/10.56521/manajemen-dirgantara.v10i1.29

Jamili, A. (2017). A robust mathematical model and heuristic algorithms for integrated aircraft routing and scheduling, with consideration of fleet assignment problem. Journal of Air Transport Management, 58, 21–30. https://doi.org/10.1016/j.jairtraman.2016.08.008

Jünger, M., Reinelt, G., & Rinami, G. (1995). The Traveling Salesman Problem (Vol. 7, pp. 225–330). Elsevier Science.

Kenan, N., Diabat, A., & Jebali, A. (2018). Codeshare agreements in the integrated aircraft routing problem. Transportation Research Part B: Methodological, 117, 272–295. https://doi.org/10.1016/j.trb.2018.08.008

Kenan, N., Jebali, A., & Diabat, A. (2018). The integrated aircraft routing problem with optional flights and delay considerations. Transportation Research Part E: Logistics and Transportation Review, 118,355–375. https://doi.org/10.1016/j.tre.2018.08.002

Kirkpatrick, S., Gelatt Jr., C. D., & Vecchi, M. P. (1983). Optimization by Simulated Annealing. Science, 220(4598), 671–680. https://doi.org/10.1126/science.220.4598.671

Mahmassani, H. (2017). Optimization in Transportation Systems: Recent Developments and Future Challenges. . Transportation Research Part C: Emerging Technologies, 80, 313–339. https://doi.org/10.1016/j.trc.2017.04.001

Ozdemir, Y., Basligil, H., & Gokhan, K. (2012). Optimization of Fleet Assignment: A Case Study in Turkey. An International Journal of Optimization and Control: Theories & Applications, 2(1), 59–71. https://doi.org/10.11121/ijocta.01.2012.0050

Pahala, F. (2019). Prediksi Lalu-lintas Penumpang Bandar Udara Soekarno-Hatta dengan Teknik Time-series Trend Forecasting. Jurnal Teknologi Dirgantara, 17(1), 45–60. https://doi.org/10.30536/j.jtd.2019.v17.a295

Redi, A. A. N. P., & Redioka, A. A. N. A. (2019). Algoritma Simulated Annealing untuk Optimasi Rute Kendaraan dan Pemindahan Lokasi Sepeda pada Sistem Public Bike Sharing. Jurnal Sistem Dan Manajemen Industri, 3(1), 50. https://doi.org/10.30656/jsmi.v3i1.1473

Rere, L. M. R., Fanany, M. I., & Arymurthy, A. M. (2015). Simulated Annealing Algorithm for Deep Learning. Procedia Computer Science, 72, 137–144. https://doi.org/10.1016/j.procs.2015.12.114

Russell, S. J., & Norvig, P. (2010). Artificial Intelligence : A Modern Approach (3rd ed.). Pearson Education.

Santosa, B. (2017). Pengantar Metaheuristik : Implementasi dengan Matlab (1st ed.). ITS Tekno Sains.

Silalahi, B. P., Sahara, F., Hanum, F., & Mayyani, H. (2022). Simulated Annealing Algorithm for Determining Travelling Salesman Problem Solution and Its Comparison with Branch and Bound Method. 6(3), 601–615. https://doi.org/10.31764/jtam.v6i3.8481

Tang, C. H., & Hsu, Y. L. (2016). Airline flight scheduling for oligopolistic competition with direct flights and a point to point network. Journal of Advanced Transportation, 50(8), 1942–1957. https://doi.org/10.1002/atr.1438

Wang, L., Cai, R., Lin, M., & Zhong, Y. (2019). Enhanced List-Based Simulated Annealing Algorithm for Large-Scale Traveling Salesman Problem. IEEE Access, 7, 144366–144380. https://doi.org/10.1109/ACCESS.2019.2945570