Compact Integer Programs for Depot-Free Multiple Traveling Salesperson Problems
Multiple traveling salesperson problems (<i>m</i>TSP) are a collection of problems that generalize the classical traveling salesperson problem (TSP). In a nutshell, an <i>m</i>TSP variant seeks a minimum cost collection of <i>m</i> paths that visit all vertices of...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-07-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/11/13/3014 |
| _version_ | 1797591248001826816 |
|---|---|
| author | José Alejandro Cornejo-Acosta Jesús García-Díaz Julio César Pérez-Sansalvador Carlos Segura |
| author_facet | José Alejandro Cornejo-Acosta Jesús García-Díaz Julio César Pérez-Sansalvador Carlos Segura |
| author_sort | José Alejandro Cornejo-Acosta |
| collection | DOAJ |
| description | Multiple traveling salesperson problems (<i>m</i>TSP) are a collection of problems that generalize the classical traveling salesperson problem (TSP). In a nutshell, an <i>m</i>TSP variant seeks a minimum cost collection of <i>m</i> paths that visit all vertices of a given weighted complete graph. This paper introduces novel compact integer programs for the depot-free <i>m</i>TSP (DF<i>m</i>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<i>m</i>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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="script">O</mi><mo>(</mo><msup><mi>n</mi><mn>2</mn></msup><mi>m</mi><mo>)</mo></mrow></semantics></math></inline-formula> binary variables and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="script">O</mi><mo>(</mo><msup><mi>n</mi><mn>2</mn></msup><mo>)</mo></mrow></semantics></math></inline-formula> constraints, where <i>m</i> is the number of salespersons and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>=</mo><mo>|</mo><mi>V</mi><mo>(</mo><mi>G</mi><mo>)</mo><mo>|</mo></mrow></semantics></math></inline-formula>. Furthermore, we introduce more compact integer programs with <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="script">O</mi><mo>(</mo><msup><mi>n</mi><mn>2</mn></msup><mo>)</mo></mrow></semantics></math></inline-formula> binary variables and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="script">O</mi><mo>(</mo><msup><mi>n</mi><mn>2</mn></msup><mo>)</mo></mrow></semantics></math></inline-formula> 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 <i>m</i>TSP (FD-M<i>m</i>TSP) and a combination of FD-M<i>m</i>TSP and DF<i>m</i>TSP, where fewer than <i>m</i> depots are part of the input, but the solution still consists of <i>m</i> 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. |
| first_indexed | 2024-03-11T01:34:47Z |
| format | Article |
| id | doaj.art-fd4975372b104bb68fb04a0928748e24 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-11T01:34:47Z |
| publishDate | 2023-07-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-fd4975372b104bb68fb04a0928748e242023-11-18T17:04:35ZengMDPI AGMathematics2227-73902023-07-011113301410.3390/math11133014Compact Integer Programs for Depot-Free Multiple Traveling Salesperson ProblemsJosé Alejandro Cornejo-Acosta0Jesús García-Díaz1Julio César Pérez-Sansalvador2Carlos Segura3Coordinación de Ciencias Computacionales, Instituto Nacional de Astrofísica, Óptica y Electrónica, Puebla 72840, MexicoCoordinación de Ciencias Computacionales, Instituto Nacional de Astrofísica, Óptica y Electrónica, Puebla 72840, MexicoCoordinación de Ciencias Computacionales, Instituto Nacional de Astrofísica, Óptica y Electrónica, Puebla 72840, MexicoÁrea de Computación, Centro de Investigación en Matemáticas, Guanajuato 36240, MexicoMultiple traveling salesperson problems (<i>m</i>TSP) are a collection of problems that generalize the classical traveling salesperson problem (TSP). In a nutshell, an <i>m</i>TSP variant seeks a minimum cost collection of <i>m</i> paths that visit all vertices of a given weighted complete graph. This paper introduces novel compact integer programs for the depot-free <i>m</i>TSP (DF<i>m</i>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<i>m</i>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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="script">O</mi><mo>(</mo><msup><mi>n</mi><mn>2</mn></msup><mi>m</mi><mo>)</mo></mrow></semantics></math></inline-formula> binary variables and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="script">O</mi><mo>(</mo><msup><mi>n</mi><mn>2</mn></msup><mo>)</mo></mrow></semantics></math></inline-formula> constraints, where <i>m</i> is the number of salespersons and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>=</mo><mo>|</mo><mi>V</mi><mo>(</mo><mi>G</mi><mo>)</mo><mo>|</mo></mrow></semantics></math></inline-formula>. Furthermore, we introduce more compact integer programs with <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="script">O</mi><mo>(</mo><msup><mi>n</mi><mn>2</mn></msup><mo>)</mo></mrow></semantics></math></inline-formula> binary variables and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="script">O</mi><mo>(</mo><msup><mi>n</mi><mn>2</mn></msup><mo>)</mo></mrow></semantics></math></inline-formula> 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 <i>m</i>TSP (FD-M<i>m</i>TSP) and a combination of FD-M<i>m</i>TSP and DF<i>m</i>TSP, where fewer than <i>m</i> depots are part of the input, but the solution still consists of <i>m</i> 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.https://www.mdpi.com/2227-7390/11/13/3014integer programmingmultiple traveling salesperson problemdepot-free <i>m</i>TSP |
| spellingShingle | José Alejandro Cornejo-Acosta Jesús García-Díaz Julio César Pérez-Sansalvador Carlos Segura Compact Integer Programs for Depot-Free Multiple Traveling Salesperson Problems Mathematics integer programming multiple traveling salesperson problem depot-free <i>m</i>TSP |
| title | Compact Integer Programs for Depot-Free Multiple Traveling Salesperson Problems |
| title_full | Compact Integer Programs for Depot-Free Multiple Traveling Salesperson Problems |
| title_fullStr | Compact Integer Programs for Depot-Free Multiple Traveling Salesperson Problems |
| title_full_unstemmed | Compact Integer Programs for Depot-Free Multiple Traveling Salesperson Problems |
| title_short | Compact Integer Programs for Depot-Free Multiple Traveling Salesperson Problems |
| title_sort | compact integer programs for depot free multiple traveling salesperson problems |
| topic | integer programming multiple traveling salesperson problem depot-free <i>m</i>TSP |
| url | https://www.mdpi.com/2227-7390/11/13/3014 |
| work_keys_str_mv | AT josealejandrocornejoacosta compactintegerprogramsfordepotfreemultipletravelingsalespersonproblems AT jesusgarciadiaz compactintegerprogramsfordepotfreemultipletravelingsalespersonproblems AT juliocesarperezsansalvador compactintegerprogramsfordepotfreemultipletravelingsalespersonproblems AT carlossegura compactintegerprogramsfordepotfreemultipletravelingsalespersonproblems |