Hamilton Graph Application on the Shortest Path Routing Trans Metro Bandung

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.