Encyclopedia
Please note this is an old version of this entry, which may differ significantly from the current revision.
Subjects:
Mathematics, Applied
Multiple traveling salesperson problems (mTSP) are a collection of problems that generalize the classical traveling salesperson problem (TSP). In a nutshell, an mTSP variant seeks a minimum cost collection of m paths that visit all vertices of a given weighted complete graph.
- integer programming
- multiple traveling salesperson problem
- depot-free mTSP
1. Introduction
The multiple traveling salesperson problem has received different labels over time, mainly because it is not a single problem but a collection of them. Thus, this text refers to this collection as the multiple traveling salesperson problems (mTSP). These problems are relevant in several social situations, including cooperative missions, transportation, delivery, disaster management, precision agriculture, and many others [1].
Each variant of mTSP is a generalization of the NP-hard traveling salesperson problem (TSP). The goal of TSP is to find a minimum-cost closed path a salesperson must follow to visit a set of given cities. In more detail, given a weighted complete graph G=(V, E), the TSP seeks a closed path that visits all vertices once, minimizing the path’s cost [2,3,4]. In the mTSP, the input is a weighted complete graph G=(V, E) and a positive integer m; its goal is to find a set of m paths such that all vertices are visited once by some salesperson [4,5]. If the input graph is undirected (resp., directed), the problem is symmetric (resp., asymmetric). An mTSP variant receives particular adjectives depending on its characteristics: depot free (DF), single depot (S), multiple depots (M), closed paths (CP), open paths (OP), bounding constraints, etc. In most cases, the objective function to minimize is the sum of the paths’ costs (minsum) or the largest path (minmax or makespan); other objective functions might be considered, such as the cost of the largest edge (bottleneck).
The most widely studied members of the mTSP collection are single-depot mTSP (SmTSP) and multiple-depots mTSP (MmTSP). However, the depot-free mTSP (DFmTSP) variant has received less attention. In SmTSP, all salespersons must start and finish their path at a specific vertex (the depot), which is part of the input. In the fixed-destination multiple-depots mTSP (FD-MmTSP), m depots are part of the input, and each salesperson must start and finish their path at their respective depot. In the non-fixed-destination multiple-depots mTSP (NFD-MmTSP), each salesperson can finish their path at a different depot. In DFmTSP, the depot concept is not involved. Therefore, it seeks a disjoint collection of closed paths that visit all vertices. In all these variants, every solution consists of exactly m paths, and the path followed by each salesperson is closed. Nevertheless, if the salespersons are constrained to follow open paths (i.e., they do not need to return to their depot), researchers refer to the problem as an open-paths (OP) variant. To clarify the difference between these variants, Figure 1 shows a set of optimal solutions for DFmTSP, SmTSP, and FD-MmTSP. In all these examples, each path must have between three and five vertices; this text refers to these as bounding constraints.
Figure 1. Optimal solutions for (a) closed-paths depot-free mTSP (CP-DFmTSP), (b) closed-paths single-depot mTSP (CP-SmTSP), and (c) closed-paths fixed-destination multiple-depots mTSP (CP-FD-MmTSP). The objective function is minsum, the number of salespersons is two (m=2), each path must have between three and five vertices (bounding constraints), the cost of each edge equals the euclidean distance between its vertices, and the depots are marked in green. Subfigures (d–f) correspond to the respective open-paths (OP) variants.
Although there are some surveys on mTSP [1,6,7], they are not structured in chronological order; order that might shed some light on how DFmTSP has received less attention than other variants. Therefore, the following sections give a general overview of how the study of mTSP has evolved. To maintain simplicity, researchers stuck to the broad categories: SmTSP, MmTSP, and DFmTSP. Namely, sophisticated requirements studied in some examined papers (objective functions, paths’ properties, time windows, etc.) are omitted.
2. TSP and SmTSP
TSP is among the most popular NP-hard combinatorial optimization problems. Its first explicit appearance in the scientific literature dates from 1954 [2], and its first mathematical formulations from 1959 and 1960 [3,4]. Interestingly, the authors of these early papers stated the problem using the depot concept, a special vertex where the salesperson starts and finishes their path. Nevertheless, it is easy to observe that the depot plays only a symbolic and didactic role, i.e., it is equivalent to stating that the path must be closed. However, the first member of the mTSP collection to be studied was SmTSP; in this version of the problem, all salespersons start and finish their path at the same vertex (the depot), which is part of the input. The most usual objective function to minimize in both TSP and mTSP is minsum, i.e., the total length of the paths. Naturally, mTSP with one salesperson (m=1) is equivalent to TSP; therefore, mTSP is NP-hard too.
3. mTSP from 1960 to 1975
Although the first IP for SmTSP dates from 1960 [4], the problem started gaining more attention between 1973 and 1975, when more efficient mathematical formulations were introduced [5,10]; the authors did not refer to the problem as SmTSP but as mTSP. For that reason, many use both names interchangeably. However, to avoid confusion, researchers refer to this variant only as SmTSP. Something remarkable about SmTSP is that it can be transformed into TSP by adding some extra vertices to the original graph [10].
4. mTSP from 1976 to 1995
SmTSP and many of its variants continued being modeled using integer programming. Most of these formulations were based on transformations to TSP [11,12,13,14,15,16,17,18,19], and only a few were direct [20,21]. Some variants included the case where at most m salespersons are in the solution; some refer to such variant as the SmTSP with fixed charges [13], and others as variable SmTSP [22]. In this variant, each salesperson incurs some cost that is considered in the objective function. Notice that the variant identified as SmTSP is where exactly m salespersons are in the solution. The exact algorithms designed for this problem within this period were based mainly on Benders decomposition [14], cutting planes [20], and branch and bound [23]. In this same period, some heuristics for SmTSP were introduced too [19,24,25,26,27]. By 1995, SmTSP with a minsum objective function was the most studied member of the mTSP collection; only the MmTSP with two salespersons (m=2) was mentioned and reduced to TSP in 1980 [15]. It was until 1995 that MmTSP was reduced to TSP [18]. In this period, only a tabu search metaheuristic approach was developed for SmTSP [28].
5. mTSP from 1996 to 2005
MmTSP started gaining more attention. More heuristics and metaheuristics considering minsum and minmax objective functions for SmTSP, MmTSP, and DFmTSP were introduced too, for instance, neural networks [29,30,31], genetic algorithms [32,33,34], particle swarm optimization [33], evolutionary strategies [33], and simulated annealing [35]. It is crucial to emphasize that during this period, DFmTSP started being spotted by some authors [32,33,36]. Although some of them referred to the problem as mTSP or SmTSP, a closer inspection reveals that the problem they worked with was actually DFmTSP.
6. mTSP from 2006 to Date
The interest in SmTSP, MmTSP, DFmTSP, and their variants continued growing. The interest in the minmax objective function grew too. However, most of the efforts were still hoarded by SmTSP and the minsum objective function. In this period, many heuristics [37,38,39,40,41], exact algorithms [42,43,44,45,46,47], and IPs [6,42,44,48,49,50,51,52,53,54] were proposed. Metaheuristics dominated the scene with neural networks [31,55,56], genetic algorithms [57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82], clustering strategies [83], ant colony optimization [76,84,85,86,87,88,89], firefly algorithm [89], ant colony system [90,91], market-based algorithms [92,93], imperialist competitive algorithm [94], tabu search [56], gravitational emulation local search algorithm [95], variable neighborhood search [96,97,98,99], bee colony optimization [100], invasive weed optimization [100], wolf pack search algorithm [101], discrete pigeon optimization [102], reinforcement learning [103], evolutionary strategies [104], hybrid search [105], memetic search [105], simulated annealing [106], and bees algorithm [107]. As in years before, only a few authors worked on DFmTSP. Remarkably, until 2017 and 2021, the first reported IPs for DFmTSP were published [51,104]. Recently, more integer programs were proposed for the DFmTSP which exploits a relationship between the FD-MmTSP and the DFmTSP [1].
7. Approximation Algorithms
Only a few approximation algorithms have been designed for some variants of mTSP. For that reason, this paragraph presents an independent account of such algorithms; these include a (4/3)(4/3)- and a (3/2)(3/2)-approximation algorithm for the SmTSP and MmTSP on a tree with two salespersons (𝑚=2) and minmax objective function [108], a (2−2/(m+1))-approximation algorithm for DFmTSP on trees with m traveling salespersons and minmax objective function [109], a faster approximation algorithm with the same approximation factor for the same problem [110], a 2-approximation algorithm for MmTSP with triangle inequality [111], a (3/2)(3/2)-approximation algorithm for MmTSP with triangle inequality and a constant number of depots [112], a (2−1/𝑘)-approximation algorithm for MmTSP [113], a (2−1/(2𝑘))-approximation algorithm for MmTSP [114], a (1+𝜖)-approximation algorithm for SmTSP on a tree with minmax objective function, with the depot located at the tree’s root [115], and a (1+𝜖)-approximation algorithm for the SmTSP on a spider, with the depot located at its center [116].
8. When Depots Are Unknown or Unnecessary
Table 1 shows the main scope of the examined papers, and Figure 2 shows how they distribute over time. From Table 1 and Figure 2, we can observe that, on the one hand, SmTSP and MmTSP have been the most studied variants. On the other hand, DFmTSP has not received as much attention; only two IPs have been published, and they are relatively recent and have a limited scope [51,104]. Since the classical TSP does not require the depot concept to be formulated, researchers believe that DFmTSP should be considered an essential member of the mTSP collection and should receive more attention. Additionally, this variant is more adequate for specific applications, such as submarine patrol routing [36], supervisor allocation [50,51], and some variations of the job scheduling problem [32]. In a nutshell, DFmTSP is a better model for social problems where depots are unknown or unnecessary. Cornejo-Acosta et al. [1] introduce novel IPs for DFmTSP and its main variants:
-
Closed paths (CP).
-
Open paths (OP).
-
Minsum objective function.
-
Minmax objective function.
-
Bounding constraints:
- -
-
Lower bound on the number of vertices per path.
- -
-
Upper bound on the number of vertices per path.
As a byproduct, the proposed IPs of Cornejo-Acosta et al. [1] are adapted to a combination of FD-MmTSP and DFmTSP, namely, a variant where fewer than m depots are part of the input, but the solution consists of exactly m paths. This variant can be helpful in situations where only a few depots have already been selected. Thus, deciding the location of the remaining depots is part of the problem.
Figure 2. Published papers directly related to mTSP over time.
Table 1. Main categories and scope of related work. S, M, and DF stand for single depot, multiple depot, and depot free, respectively.
| Main Scope | mTSP | Reference |
|---|---|---|
| Integer programming | S M DF |
[4,5,6,10,11,12,13,14,15,16,17,18,19,20,21,22,49] [6,15,18,42,44,47,48,50,51,52,53,54] [36,51,104] |
| Exact algorithm | S M DF |
[14,20,23,45,46] [42,43,44,45,47,115] - |
| Heuristic | S M DF |
[19,24,25,26,27,40,41] [38,39,40] [37,40] |
| Metaheuristic | S | [28,29,30,31,34,35,55,56,57,58,59,60,61,62,63,64,65,67,68,69,70,71,72,73,74,76,78,80,81] |
| [83,84,85,87,88,90,91,94,95,96,97,98,100,101,102,103,104,105,107,117] | ||
| M DF |
[82,86,88,89,92,93,99,104,105,118] [32,33,66,75,77,79,104,106] |
|
| Approximation algorithm | S M DF |
[108,116] [108,110,111,112,113,114,115] [109] |
This entry is adapted from the peer-reviewed paper 10.3390/math11133014
This entry is offline, you can click here to edit this entry!
