A scheduling model and a solution algorithm for inter-city bus carriers

The setting of timetables and bus routing/scheduling are essential to an inter-city bus carrier's profitability, its level of service and its competitive capability in the market. In the past, carriers in Taiwan usually set their timetables and bus routes/schedules manually, which was inefficient. In this research we thus attempt to develop a model that will help Taiwan inter-city bus carriers in timetable setting and bus routing/scheduling. The model employs multiple time–space networks that can formulate bus movements and passenger flows and manage the interrelationships between passenger trip demands and bus trip supplies to produce the best timetables and bus routes/schedules. Mathematically, the model is formulated as a mixed integer multiple commodity network flow problem. An algorithm, based on Lagrangian relaxation, a sub-gradient method, the network simplex method, a Lagrangian heuristic and a flow decomposition algorithm, is developed to efficiently solve the problem. The results of a case study, regarding a major Taiwan inter-city bus operation, illustrate the model performance.