Hamilton Graph Application on the Shortest Path Routing Trans Metro Bandung

Yusuf Ibrahim Abdallah, Yani Ramdani, Yurika Permanasari

Abstract


The bus ride Trans Metro Bandung (TMB) corridor 1 and 2 can be formulated into the form of graphs to find the closest from a terminal to shelters that must be passed exactly once, and had to go back to the terminal of origin is a very important issue. It is an attempt to streamline the process within the transportation system. This trip bus transportation system could be modeled in a graph with symbols the point (Vertex)as ashelter and symbols the line (edge) as a line connect between the shelters. Routes TMB bus trip into the graph a closed path is called Cycle Hamilton. As for determining the shortest route from the TMB trip used two methods: Sequential Insertion and Nearest Neighbor. The results of route calculations and searches TMB corridor 1 and 2 yield different routes and distances from beginning of route and distance. Corridor 1 has the original route A-B-C-D-E-F-G-H-I-J-K-L-M-N-O-P-Q-R-S-T-U-V-W-X-Y-A with a total distance of 44.4 km and the route alternative is A-C-D-E-F-G-H-I-J-K-L-M-N-O-P-Q-R-S-T-U-V-W-X-Y-A with a total distance of 42.95 km. Corridor 2 has the same beginning and alternatives is  A-B-C-D-E-F-G-H-I-J-K-L-M-N-O-P-Q-R-S-T-U-V-A with the difference in a total distance is 28.4 km and 26.2 km because side F-G has two sides with a distance of 1 km and 2.2 km.


Keywords


Graph Hamilton, Shortest Path, Sequential Insertion, Nearest Neighbor, Trans Metro Bandung.

References


Budayasa., 2007, Teori Graf dan Aplikasinya. Surabaya: Unesa University Press.

Chairul., 2014, Jurnal Institut Teknologi Nasional. Penentuan Rute Kendaraan Distribusi Produk Roti Menggunakan Metode Nearest Neighbor dan Sequential insertion.

Kreyzig, E., 1993, Matematika Teknik Lanjutan. Jakarta: Gramedia Pustaka Utama.

Madonna, E., 2013, Jurnal Elektron. Aplikasi Metode Nearest Neighbour pada Penentuan Jalur Evakuasi Terpendek untuk Daerah Rawan Gempa dan Tsunami, 45-46.

Sutarno, H., 2005, Matematika Diskrit. Malang: Universitas Negeri Malang.

Ramdani, Yani., 2014, Pembelajaran dengan Scientific Debate untuk Meningkatkan Kemampuan Berpikir Kreatif Mahasiswa, Mimbar Vol. 30 No. 1




Flag Counter