OPTIMALISASI RUTE ANGKUTAN KOTA JALUR AL DI KOTA MALANG MENGGUNAKAN ALGORITMA CHEAPEST INSERTION HEURISTIC PADA TSPTW

Enik Susanti, Sapti Wahyuningsih

Abstract


Travelling Salesman Problem with Time Windows (TSPTW) merupakan varian dari TSP yang dapat digunakan untuk pencarian rute optimal dengan mempertimbangkan total waktu perjalanan, waktu pengiriman, waktu pelayanan, dan waktu kedatangan. Rute optimal untuk angkutan kota ialah jika rute angkutan kota dapat melewati tempat-tempat keramaian seperti pasar tradisional, swalayan, kampus, dan rumah sakit yang memungkinkan angkutan kota menjangkau banyak penumpang. Fokus pembahasan artikel ini adalah menentukan rute optimum angkutan kota jalur AL di Kota Malang menggunakan algoritma Cheapest Insertion Heuristic pada TSPTW dan alat bantu TSP-VRP. Hasil perhitungan algoritma dengan Cheapest Insertion Heuristic diperoleh total jarak sebesar 35.95 km dan total waktu tempuh 149 menit dan menggunakan alat bantu program diperoleh total jarak sebesar 35.95 km dan total waktu tempuh 141 menit. Dengan penelitian ini dapat ditunjukkan salah satu penerapan dari teori graf yakni untuk menentukan rute optimum suatu transportasi.


Full Text:

PDF

References


M. Gunduz and M. Aslan, “DJAYA: A discrete Jaya algorithm for solving traveling salesman problem,” Appl. Soft Comput., vol. 105, p. 107275, 2021, doi: 10.1016/j.asoc.2021.107275.

İ. Küçükoğlu, R. Dewil, and D. Cattrysse, “Hybrid simulated annealing and tabu search method for the electric travelling salesman problem with time windows and mixed charging rates,” Expert Syst. Appl., vol. 134, pp. 279–303, 2019, doi: 10.1016/j.eswa.2019.05.037.

O. Cheikhrouhou and I. Khoufi, “A comprehensive survey on the Multiple Traveling Salesman Problem: Applications, approaches and taxonomy,” Comput. Sci. Rev., vol. 40, p. 100369, 2021, doi: 10.1016/j.cosrev.2021.100369.

X. Bao, Z. Liu, W. Yu, and G. Li, “A note on approximation algorithms of the clustered traveling salesman problem,” Inf. Process. Lett., 2017, doi: 10.1016/j.ipl.2017.07.003.

Y. Yuan, D. Cattaruzza, M. Ogier, and F. Semet, “A branch-and-cut algorithm for the generalized traveling salesman problem with time windows,” Eur. J. Oper. Res., vol. 286, no. 3, pp. 849–866, 2020, doi: 10.1016/j.ejor.2020.04.024.

R. Suganda, E. Sutrisno, and I. W. Wardana, “Optimalisasi Travelling Salesman with Time Windows (TSPTW) Dengan Algoritma Semut,” J. Chem. Inf. Model., vol. 53, no. 9, pp. 1689–1699, 2013.

M. López-Ibáñez and C. Blum, “Beam-ACO for the travelling salesman problem with time windows,” Comput. Oper. Res., 2018, doi: 10.1016/j.cor.2009.11.015.

N. Boland, M. Hewitt, D. M. Vu, and M. Savelsbergh, “Solving the traveling salesman problem with time windows through dynamically generated time-expanded networks,” Lect. Notes Comput. Sci., vol. 10335 LNCS, no. June, pp. 254–262, 2017, doi: 10.1007/978-3-319-59776-8_21.

D. Rachmawati and Wilyanto, “Implementation of Modified Cheapest Insertion Heuristic on Generating Medan City Tourism Route,” J. Phys. Conf. Ser., vol. 1566, no. 1, 2020, doi: 10.1088/1742-6596/1566/1/012076.

L. V. Hignasari and E. D. Mahira, “Optimization Of Goods Distribution Route Assisted By Google Map With Cheapest Insertion Heuristic Algorithm (CIH),” Sinerg. Press, vol. 22, p. 2, 2018, doi: 10.22441/sinergi.2018.2.010.


Refbacks

  • There are currently no refbacks.