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]}^{[8]}; 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 ^{[8]}.
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 ^{[9]}^{[10]}^{[11]}^{[12]}^{[13]}^{[14]}^{[15]}^{[16]}^{[17]}, and only a few were direct ^{[18]}^{[19]}. 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 ^{[11]}, and others as variable SmTSP ^{[20]}. 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 ^{[12]}, cutting planes ^{[18]}, and branch and bound ^{[21]}. In this same period, some heuristics for SmTSP were introduced too ^{[17]}^{[22]}^{[23]}^{[24]}^{[25]}. 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 ^{[13]}. It was until 1995 that MmTSP was reduced to TSP ^{[16]}. In this period, only a tabu search metaheuristic approach was developed for SmTSP ^{[26]}.
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 ^{[27]}^{[28]}^{[29]}, genetic algorithms ^{[30]}^{[31]}^{[32]}, particle swarm optimization ^{[31]}, evolutionary strategies ^{[31]}, and simulated annealing ^{[33]}. It is crucial to emphasize that during this period, DFmTSP started being spotted by some authors ^{[30]}^{[31]}^{[34]}. 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 ^{[35]}^{[36]}^{[37]}^{[38]}^{[39]}, exact algorithms ^{[40]}^{[41]}^{[42]}^{[43]}^{[44]}^{[45]}, and IPs ^{[6]}^{[40]}^{[42]}^{[46]}^{[47]}^{[48]}^{[49]}^{[50]}^{[51]}^{[52]} were proposed. Metaheuristics dominated the scene with neural networks ^{[29]}^{[53]}^{[54]}, genetic algorithms ^{[55]}^{[56]}^{[57]}^{[58]}^{[59]}^{[60]}^{[61]}^{[62]}^{[63]}^{[64]}^{[65]}^{[66]}^{[67]}^{[68]}^{[69]}^{[70]}^{[71]}^{[72]}^{[73]}^{[74]}^{[75]}^{[76]}^{[77]}^{[78]}^{[79]}^{[80]}, clustering strategies ^{[81]}, ant colony optimization ^{[74]}^{[82]}^{[83]}^{[84]}^{[85]}^{[86]}^{[87]}, firefly algorithm ^{[87]}, ant colony system ^{[88]}^{[89]}, market-based algorithms ^{[90]}^{[91]}, imperialist competitive algorithm ^{[92]}, tabu search ^{[54]}, gravitational emulation local search algorithm ^{[93]}, variable neighborhood search ^{[94]}^{[95]}^{[96]}^{[97]}, bee colony optimization ^{[98]}, invasive weed optimization ^{[98]}, wolf pack search algorithm ^{[99]}, discrete pigeon optimization ^{[100]}, reinforcement learning ^{[101]}, evolutionary strategies ^{[102]}, hybrid search ^{[103]}, memetic search ^{[103]}, simulated annealing ^{[104]}, and bees algorithm ^{[105]}. As in years before, only a few authors worked on DFmTSP. Remarkably, until 2017 and 2021, the first reported IPs for DFmTSP were published ^{[49]}^{[102]}. 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 ^{[106]}, a (2−2/(m+1))-approximation algorithm for DFmTSP on trees with m traveling salespersons and minmax objective function ^{[107]}, a faster approximation algorithm with the same approximation factor for the same problem ^{[108]}, a 2-approximation algorithm for MmTSP with triangle inequality ^{[109]}, a (3/2)-approximation algorithm for MmTSP with triangle inequality and a constant number of depots ^{[110]}, a (2−1/𝑘)-approximation algorithm for MmTSP ^{[111]}, a (2−1/(2𝑘))-approximation algorithm for MmTSP ^{[112]}, a (1+𝜖)-approximation algorithm for SmTSP on a tree with minmax objective function, with the depot located at the tree’s root ^{[113]}, and a (1+𝜖)-approximation algorithm for the SmTSP on a spider, with the depot located at its center ^{[114]}.
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 ^{[49]}^{[102]}. 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 ^{[34]}, supervisor allocation ^{[48]}^{[49]}, and some variations of the job scheduling problem ^{[30]}. 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:
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.