@misc{anonymous_rolling_2023,
	title = {Rolling {Horizon} based {Temporal} {Decomposition} for the {Offline} {Pickup} and {Delivery} {Problem} with {TimeWindows}},
	abstract = {The offline pickup and delivery problem with time windows
(PDPTW), also known as the offline Dial-a-Ride problem, 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, 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. 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.},
	collaborator = {{Anonymous}},
	year = {2023},
	note = {Weak Accept -{\textgreater} Accept},
}

{"_id":"jkWfByRY2JT4vpwkf","bibbaseid":"anonymous-rollinghorizonbasedtemporaldecompositionfortheofflinepickupanddeliveryproblemwithtimewindows-2023","bibdata":{"bibtype":"misc","type":"misc","title":"Rolling Horizon based Temporal Decomposition for the Offline Pickup and Delivery Problem with TimeWindows","abstract":"The offline pickup and delivery problem with time windows (PDPTW), also known as the offline Dial-a-Ride problem, 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, 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. 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.","collaborator":"Anonymous","year":"2023","note":"Weak Accept -\\textgreater Accept","bibtex":"@misc{anonymous_rolling_2023,\n\ttitle = {Rolling {Horizon} based {Temporal} {Decomposition} for the {Offline} {Pickup} and {Delivery} {Problem} with {TimeWindows}},\n\tabstract = {The offline pickup and delivery problem with time windows\n(PDPTW), also known as the offline Dial-a-Ride problem, is\na classical combinatorial-optimization problem in the transportation\ncommunity, which has proven to be very challenging\ncomputationally. Due to the complexity of the problem,\npractical problem instances can be solved only via heuristics,\nwhich trade-off solution quality for computational tractability.\nAmong the various heuristics, a common strategy is problem\ndecomposition, that is, reduction of a large-scale problem\ninto a collection of smaller sub-problems, with spatial\nand temporal decompositions being two natural approaches.\nWhile spatial decomposition has been successful in certain\nsettings, effective temporal decomposition has been challenging\ndue to the difficulty of stitching together the sub-problem\nsolutions across the decomposition boundaries. In this work,\nwe introduce a novel temporal decomposition scheme for\nsolving a class of PDPTWs that have narrow time windows,\nfor which it is able to provide both fast and high-quality solutions.\nWe utilize techniques that have been popularized recently\nin the context of online Dial-a-Ride problems along\nwith the general idea of rolling horizon optimization. To the\nbest of our knowledge, this is the first attempt to solve offline\nPDPTWs using such an approach. To show the performance\nand scalability of our framework, we use the optimization of\nparatransit services as a motivating example. Due to the lack\nof benchmark solvers similar to ours (i.e., temporal decomposition\nwith an online solver), we compare our results with an\noffline heuristic algorithm using Google OR-Tools. In smaller\nproblem instances (with an average of 129 requests per instance),\nthe baseline approach is as competitive as our framework.\nHowever, in larger problem instances (approximately\n2,500 requests per instance), our framework is more scalable\nand can provide good solutions to problem instances of varying\ndegrees of difficulty, while the baseline algorithm often\nfails to find a feasible solution within comparable compute\ntimes.},\n\tcollaborator = {{Anonymous}},\n\tyear = {2023},\n\tnote = {Weak Accept -{\\textgreater} Accept},\n}\n\n\n\n","key":"anonymous_rolling_2023","id":"anonymous_rolling_2023","bibbaseid":"anonymous-rollinghorizonbasedtemporaldecompositionfortheofflinepickupanddeliveryproblemwithtimewindows-2023","role":"","urls":{},"metadata":{"authorlinks":{}},"downloads":0,"html":""},"bibtype":"misc","biburl":"https://bibbase.org/zotero/matteocarde","dataSources":["BLJPWpPi3hneTGaPF"],"keywords":[],"search_terms":["rolling","horizon","based","temporal","decomposition","offline","pickup","delivery","problem","timewindows"],"title":"Rolling Horizon based Temporal Decomposition for the Offline Pickup and Delivery Problem with TimeWindows","year":2023}