Enhanced Route Planning with Calibrated Uncertainty Set

Lingxuan Tang, Rui Luo, Zhixin Zhou, Nicolo Colombo · 2025

Read Enhanced Route Planning with Calibrated Uncertainty Set by Lingxuan Tang, Rui Luo, Zhixin Zhou, Nicolo Colombo (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-10088.txt.

Introduction

Lingxuan Tang and co-authors add honest error bounds to route planning in a 2025 paper. Drivers and dispatchers need routes that hold up when travel times shift. A forecast without a sense of its own error can lead to poor choices.

Their method pairs a graph-based autoencoder with a conformal method that wraps forecasts in a range. The range comes with a coverage promise, so users know how much to trust it. Planners then choose routes that stay good across that whole range. On a real traffic case, the method beat baseline tools by a clear margin. The authors see it as a step toward smarter transport systems that plan under doubt, not false certainty.

Catalog record

CREATORLingxuan Tang, Rui Luo, Zhixin Zhou, Nicolo Colombo
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE35 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-10088

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Enhanced Route Planning with Calibrated Uncertainty Set Lingxuan Tang, Rui Luo, Zhixin Zhou, Nicolo Colombo Abstract This paper investigates the application of probabilistic prediction methodologies in route planning within a road network context. Specifically, we introduce the Conformalized Quantile Regression for Graph Autoencoders (CQR-GAE), which leverages the conformal prediction technique to offer a coverage guarantee, thus improving the reliability and robustness of our predictions. By incorporating uncertainty sets derived from CQR-GAE, we substantially improve the decision-making process in route planning under a robust optimization framework. We demonstrate the effectiveness of our approach by applying the CQR-GAE model to a real-world traffic scenario. The results indicate that our model significantly outperforms baseline methods, offering a promising avenue for advancing intelligent transportation systems. August 24, 2026 K eywords Route planning, robust optimization, covariate information, conformal prediction, quantile regression 1 Introduction The route planning problem involves determining the most effective paths for a vehicle or a set of vehicles, taking into account various limitations and goals. This issue is crucial in logistics, transportation, and delivery services, where the efficiency of the routes chosen has a direct effect on the economic success and the quality of service provided. Route planning problems that account for uncertainty are fundamental to intelligent transportation systems and have garnered growing interest. Existing stochastic shortest path models require the exact probability distributions for travel times and often assume independence between these times. Nonetheless, these distributions are frequently unavailable or imprecise due to insufficient data, and the existence of correlations between travel times on various links has been noted ( Zhang et al., 2017 ) . Contextual data ( Patel et al., 2023 ; Qi et al., 2020 ; Guo et al., 2023 ; Sadana et al., 2023 ) represents some relevant features that correlate with the unknown uncertainty parameter, which is revealed to assist the decision making under uncertainty. The presence of this contextual data enables the creation of a prediction model to forecast the uncertainty, which in turn informs the development of an uncertainty set within the optimization model. Advances in graph machine learning techniques offer an opportunity to harness this contextual information within the traffic network, enhancing the uncertainty predictions. In graph machine learning, the interaction between nodes is captured by edges with associated weights. In a traffic network, where junctions are depicted as nodes and road sections as edges, the edge weights can represent the traffic capacity of each road. The prediction of the edge weights is thus vital to modeling the uncertainty within the transportation system. Graph Neural Networks (GNNs) have been successfully used in node classification and link prediction tasks. In this work, we consider their application to edge weight prediction. Edge weight prediction has found use in diverse domains such as message volume prediction in online social networks ( Hou and Holder, 2017 ) , forecasting airport transportation networks ( Mueller, 2023 ) , and assessing trust in Bitcoin networks ( Kumar et al., 2016 ) . These examples highlight the wide-ranging applicability and importance of edge weight prediction and load forecasting techniques in different network-based systems. 2 Related Works 2.1 Robust Optimization for Networks Robust optimization for networks is a rapidly evolving field that aims to address decision-making problems in network settings under uncertainty. Recent advancements in this field have focused on combining prediction algorithms and optimization techniques to solve decision-making problems in the face of uncertainty ( Sadana et al., 2024 ; Patel et al., 2024 ) . Sun et al. ( Sun et al., 2024 ) developed the Contextual Predict-then-Optimize (CPO) framework combining probabilistic weather prediction and risk-sensitive value to provide less conservative robust decision-making under uncertainty in network optimization. Incorporating uncertainty on the weight of edges in a graph-based network has been explored through random variables. Previous studies have employed Monte Carlo programming ( Frank, 1969 ) and normal distribution ( Chen et al., 2013 ) to model the uncertainty of edge weights and approach the optimal shortest path. Chassein et al. ( Chassein et al., 2019 ) proposed a data-driven approach for robust shortest-path problems in a road network. Experiment results on the Chicago traffic dataset demonstrate that ellipsoidal uncertainty sets performed well, and the authors propose using axis-parallel ellipsoids (ignoring correlations) which allows the development of a specialized branch-and-bound algorithm that significantly outperforms a generic solver. However, the properties of conventional random variables are unable to accurately deliver the characteristics of uncertainty. Recent studies have introduced data-driven robust optimization, which generates uncertainty representations from existing observational data ( Bertsimas et al., 2018 ; Chassein et al., 2019 ) . Robust optimization focuses on optimizing under the worst-case scenario disregarding other information about the uncertainty distribution. To address this limitation, Zhang et al. ( Zhang et al., 2017 ) propose the utilization of \alpha -reliable parameters to regulate the level of robustness, aiming to achieve a robustness degree of 1-\alpha . 2.2 Traffic Prediction Many existing studies on traffic forecasting primarily focus on developing deterministic prediction models ( Bui et al., 2022 ) . Derrow et al. ( Derrow-Pinion et al., 2021 ) demonstrates successful application of GNNs in travel time predictions in Google Maps. The model represents the road network as a graph, where each route segment is a node and edges exist between consecutive segments or segments connected via an intersection. The message passing mechanism of GNN enables us to handle not only traffic ahead or behind us, but also along adjacent and intersecting roads Traffic applications, however, often require uncertainty estimates for future scenarios. Zhou et al. ( Zhou et al., 2020 ) incorporate the uncertainty in the node representations. In ( Xu et al., 2023 ) , a Bayesian ensemble of GNN models combines posterior distributions of density forecasts for large-scale prediction. ( Maas and Bloem, 2020 ) combine Quantile Regression (QR) and Graph WaveNet to estimate the quantiles of the load distribution. Traditionally, traffic forecasting is approached as a node-level regression problem ( Cui et al., 2019 ; Jiang and Luo, 2022 ) , i.e. nodes and edges in a graph represent monitoring stations and their connections. We adopt an edge-centric approach, i.e. we predict traffic flow over road segments through edge regression. Interestingly, the strategy aligns with several real-world setups, e.g. the Smart City Blueprint for Hong Kong 2.0, which emphasizes monitoring road segments (edges) rather than intersections (nodes) ( Officer, 2019 ) . 2.3 Conformal Prediction Conformal prediction (CP) ( Vovk et al., 2005 ) , is a methodology designed to generate prediction regions for variables of interest, thereby enabling the estimation of model uncertainty by substituting point predictions with prediction regions. This methodology has been widely applied in both classification ( Luo and Zhou, 2024 ; Luo and Colombo, 2024 ; Luo and Zhou, 2024a ) and regression tasks ( Luo and Zhou, 2024b ; Luo and Zhou, 2025 ) . Recently, the application of CP has broadened significantly across various domains, including pandemic-driven passenger booking systems ( Werner et al., 2021 ) , smartwatch-based detection of coughing and sneezing events ( Nguyen and Luo, 2018 ) , and model calibration in the scikit-learn library ( Sweidan and Johansson, 2021 ) . The conventional approach for CP uncertainty estimation presumes the

Read the complete text