Routing Optimization Under Uncertainty

Patrick Jaillet, Jin Qi, Melvyn SimOper. res 2016 · DOI

TL;DR

This paper introduces a novel "Requirements Violation (RV) Index" to quantify the risk of routing solutions failing to meet specified requirements under uncertainty. It then develops a robust optimization framework and efficient algorithms to find optimal routing solutions that minimize this risk, offering a more nuanced approach than traditional methods.

What Problem Does This Paper Address?

Real-world routing problems, from logistics to network design, are inherently uncertain. Travel times, customer demands, and other factors can fluctuate, making it challenging to find optimal routes that guarantee desired outcomes. Traditional approaches often rely on deterministic models or simplistic probabilistic assumptions, which can lead to overly conservative or unreliable solutions. This paper tackles the critical challenge of optimizing routing decisions when faced with uncertainty, aiming to provide solutions that are not only efficient but also robust and adaptable to unforeseen circumstances. Specifically, it addresses the need for a precise way to define and manage the risk associated with violating requirements (like time windows) when the exact probability distributions of uncertain parameters are unknown or only partially characterized.

Methods

The core contribution of this paper is the Requirements Violation (RV) Index. This index quantifies the risk of a solution failing to meet specified requirements by considering both the frequency and magnitude of violations. It's designed to be sensitive to the severity of deviations, unlike simpler probability-based measures.

The authors then embed this index within a distributionally robust optimization framework. Instead of assuming a single, known probability distribution for uncertain parameters, they consider a set of possible distributions (an ambiguity set) characterized by descriptive statistics like moments. This allows for less conservative solutions than traditional robust optimization, which often ignores distributional information.

To solve the resulting optimization problems, they develop efficient algorithms based on Benders decomposition. This technique breaks down the complex problem into smaller, more manageable subproblems, making it computationally tractable. They also introduce a multi-commodity flow formulation to derive arrival times as linear functions of uncertain travel times, which is crucial for calculating the RV Index.

Datasets

Not discussed in the paper. The paper focuses on a theoretical framework and algorithmic development, with computational studies using randomly generated networks.

Key Insights and Ideas

  • Quantifying Risk Beyond Probability: The RV Index is a significant step beyond simply minimizing the probability of violation. It explicitly accounts for how bad a violation is, leading to more practical and risk-aware decisions.
  • Bridging Deterministic and Probabilistic Approaches: The distributionally robust framework offers a middle ground. It leverages available distributional information (like moments) without requiring full knowledge, leading to less conservative and more efficient solutions than pure robust optimization.
  • Tractable Optimization for Uncertainty: The development of Benders decomposition and multi-commodity flow formulations demonstrates that complex routing problems under uncertainty can be solved efficiently, making the proposed framework practical for real-world applications.
  • Worst-Case vs. RV Index: The computational study highlights that purely worst-case approaches can be overly conservative, while the RV Index provides a more balanced trade-off between risk and performance.

Key Results

The paper presents a novel RV Index and a general mathematical framework for routing optimization under uncertainty. They demonstrate its application to vehicle routing with uncertain travel times and soft time windows, and also to a stochastic shortest path problem with a deadline.

Key findings from their computational studies include:

  • The RV Index model provides solutions that are less risky (lower lateness probability and expected lateness) compared to other criteria like minimizing average travel time or maximizing arrival probability.
  • While the RV Index might yield slightly longer average travel times, it significantly reduces the standard deviation of lateness, indicating more reliable performance.
  • The proposed RO algorithm is computationally efficient, capable of solving moderate-sized problems within reasonable time limits. For instance, it can handle networks with 100 nodes and 450 arcs.
  • The RV Index approach is shown to be more robust and performant than other selection criteria in a comparative study of stochastic shortest path problems with deadlines.

Limitations and Future Work

The authors acknowledge that the computational complexity of their approach can still be significant, especially for larger or more complex networks. They suggest that further improvements in algorithmic efficiency, particularly for solving the subproblems within the Benders decomposition, could be achieved through techniques like branch-and-cut.

Future work could explore:

  • Extending the framework to account for correlations between uncertain parameters, which is a significant challenge in real-world scenarios.
  • Investigating more complex uncertainty sets and distributions.
  • Applying the framework to a wider range of routing problems and real-world applications.
  • Developing more advanced algorithms for solving the subproblems to further improve computational efficiency.

Summary updated

BibTeX
@article{jaillet2016routing,
  author = {Patrick Jaillet and Jin Qi and Melvyn Sim},
  title = {{Routing Optimization Under Uncertainty}},
  journal = {Oper. res},
  year = {2016},
  doi = {10.1287/opre.2015.1462},
}
Figure