Rolling Horizon based Temporal Decomposition for the Offline Pickup and Delivery Problem with Time Windows

Youngseo Kim, Danushka Edirimanna, Michael Wilbur, Philip Pugliese, Aron Laszka, Abhishek Dubey, Samitha Samaranayake

Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI-23) 2023

PDF

Why This Matters

The pickup and delivery problem with time windows is computationally challenging, and practical instances often exceed the size that exact solvers can handle. This work is important because it provides a scalable decomposition approach that maintains solution quality while dramatically reducing computation time. The rolling horizon method cleverly addresses the boundary stitching problem that makes temporal decomposition difficult, enabling practical solutions for large real-world instances.

What We Did

This paper develops a rolling horizon temporal decomposition approach for solving offline pickup and delivery problems with time windows at scale. The method divides large problem instances into smaller sub-problems by creating overlapping time windows and solving them sequentially. The approach uses a horizon optimization framework that smoothly transitions between time intervals, achieving good solutions that are tractable to compute compared to solving the full problem at once.

Key Results

The rolling horizon decomposition framework demonstrates substantial improvements in computation time compared to standard approaches while maintaining near-optimal solution quality. Experimental validation on realistic paratransit and courier instances shows the approach is competitive or superior to baseline methods. The temporal decomposition framework provides a practical approach for solving large transportation optimization problems that would otherwise be intractable.

Full Abstract

The offline pickup and delivery problem with time windows (PDPTW) is a classical combinatorial optimization problem in the transportation community, which has proven to be very challenging computationally. Due to the complexity of the problem, practical problem instances can be solved only via heuristics, which trade-off solution quality for computational tractability. Among the various heuristics, a common strategy is problem decomposition, that is, the reduction of a largescale problem into a collection of smaller sub-problems, with spatial and temporal decompositions being two natural approaches. While spatial decomposition has been successful in certain settings, effective temporal decomposition has been challenging due to the difficulty of stitching together the sub-problem solutions across the decomposition boundaries. In this work, we introduce a novel temporal decomposition scheme for solving a class of PDPTWs that have narrow time windows, for which it is able to provide both fast and highquality solutions. We utilize techniques that have been popularized recently in the context of online dial-a-ride problems along with the general idea of rolling horizon optimization. To the best of our knowledge, this is the first attempt to solve offline PDPTWs using such an approach. To show the performance and scalability of our framework, we use the optimization of paratransit services as a motivating example. Due to the lack of benchmark solvers similar to ours (i.e., temporal decomposition with an online solver), we compare our results with an offline heuristic algorithm using Google OR-Tools. In smaller problem instances (with an average of 129 requests per instance), the baseline approach is as competitive as our framework. However, in larger problem instances (approximately 2,500 requests per instance), our framework is more scalable and can provide good solutions to problem instances of varying degrees of difficulty, while the baseline algorithm often fails to find a feasible solution within comparable compute times.

Cite This Paper

@inproceedings{youngseo2023,
  author = {Kim, Youngseo and Edirimanna, Danushka and Wilbur, Michael and Pugliese, Philip and Laszka, Aron and Dubey, Abhishek and Samaranayake, Samitha},
  booktitle = {Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI-23)},
  title = {Rolling Horizon based Temporal Decomposition for the Offline Pickup and Delivery Problem with Time Windows},
  year = {2023},
  abstract = {The offline pickup and delivery problem with time windows (PDPTW) is a classical combinatorial optimization problem in the transportation community, which has proven to be very challenging computationally. Due to the complexity of the problem, practical problem instances can be solved only via heuristics, which trade-off solution quality for computational tractability. Among the various heuristics, a common strategy is problem decomposition, that is, the reduction of a largescale problem into a collection of smaller sub-problems, with spatial and temporal decompositions being two natural approaches. While spatial decomposition has been successful in certain settings, effective temporal decomposition has been challenging due to the difficulty of stitching together the sub-problem solutions across the decomposition boundaries. In this work, we introduce a novel temporal decomposition scheme for solving a class of PDPTWs that have narrow time windows, for which it is able to provide both fast and highquality solutions. We utilize techniques that have been popularized recently in the context of online dial-a-ride problems along with the general idea of rolling horizon optimization. To the best of our knowledge, this is the first attempt to solve offline PDPTWs using such an approach. To show the performance and scalability of our framework, we use the optimization of paratransit services as a motivating example. Due to the lack of benchmark solvers similar to ours (i.e., temporal decomposition with an online solver), we compare our results with an offline heuristic algorithm using Google OR-Tools. In smaller problem instances (with an average of 129 requests per instance), the baseline approach is as competitive as our framework. However, in larger problem instances (approximately 2,500 requests per instance), our framework is more scalable and can provide good solutions to problem instances of varying degrees of difficulty, while the baseline algorithm often fails to find a feasible solution within comparable compute times.},
  contribution = {colab},
  acceptance = {19.6},
  tag = {ai4cps,transit},
  keywords = {pickup and delivery, time windows, temporal decomposition, vehicle routing, optimization at scale, rolling horizon, routing algorithms, transportation planning}
}

Rolling Horizon based Temporal Decomposition for the Offline Pickup and Delivery Problem with Time Windows

Why This Matters

What We Did

Key Results

Full Abstract

Cite This Paper

Quick Info

Keywords

Research Areas

Search Tags