A Two Stage Method for the Multiple Traveling Salesman Problem

A Two Stage Method for the Multiple Traveling Salesman Problem

Azcarie Manuel Cabrera Cuevas (Universidad Autónoma de Nuevo León, San Nicolás de los Garza, Mexico), Jania Astrid Saucedo Martínez (Universidad Autónoma de Nuevo León, San Nicolás de los Garza, Mexico) and José Antonio Marmolejo Saucedo (Universidad Panamericana, Facultad de Ingeniería, Ciudad de México, Mexico)
Copyright: © 2020 |Pages: 13
DOI: 10.4018/IJAMC.2020070104

Abstract

The variation of the traveling salesman problem (TSP) with multiple salesmen (m-TSP) has been studied for many years resulting in diverse solution methods, both exact and heuristic. However, the high difficulty level on finding optimal (or acceptable) solutions has opposed the many efforts of doing so. The proposed method regards a two stage procedure which implies a modified version of the p-Median Problem (PMP) alongside the TSP, making a partition of the nodes into subsets that will be assigned to each salesman, solving it with Branch & Cut (B&C), in the first stage. This is followed by the routing, applying an Ant Colony Optimization (ACO) metaheuristic algorithm to solve a TSP for each subset of nodes. A case study was reviewed, detailing the positioning of five vehicles in strategic places in the Mexican Republic.
Article Preview
Top

1. 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.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 12: 4 Issues (2021): Forthcoming, Available for Pre-Order
Volume 11: 4 Issues (2020): 3 Released, 1 Forthcoming
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing