Optimization of public transport bus scheduling using kmeans and genetic algorithm

Abstract

Along with economic growth in the developing countries, the population of urban areas is increasing tremendously. Alongside this, the public transport bus service is expected to develop with the growth of urbanization. For that reason, optimization of the scheduling of public transport such as public buses is an important task in the operation of public transport. In scheduling public transport operations, it is difficult to plan for optimal service provision that can apply to different travel areas, time zones, cycle frequency, and scheduling of vehicles and crew. Basically, public transport design consists of four plans: network design, timetabling, vehicle scheduling, and crew scheduling. The timetabling is important in those plans for financial reasons as well as meeting passenger demand for a reliable service. Several methods have been proposed to deal with the task of public transport scheduling. For example, some research has been conducted to shorten the waiting time of passengers and to review cycles in areas where there are few passengers, but these still could not meet the passenger demand. Therefore, providing the optimum scheduling of public transport, designed accurately according to the demand, is a means to shorten the waiting time of passengers and eliminate useless bus cycles. This research started with investigating and clustering the time zones by using K-means based on the collected GPS data of public buses. The GPS data was processed to produce three attributes known as “Time”, “Volume” and “Quality”. Then, a genetic algorithm was implemented to optimize the public transport scheduling. The result of the experiment shows that the proposed optimization method increases the frequency of bus cycles during peak passenger hours in some time zones and conversely reduces the frequency of bus cycles for low passenger hours. The proposed method is able to both optimize the financial benefit and meet passenger demand. The result of the experiments shows that the proposed method is better than existing methods, increasing by about 30% the optimization accuracy. The dataset for the experiments used was GPS Public Bus in Okinawa, Japan.