Stochastic Optimization of Urban Bus Schedules Using Graph Neural Networks-Based Traffic Predictions

Efficient public transport scheduling is critical to improving urban mobility, minimizing passenger waiting times, and ensuring resilient service delivery under real-world uncertainties. Traditional scheduling methods often rely on deterministic inputs, failing to account for dynamic traffic conditions and fluctuating passenger demand, which leads to suboptimal service and reduced passenger satisfaction. This thesis presents a novel, data-driven, and stochastic optimization framework for next-day bus timetable planning, integrating advanced forecasting techniques with constraint-based optimization.This master thesis leverages Graph Neural Networks (GNNs) to predict probabilistic traffic speeds across a city’s road network, allowing for the computation of Expected Time of Arrival (ETA) distributions for all bus routes. Simultaneously, in the absence of real-world passenger data, a realistic passenger demand simulation model is developed, using Points of Interest (POIs) and temporal rush-hour dynamics to generate demand distributions per stop. These two probabilistic components—traffic speeds and passenger demand—are combined through stochastic modeling to estimate expected passenger gaps, defined as the number of passengers expected to accumulate at a bus stop during time intervals when no bus service is available. This metric serves as the foundation of the optimization process, capturing the impact of both schedule spacing and demand fluctuations on passenger waiting experience.The optimization model minimizes the weighted average maximum number of unserved passengers at each stop, while respecting operational constraints such as maximum service gaps, vehicle availability, and minimum service requirements at critical stops. Comprehensive experiments were conducted on a real-world inspired dataset of the Thessaloniki bus network (OASTH), validating the approach against heuristic and random scheduling strategies. Com- parative results demonstrate that the proposed method significantly reduces peak passenger waiting times, while remaining computationally feasible for real-world deployment.Additionally, the system’s resilience to traffic anomalies was tested, confirming that stochas- tic scheduling delivers more robust solutions under uncertainty compared to deterministic alternatives. Future work will explore the integration of real passenger data, more complex operational constraints, and adaptive handling of special events and road closures.