# The Multiagent Planning Problem

Authors: Tamás Kalmár-Nagy; Giovanni Giardini; Bendegúz Dezső Bak
Journal: Complexity
 (2017)

---

## Abstract

The classical Multiple Traveling Salesmen Problem is a well-studied optimization problem. Given a set ofn 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.


---

## Body

## 1. Introduction

Applications from space exploration [1–3] and drone delivery to search and rescue problems [4–7] have underlined the need to plan a coordinated strategy for a team of vehicles to visit targets. It is important to develop a multiagent planner for a team of autonomous vehicles to cooperatively explore their environment [8, 9]. We formulate the overall planning problem as finding a near-optimal set of paths that allows the team of agents to visit a given number of targets in the shortest amount of time. This problem is quite similar to the well-known Multiple Traveling Salesmen Problem (MTSP) [10–13], a generalization of the Traveling Salesman Problem (TSP) [14–16], that can be stated as follows: given n nodes (targets) and m salesmen (agents), the MTSP consists of finding m closed tours (paths start and end at the starting point of the agents), such that each target is visited only once and by only one agent and the total cost of visiting all nodes is minimal. MTSP has been used for modeling many real situations, from scheduling activities of companies and industries to cooperative planning problems. See, for example, [17], where MTSP is used for modeling the preprinted insert scheduling problem. Planning problems have also been investigated through MTSP formulations, specifically in [18, 19], where a dynamic mission planning system for multiple mobile robots operating in unstructured environments is presented (analysis of planetary exploration), or in [20], where the MTSP formulation is used to describe a path planning problem for a team of cooperative vehicles. An important and well-studied extension of the MTSP is the Vehicle Routing Problem [21, 22], where a fleet of vehicles of different capacities, based at either one or several depots, must deliver different customer demands (the number of vehicles is often considered as a minimization criterion in addition to total traveled distance).A long-term goal of this work is to endow a team of autonomous agents (drones) with the capability of cooperative motion planning. In this application, the time available for the solution is limited and real-time algorithms providing good approximate solutions are required. In this work, the problem of planning a set of strategies for cooperatively exploring the environment with a fleet of vehicles is modeled as a variant of the classical MTSP, referred to as the Multiagent Planning Problem (MAPP): givenn nodes (targets) and m salesmen (agents) located at different depots, the MAPP seeks m tours such that each target is visited only once and by only one agent that minimizes a given cost function (specified by (8) and (9)). The paper presents a Genetic Algorithm Inspired Descent (GAID) method for obtaining good quality MAPP solutions.The paper is organized as follows: after describing the MAPP in detail (Section2) and an overview of how similar problems (MTSP in particular) are solved (Section 3), the proposed GA-Inspired Descent method is described in Section 4. Results are reported in Section 5, and conclusions are drawn in Section 6.


## 2. The Multiagent Planning Problem: Notations

Graph theory [23, 24] provides a natural framework to describe the Multiagent Planning Problem. Given V={v1,…,vm}, a set of m elements referred to asvertices (targets), and E={(vi,vj)∣vi,vj∈V}, a set ofedges connecting vertices vi and vj, agraphG is defined as the pair (V,E). Here we consider onlyundirected graphs, that is, graphs whose edges are unordered pairs with the symmetry relation (vi,vj)=(vj,vi). Acomplete graph is a graph where all vertices of V are connected to each other. The complete graph induced by the vertex set V is denoted by Km(V), where m=V (· denotes the cardinality of a set) is the number of vertices. A graph G1=(V1,E1) is asubgraph of G (G1⊆G) if V1⊆V and E1⊆E such that(1)E1=vi,vj∣vi,vj∈V1.A subgraph P=(V1,E1) is called apath in G=(V,E) if V1 is a set of k vertices of the original graph and(2)E1=x1,x2,x2,x3,…,xk-1,xk⊆Eis the set of k-1 edges that connect those vertices. In other words, a path is a sequence of edges with each consecutive pair of edges having a vertex in common. Similarly, a subgraph C=(V2,E2) of G=(V,E), with(3)V2=x1,…,xk⊆V,E2=x1,x2,…,xk-1,xk,xk,x1⊆E,is called acycle. The length of a path or cycle is the number of its edges. The set of all paths and cycles of length k in G will be denoted by Pk(G) and Ck(G), respectively.Paths and cycles with no repeated vertices are calledsimple. A simple path/cycle that includes every vertex of the graph is known as a Hamiltonian path/cycle. Graph G is calledweighted if aweight (orcost) w(vi,vj) is assigned to every edge (vi,vj). A weighted graph G is calledsymmetric if w(vi,vj)=w(vj,vi). In this paper, the weight associated with each edge is the Euclidean distance between the corresponding vertices (locations); that is, w(vi,vj)=w(vj,vi)=r(vi)-r(vj). The total cost c(·) of a path P∈Pk(G) is the sum of its edge weights(4)cP=∑i=1kwxi,xi+1.Analogously, for a cycle C∈Ck(G)(5)cC=∑i=1k-1wxi,xi+1+wxk,x1.After having introduced the necessary notation, we are now in the position to formalize the combinatorial problems of interest. TheSubtour Problem [25] is defined as finding a simple path P∈Pk(Kn+1(V)) of length k, starting at vertex x1=a and having the lowest cost c(P)=∑i=1kw(xi,xi+1). If k=n, the problem is equivalent to finding the “cheapest” Hamiltonian path, where all the n targets in T are to be visited. The general Traveling Salesman Problem, or k-TSP, poses to find a simple cycle C∈Ck+1(Kn+1(V)) of minimal cost starting and ending at vertex a, visiting k targets.LetT={t1,…,tn} be the set of n targets (goals) to be visited. The ith target ti is an object located in Euclidean space whose position is specified by the vector r(ti). Let A={a1,…,am} denote the set of m agents with position specified by r(ai). The classical Multiple Traveling Salesman Problem can be formulated as follows. Let a denote the unique depot; that is, ai=a. Theaugmented vertex set is V=T∪a and the configuration space of the problem is the complete graph Kn+1(V). Let Ci denote a cycle of length ki starting and ending at vertex a (the depot). The Multiple Traveling Salesmen Problem is to find m cycles (we also refer to these astours) Ci of length ki(6)C=C1,…,Cm,∑i=1mki=n+m,such that each target is visited only once (this also implies visitation by only one agent) and the sum of the lengths (costs) of all the m tours(7)cC=∑i=1mcCiis minimal.The Multiagent Planning Problem can be formulated similarly. For theith agent, the augmented vertex set is given by Vi=T∪ai and the configuration space of the problem is the complete graph Kn+1(Vi). The weight associated with each edge is the Euclidean distance between the corresponding locations, that is, w(vi,vj)=w(vj,vi)=r(vi)-r(vj), with vi,vj∈Vi, rendering Kn+1(Vi) a weighted and symmetric graph. Let Pi denote a simple path (no repeated vertices) of length Pi=ki starting at vertex ai. The optimal solution of the Multiagent Planning Problem (MAPP) is a set P of m pairwise disjoint (modulo the starting points) paths Pi(8)P=P1,…,Pm,∑i=1mki=n,such that the length of the longest path(9)cmaxP=maxi⁡cPiis minimal (a min–max problem). In other words, the m agents have to visit n targets in the least amount of time, and every target is visited only once. The number of targets visited by each agent can be different, but each agent has to visit at least one target (i.e., ki≥2).


