Towards Fast and Accurate Solutions to Vehicle Routing in a Large-Scale and Dynamic Environment

Yaguang Li, Dingxiong Deng, Ugur Demiryurek, Cyrus Shahabi, Siva RavadaSSTD 2015 · DOI

TL;DR

This paper tackles the challenge of optimizing vehicle routes in real-time, considering dynamic traffic conditions and a large number of delivery locations. They propose a novel "Spatial-Search-Based Local Search" (SSBLS) framework that significantly speeds up route computation by eliminating pre-computation steps and adaptively focusing the search on promising delivery locations and operators.

What Problem Does This Paper Address?

The traditional Vehicle Routing Problem (VRP) is a well-studied area, but recent trends in e-commerce and on-demand delivery have introduced new complexities. These include the need for near real-time route computation for a massive number of locations and the crucial impact of dynamic traffic conditions on travel times. Existing Operations Research (OR) approaches, which often rely on pre-computing a cost matrix between all location pairs, become computationally prohibitive under these dynamic and large-scale scenarios. This paper addresses the Time-Dependent Vehicle Routing Problem (TDVRP) in such environments, aiming for solutions that are both fast and accurate.

Methods

The core of the proposed solution is the Spatial-Search-Based Local Search (SSBLS) framework. It builds upon existing local search techniques but introduces two key innovations:

  • Elimination of Data Preparation: Instead of pre-computing a massive cost matrix, SSBLS computes travel times "on-demand" using a time-dependent shortest path algorithm. This drastically reduces the initial computational burden.
  • Adaptive Search: SSBLS intelligently guides the search process by:
  • Adaptive Delivery Location Selection: Assigning weights to delivery locations based on their past effectiveness in generating better solutions. Locations that contribute more to improving routes are prioritized.
  • Adaptive Operator Selection: Similarly, prioritizing local search operators (like One-Point, Two-Point, Two-Opt moves) that have historically been more successful.

This adaptive approach aims to reduce the number of evaluated moves, thereby speeding up the search for optimal routes.

Datasets

The experiments were conducted using a real-world Los Angeles (LA) road network dataset, comprising 111,532 vertices and 183,945 edges. Time-varying edge weights were generated from three years of sensor data, divided into 60 intervals from 6 am to 9 pm. Delivery locations were sourced from a real delivery company in Los Angeles. The authors generated 40 test cases with varying numbers of delivery locations: 100, 200, 500, and 1000.

Key Insights and Ideas

  • Pre-computation is a Bottleneck: The paper strongly argues that the traditional data-preparation phase in VRP is a major bottleneck, especially for time-dependent scenarios. The vast majority of pre-computed travel costs are often never used.
  • Not All Locations/Operators Are Equal: The effectiveness of local search moves is highly dependent on which delivery locations and operators are chosen. Focusing the search on "promising" elements significantly boosts efficiency.
  • On-Demand Calculation is Viable: By intelligently caching partial results from shortest path computations, on-demand calculation can be made efficient enough for practical use, even in dynamic environments.
  • Dynamic Traffic Matters: Incorporating time-dependent traffic data can lead to significant cost savings (up to 8%) compared to static routing.

Key Results

  • Speedup: SSBLS solves TDVRP instances with 1000 delivery locations in approximately 20 minutes, which is 8 times faster than the state-of-the-art approach (TDRTR).
  • Accuracy: SSBLS achieves similar accuracy to TDRTR and is significantly more accurate (15-27%) than traditional heuristics like Sweep and Clarke-Wright.
  • Dynamic Traffic Benefits: Using time-dependent road networks (as opposed to static ones) can save 6-8% in travel cost.
  • Adaptive Strategies Effectiveness: Adaptive delivery location selection reduced the number of evaluated moves by half while improving accuracy. Adaptive operator selection also showed significant efficiency gains without compromising accuracy.

Limitations and Future Work

  • Parameter Tuning: The performance of SSBLS, particularly the learning rate (η) for adaptive selection, requires careful parameter tuning for optimal results.
  • Local Optima: Like most local search algorithms, SSBLS is susceptible to getting stuck in local optima. While the "record-to-record" search component helps mitigate this, it's an inherent challenge.
  • Future Work: The paper suggests that the proposed framework can be easily adapted to other local search algorithms. Further exploration of adaptive operator selection strategies and more sophisticated methods for handling dynamic environments are implied.

Summary updated

BibTeX
@inproceedings{li2015towards,
  author = {Yaguang Li and Dingxiong Deng and Ugur Demiryurek and Cyrus Shahabi and Siva Ravada},
  title = {{Towards Fast and Accurate Solutions to Vehicle Routing in a Large-Scale and Dynamic Environment}},
  booktitle = {SSTD},
  year = {2015},
  doi = {10.1007/978-3-319-22363-6\_7},
}
Figure