Compact Integer Programs for Depot-Free Multiple Traveling Salesperson Problems

José Alejandro Cornejo-Acosta, Jesús García-Díaz (), Julio César Pérez-Sansalvador and Carlos Segura
Additional contact information
José Alejandro Cornejo-Acosta: Coordinación de Ciencias Computacionales, Instituto Nacional de Astrofísica, Óptica y Electrónica, Puebla 72840, Mexico
Jesús García-Díaz: Coordinación de Ciencias Computacionales, Instituto Nacional de Astrofísica, Óptica y Electrónica, Puebla 72840, Mexico
Julio César Pérez-Sansalvador: Coordinación de Ciencias Computacionales, Instituto Nacional de Astrofísica, Óptica y Electrónica, Puebla 72840, Mexico
Carlos Segura: Área de Computación, Centro de Investigación en Matemáticas, Guanajuato 36240, Mexico

Mathematics, 2023, vol. 11, issue 13, 1-25

Abstract: Multiple traveling salesperson problems ( m TSP) are a collection of problems that generalize the classical traveling salesperson problem (TSP). In a nutshell, an m TSP variant seeks a minimum cost collection of m paths that visit all vertices of a given weighted complete graph. This paper introduces novel compact integer programs for the depot-free m TSP (DF m TSP). This fundamental variant models real scenarios where depots are unknown or unnecessary. The proposed integer programs are adapted to the main variants of the DF m TSP, such as closed paths, open paths, bounding constraints (also known as load balance), and the minsum and minmax objective functions. Some of these integer programs have O ( n 2 m ) binary variables and O ( n 2 ) constraints, where m is the number of salespersons and n = | V ( G ) | . Furthermore, we introduce more compact integer programs with O ( n 2 ) binary variables and O ( n 2 ) constraints for the same problem and most of its main variants. Without losing their compactness, all the proposed programs are adapted to fixed-destination multiple-depots m TSP (FD-M m TSP) and a combination of FD-M m TSP and DF m TSP, where fewer than m depots are part of the input, but the solution still consists of m paths. We used off-the-shelf optimization software to empirically test the proposed integer programs over a classical benchmark dataset; these tests show that the proposed programs meet desirable theoretical properties and have practical advantages over the state of the art.

Keywords: integer programming; multiple traveling salesperson problem; depot-free m TSP (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/13/3014/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/13/3014/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:13:p:3014-:d:1188551

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().