## 3. Overview of Solution Methods

The Multiple Traveling Salesmen Problem (MTSP) and the Multiagent Planning Problem are notoriously difficult to solve due to their combinatorial nature (they are NP-hard).A common approach is to transform the MTSP into an equivalent Traveling Salesman Problem, for which solutions can be found by exact methods (e.g., branch-and-bound algorithms and linear programming [26–28]) or approximate algorithms such as Genetic Algorithms, Simulated Annealing, and Ant System [29, 30]. For example, in [31, 32] the authors proposed to transform the MTSP into an equivalent TSP by adding dummy cities and edges with ad hoc null or infinite costs. However, as stated in [33–35], transforming the MTSP into an equivalent TSP might yield an even harder problem to solve. Similar approaches are investigated in [13, 36, 37].The first attempt to solve large-scale MTSPs is given in [33], where a branch-and-bound method (the most widely adopted technique for solving these combinatorial problems [38]) is applied to both Euclidean (up to 100 cities and 10 salesmen) and non-Euclidean problems (up to 500 cities and 10 salesmen). Branch-and-bound is also applied in [39] for solving an asymmetric MTSP up to 100 cities.Other solution methods have also been proposed, for example, simulated annealing [18], Gravitational Emulation Local Search (GELS) algorithm [40], and evolutionary algorithms. In [41], different evolutionary algorithms, ranging from Genetic Algorithms to Particle Swarm and Monte-Carlo optimization, are compared. The MTSP with ability constraint is solved with an Ant Colony Optimization (ACO) algorithm in [34], where the MTSP is not translated into an equivalent TSP and the ACO algorithm is modified for dealing with the characteristics of the original problem. In [34] results are compared with a Modified Genetic Algorithm that solves the equivalent TSP. Linear Programming is used in [35], and similarly to [34], the original MTSP is analyzed and solved. In both [34, 35], the authors conclude that the original MTSP is easier to solve than the derived TSP. An important work is [42], where different local search heuristics are presented and compared. In [17, 29, 43, 44] Genetic Algorithms are used to minimize the sum of the salesmen path lengths together with the maximum distance traveled by each salesmen (to balance the agent workload). A Modified Genetic Algorithm on the equivalent TSP is used in [32]. Shirafkan et al. [45] proposed a hybrid method incorporating simulated annealing and Genetic Algorithm to solve the multidepot MTSP. In this MTSP variant the starting location (depot) of each agent is fixed and multiple agents can have start from the same depot. The multiobjective MTSP variant is presented in [46] and Genetic Algorithm is used to find approximate solutions. In multiobjective MTSP the total distance traveled by the agents and the balance of agent working times are the objectives. Kaliaperumal et al. [47] also used Genetic Algorithm to solve the MTSP. They developed a brand new crossover operator called modified two-part chromosome crossover and obtained better results using this new operator. A new (branch-and-cut type) exact method is presented in [48] for the heterogeneous MTSP (some targets can be visited only by a specific agent). In [49] a heuristic search method is proposed to solve the Multiagent Path Finding problem, which is similar to MAPP, except that the endpoints of the tours are also fixed. These methods work well on the problem they were constructed for, but none of them is designed to solve the MAPP. In Section 5.1.2 we benchmark our GAID against some of these methods in MTSP solving. In Section 5.2 we compare GAID against a Matlab solver which is capable of solving MAPP as well as MTSP.


## 4. The Multiagent Planning Problem: Approximate Solution

Givenm≥1 agents and n known targets/cities to visit, the optimal team strategy (called Team Plan) is sought that allows the fleet to visit every target only once.We represent the Team Plan as a collection ofm distinct subtours. Thus, given m agents and n targets, Team Plan P is defined as P={P1,…,Pm}, where Pi is the path of the ith agent visiting ki<n targets. Note that this representation allows the individual subtours to have different lengths. Moreover, the Multiagent Planning Problem can also be rewritten for each ith agent to find the best possible subtour of length ki<n that satisfies the imposed cost function. We propose an optimization technique we call the Genetic Algorithm Inspired Descent (GAID) method. Briefly, a Genetic Algorithm (GA) is an optimization technique used to find approximate solutions of optimization and search problems [50–52]. Genetic Algorithms are a particular class of evolutionary methods that use techniques inspired by Darwin’s theory of evolution and evolutionary biology, such as inheritance, mutation, selection, and crossover. In these systems, populations of solutions compete and only the fittest survive.Similarly to the classical GA, GAID consists of two phases: initialization and evolution. In the initialization phase, the starting Team Plan is created (see Section4.1), while the evolution phase (see Section 4.2) evolves Team Plan P toward a better quality final solution.


### 4.1. Initialization Phase

During the initialization phase, the starting Team Plan—a starting set of subtours—is created. LetT1={t1,…,tn} and A={a1,…,am} be the sets of n targets and the m agents, respectively. Without loss of generality, we assume that the order of planning is a1,a2,…,am and that the starting subtours have similar lengths. A Team Plan is feasible if the subtours are pairwise disjoint (except possibly their starting points).At first, a subtourP1 (with starting point a1) of length k1 is chosen. Then subtour P2 is chosen from the target set T2 that is simply obtained by discarding from T1 the targets visited by agent a1. In general, the ith agent plans a subtour Pi on the targets not yet allocated previously. Obviously, this process yields a feasible Team Plan P={P1,…,Pm}.Here we utilize three simple initialization methods.(i)
Random initialization: for each agent the targets are selected at random from the unallocated ones.(ii)
Greedy initialization: the initial Team Plan is created using a greedy approach to form feasible starting subtours. Each agent selects its targets using a Nearest Neighbor heuristics: for a given a target, the next target will be the nearest one.(iii)
TSP-based initialization: for problems where the positions of them agents are not imposed (the m agents can start from any target ti∈T), a feasible starting Team Plan can be generated by clustering the TSP solution computed on the complete graph Kn(T). “Clustering” is carried out by discarding m edges from the TSP tour, in order to subdivide it “fairly”, and having m starting subtours with similar costs. This initialization method introduces a degree of complexity in the overall system, since a TSP solution must be computed.The initialization phase is an important step in the optimization process, since it directly influences the efficacy of the algorithm.


### 4.2. Evolution Phase

The evolution phase evolves the Team Plan, trying to design a strategy where the overall time is reduced (minimizing the costcmax(P); see (9)).This phase has the same mechanism of a classical Genetic Algorithm [50] with one important difference: there is only one Team Plan P to be evolved (i.e., the population size is 1).At every evolution/generation step, a set of operators (see Section4.3) is applied to the subtours Pi∈P. If P improves, it is kept for the next generation step, otherwise the previous Team Plan is restored (we expect that a simulated annealing-type modification will be even more efficient). The flowchart of the GAID evolution phase is shown in Figure 1.Figure 1
Flowchart of the evolution phase, together with the sequence of operators.


