OPTIMALISASI RUTE ANGKUTAN KOTA MALANG DENGAN ALGORITMA CHEAPEST INSERTION HEURISTIC PADA TSPTW

Ana Hamimatul Mangdhuroh, Sapti Wahyuningsih

Abstract


Travelling Salesman Problem (TSP) kajian teori graph yang dapat digunakan untuk menentukan rute optimal. Travelling Salesman Problem with Time Windows (TSPTW) adalah varian TSP dengan tambahan interval waktu. Fokus pembahasan artikel ini menyelesaikan permasalahan rute angkutan kota Malang jalur AMG (Arjosari Madyopuro Gadang) dengan total waktu perjalanan minimum dengan algoritma Cheapest Insertion Heuristic (CIH) pada TSPTW dan alat bantu program. Kinerja algoritma CIH yaitu mencari suatu sikel Hamilton yang memiliki total bobot minimum. Pencarian rute optimum dapat direpresentasikan kedalam Graf dengan titik pada graf merepresentasikan tempat pemberhentian angkutan kota dan bobot isi merepresentasikan jarak antar tempat pemberhentian. Hasil perhitungan rute angkutan kota jalur AMG dengan algoritma CIH 29.70 km dan hasil perhitungan dengan aplikasi TSP-VRP 29.70 km. Permasalahan rute optimal dengan tambahan variabel waktu dapat diselesaikan dengan algoritma pada TSPTW.


Full Text:

PDF

References


T. Ma, H. Wang, L. Zhang, Y. Tian, and N. Al-Nabhan, “Graph classification based on structural features of significant nodes and spatial convolutional neural networks,” Neurocomputing, vol. 423, pp. 639–650, Jan. 2021, doi: 10.1016/j.neucom.2020.10.060.

Y. Wang and Z. Han, “Ant colony optimization for traveling salesman problem based on parameters optimization,” Appl. Soft Comput., vol. 107, p. 107439, Aug. 2021, doi: 10.1016/j.asoc.2021.107439.

N. Boland, M. Hewitt, D. M. Vu, and M. Savelsbergh, “Solving the Traveling Salesman Problem with Time Windows Through Dynamically Generated Time-Expanded Networks,” in Integration of AI and OR Techniques in Constraint Programming, vol. 10335, D. Salvagnin and M. Lombardi, Eds. Cham: Springer International Publishing, 2017, pp. 254–262. doi: 10.1007/978-3-319-59776-8_21.

R. F. da Silva and S. Urrutia, “A General VNS heuristic for the traveling salesman problem with time windows,” Discrete Optim., vol. 7, no. 4, pp. 203–211, Nov. 2010, doi: 10.1016/j.disopt.2010.04.002.

R. Hassin and A. Keinan, “Greedy heuristics with regret, with application to the cheapest insertion algorithm for the TSP,” Oper. Res. Lett., vol. 36, no. 2, pp. 243–246, Mar. 2008, doi: 10.1016/j.orl.2007.05.001.

I. Mulyasari, “Optimasi Rute Distribusi Barang Pos Dari Kantor Pos Blitar ke KCP Wilayah Barat Menggunakan Metode traveling salesman problem with time windows (TSP-TW).” 2018.

S. Wahyuningsih, D. Satyananda, and D. Hasanah, “KAJIAN KARAKTERISTIK SOLUSI VARIAN TRAVELING SALESMAN PROBLEM (TSP) DAN APLIKASINYA,” no. 978, p. 9, 2015.

I. Kara and T. Derya, “Formulations for Minimizing Tour Duration of the Traveling Salesman Problem with Time Windows,” Procedia Econ. Finance, vol. 26, pp. 1026–1034, 2015, doi: 10.1016/S2212-5671(15)00926-0.

A. Bretin, G. Desaulniers, and L.-M. Rousseau, “The traveling salesman problem with time windows in postal services,” J. Oper. Res. Soc., vol. 72, no. 2, pp. 383–397, Feb. 2021, doi: 10.1080/01605682.2019.1678403.

L. V. Hignasari and E. D. Mahira, “OPTIMIZATION OF GOODS DISTRIBUTION ROUTE ASSISTED BY GOOGLE MAP WITH CHEAPEST INSERTION HEURISTIC ALGORITHM (CIH),” SINERGI, vol. 22, no. 2, p. 132, Jun. 2018, doi: 10.22441/sinergi.2018.2.010.

Q. Lu and M. M. Dessouky, “A new insertion-based construction heuristic for solving the pickup and delivery problem with time windows,” Eur. J. Oper. Res., vol. 175, no. 2, pp. 672–687, Dec. 2006, doi: 10.1016/j.ejor.2005.05.012.

L. V. Hignasari, “Komparasi Algoritma Cheapest Insertion Heuristic (CIH) Dan Greedy Dalam Optimasi Rute Pendistribusian Barang,” J. Ilm. Vastuwidya, vol. 2, no. 2, pp. 31–39, Jun. 2020, doi: 10.47532/jiv.v2i2.87.


Refbacks

  • There are currently no refbacks.