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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Accelerating Model Solving for Integrated Optimization of Timetabling and Vehicle Scheduling based on Graph Convolutional Network


    Contributors:
    Liu, YeCheng (author) / Chen, Xu (author) / Xu, YongXin (author) / Xiang, Dong (author) / Mo, LinJian (author)


    Publication date :

    2023-09-24


    Size :

    653771 byte





    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English




    Integrated Bus Timetabling, Vehicle Scheduling, and Crew Scheduling with a mutation-based evolutionary scheme

    Mertens, Lucas / Amberg, Bastian / Kliewer, Natalia | Elsevier | 2024

    Free access

    Solving School Timetabling Problems by Microcanonical Optimization (abstract)

    Souza, M. J. F. / Maculan, N. / Ochi, L. S. | British Library Conference Proceedings | 2000


    Combined Timetabling and Vehicle Scheduling for Electric Buses

    QUTTINEH, N-H. / HÄLL, C. H. / EKSTRÖM, J. et al. | TIBKAT | 2017


    Integrated Model of Airport Shuttle Bus Timetabling and Scheduling Based on Improved SPEA2

    Wang, Ning / Fan, Dengke / Dong, Hongxia et al. | ASCE | 2025