A Two Stage Method for the Multiple Traveling Salesman Problem

Cabrera Cuevas, Azcarie Manuel; Saucedo Martínez, Jania Astrid; Marmolejo Saucedo, José Antonio

doi:10.4018/IJAMC.2020070104

A Two Stage Method for the Multiple Traveling Salesman Problem

Journal

International Journal of Applied Metaheuristic Computing

ISSN

1947-8283

1947-8291

Date Issued

2020

Author(s)

Cabrera Cuevas, Azcarie Manuel

Saucedo Martínez, Jania Astrid

Marmolejo Saucedo, José Antonio

Facultad de Ingeniería - CampCM

Type

text::journal::journal article

DOI

10.4018/IJAMC.2020070104

URL

https://scripta.up.edu.mx/handle/20.500.12552/3972

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. ©2020 International Journal of Applied Metaheuristic Computing, IGI Global.