Wasserstein distributionally robust shortest path problem

Zhuolin Wang, Keyou You, Shiji Song, Yuli ZhangEur. J. Oper. Res 2020 · DOI

TL;DR

This paper introduces a novel data-driven approach to the shortest path problem that accounts for uncertainty in travel times. By using a Wasserstein ball to define an ambiguity set for travel time distributions, the authors develop a tractable model that offers improved out-of-sample performance and computational efficiency compared to existing methods.

What Problem Does This Paper Address?

The classic shortest path problem assumes deterministic travel times. However, in real-world transportation networks, travel times are inherently uncertain due to factors like traffic, weather, and road conditions. Traditional approaches to handle this uncertainty, such as stochastic shortest path (SSP) models, often require an exact knowledge of the travel time distribution, which is rarely available in practice. Sample-average approximation (SAA) methods can be used to estimate distributions from data, but they can suffer from poor performance when the sample data is limited or of low quality. Distributionally robust optimization (DRO) offers a way to handle this uncertainty by considering a set of possible distributions (an ambiguity set). However, many existing DRO models for shortest paths are computationally intractable or rely on assumptions about known moments of the distribution, which are also difficult to obtain precisely from limited data. This paper addresses the challenge of finding robust shortest paths when only a finite number of travel time samples are available, aiming for a model that is both theoretically sound and computationally efficient.

Methods

The core of this paper is the development of a Wasserstein distributionally robust shortest path (DRSP) model. Instead of assuming a precise distribution, the model considers a Wasserstein ball centered around the empirical distribution of the available travel time samples. This ball represents the set of plausible true distributions, with its radius ($\epsilon_N$) reflecting the confidence in the empirical distribution. A larger radius indicates less confidence and a wider range of possible distributions.

The authors reformulate the problem of minimizing the worst-case mean-excess travel time (METT) over this Wasserstein ball into a solvable mixed 0-1 convex program. This is a significant contribution, as many existing DRSP models are NP-hard. They also explicitly derive the worst-case distribution that achieves the minimum METT, which is valuable for understanding the model's behavior and assessing the quality of the chosen path. The paper also considers the impact of a support set for travel times, defining an interval within which travel times are known to lie, further refining the ambiguity set.

Datasets

The paper uses two main datasets for evaluation:

  • Eastern Massachusetts (EMA) network: This is a standard benchmark network with 74 vertices and 258 links. Travel times for each arc are modeled as a mixture of Gaussian and uniform distributions, with samples generated from these distributions.
  • Real road network (THU to BCIA): This dataset is derived from real traffic data collected from the AMAP service, capturing travel times for 21 common paths between Tsinghua University and Beijing Capital International Airport.

Key Insights and Ideas

  • Wasserstein Ball for Ambiguity: Using a Wasserstein ball as the ambiguity set is a novel approach for DRSP. It directly leverages the empirical distribution and its radius provides a flexible way to hedge against uncertainty based on data quality.
  • Tractable Reformulation: The ability to reformulate the DRSP problem into a mixed 0-1 convex program (specifically, LP or SOCP depending on the norm used) is a major breakthrough, making the problem computationally tractable.
  • Explicit Worst-Case Distribution: Deriving the explicit form of the worst-case distribution is crucial for understanding the model's conservatism and for potential post-hoc analysis of the chosen path.
  • Data-Driven Robustness: The model is inherently data-driven, meaning its robustness is directly tied to the quality and quantity of the available sample data.
  • Asymptotic Consistency: The model is shown to converge to the optimal solution of the true SSP problem as the sample size increases, providing theoretical justification for its use.

Key Results

  • Improved Out-of-Sample Performance: The proposed DRSP model consistently outperforms the SAA method and the moment-based DRSP model in terms of out-of-sample performance across various network sizes and parameter settings. For instance, in Table 3, the DRSP model shows percentage differences of -5.4% and -3.3% compared to SAA for the DRSP and DRSP-S models respectively, indicating better performance.
  • Computational Efficiency: While the DRSP-S model (with support set) can be more computationally intensive for small datasets, the DRSP model (without support set) is shown to be solvable in reasonable times even for large sample sizes, as evidenced by Table 4 and Table 6.
  • Impact of Parameters: Experiments demonstrate that the out-of-sample performance is sensitive to the Wasserstein radius ($\epsilon_N$) and sample size ($N$). An optimal radius exists, and performance generally improves with larger sample sizes, validating the asymptotic consistency.
  • Extensions: The paper successfully extends the DRSP framework to address bi-criteria shortest path problems and minimum cost flow problems, demonstrating its versatility.

Limitations and Future Work

  • Parameter Tuning: The optimal selection of the Wasserstein radius ($\epsilon_N$) is crucial for achieving good out-of-sample performance and requires careful tuning based on the dataset.
  • Computational Complexity of DRSP-S: While the DRSP model is generally efficient, the DRSP-S variant can incur higher computational costs, especially with smaller datasets.
  • Future Work: The paper suggests extending the model to handle more complex scenarios, such as time-dependent travel times and more general ambiguity sets. The authors also highlight the potential for further research into efficient algorithms for solving the derived mixed 0-1 convex programs.

Summary updated

BibTeX
@article{wang2020wasserstein,
  author = {Zhuolin Wang and Keyou You and Shiji Song and Yuli Zhang},
  title = {{Wasserstein distributionally robust shortest path problem}},
  journal = {Eur. J. Oper. Res.},
  year = {2020},
  doi = {10.1016/j.ejor.2020.01.009},
}
Figure