Solving the Team Orienteering Problem with Transformers
- URL: http://arxiv.org/abs/2311.18662v2
- Date: Fri, 1 Dec 2023 09:48:02 GMT
- Title: Solving the Team Orienteering Problem with Transformers
- Authors: Daniel Fuertes, Carlos R. del-Blanco, Fernando Jaureguizar, Narciso
Garc\'ia
- Abstract summary: Route planning for a fleet of vehicles is an important task in applications such as package delivery, surveillance, or transportation.
This paper presents a multi-agent route planning system capable of solving the Team Orienteering Problem in a very fast and accurate manner.
- Score: 46.93254771681026
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Route planning for a fleet of vehicles is an important task in applications
such as package delivery, surveillance, or transportation. This problem is
usually modeled as a Combinatorial Optimization problem named as Team
Orienteering Problem. The most popular Team Orienteering Problem solvers are
mainly based on either linear programming, which provides accurate solutions by
employing a large computation time that grows with the size of the problem, or
heuristic methods, which usually find suboptimal solutions in a shorter amount
of time. In this paper, a multi-agent route planning system capable of solving
the Team Orienteering Problem in a very fast and accurate manner is presented.
The proposed system is based on a centralized Transformer neural network that
can learn to encode the scenario (modeled as a graph) and the context of the
agents to provide fast and accurate solutions. Several experiments have been
performed to demonstrate that the presented system can outperform most of the
state-of-the-art works in terms of computation speed. In addition, the code is
publicly available at http://gti.ssr.upm.es/data.
Related papers
- Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
Sequentially solving similar optimization problems under strict runtime constraints is essential for many applications.
We propose learning to predict emphmultiple diverse initial solutions given parameters that define the problem instance.
We find significant and consistent improvement with our method across all evaluation settings and demonstrate that it efficiently scales with the number of initial solutions required.
arXiv Detail & Related papers (2024-11-04T15:17:19Z) - Robotic warehousing operations: a learn-then-optimize approach to large-scale neighborhood search [84.39855372157616]
This paper supports robotic parts-to-picker operations in warehousing by optimizing order-workstation assignments, item-pod assignments and the schedule of order fulfillment at workstations.
We solve it via large-scale neighborhood search, with a novel learn-then-optimize approach to subproblem generation.
In collaboration with Amazon Robotics, we show that our model and algorithm generate much stronger solutions for practical problems than state-of-the-art approaches.
arXiv Detail & Related papers (2024-08-29T20:22:22Z) - Solving Complex Multi-UAV Mission Planning Problems using
Multi-objective Genetic Algorithms [4.198865250277024]
This paper presents a new Multi-Objective Genetic Algorithm for solving complex Mission Planning Problems (MPP)
A hybrid fitness function has been designed using a Constraint Satisfaction Problem (CSP) to check if solutions are valid.
Experimental results show that the new algorithm is able to obtain good solutions, however as the problem becomes more complex, the optimal solutions also become harder to find.
arXiv Detail & Related papers (2024-02-09T16:13:21Z) - Symmetry-preserving graph attention network to solve routing problems at
multiple resolutions [1.9304772860080408]
We introduce the first-ever completely equivariant model and training to solve problems.
It is essential to capture the multiscale structure of the input graph.
We propose a Multiresolution scheme in combination with Equi Graph Attention network (mEGAT) architecture.
arXiv Detail & Related papers (2023-10-24T06:22:20Z) - Learning to Optimize Permutation Flow Shop Scheduling via Graph-based
Imitation Learning [70.65666982566655]
Permutation flow shop scheduling (PFSS) is widely used in manufacturing systems.
We propose to train the model via expert-driven imitation learning, which accelerates convergence more stably and accurately.
Our model's network parameters are reduced to only 37% of theirs, and the solution gap of our model towards the expert solutions decreases from 6.8% to 1.3% on average.
arXiv Detail & Related papers (2022-10-31T09:46:26Z) - Scalable Vehicle Re-Identification via Self-Supervision [66.2562538902156]
Vehicle Re-Identification is one of the key elements in city-scale vehicle analytics systems.
Many state-of-the-art solutions for vehicle re-id mostly focus on improving the accuracy on existing re-id benchmarks and often ignore computational complexity.
We propose a simple yet effective hybrid solution empowered by self-supervised training which only uses a single network during inference time.
arXiv Detail & Related papers (2022-05-16T12:14:42Z) - Multi-Agent Path Planning Using Deep Reinforcement Learning [0.0]
In this paper a deep reinforcement based multi-agent path planning approach is introduced.
The experiments are realized in a simulation environment and in this environment different multi-agent path planning problems are produced.
The produced problems are actually similar to a vehicle routing problem and they are solved using multi-agent deep reinforcement learning.
arXiv Detail & Related papers (2021-10-04T13:56:23Z) - Multi-Agent Routing Value Iteration Network [88.38796921838203]
We propose a graph neural network based model that is able to perform multi-agent routing based on learned value in a sparsely connected graph.
We show that our model trained with only two agents on graphs with a maximum of 25 nodes can easily generalize to situations with more agents and/or nodes.
arXiv Detail & Related papers (2020-07-09T22:16:45Z) - A Novel Multi-Agent System for Complex Scheduling Problems [2.294014185517203]
This paper is the conception and implementation of a multi-agent system that is applicable in various problem domains.
We simulate a NP-hard scheduling problem to demonstrate the validity of our approach.
This paper highlights the advantages of the agent-based approach, like the reduction in layout complexity, improved control of complicated systems, and extendability.
arXiv Detail & Related papers (2020-04-20T14:04:58Z) - Multi-Vehicle Routing Problems with Soft Time Windows: A Multi-Agent
Reinforcement Learning Approach [9.717648122961483]
Multi-vehicle routing problem with soft time windows (MVRPSTW) is an indispensable constituent in urban logistics systems.
Traditional methods incur the dilemma between computational efficiency and solution quality.
We propose a novel reinforcement learning algorithm called the Multi-Agent Attention Model that can solve routing problem instantly benefit from lengthy offline training.
arXiv Detail & Related papers (2020-02-13T14:26:27Z)
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.