### 4.3. Team Plan Operators and Boosting

The evolution ofP toward a near-optimal multiagent strategy is accomplished by combining the genetic materials of its subtours through the application of genetic-like operators. Three different operators have been designed: crossover, mutation, and migration. The operators are applied in a predefined order, and their application depends on a given probability, as shown in Figure 1.Thecrossover operator (Figure 2) is applied with probability pcrossover and combines the genetic materials of two selected subtours (called parents), replacing them with the two newly created ones (the offsprings). Parents are chosen using the best-worst selection with probability pbest-worst (Figure 2(a)) or randomly (Figure 2(b)) with probability 1-pbest-worst. The parents are mated the classical way [50]: they are randomly halved (not necessarily at the same position) and the halves are simply swapped.Figure 2
Crossover operator. (a) In case of best-worst selection the best and the worst subtours are mated (with probabilitypbest-worst). (b) By random selection the two subtours are selected at random (with probability 1-pbest-worst).
(a)
Best-worst selection (b)
Random selectionTheMutation Operator changes the Team Plan (with probability pmutation) by randomly swapping two genes between two different subtours. TheMigration Operator (applied with probability pmigration) removes a randomly chosen target from subtour Pi (of length ki) and adds it to subtour Pj (of length kj). The location at which this target is placed into subtour Pj is also chosen at random. Note that the lengths of the subtours change: ki decreases while kj increases.With probabilitypboost, each subtour is processed with aheuristic boosting technique. The 2-opt method [53–55] is adopted here to directly improve the quality of subtours (it replaces subtours with better ones from their “neighborhood”). The 2-opt method determines whether the inequality(10)cxi,xi+1+cxj,xj+1>cxi,xj+cxi+1,xj+1between the four vertices xi, xi+1, xj, and xj+1 of a path/subtour holds, in which case edges (xi,xi+1) and (xj,xj+1) are replaced with edges (xi,xj) and (xi+1,xj+1), respectively. This method provides a shorter path without intersecting edges.


## 4.1. Initialization Phase

During the initialization phase, the starting Team Plan—a starting set of subtours—is created. LetT1={t1,…,tn} and A={a1,…,am} be the sets of n targets and the m agents, respectively. Without loss of generality, we assume that the order of planning is a1,a2,…,am and that the starting subtours have similar lengths. A Team Plan is feasible if the subtours are pairwise disjoint (except possibly their starting points).At first, a subtourP1 (with starting point a1) of length k1 is chosen. Then subtour P2 is chosen from the target set T2 that is simply obtained by discarding from T1 the targets visited by agent a1. In general, the ith agent plans a subtour Pi on the targets not yet allocated previously. Obviously, this process yields a feasible Team Plan P={P1,…,Pm}.Here we utilize three simple initialization methods.(i)
Random initialization: for each agent the targets are selected at random from the unallocated ones.(ii)
Greedy initialization: the initial Team Plan is created using a greedy approach to form feasible starting subtours. Each agent selects its targets using a Nearest Neighbor heuristics: for a given a target, the next target will be the nearest one.(iii)
TSP-based initialization: for problems where the positions of them agents are not imposed (the m agents can start from any target ti∈T), a feasible starting Team Plan can be generated by clustering the TSP solution computed on the complete graph Kn(T). “Clustering” is carried out by discarding m edges from the TSP tour, in order to subdivide it “fairly”, and having m starting subtours with similar costs. This initialization method introduces a degree of complexity in the overall system, since a TSP solution must be computed.The initialization phase is an important step in the optimization process, since it directly influences the efficacy of the algorithm.


## 4.2. Evolution Phase

The evolution phase evolves the Team Plan, trying to design a strategy where the overall time is reduced (minimizing the costcmax(P); see (9)).This phase has the same mechanism of a classical Genetic Algorithm [50] with one important difference: there is only one Team Plan P to be evolved (i.e., the population size is 1).At every evolution/generation step, a set of operators (see Section4.3) is applied to the subtours Pi∈P. If P improves, it is kept for the next generation step, otherwise the previous Team Plan is restored (we expect that a simulated annealing-type modification will be even more efficient). The flowchart of the GAID evolution phase is shown in Figure 1.Figure 1
Flowchart of the evolution phase, together with the sequence of operators.


## 4.3. Team Plan Operators and Boosting

The evolution ofP toward a near-optimal multiagent strategy is accomplished by combining the genetic materials of its subtours through the application of genetic-like operators. Three different operators have been designed: crossover, mutation, and migration. The operators are applied in a predefined order, and their application depends on a given probability, as shown in Figure 1.Thecrossover operator (Figure 2) is applied with probability pcrossover and combines the genetic materials of two selected subtours (called parents), replacing them with the two newly created ones (the offsprings). Parents are chosen using the best-worst selection with probability pbest-worst (Figure 2(a)) or randomly (Figure 2(b)) with probability 1-pbest-worst. The parents are mated the classical way [50]: they are randomly halved (not necessarily at the same position) and the halves are simply swapped.Figure 2
Crossover operator. (a) In case of best-worst selection the best and the worst subtours are mated (with probabilitypbest-worst). (b) By random selection the two subtours are selected at random (with probability 1-pbest-worst).
(a)
Best-worst selection (b)
Random selectionTheMutation Operator changes the Team Plan (with probability pmutation) by randomly swapping two genes between two different subtours. TheMigration Operator (applied with probability pmigration) removes a randomly chosen target from subtour Pi (of length ki) and adds it to subtour Pj (of length kj). The location at which this target is placed into subtour Pj is also chosen at random. Note that the lengths of the subtours change: ki decreases while kj increases.With probabilitypboost, each subtour is processed with aheuristic boosting technique. The 2-opt method [53–55] is adopted here to directly improve the quality of subtours (it replaces subtours with better ones from their “neighborhood”). The 2-opt method determines whether the inequality(10)cxi,xi+1+cxj,xj+1>cxi,xj+cxi+1,xj+1between the four vertices xi, xi+1, xj, and xj+1 of a path/subtour holds, in which case edges (xi,xi+1) and (xj,xj+1) are replaced with edges (xi,xj) and (xi+1,xj+1), respectively. This method provides a shorter path without intersecting edges.


## 5. Results

An extensive set of simulations were run to test the performance of the proposed GAID method. Unless otherwise specified, simulations were run for150000 generation steps, while the crossover, mutation, migration, and boosting (2-opt) operators were applied with probabilities pcrossover=0.7, pmutation=0.4, pmigration=0.6, and pboost=0.3, respectively. For the application of the crossover operator, the probability of best-worst selection is pbest-worst=0.5 (thus the probability for random selection is 1-pbest-worst=0.5).


### 5.1. Comparison with Structured and Known Solutions

In this section, GAID is compared with known results. In order to make the comparison meaningful, we also imposed the same constraints (if any) used in the referenced works.


#### 5.1.1. An Example Problem with Known Solution

