Application Of Min-Plus Algebra in Determining the Shortest Route for Semarang Feeder Buses

Source abstract

Feeder buses extend the Bus Rapid Transit (BRT) network of Semarang City to areas that the BRT cannot reach, yet their routes are rarely reviewed against travel time, which determines service efficiency and fuel use. This study applies min-plus algebra to find the shortest feeder bus routes because it represents a weighted directed network as a matrix and gives the earliest and the latest travel time to every stop in one computation, so that the stops lying on a shortest route can be identified. The aims were (1) to model two feeder routes as weighted directed simple graphs and adjacency matrices, (2) to determine the optimal route on each, and (3) to implement the computation in Python with Google Colab. Distances, travel times, and average bus speeds (18 and 17 km/h) were collected by field observation for the route from the BNI UNNES bus stop to Bandarjo Market (15 vertices) and for the route from the Semarang State Polytechnic to Banyumanik Terminal (20 vertices). The shortest route of the first network takes 35.63 minutes over 10.48 km, and that of the second takes 21.67 minutes over 6.14 km. Both differ from the current feeder bus routes and are proposed as route alternatives, to be validated against traffic conditions and passenger demand. The Python implementation reproduced the manual calculation and can be reused for larger networks.