Flex-route buses scheduling based on priority topological sorting

Abstract

In order to improve the service level of flex-route buses, a scheduling method based on station priority topology sequencing is proposed. According to the travel needs, the directed acyclic graph (DAG) is determined, and the station priority is calibrated based on the convenience of arrival, node degree, demand for boarding, and alighting, etc. The only topological order of station demand processing is obtained finally. A scheduling model aiming at minimizing travel costs of buses and generalized travel costs of passengers is established, which is optimized by genetic algorithm based on topological sorting. Using No.385 bus in Tianjin city as an example, the results show that compared with the traditional scheduling method and the method with topological sequencing of demand but without considering priority. The travel cost of buses per passenger of our scheduling method is reduced by 11.87% and 6.85% respectively, and the generalized travel cost per passenger is reduced by 9.06% and 3.28% respectively when the travel demand level is higher than expected. This method can effectively improve the service quality and profitability of flex-route buses, and has lower per capita driving cost and per capita generalized travel cost, as well as lower reservation rejection rate.

Keywords

• transportation engineering
• public transit
• flex-route buses
• scheduling
• priority
• topological sorting