In this section we present a 9-81 MAPP (9 agents, 81 targets), in which the agents and targets form9 tightly packed clusters as shown in Figure 3. Each cluster contains an agent and 9 targets. Since the distances among the clusters are considerably longer than those among the points of a cluster, the optimal solution can be found by treating each cluster as a 1-9 MAPP (1 agent, 9 targets). The tour lengths are between 356.1 and 548.6, meaning that the optimal cost (the length of the longest tour) is 548.6 (see (9)). In Figure 3 we show the random and greedy initialization for this MAPP. In both cases some of the subtours contain a higher number of targets than others. We intentionally set the initialization this way to further challenge the algorithm. The initial tour lengths vary between 1944.9–15302.3 for the random, and 175.3–1627.9 for the greedy initialization. Consequently, the initial Team Plan costs are 15302.3 and 1627.9, respectively.Figure 3
The GAID algorithm was tested on a MAPP which contains 81 targets forming 9 clusters on a 2200 × 2200 square domain. An agent was placed into each cluster (white diamonds); thus the number of agents ism=9. The initial cost based on (9) is 15302.3 for random and 1627.9 for greedy initialization. The longest subtour is highlighted with thick line.
(a)
9-81 MAPP: initial plan with random initialization (b)
9-81 MAPP: initial plan with greedy initializationThe convergence of the Team Plan cost for both simulations is shown in Figure4 together with the cost of the optimal solution (548.6). At the end of the simulations the costs of the subtours varied between 378.3–612.3 and 389.9–594.1 for solutions starting from randomly initialized and greedy initialized Team Plans, respectively.Figure 4
Convergence of the Team Plan cost for the 9-81 MAPP shown in Figure3.The final Team Plans of the two simulations are shown in Figure5. We see that those long edges which initially connected targets belonging to different clusters were completely eliminated. The longest subtour connects the targets in the middle-top cluster for both simulations.Figure 5
The GAID algorithm found 9 subtours which connect targets belonging to the same cluster for the 9-81 MAPP with both initialization strategies. The final costs are612.3 and 594.1, respectively.
(a)
9-81 MAPP problem: final plan after random initialization (b)
9-81 MAPP problem: final plan after greedy initialization


#### 5.1.2. Comparison with Evolutionary Algorithms

We also compare our method with the results reported in [34], where an Ant Colony Optimization algorithm is compared with the Modified Genetic Algorithm (MGA) of [32]. We note here that these methods cannot solve the MAPP, therefore six MTSPs, all taken from well-known TSPLIB [56], are solved. The number of agents is set to m=5, and their starting location is the first target in the corresponding problem data file. Since a single depot is considered, only the greedy initialization method is used. In both [32, 34], rounded costs are considered. Therefore, for meaningful comparison, we need to minimize the following cost function:(11)croundC=∑i=1mroundcCi.In addition, the maximum length of the cycles,kmax, is limited to 20 (note that since MTSPs are considered here, we need to modify the Team Plan using cycles instead of paths). Results based on 100 simulations are presented in Table 1. In this case, our results outperform those reported in the above references. Figure 6 also shows the solution obtained for the pr76 TSPLIB problem.Table 1
Comparison between the proposed GAID, the Ant Colony Optimization, and the Modified Genetic Algorithm methods. Results are averaged over100 simulations. The number of targets is included in the TSPLIB problem name. kmax is the maximum number of targets an agent can visit. For each case, the fixed number of m=5 agents is considered, starting from the same location (one-depot problem). Only the greedy initialization method is used.
TSPLIB Problem k m a x ACO MGA GAID Difference of means Min Mean Min Mean Min Mean ACO MGA pr76 20 178597 180690 157444 160574 152722 156503.9 - 15.4 % -2.6% pr152 40 130953 136341 127839 133337 114698 126128.8 - 8 % -5.7% pr226 50 167646 170877 166827 178501 152198 158073.9 - 8 % -12.9% pr299 70 82106 83845 82176 85796 70059 71705.1 - 16.9 % -19.6% pr439 100 161955 165035 173839 183698 136169 138655.5 - 15.6 % -24.5% pr1002 220 382198 387205 427269 459179 311492 319240.4 - 17.5 % -30.5%Figure 6
The MTSP is solved for the pr76 TSPLIB target configuration. The maximum plan length iskmax=20 targets and the number of agents is m=5. The cost function specified by (11) is minimized, and the comparison between the starting and the final Team Plans is shown. In (a) the starting Team Plan, with cost equal to 194618, is shown, while in (b) the final Team Plan, with cost equal to 152722, is reported. These solutions are 15.4% and 2.6% better than the referenced ones, obtained by implementing an Ant Colony Optimization method and a Modified Genetic Algorithm, respectively.
(a)
pr76 TSPLIB problem: starting Team Plan (b)
pr76 TSPLIB problem: final Team Plan


#### 5.1.3. Comparison with Heuristics

We compare our method against the results reported in [42], where different heuristics for solving MTSP instances are proposed and compared.In [42], a no-depot MTSP variant is considered (the agents do not have a predefined starting location), and the min–max optimization problem is solved ((9) is minimized). In addition, the number of salesmen is fixed and no constraints on the plan lengths are imposed. Note that since we are comparing our method with MTSP results, we need to modify our Team Plan accordingly, using cycles instead of paths. In addition, since in [42] rounded distances are considered, for meaningful comparison the cost function (see (9)) is modified accordingly: (12)cmaxroundC=maxi⁡roundcCi.For each test case, our results are compared with only the best ones of [42]. We also report the name of the Heuristic with which each referenced solution has been obtained (please refer to [42] for a more detailed description of the adopted heuristic methods). Tables 2 and 3 show the results obtained by initializing the Team Plan with either the greedy or the TSP-based initialization methods, respectively. Results are averaged over 100 simulations.Table 2
Heuristics comparison for100 simulations. The greedy initialization method was used.
TSPLIB Problem Number of Agents Heuristics Greedy initialization Errors Method Minimum Mean Minimum Mean Minimum Mean berlin52 4 Bisection 2182 2204.3 2183 2422.4 0.04 % 9.8 % 5 k-split 1713 1739.7 1825 2160.4 6.5 % 24.2 % 6 SGH 1531 1585 1611 1905.8 — 20.2 % Bisection 1476 1643.1 9.1 % —  kroA100 4 SGH 5955 6096.7 6000 6690.3 0.7 % 9.7 % 5 k-split 4629 5025.9 4964 5620.1 7.2 % 11.8 % 6 k-center 4200 4429.4 4370 5038.4 4 % — k-means 4230 4234.6 — 18.9 %  bier127 4 Bisection 32423 32757.5 32434 35740.9 0.03 % 9.1 % 6 k-split 22815 23071.7 24608 26993.3 7.8 % 16.9 %  pr264 4 Bisection 12705 12705 12196 13830.3 - 4.1 % 8.8 % 6 k-means 8526 9131.6 9000 10256.3 5.5 % — Bisection 8739 9051.6 — 13.3 %Table 3
Heuristics comparison for100 simulations using the TSP-based initialization.
TSPLIB Problem Number of Agents Heuristics TSP-based initialization Errors Method Minimum Mean Minimum Mean Minimum Mean berlin52 4 Bisection 2182 2204.3 2088 2359.6 - 4.5 % 7% 5 k-split 1713 1739.7 1804 2014.8 5.3 % 15.8% 6 SGH 1531 1585 1576 1801.2 — 13.6% Bisection 1476 1643.1 6.7 % —  kroA100 4 SGH 5955 6096.7 6000 6443.6 0.7 % 5.7% 5 k-split 4629 5025.9 4796 5314.6 3.6 % 5.7% 6 k-center 4200 4429.4 4310 4693.9 2.6 % — k-means 4230 4234.6 — 10.8%  bier127 4 Bisection 32423 32757.5 32948 34606 1.6 % 5.6% 6 k-split 22815 23071.7 24290 26497.1 6.4 % 14.8%  pr264 4 Bisection 12705 12705 13400 19135.3 5.4 % 50.6% 6 k-means 8526 9131.6 8629 14395.8 1.2 % — Bisection 8739 9051.6 — 59%In each test case, GAID returns good solutions, regardless of the applied initialization method. In general, our best solutions are close to the ones from the literature and in a few cases (e.g., in the berlin52 or the pr264 problems) are even better. The greedy initialization method seems to provide a better initial Team Plan in those problems where the distribution of targets has a well-defined structure (the pr264 problem), while in “small-size” problems (i.e., berlin52) the TSP-based method is preferable (even if the obtained improvement does not justify its required complexity, time, and computational costs). Even though these heuristics are superior in solving MTSP compared to GAID, they cannot solve MAPP, while our method can solve both.Figure7 shows the solutions obtained by applying the greedy (Figure 7(a)) and the TSP-based (Figure 7(b)) initialization methods for the kroA100 problem (with m=5 agents). Compared with [42], the TSP-based method and the greedy method result in final solutions that are only 3.6% and 7.2% worse than the cited one, respectively.Figure 7
Solving the MTSP by the greedy and the cluster initialization methods. In both cases,m=5 agents are considered, and the target set is kroA100. In (a), the greedy initialization method is used and the final obtained Team Plan is shown. The cost is 4964, and it is 7.2% worse than the referenced one. In (b), the TSP-based initialization method is used and the obtained final Team Plan is shown. The cost is 4796, which is only 3.6% worse than the referenced one.
(a)
kroA100 problem: greedy initialization (b)
kroA100 problem: TSP-based initialization


