Solving the capacitated vehicle routing problem with timing windows
using rollouts and MAX-SAT
- URL: http://arxiv.org/abs/2206.06618v1
- Date: Tue, 14 Jun 2022 06:27:09 GMT
- Title: Solving the capacitated vehicle routing problem with timing windows
using rollouts and MAX-SAT
- Authors: Harshad Khadilkar
- Abstract summary: 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.
- Score: 4.873362301533824
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: The vehicle routing problem is a well known class of NP-hard combinatorial
optimisation problems in literature. Traditional solution methods involve
either carefully designed heuristics, or time-consuming metaheuristics. Recent
work in reinforcement learning has been a promising alternative approach, but
has found it difficult to compete with traditional methods in terms of solution
quality. This paper proposes a hybrid approach that combines reinforcement
learning, policy rollouts, and a satisfiability solver to enable a tunable
tradeoff between computation times and solution quality. Results on a popular
public data set show that the algorithm is able to produce solutions closer to
optimal levels than existing learning based approaches, and with shorter
computation times than meta-heuristics. The approach requires minimal design
effort and is able to solve unseen problems of arbitrary scale without
additional training. Furthermore, the methodology is generalisable to other
combinatorial optimisation problems.
Related papers
- Socio-cognitive Optimization of Time-delay Control Problems using
Evolutionary Metaheuristics [89.24951036534168]
Metaheuristics are universal optimization algorithms which should be used for solving difficult problems, unsolvable by classic approaches.
In this paper we aim at constructing novel socio-cognitive metaheuristic based on castes, and apply several versions of this algorithm to optimization of time-delay system model.
arXiv Detail & Related papers (2022-10-23T22:21:10Z) - Sample-Efficient, Exploration-Based Policy Optimisation for Routing
Problems [2.6782615615913348]
This paper presents a new reinforcement learning approach that is based on entropy.
In addition, we design an off-policy-based reinforcement learning technique that maximises the expected return.
We show that our model can generalise to various route problems.
arXiv Detail & Related papers (2022-05-31T09:51:48Z) - Combining Reinforcement Learning and Optimal Transport for the Traveling
Salesman Problem [18.735056206844202]
We show that we can construct a model capable of learning without supervision and inferences significantly faster than current autoregressive approaches.
We also empirically evaluate the benefits of including optimal transport algorithms within deep learning models to enforce assignment constraints during end-to-end training.
arXiv Detail & Related papers (2022-03-02T07:21:56Z) - Ranking Cost: Building An Efficient and Scalable Circuit Routing Planner
with Evolution-Based Optimization [49.207538634692916]
We propose a new algorithm for circuit routing, named Ranking Cost, to form an efficient and trainable router.
In our method, we introduce a new set of variables called cost maps, which can help the A* router to find out proper paths.
Our algorithm is trained in an end-to-end manner and does not use any artificial data or human demonstration.
arXiv Detail & Related papers (2021-10-08T07:22:45Z) - An Overview and Experimental Study of Learning-based Optimization
Algorithms for Vehicle Routing Problem [49.04543375851723]
Vehicle routing problem (VRP) is a typical discrete optimization problem.
Many studies consider learning-based optimization algorithms to solve VRP.
This paper reviews recent advances in this field and divides relevant approaches into end-to-end approaches and step-by-step approaches.
arXiv Detail & Related papers (2021-07-15T02:13:03Z) - A Bi-Level Framework for Learning to Solve Combinatorial Optimization on
Graphs [91.07247251502564]
We propose a hybrid approach to combine the best of the two worlds, in which a bi-level framework is developed with an upper-level learning method to optimize the graph.
Such a bi-level approach simplifies the learning on the original hard CO and can effectively mitigate the demand for model capacity.
arXiv Detail & Related papers (2021-06-09T09:18:18Z) - SOLO: Search Online, Learn Offline for Combinatorial Optimization
Problems [4.777801093677586]
We study problems with real world applications such as machine scheduling, routing, and assignment.
We propose a method that combines Reinforcement Learning (RL) and planning.
This method can equally be applied to both the offline, as well as online, variants of the problem, in which the problem components are not known in advance, but rather arrive during the decision-making process.
arXiv Detail & Related papers (2021-04-04T17:12:24Z) - A Two-stage Framework and Reinforcement Learning-based Optimization
Algorithms for Complex Scheduling Problems [54.61091936472494]
We develop a two-stage framework, in which reinforcement learning (RL) and traditional operations research (OR) algorithms are combined together.
The scheduling problem is solved in two stages, including a finite Markov decision process (MDP) and a mixed-integer programming process, respectively.
Results show that the proposed algorithms could stably and efficiently obtain satisfactory scheduling schemes for agile Earth observation satellite scheduling problems.
arXiv Detail & Related papers (2021-03-10T03:16:12Z) - SeaPearl: A Constraint Programming Solver guided by Reinforcement
Learning [0.0]
This paper presents the proof of concept for SeaPearl, a new constraint programming solver implemented in Julia.
SeaPearl supports machine learning routines in order to learn branching decisions using reinforcement learning.
Although not yet competitive with industrial solvers, SeaPearl aims to provide a flexible and open-source framework.
arXiv Detail & Related papers (2021-02-18T07:34:38Z) - 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) - Reinforcement Learning for Combinatorial Optimization: A Survey [12.323976053967066]
Many traditional algorithms for solving optimization problems involve using hand-crafteds that sequentially construct a solution.
Reinforcement learning (RL) proposes a good alternative to automate the search of theses by training an agent in a supervised or self-supervised manner.
arXiv Detail & Related papers (2020-03-07T16:19:45Z)
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.