Stochastic service network design with rerouting

Ruibin Bai, Stein W. Wallace, Jingpeng Li, Alain Yee‐Loong ChongTransportation 2014 · DOI

TL;DR

This paper introduces a novel stochastic programming model for freight service network design that explicitly incorporates vehicle rerouting as a strategy to handle demand uncertainty, in addition to traditional outsourcing. The model aims to find a balance between network setup costs and operational costs, offering greater flexibility and potentially reducing reliance on costly outsourcing.

What Problem Does This Paper Address?

The freight transportation industry faces a significant challenge in designing service networks that can effectively handle unpredictable demand fluctuations. Traditional approaches often struggle to balance the costs of establishing a robust network (setup costs) with the costs of operating it under varying conditions (operational costs). While some research has addressed this by incorporating uncertainty through scenarios and allowing for outsourcing, this paper highlights that rerouting is a common and often preferred strategy for freight companies to adapt to unforeseen changes. The problem is that existing models don't adequately capture this rerouting flexibility, potentially leading to suboptimal network designs that either over-invest in capacity or rely too heavily on outsourcing, which can harm long-term market share.

Methods

The core contribution is a new two-stage stochastic programming model (M-Stoch2) that extends a previous model (M-Stoch1) by explicitly including vehicle rerouting.

  • Deterministic Model (M-Determ): A baseline model representing the problem without uncertainty.
  • Stochastic Model with Outsourcing (M-Stoch1): The existing model that handles uncertainty by allowing for outsourcing.
  • Proposed Stochastic Model with Rerouting and Outsourcing (M-Stoch2): This is the novel model. It introduces new integer variables to represent the increase or decrease of vehicles on arcs in the second stage (operational phase) to handle demand variations. It also retains the outsourcing option. The model aims to minimize the sum of fixed network costs and expected operational costs, which now include rerouting and outsourcing.

Due to the computational complexity of M-Stoch2, the authors also propose and evaluate two decomposition-based heuristics:

  • Determ-Stoch2: Uses a deterministic network design (M-Determ) and then applies M-Stoch2's second stage with rerouting.
  • Stoch1-Stoch2: Uses a stochastic network design (M-Stoch1) and then applies M-Stoch2's second stage with rerouting.

Datasets

The paper uses two sets of instances for evaluation:

  • Set-LTL8: A smaller set of instances adapted from Lium et al. (2009), consisting of 9 commodity sets, 6 nodes, 5 periods, and 8 commodities per set. This set was used for detailed analysis and comparison of the models.
  • Set-LTL20: A larger set of instances with 8 randomly created commodity sets, each containing 20 commodities. This set was used to test the performance of the decomposition heuristics on larger problems.

The demand scenarios were generated using a combination of different uncertainty levels, correlation types (uncorrelated, positive, mixed), and triangular distributions, following methodologies from previous research.

Key Insights and Ideas

  • Rerouting as a Strategic Tool: Explicitly modeling rerouting provides freight companies with a more realistic and flexible way to manage demand uncertainty compared to solely relying on outsourcing.
  • Balancing Act: The model demonstrates that a strategic blend of network design, rerouting, and outsourcing can lead to better overall performance and cost savings.
  • Deterministic Foundation with Stochastic Flexibility: Even with moderate rerouting costs, a network designed based on deterministic (average) demand can perform surprisingly well when coupled with flexible rerouting capabilities in the operational phase. This suggests that deterministic models might be less "brittle" than previously thought if rerouting is an option.
  • Cost Trade-offs are Crucial: The relative costs of rerouting (γ, η) versus outsourcing (λ) significantly influence the optimal network design and operational strategies.
  • Spatio-Temporal Distribution Matters: The way demand is distributed across time and space within a commodity set can have a substantial impact on network costs. "Clustered" demands (where demand peaks occur at similar times) seem to be more cost-effective to service than "balanced" demands.

Key Results

  • Improved Objective Values: For instances with moderate rerouting costs, the proposed model (M-Stoch2), when solved to optimality, generally yielded better objective values than the outsourcing-only stochastic model (M-Stoch1).
  • Reduced Outsourcing: M-Stoch2 solutions consistently showed considerably less outsourcing compared to M-Stoch1, which is strategically important for companies aiming to increase market share.
  • Heuristic Performance: For larger instances where M-Stoch2 was computationally intractable, the decomposition heuristics (Determ-Stoch2 and Stoch1-Stoch2) provided good solutions, often outperforming M-Stoch1 and M-Determ within limited computational time.
  • Impact of Uncertainty: High uncertainty and correlated demands led to the highest savings when using stochastic network design models (M-Stoch1 and M-Stoch2).
  • Cost Savings with Clustered Demand: For instances where demand was "clustered" in time, the service network costs were significantly lower (over 10% reduction) compared to "balanced" demand scenarios across all tested models.

Limitations and Future Work

  • Computational Complexity: The primary limitation of the proposed M-Stoch2 model is its high computational cost, making it difficult to solve to optimality for large-scale problems.
  • Heuristic Development: The paper suggests that the decomposition heuristics (Determ-Stoch2 and Stoch1-Stoch2) are promising avenues for developing efficient algorithms for M-Stoch2.
  • Further Uncertainties: Future work could extend the model to include other uncertainties, such as variations in edge lengths or vehicle availability.
  • Market Development: Understanding the beneficial spatio-temporal characteristics of commodity sets that lead to better trade-offs between fixed and operational costs is identified as a key area for future research, with significant implications for freight companies' market development strategies.

Summary updated

BibTeX
@inproceedings{bai2014stochastic,
  author = {Ruibin Bai and Stein W. Wallace and Jingpeng Li and Alain Yee‐Loong Chong},
  title = {{Stochastic service network design with rerouting}},
  booktitle = {Transportation},
  year = {2014},
  doi = {10.1016/j.trb.2013.11.001},
}
Figure