### 5.2. Comparison with Other Software

In this section we test GAID against a freely available Matlab MTSP solver based on a Genetic Algorithm [57].The number of agents is fixed, and the minimum path size,kmin=2, is imposed (this way, solutions with paths composed of only one target are avoided). The cost function, which is specified by (9), is minimized, and targets are randomly generated over the unit square map. In all simulations, the greedy initialization method is adopted. Since the Matlab MTSP solver is based only on a Genetic Algorithm and no heuristics is used, we also run a set of tests with pboost=0%.Table4 shows the obtained results, averaged over 100 simulations. Our method clearly outperforms the Matlab solver (clearly, with the 2-opt method the results are much better). Figure 8 shows two examples where the Matlab MTSP solver solution is compared with the GAID ones.Table 4
Comparison between the proposed GAID method and a Matlab MTSP code. For each test,kmin=2 and the greedy initialization method is used. Targets are randomly generated over the unit square.
Test case Matlab code Proposed method Cost variation Min Mean Max p b o o s t Min Mean Max Min Mean Max 100 targets 7.14 8.19 9.21 30 % 6.37 6.72 7.11 - 10.7 % - 17.9 % -22.8% 10 agents 0 % 6.67 7.14 7.58 - 6.5 % - 12.8 % -17.7%  200 targets 15.64 17.5 19.65 30 % 9.55 9.89 10.25 - 39 % - 43.5 % -47.8% 20 agents 0 % 10.05 10.6 11.23 - 35.7 % - 39.4 % -42.8%Figure 8
GAID has been compared with the Matlab MTSP solver. In this example, MAPP is solved for100 targets randomly distributed in the unit square. m=10 agents are considered. The minimum path length is kmin=2. The cost function (see (9)) is minimized. In (a) the solution obtained by running the MTSP Matlab solver is shown, with cost 7.92. In (b) our solution is shown with cost 6.37, which is 19.5% better than the Matlab MTSP solution.
(a)
Matlab solution (b)
Proposed method


### 5.3. Solution for a Large Example Problem

We tested our algorithm on a 20-400 MAPP. The initial Team Plan was constructed by means of the greedy initialization method, such that each subtour visits10 targets. The simulation was ran for 1000000 generations.Figures9 and 10 summarize the results. The initial cost of 1.94 was reduced by 43.5% (to 1.08) by the end of the 150000th generation and by a further 5.7% (to 0.94) till the end of the simulation.Figure 9
The GAID algorithm was performed on a MAPP with 20 agents and 400 targets located in the unit square. The Team Plan cost was1.91 after the initialization and was reduced to 1.08 by the end of the 150000th generation and to 0.94 by the end of the simulation. The longest subtour is highlighted by a thick line.
(a)
20-400 MAPP: initial Team Plan with greedy initialization (b)
20-400 MAPP: final Team Plan after the 1000000th generationFigure 10
Convergence of the Team Plan cost for the 20-400 MAPP shown in Figure9.


## 5.1. Comparison with Structured and Known Solutions

In this section, GAID is compared with known results. In order to make the comparison meaningful, we also imposed the same constraints (if any) used in the referenced works.


### 5.1.1. An Example Problem with Known Solution

In this section we present a 9-81 MAPP (9 agents, 81 targets), in which the agents and targets form9 tightly packed clusters as shown in Figure 3. Each cluster contains an agent and 9 targets. Since the distances among the clusters are considerably longer than those among the points of a cluster, the optimal solution can be found by treating each cluster as a 1-9 MAPP (1 agent, 9 targets). The tour lengths are between 356.1 and 548.6, meaning that the optimal cost (the length of the longest tour) is 548.6 (see (9)). In Figure 3 we show the random and greedy initialization for this MAPP. In both cases some of the subtours contain a higher number of targets than others. We intentionally set the initialization this way to further challenge the algorithm. The initial tour lengths vary between 1944.9–15302.3 for the random, and 175.3–1627.9 for the greedy initialization. Consequently, the initial Team Plan costs are 15302.3 and 1627.9, respectively.Figure 3
The GAID algorithm was tested on a MAPP which contains 81 targets forming 9 clusters on a 2200 × 2200 square domain. An agent was placed into each cluster (white diamonds); thus the number of agents ism=9. The initial cost based on (9) is 15302.3 for random and 1627.9 for greedy initialization. The longest subtour is highlighted with thick line.
(a)
9-81 MAPP: initial plan with random initialization (b)
9-81 MAPP: initial plan with greedy initializationThe convergence of the Team Plan cost for both simulations is shown in Figure4 together with the cost of the optimal solution (548.6). At the end of the simulations the costs of the subtours varied between 378.3–612.3 and 389.9–594.1 for solutions starting from randomly initialized and greedy initialized Team Plans, respectively.Figure 4
Convergence of the Team Plan cost for the 9-81 MAPP shown in Figure3.The final Team Plans of the two simulations are shown in Figure5. We see that those long edges which initially connected targets belonging to different clusters were completely eliminated. The longest subtour connects the targets in the middle-top cluster for both simulations.Figure 5
The GAID algorithm found 9 subtours which connect targets belonging to the same cluster for the 9-81 MAPP with both initialization strategies. The final costs are612.3 and 594.1, respectively.
(a)
9-81 MAPP problem: final plan after random initialization (b)
9-81 MAPP problem: final plan after greedy initialization


