Article Preview
Top1. Introduction
The m-TSP is a variation of the well-known TSP where a defined number of salesmen must visit a set of cities, each city being visited only once by an undetermined salesman and every one of them have to return to the starting city (Johnson & Pilcher, 1988). The exact algorithms including branch and bound (Pekny & Miller, 1992; Annals of Operations Research, 1987), cutting hyperplanes (Fleischmann, 1988) and branch and cut (Ropke et al., 2008; Elf et al., 2001; Ascheuer et al., 2000), prove to find the best known solutions, but due to the complexity concerning the solution of the m-TSP, the optimal solution goes away dismally in terms of calculation time as the problem dimensions increases and it’s considered to be part of the set of NP problems, that doesn’t have a known solution algorithm bound to a polynomial time (Garey & Johnson, 1979).
Notwithstanding the fact that using other types of algorithms than the exact ones doesn’t always guarantee to retrieve the optimal result, there are several works that include heuristic methods that are based on simple reasoning trying to minimize the need of computational calculation resources, generating acceptable results (Díaz et al., 1996). Conjointly, various approximation algorithms that combine or subordinate a series of heuristic algorithms to define a framework of a single algorithm to solve difficult problems, such as the m-TSP, exist: the metaheuristics (Blum & Roli, 2003; Dorigo et al., 2006; Vasant et al., 2017; Vasant et al., 2018). There are related works that successfully apply metaheuristics to the TSP and m-TSP, including the previous assignment of the nodes to each salesman and building the route subsequently (Xu et al., 2017; Yu et al., 2012) making use of genetic algorithms (GA) (Kang et al., 2016; Lu et al., 2016; Zhang & Liu, 2014), a noteworthy fact about the mentioned work is that the distances between the nodes are calculated as Euclidean distances to make use of the k-means approximation algorithm, but in the occurrence of vehicles that will transit the road infrastructure, this postulation become less attached to a real application. Other algorithms include: Tabu Search (TS) (Lin et al., 2016; Basu, 2012), Invasive Weed Optimization (IWO) (Zhou et al., 2015; Venkatesh & Singh, 2015). Also, the use of swarm intelligence algorithms has thrived within the efforts on finding the best solutions possible over a reasonable time, other remarkable approaches make use of Ant Colony Optimization (ACO) (Necula et al., 2015; Necula et al., 2017; Changdar et al., 2016; Gülcü et al., 2016), Particle Swarm Optimization (PSO) (Mahi et al., 2015; Vallade & Nakashima, 2014: Ganesan et al., 2016) and Cuckoo Search (Ouaarab et al., 2013a, 2013b), to name a few.
The proposed method entails the contribution of a combination of two Mixed Integer Linear Programming (MILP) models, using the PMP to generate the partitions of the subsets of nodes that will be assigned to each salesman, solving it with a B&C exact algorithm, applying an ACO algorithm to solve the TSP for each generated subset, creating the routes. In Section 2 a description of the problem that commenced the project will be detailed, in Section 3 the TSP will be defined, as well as its variation for multiple salesman, followed by the Section 4 in which the used PMP will be presented. The metaheurisic used for the routing will be itemized in Section 5. The proposed approximation algorithm and the solution for the Case Study will be specified in Section 6, ending with the conclusions at Section 7.