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
24.09.2023
653771 byte
Aufsatz (Konferenz)
Elektronische Ressource
Englisch
DOAJ | 2021
|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
|Efficient Timetabling and Vehicle Scheduling for Public Transport
Springer Verlag | 2001
|