### 5.1.2. Comparison with Evolutionary Algorithms

We also compare our method with the results reported in [34], where an Ant Colony Optimization algorithm is compared with the Modified Genetic Algorithm (MGA) of [32]. We note here that these methods cannot solve the MAPP, therefore six MTSPs, all taken from well-known TSPLIB [56], are solved. The number of agents is set to m=5, and their starting location is the first target in the corresponding problem data file. Since a single depot is considered, only the greedy initialization method is used. In both [32, 34], rounded costs are considered. Therefore, for meaningful comparison, we need to minimize the following cost function:(11)croundC=∑i=1mroundcCi.In addition, the maximum length of the cycles,kmax, is limited to 20 (note that since MTSPs are considered here, we need to modify the Team Plan using cycles instead of paths). Results based on 100 simulations are presented in Table 1. In this case, our results outperform those reported in the above references. Figure 6 also shows the solution obtained for the pr76 TSPLIB problem.Table 1
Comparison between the proposed GAID, the Ant Colony Optimization, and the Modified Genetic Algorithm methods. Results are averaged over100 simulations. The number of targets is included in the TSPLIB problem name. kmax is the maximum number of targets an agent can visit. For each case, the fixed number of m=5 agents is considered, starting from the same location (one-depot problem). Only the greedy initialization method is used.
TSPLIB Problem k m a x ACO MGA GAID Difference of means Min Mean Min Mean Min Mean ACO MGA pr76 20 178597 180690 157444 160574 152722 156503.9 - 15.4 % -2.6% pr152 40 130953 136341 127839 133337 114698 126128.8 - 8 % -5.7% pr226 50 167646 170877 166827 178501 152198 158073.9 - 8 % -12.9% pr299 70 82106 83845 82176 85796 70059 71705.1 - 16.9 % -19.6% pr439 100 161955 165035 173839 183698 136169 138655.5 - 15.6 % -24.5% pr1002 220 382198 387205 427269 459179 311492 319240.4 - 17.5 % -30.5%Figure 6
The MTSP is solved for the pr76 TSPLIB target configuration. The maximum plan length iskmax=20 targets and the number of agents is m=5. The cost function specified by (11) is minimized, and the comparison between the starting and the final Team Plans is shown. In (a) the starting Team Plan, with cost equal to 194618, is shown, while in (b) the final Team Plan, with cost equal to 152722, is reported. These solutions are 15.4% and 2.6% better than the referenced ones, obtained by implementing an Ant Colony Optimization method and a Modified Genetic Algorithm, respectively.
(a)
pr76 TSPLIB problem: starting Team Plan (b)
pr76 TSPLIB problem: final Team Plan


### 5.1.3. Comparison with Heuristics

We compare our method against the results reported in [42], where different heuristics for solving MTSP instances are proposed and compared.In [42], a no-depot MTSP variant is considered (the agents do not have a predefined starting location), and the min–max optimization problem is solved ((9) is minimized). In addition, the number of salesmen is fixed and no constraints on the plan lengths are imposed. Note that since we are comparing our method with MTSP results, we need to modify our Team Plan accordingly, using cycles instead of paths. In addition, since in [42] rounded distances are considered, for meaningful comparison the cost function (see (9)) is modified accordingly: (12)cmaxroundC=maxi⁡roundcCi.For each test case, our results are compared with only the best ones of [42]. We also report the name of the Heuristic with which each referenced solution has been obtained (please refer to [42] for a more detailed description of the adopted heuristic methods). Tables 2 and 3 show the results obtained by initializing the Team Plan with either the greedy or the TSP-based initialization methods, respectively. Results are averaged over 100 simulations.Table 2
Heuristics comparison for100 simulations. The greedy initialization method was used.
TSPLIB Problem Number of Agents Heuristics Greedy initialization Errors Method Minimum Mean Minimum Mean Minimum Mean berlin52 4 Bisection 2182 2204.3 2183 2422.4 0.04 % 9.8 % 5 k-split 1713 1739.7 1825 2160.4 6.5 % 24.2 % 6 SGH 1531 1585 1611 1905.8 — 20.2 % Bisection 1476 1643.1 9.1 % —  kroA100 4 SGH 5955 6096.7 6000 6690.3 0.7 % 9.7 % 5 k-split 4629 5025.9 4964 5620.1 7.2 % 11.8 % 6 k-center 4200 4429.4 4370 5038.4 4 % — k-means 4230 4234.6 — 18.9 %  bier127 4 Bisection 32423 32757.5 32434 35740.9 0.03 % 9.1 % 6 k-split 22815 23071.7 24608 26993.3 7.8 % 16.9 %  pr264 4 Bisection 12705 12705 12196 13830.3 - 4.1 % 8.8 % 6 k-means 8526 9131.6 9000 10256.3 5.5 % — Bisection 8739 9051.6 — 13.3 %Table 3
Heuristics comparison for100 simulations using the TSP-based initialization.
TSPLIB Problem Number of Agents Heuristics TSP-based initialization Errors Method Minimum Mean Minimum Mean Minimum Mean berlin52 4 Bisection 2182 2204.3 2088 2359.6 - 4.5 % 7% 5 k-split 1713 1739.7 1804 2014.8 5.3 % 15.8% 6 SGH 1531 1585 1576 1801.2 — 13.6% Bisection 1476 1643.1 6.7 % —  kroA100 4 SGH 5955 6096.7 6000 6443.6 0.7 % 5.7% 5 k-split 4629 5025.9 4796 5314.6 3.6 % 5.7% 6 k-center 4200 4429.4 4310 4693.9 2.6 % — k-means 4230 4234.6 — 10.8%  bier127 4 Bisection 32423 32757.5 32948 34606 1.6 % 5.6% 6 k-split 22815 23071.7 24290 26497.1 6.4 % 14.8%  pr264 4 Bisection 12705 12705 13400 19135.3 5.4 % 50.6% 6 k-means 8526 9131.6 8629 14395.8 1.2 % — Bisection 8739 9051.6 — 59%In each test case, GAID returns good solutions, regardless of the applied initialization method. In general, our best solutions are close to the ones from the literature and in a few cases (e.g., in the berlin52 or the pr264 problems) are even better. The greedy initialization method seems to provide a better initial Team Plan in those problems where the distribution of targets has a well-defined structure (the pr264 problem), while in “small-size” problems (i.e., berlin52) the TSP-based method is preferable (even if the obtained improvement does not justify its required complexity, time, and computational costs). Even though these heuristics are superior in solving MTSP compared to GAID, they cannot solve MAPP, while our method can solve both.Figure7 shows the solutions obtained by applying the greedy (Figure 7(a)) and the TSP-based (Figure 7(b)) initialization methods for the kroA100 problem (with m=5 agents). Compared with [42], the TSP-based method and the greedy method result in final solutions that are only 3.6% and 7.2% worse than the cited one, respectively.Figure 7
Solving the MTSP by the greedy and the cluster initialization methods. In both cases,m=5 agents are considered, and the target set is kroA100. In (a), the greedy initialization method is used and the final obtained Team Plan is shown. The cost is 4964, and it is 7.2% worse than the referenced one. In (b), the TSP-based initialization method is used and the obtained final Team Plan is shown. The cost is 4796, which is only 3.6% worse than the referenced one.
(a)
kroA100 problem: greedy initialization (b)
kroA100 problem: TSP-based initialization


