Rolling Horizon based Temporal Decomposition for the Offline Pickup and
Delivery Problem with Time Windows
- URL: http://arxiv.org/abs/2303.03475v1
- Date: Mon, 6 Mar 2023 20:07:05 GMT
- Title: Rolling Horizon based Temporal Decomposition for the Offline Pickup and
Delivery Problem with Time Windows
- Authors: Youngseo Kim, Danushka Edirimanna, Michael Wilbur, Philip Pugliese,
Aron Laszka, Abhishek Dubey, Samitha Samaranayake
- Abstract summary: We introduce a novel temporal decomposition scheme for solving a class of offline PDPTWs.
Our framework is more scalable and can provide good solutions to problem instances of varying degrees of difficulty.
- Score: 5.818566833386833
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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 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.
Related papers
- Dancing to the State of the Art? How Candidate Lists Influence LKH for Solving the Traveling Salesperson Problem [1.6874375111244329]
Solving the Traveling Salesperson Problem (TSP) remains a persistent challenge.
Heuristic solvers address the demand for finding high-quality solutions efficiently.
Among these solvers, the Lin-Kernighan-Helsgaun (LKH) stands out, as it complements the performance of genetic algorithms.
arXiv Detail & Related papers (2024-07-04T13:38:19Z) - Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks [57.24087627267086]
We consider the task of minimizing the sum of convex functions stored in a decentralized manner across the nodes of a communication network.
Lower bounds on the number of decentralized communications and (sub)gradient computations required to solve the problem have been established.
We develop the first optimal algorithm that matches these lower bounds and offers substantially improved theoretical performance compared to the existing state of the art.
arXiv Detail & Related papers (2024-05-28T10:28:45Z) - Paired Autoencoders for Inverse Problems [3.355436702348694]
We consider the solution of nonlinear inverse problems where the forward problem is a discretization of a partial differential equation.
The main computational bottleneck of typical algorithms is the direct estimation of the data misfit.
We use a paired autoencoder framework as a likelihood-free estimator for inverse problems.
arXiv Detail & Related papers (2024-05-21T22:00:34Z) - A Greedy Quantum Route-Generation Algorithm [0.0]
We propose a greedy algorithm that generates routes by using information from all samples obtained from the quantum computer.
By noticing the relationship between qubits in our formulation as a directed acyclic graph (DAG), we designed an algorithm that adaptively constructs a feasible solution.
arXiv Detail & Related papers (2024-05-05T21:20:46Z) - Looking Ahead to Avoid Being Late: Solving Hard-Constrained Traveling
Salesman Problem [36.88003015541172]
We propose a novel learning-based method that uses looking-ahead information as the feature to improve the legality of TSP with Time Windows (TSPTW) solutions.
With comprehensive experiments on diverse datasets, MUSLA outperforms existing baselines and shows generalizability potential.
arXiv Detail & Related papers (2024-03-08T13:49:21Z) - Let the Flows Tell: Solving Graph Combinatorial Optimization Problems
with GFlowNets [86.43523688236077]
Combinatorial optimization (CO) problems are often NP-hard and out of reach for exact algorithms.
GFlowNets have emerged as a powerful machinery to efficiently sample from composite unnormalized densities sequentially.
In this paper, we design Markov decision processes (MDPs) for different problems and propose to train conditional GFlowNets to sample from the solution space.
arXiv Detail & Related papers (2023-05-26T15:13:09Z) - Solving the capacitated vehicle routing problem with timing windows
using rollouts and MAX-SAT [4.873362301533824]
Vehicle routing is a well known class of NP-hard optimisation problems.
Recent work in reinforcement learning has been a promising alternative approach.
This paper proposes a hybrid approach that combines reinforcement learning, policy rollouts, and a satisfiability.
arXiv Detail & Related papers (2022-06-14T06:27:09Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
We introduce novel online algorithms that can exploit smoothness and replace the dependence on $T$ in dynamic regret with problem-dependent quantities.
Our results are adaptive to the intrinsic difficulty of the problem, since the bounds are tighter than existing results for easy problems and safeguard the same rate in the worst case.
arXiv Detail & Related papers (2021-12-29T02:42:59Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
Security-constrained optimal power flow (SCOPF) is fundamental in power systems.
Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs.
This paper proposes a novel approach that combines deep learning and robust optimization techniques.
arXiv Detail & Related papers (2020-07-14T12:38:21Z) - MineReduce: an approach based on data mining for problem size reduction [58.720142291102135]
This paper presents an approach named MineReduce, which uses mined patterns to perform problem size reduction.
We present an application of MineReduce to improve a for the heterogeneous fleet vehicle routing problem.
arXiv Detail & Related papers (2020-05-15T08:49:50Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc.
Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource.
We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
arXiv Detail & Related papers (2020-05-09T02:48:23Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.