The multiagent planning problem
type: Item
instance of: scholarly article
title: The multiagent planning problem
zbMATH Open document ID: 1376.90049
DOI: 10.1155/2017/3813912
author: Tamás Kalmár-Nagy
author: Giovanni Giardini
author: Bendegúz Dezso Bak
published in: Complexity
publication date: 2017-08-03T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 6755972
zbMATH Keywords: multiple traveling salesmen problem
zbMATH Keywords: multiagent planning problem
zbMATH Keywords: genetic algorithm inspired descent (GAID) method
zbMATH Keywords: ant colony optimization
zbMATH Keywords: modified genetic algorithm
Wikidata QID: Q59142891
describes a project that uses: TSPLIB
describes a project that uses: Matlab
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2017/3813912
OpenAlex ID: W2585469234
cites work: Technical Note—A Note on the Symmetric Multiple Traveling Salesman Problem with Fixed Charges
cites work: Q4365133
cites work: The traveling salesman problem and its variations
cites work: Q3097395
cites work: Q5315023
cites work: Genetic algorithm for combinatorial path planning: the subtour problem
cites work: Q3686500
cites work: Q3818127
cites work: A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron \& Steel Complex
cites work: An Optimal Solution Method for Large-Scale Multiple Traveling Salesmen Problems
cites work: Integer linear programming formulations of multiple salesman problems and its variations
cites work: Transformation of Multisalesman Problem to the Standard Traveling Salesman Problem
cites work: A branch-and-bound algorithm for the asymmetrical distance-constrained vehicle routing problem
cites work: The asymmetric m-travelling salesman problem: A duality based branch-and- bound algorithm
cites work: Q4472039
cites work: A new approach to solving the multiple traveling salesperson problem using genetic algorithms
cites work: A GROUPING GENETIC ALGORITHM FOR THE MULTIPLE TRAVELING SALESPERSON PROBLEM
cites work: The increasing cost tree search for optimal multi-agent pathfinding
cites work: Q4692508
cites work: The efficiency of hybrid mutation genetic algorithm for the travelling salesman problem.
cites work: Q3138882
cites work: TSPLIB—A Traveling Salesman Problem Library
DBLP publication ID: journals/complexity/Kalmar-NagyGB17
description: scientific article; zbMATH DE number 6755972