## 5.1.1. An Example Problem with Known Solution

In this section we present a 9-81 MAPP (9 agents, 81 targets), in which the agents and targets form9 tightly packed clusters as shown in Figure 3. Each cluster contains an agent and 9 targets. Since the distances among the clusters are considerably longer than those among the points of a cluster, the optimal solution can be found by treating each cluster as a 1-9 MAPP (1 agent, 9 targets). The tour lengths are between 356.1 and 548.6, meaning that the optimal cost (the length of the longest tour) is 548.6 (see (9)). In Figure 3 we show the random and greedy initialization for this MAPP. In both cases some of the subtours contain a higher number of targets than others. We intentionally set the initialization this way to further challenge the algorithm. The initial tour lengths vary between 1944.9–15302.3 for the random, and 175.3–1627.9 for the greedy initialization. Consequently, the initial Team Plan costs are 15302.3 and 1627.9, respectively.Figure 3
The GAID algorithm was tested on a MAPP which contains 81 targets forming 9 clusters on a 2200 × 2200 square domain. An agent was placed into each cluster (white diamonds); thus the number of agents ism=9. The initial cost based on (9) is 15302.3 for random and 1627.9 for greedy initialization. The longest subtour is highlighted with thick line.
(a)
9-81 MAPP: initial plan with random initialization (b)
9-81 MAPP: initial plan with greedy initializationThe convergence of the Team Plan cost for both simulations is shown in Figure4 together with the cost of the optimal solution (548.6). At the end of the simulations the costs of the subtours varied between 378.3–612.3 and 389.9–594.1 for solutions starting from randomly initialized and greedy initialized Team Plans, respectively.Figure 4
Convergence of the Team Plan cost for the 9-81 MAPP shown in Figure3.The final Team Plans of the two simulations are shown in Figure5. We see that those long edges which initially connected targets belonging to different clusters were completely eliminated. The longest subtour connects the targets in the middle-top cluster for both simulations.Figure 5
The GAID algorithm found 9 subtours which connect targets belonging to the same cluster for the 9-81 MAPP with both initialization strategies. The final costs are612.3 and 594.1, respectively.
(a)
9-81 MAPP problem: final plan after random initialization (b)
9-81 MAPP problem: final plan after greedy initialization


## 5.1.2. Comparison with Evolutionary Algorithms

We also compare our method with the results reported in [34], where an Ant Colony Optimization algorithm is compared with the Modified Genetic Algorithm (MGA) of [32]. We note here that these methods cannot solve the MAPP, therefore six MTSPs, all taken from well-known TSPLIB [56], are solved. The number of agents is set to m=5, and their starting location is the first target in the corresponding problem data file. Since a single depot is considered, only the greedy initialization method is used. In both [32, 34], rounded costs are considered. Therefore, for meaningful comparison, we need to minimize the following cost function:(11)croundC=∑i=1mroundcCi.In addition, the maximum length of the cycles,kmax, is limited to 20 (note that since MTSPs are considered here, we need to modify the Team Plan using cycles instead of paths). Results based on 100 simulations are presented in Table 1. In this case, our results outperform those reported in the above references. Figure 6 also shows the solution obtained for the pr76 TSPLIB problem.Table 1
Comparison between the proposed GAID, the Ant Colony Optimization, and the Modified Genetic Algorithm methods. Results are averaged over100 simulations. The number of targets is included in the TSPLIB problem name. kmax is the maximum number of targets an agent can visit. For each case, the fixed number of m=5 agents is considered, starting from the same location (one-depot problem). Only the greedy initialization method is used.
TSPLIB Problem k m a x ACO MGA GAID Difference of means Min Mean Min Mean Min Mean ACO MGA pr76 20 178597 180690 157444 160574 152722 156503.9 - 15.4 % -2.6% pr152 40 130953 136341 127839 133337 114698 126128.8 - 8 % -5.7% pr226 50 167646 170877 166827 178501 152198 158073.9 - 8 % -12.9% pr299 70 82106 83845 82176 85796 70059 71705.1 - 16.9 % -19.6% pr439 100 161955 165035 173839 183698 136169 138655.5 - 15.6 % -24.5% pr1002 220 382198 387205 427269 459179 311492 319240.4 - 17.5 % -30.5%Figure 6
The MTSP is solved for the pr76 TSPLIB target configuration. The maximum plan length iskmax=20 targets and the number of agents is m=5. The cost function specified by (11) is minimized, and the comparison between the starting and the final Team Plans is shown. In (a) the starting Team Plan, with cost equal to 194618, is shown, while in (b) the final Team Plan, with cost equal to 152722, is reported. These solutions are 15.4% and 2.6% better than the referenced ones, obtained by implementing an Ant Colony Optimization method and a Modified Genetic Algorithm, respectively.
(a)
pr76 TSPLIB problem: starting Team Plan (b)
pr76 TSPLIB problem: final Team Plan


## 5.1.3. Comparison with Heuristics

