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
- 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) - Thought Propagation: An Analogical Approach to Complex Reasoning with Large Language Models [62.96551299003463]
We propose textbftextitThought Propagation (TP) to enhance the complex reasoning ability of Large Language Models.
TP first prompts LLMs to propose and solve a set of analogous problems that are related to the input one.
TP reuses the results of analogous problems to directly yield a new solution or derive a knowledge-intensive plan for execution to amend the initial solution obtained from scratch.
arXiv Detail & Related papers (2023-10-06T01:40:09Z) - 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) - A Machine Learning Approach for Task and Resource Allocation in Mobile
Edge Computing Based Networks [108.57859531628264]
A joint task, spectrum, and transmit power allocation problem is investigated for a wireless network.
The proposed algorithm can reduce the number of iterations needed for convergence and the maximal delay among all users by up to 18% and 11.1% compared to the standard Q-learning algorithm.
arXiv Detail & Related papers (2020-07-20T13:46:42Z) - 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.