The multiagent planning problem
Summary: The classical multiple traveling salesmen problem is a well-studied optimization problem. Given a set of \(n\) goals/targets and \(m\) agents, the objective is to find \(m\) round trips, such that each target is visited only once and by only one agent, and the total distance of these round trips is minimal. In this paper we describe the multiagent planning problem, a variant of the classical multiple traveling salesmen problem: given a set of \(n\) goals/targets and a team of \(m\) agents, \(m\) subtours (simple paths) are sought such that each target is visited only once and by only one agent. We optimize for minimum time rather than minimum total distance; therefore the objective is to find the team plan in which the longest subtour is as short as possible (a min-max problem). We propose an easy to implement Genetic Algorithm Inspired Descent (GAID) method which evolves a set of subtours using genetic operators. We benchmarked GAID against other evolutionary algorithms and heuristics. GAID outperformed the Ant Colony Optimization and the Modified Genetic Algorithm. Even though the heuristics specifically developed for multiple traveling salesmen problem (e.g., \(k\)-split, bisection) outperformed GAID, these methods cannot solve the multiagent planning problem. GAID proved to be much better than an open-source Matlab multiple traveling salesmen problem solver.
- A branch-and-bound algorithm for the asymmetrical distance-constrained vehicle routing problem
- A GROUPING GENETIC ALGORITHM FOR THE MULTIPLE TRAVELING SALESPERSON PROBLEM
- A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron \& Steel Complex
- A new approach to solving the multiple traveling salesperson problem using genetic algorithms
- An Optimal Solution Method for Large-Scale Multiple Traveling Salesmen Problems
- Genetic algorithm for combinatorial path planning: the subtour problem
- Graph theory with applications
- scientific article; zbMATH DE number 432754 (Why is no real title available?)
- scientific article; zbMATH DE number 3908167 (Why is no real title available?)
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 1082106 (Why is no real title available?)
- scientific article; zbMATH DE number 2079898 (Why is no real title available?)
- scientific article; zbMATH DE number 194544 (Why is no real title available?)
- scientific article; zbMATH DE number 2203240 (Why is no real title available?)
- Integer linear programming formulations of multiple salesman problems and its variations
- Technical Note—A Note on the Symmetric Multiple Traveling Salesman Problem with Fixed Charges
- The asymmetric m-travelling salesman problem: A duality based branch-and- bound algorithm
- The efficiency of hybrid mutation genetic algorithm for the travelling salesman problem.
- The increasing cost tree search for optimal multi-agent pathfinding
- The traveling salesman problem and its variations
- Transformation of Multisalesman Problem to the Standard Traveling Salesman Problem
- TSPLIB—A Traveling Salesman Problem Library
This page was built for publication: The multiagent planning problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2012788)
