  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.
