A Novel Approach to the Optimization of a Public Bus Schedule Using K-Means and a Genetic Algorithm

Abstract

With the continuing economic growth of developing countries, the populations of their urban areas are increasing dramatically. In view of this trend, the optimization of bus service scheduling has become an important task. The efficiency of a transport system depends on several different planning processes, and the balance between these elements is rather complex. In this paper, we consider timetabling and vehicle allocation as the bases for our work. With the aim of providing a reliable service to passengers at a reasonable cost, we focus on the optimization of a bus schedule using a method based on K-means and a genetic algorithm. Our approach starts with parameter setting and data preparation, using a dataset of real bus operating schedules. Three elements are identified from this dataset: the time zones in which the bus service operates, the number of stops made by each bus in each trip, and the dwell time at bus stops. K-means clustering is used to identify moderate operation conditions. The outcome of the K-means algorithm is used as the objective fitness value for optimization of the bus schedule using a genetic algorithm. The results of experiments show that the proposed optimization model can improve the dwell time while maintaining the operating cost at its current level or less, and a remarkable increase in the operation rate is achieved in the case study. The proposed model is able to both effectively optimize the financial outlay and enable bus operators to meet passenger demand in a mutually satisfactory way.

Keywords

• Bus service reliability
• clustering methods
• genetic algorithm
• K-means
• optimal scheduling
• optimization