Rolling Horizon based Temporal Decomposition for the Offline Pickup and Delivery Problem with Time Windows
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 large-scale 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 high-quality 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. We compare our results with an offline heuristic algorithm using Google OR-Tools. In smaller problem instances, the baseline approach is as competitive as our framework. However, in larger problem instances, 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.
Code (1)
Tasks
Combinatorial OptimizationProblem DecompositionSimilar Papers 제목 키워드 기반
Offline Imitation Learning by Controlling the Effective Planning Horizon
In offline imitation learning (IL), we generally assume only a handful of expert trajectories and a supplementary offline dataset from suboptimal behaviors to learn the expert policy. While it is now common to minimize t…
Imitation LearningAdvancing MG Energy Management: A Rolling Horizon Optimization Framework for Three-Phase Unbalanced Networks Integrating Convex Formulations
Real-world three-phase microgrids face two interconnected challenges: 1. time-varying uncertainty from renewable generation and demand, and 2. persistent phase imbalances caused by uneven distributed energy resources DER…
energy managementManagementSchedulingOffline RL with Hierarchical Action Chunking
Offline goal-conditioned reinforcement learning (RL) holds the promise of learning general-purpose policies from static datasets. However, scaling these methods to long-horizon tasks remains a challenge due to the curse …
Reinforcement LearningOffline RLThreshold-Based Algorithms for an Online Rolling Horizon Framework Under Uncertainty -- With an Application to Energy Management
Decision problems encountered in practice often possess a highly dynamic and uncertain nature. In particular fast changing forecasts for parameters (e.g., photovoltaic generation forecasts in the context of energy manage…
energy managementManagementSchedulingTerraforming -- Environment Manipulation during Disruptions for Multi-Agent Pickup and Delivery
In automated warehouses, teams of mobile robots fulfill the packaging process by transferring inventory pods to designated workstations while navigating narrow aisles formed by tightly packed pods. This problem is typica…