An approximate bus route planning algorithm

Abstract

Much effort has been put into producing algorithms that solves the transport design problem. As this is a NP-hard problem, algorithms found in literature are typically stochastic and requires a high amount of time to compute. The main purpose of this paper is to propose a fast and deterministic approximate algorithm for bus route planning. In this paper, we will describe the algorithm proposed and show that it produces satisfactory results relative to existing algorithms when applied to Mandl's benchmark. The main advantage of the proposed algorithm is that it is able to provide users with a performance lower bound that is fast to compute. The results may also be used as an initial design where stochastic methods may be applied upon to produce better results. Another possible advantage is that the algorithm may be applied if a fast, ad hoc bus route planning is required; perhaps during festival and different occasions. It can be very useful if commuters are able to check available bus routes whenever they travel. © 2013 IEEE.