We study the integrated optimization of timetabling and vehicle scheduling for typical two-way bus lines in public bus transportation. A novel Mixed Integer Linear Programming (MILP) model is built for the integrated problem, where some real-life and complex operational constraints, e.g., the upper limits of headways in different time periods, lunch breaks, and max working time, are considered. Since the integrated problem itself is NP-Hard and is difficult to be solved efficiently by off-the-shelf open source solvers, we especially propose a novel approach based on Graph Convolutional Network(GCN) to explore the correlations between problem structures and the resulting solution values. In this methodology, an integrated problem instance is represented as a trip chain graph, and a supervised GCN is trained to predict the solution value of partial binary variables which are hard to determine during problem solving. The values of predicted variables will be fixed and the remaining subMILP with smaller search space can be solved faster than the original MILP. To our knowledge, this is the first time machine learning techniques have been used to accelerate the joint solving of timetabling and vehicle scheduling in literature. Our computational evaluations of 100 real problem instances show that the GCN-based methodology outperforms existing solvers, reducing average wall-clock time by 20% while achieving better solution quality.
Accelerating Model Solving for Integrated Optimization of Timetabling and Vehicle Scheduling based on Graph Convolutional Network
2023-09-24
653771 byte
Conference paper
Electronic Resource
English
Elsevier | 2024
|Solving School Timetabling Problems by Microcanonical Optimization (abstract)
British Library Conference Proceedings | 2000
|Combined Timetabling and Vehicle Scheduling for Electric Buses
TIBKAT | 2017
|