We compare our method against the results reported in [42], where different heuristics for solving MTSP instances are proposed and compared.In [42], a no-depot MTSP variant is considered (the agents do not have a predefined starting location), and the min–max optimization problem is solved ((9) is minimized). In addition, the number of salesmen is fixed and no constraints on the plan lengths are imposed. Note that since we are comparing our method with MTSP results, we need to modify our Team Plan accordingly, using cycles instead of paths. In addition, since in [42] rounded distances are considered, for meaningful comparison the cost function (see (9)) is modified accordingly: (12)cmaxroundC=maxi⁡roundcCi.For each test case, our results are compared with only the best ones of [42]. We also report the name of the Heuristic with which each referenced solution has been obtained (please refer to [42] for a more detailed description of the adopted heuristic methods). Tables 2 and 3 show the results obtained by initializing the Team Plan with either the greedy or the TSP-based initialization methods, respectively. Results are averaged over 100 simulations.Table 2
Heuristics comparison for100 simulations. The greedy initialization method was used.
TSPLIB Problem Number of Agents Heuristics Greedy initialization Errors Method Minimum Mean Minimum Mean Minimum Mean berlin52 4 Bisection 2182 2204.3 2183 2422.4 0.04 % 9.8 % 5 k-split 1713 1739.7 1825 2160.4 6.5 % 24.2 % 6 SGH 1531 1585 1611 1905.8 — 20.2 % Bisection 1476 1643.1 9.1 % —  kroA100 4 SGH 5955 6096.7 6000 6690.3 0.7 % 9.7 % 5 k-split 4629 5025.9 4964 5620.1 7.2 % 11.8 % 6 k-center 4200 4429.4 4370 5038.4 4 % — k-means 4230 4234.6 — 18.9 %  bier127 4 Bisection 32423 32757.5 32434 35740.9 0.03 % 9.1 % 6 k-split 22815 23071.7 24608 26993.3 7.8 % 16.9 %  pr264 4 Bisection 12705 12705 12196 13830.3 - 4.1 % 8.8 % 6 k-means 8526 9131.6 9000 10256.3 5.5 % — Bisection 8739 9051.6 — 13.3 %Table 3
Heuristics comparison for100 simulations using the TSP-based initialization.
TSPLIB Problem Number of Agents Heuristics TSP-based initialization Errors Method Minimum Mean Minimum Mean Minimum Mean berlin52 4 Bisection 2182 2204.3 2088 2359.6 - 4.5 % 7% 5 k-split 1713 1739.7 1804 2014.8 5.3 % 15.8% 6 SGH 1531 1585 1576 1801.2 — 13.6% Bisection 1476 1643.1 6.7 % —  kroA100 4 SGH 5955 6096.7 6000 6443.6 0.7 % 5.7% 5 k-split 4629 5025.9 4796 5314.6 3.6 % 5.7% 6 k-center 4200 4429.4 4310 4693.9 2.6 % — k-means 4230 4234.6 — 10.8%  bier127 4 Bisection 32423 32757.5 32948 34606 1.6 % 5.6% 6 k-split 22815 23071.7 24290 26497.1 6.4 % 14.8%  pr264 4 Bisection 12705 12705 13400 19135.3 5.4 % 50.6% 6 k-means 8526 9131.6 8629 14395.8 1.2 % — Bisection 8739 9051.6 — 59%In each test case, GAID returns good solutions, regardless of the applied initialization method. In general, our best solutions are close to the ones from the literature and in a few cases (e.g., in the berlin52 or the pr264 problems) are even better. The greedy initialization method seems to provide a better initial Team Plan in those problems where the distribution of targets has a well-defined structure (the pr264 problem), while in “small-size” problems (i.e., berlin52) the TSP-based method is preferable (even if the obtained improvement does not justify its required complexity, time, and computational costs). Even though these heuristics are superior in solving MTSP compared to GAID, they cannot solve MAPP, while our method can solve both.Figure7 shows the solutions obtained by applying the greedy (Figure 7(a)) and the TSP-based (Figure 7(b)) initialization methods for the kroA100 problem (with m=5 agents). Compared with [42], the TSP-based method and the greedy method result in final solutions that are only 3.6% and 7.2% worse than the cited one, respectively.Figure 7
Solving the MTSP by the greedy and the cluster initialization methods. In both cases,m=5 agents are considered, and the target set is kroA100. In (a), the greedy initialization method is used and the final obtained Team Plan is shown. The cost is 4964, and it is 7.2% worse than the referenced one. In (b), the TSP-based initialization method is used and the obtained final Team Plan is shown. The cost is 4796, which is only 3.6% worse than the referenced one.
(a)
kroA100 problem: greedy initialization (b)
kroA100 problem: TSP-based initialization


## 5.2. Comparison with Other Software

In this section we test GAID against a freely available Matlab MTSP solver based on a Genetic Algorithm [57].The number of agents is fixed, and the minimum path size,kmin=2, is imposed (this way, solutions with paths composed of only one target are avoided). The cost function, which is specified by (9), is minimized, and targets are randomly generated over the unit square map. In all simulations, the greedy initialization method is adopted. Since the Matlab MTSP solver is based only on a Genetic Algorithm and no heuristics is used, we also run a set of tests with pboost=0%.Table4 shows the obtained results, averaged over 100 simulations. Our method clearly outperforms the Matlab solver (clearly, with the 2-opt method the results are much better). Figure 8 shows two examples where the Matlab MTSP solver solution is compared with the GAID ones.Table 4
Comparison between the proposed GAID method and a Matlab MTSP code. For each test,kmin=2 and the greedy initialization method is used. Targets are randomly generated over the unit square.
Test case Matlab code Proposed method Cost variation Min Mean Max p b o o s t Min Mean Max Min Mean Max 100 targets 7.14 8.19 9.21 30 % 6.37 6.72 7.11 - 10.7 % - 17.9 % -22.8% 10 agents 0 % 6.67 7.14 7.58 - 6.5 % - 12.8 % -17.7%  200 targets 15.64 17.5 19.65 30 % 9.55 9.89 10.25 - 39 % - 43.5 % -47.8% 20 agents 0 % 10.05 10.6 11.23 - 35.7 % - 39.4 % -42.8%Figure 8
GAID has been compared with the Matlab MTSP solver. In this example, MAPP is solved for100 targets randomly distributed in the unit square. m=10 agents are considered. The minimum path length is kmin=2. The cost function (see (9)) is minimized. In (a) the solution obtained by running the MTSP Matlab solver is shown, with cost 7.92. In (b) our solution is shown with cost 6.37, which is 19.5% better than the Matlab MTSP solution.
(a)
Matlab solution (b)
Proposed method


## 5.3. Solution for a Large Example Problem

We tested our algorithm on a 20-400 MAPP. The initial Team Plan was constructed by means of the greedy initialization method, such that each subtour visits10 targets. The simulation was ran for 1000000 generations.Figures9 and 10 summarize the results. The initial cost of 1.94 was reduced by 43.5% (to 1.08) by the end of the 150000th generation and by a further 5.7% (to 0.94) till the end of the simulation.Figure 9
The GAID algorithm was performed on a MAPP with 20 agents and 400 targets located in the unit square. The Team Plan cost was1.91 after the initialization and was reduced to 1.08 by the end of the 150000th generation and to 0.94 by the end of the simulation. The longest subtour is highlighted by a thick line.
(a)
20-400 MAPP: initial Team Plan with greedy initialization (b)
20-400 MAPP: final Team Plan after the 1000000th generationFigure 10
Convergence of the Team Plan cost for the 20-400 MAPP shown in Figure9.


## 6. Conclusions and Future Work

This paper describes the Multiagent Planning Problem, a variant of the classical Multiple Traveling Salesman Problem. Our solution method uses a simplified Genetic Algorithm, called Genetic Algorithm Inspired Descent (GAID), capable of solving both the MTSP and the MAPP. GAID takes an initial Team Plan and applies various genetic operators to decrease the length of the longest path. 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 MTSP (e.g.,k-split, bisection) outperformed GAID, these methods cannot solve MAPP. GAID proved to be much better than the Matlab MAPP solver. GAID is also easy to implement.A long-term goal of this work is to endow a team of autonomous agents (drones) with the capability of cooperative motion planning. In this application, the time available for the solution is limited and fast algorithms providing good approximate solutions prevail. The results presented here show the success of the approach, demonstrating how a simple method can solve an otherwise hard combinatorial problem.



---

*Source: 3813912-2017-02-05.xml*