TSP solution using an exact model based on the branch flow formulation and automatic cases generation via the Julia software
The traveling salesman problem (TSP) is a classical optimization problem with practical applications in logistics, transportation, and network design. This research proposes an efficient mixed-integer linear programming (MILP) model based on the branch flow formulation which prevents the formation o...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2024-12-01
|
| Series: | Results in Control and Optimization |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S266672072400136X |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850114720091078656 |
|---|---|
| author | Oscar Danilo Montoya Walter Gil-González Luis Fernando Grisales-Noreña Rubén Iván Bolaños Jorge Ardila-Rey |
| author_facet | Oscar Danilo Montoya Walter Gil-González Luis Fernando Grisales-Noreña Rubén Iván Bolaños Jorge Ardila-Rey |
| author_sort | Oscar Danilo Montoya |
| collection | DOAJ |
| description | The traveling salesman problem (TSP) is a classical optimization problem with practical applications in logistics, transportation, and network design. This research proposes an efficient mixed-integer linear programming (MILP) model based on the branch flow formulation which prevents the formation of sub-tours during the solution process and guarantees valid optimal routes. Implemented in Julia with the JuMP optimization package and the HiGHS solver, the model achieves high computational efficiency. Unlike classical models, the branch flow formulation ensures a quadratic constraint growth, rather than an exponential one, significantly enhancing scalability. Benchmark tests on various instances (Eil51, Eil76, KroA100) demonstrate results comparable to state-of-the-art combinatorial optimizers, and six new TSP instances, ranging from 50 to 300 cities, validate the model’s performance. This scalable and robust approach is well-suited for real-world applications in supply chain management, network optimization, and urban planning, and it shows potential for future extensions to dynamic or multi-objective TSP variants. |
| format | Article |
| id | doaj-art-d13c924f2960441fa5d7f309a8161648 |
| institution | OA Journals |
| issn | 2666-7207 |
| language | English |
| publishDate | 2024-12-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Results in Control and Optimization |
| spelling | doaj-art-d13c924f2960441fa5d7f309a81616482025-08-20T02:36:46ZengElsevierResults in Control and Optimization2666-72072024-12-011710050710.1016/j.rico.2024.100507TSP solution using an exact model based on the branch flow formulation and automatic cases generation via the Julia softwareOscar Danilo Montoya0Walter Gil-González1Luis Fernando Grisales-Noreña2Rubén Iván Bolaños3Jorge Ardila-Rey4Grupo de Compatibilidad e Interferencia Electromagnética, Facultad de Ingeniería, Universidad Distrital Francisco José de Caldas, Bogotá 110231, Colombia; Corresponding authors.Department of Electrical Engineering, Faculty of Engineering, Universidad Tecnológica de Pereira, Pereira 660003, ColombiaDepartment of Electrical Engineering, Faculty of Engineering, Universidad de Talca, Curicó 3340000, Chile; Corresponding authors.Facultad de Ingeniería, Instituto Tecnológico Metropolitano, Campus Robledo, Medellín 050036, ColombiaDepartment of Electrical Engineering, Universidad Tecnica Federico Santa Maria, Valparaiso 2390123, ChileThe traveling salesman problem (TSP) is a classical optimization problem with practical applications in logistics, transportation, and network design. This research proposes an efficient mixed-integer linear programming (MILP) model based on the branch flow formulation which prevents the formation of sub-tours during the solution process and guarantees valid optimal routes. Implemented in Julia with the JuMP optimization package and the HiGHS solver, the model achieves high computational efficiency. Unlike classical models, the branch flow formulation ensures a quadratic constraint growth, rather than an exponential one, significantly enhancing scalability. Benchmark tests on various instances (Eil51, Eil76, KroA100) demonstrate results comparable to state-of-the-art combinatorial optimizers, and six new TSP instances, ranging from 50 to 300 cities, validate the model’s performance. This scalable and robust approach is well-suited for real-world applications in supply chain management, network optimization, and urban planning, and it shows potential for future extensions to dynamic or multi-objective TSP variants.http://www.sciencedirect.com/science/article/pii/S266672072400136XTraveling salesman problem (TSP)Mixed-integer linear programming (MILP)Sub-tour eliminationCombinatorial optimizationBranch flow formulation |
| spellingShingle | Oscar Danilo Montoya Walter Gil-González Luis Fernando Grisales-Noreña Rubén Iván Bolaños Jorge Ardila-Rey TSP solution using an exact model based on the branch flow formulation and automatic cases generation via the Julia software Results in Control and Optimization Traveling salesman problem (TSP) Mixed-integer linear programming (MILP) Sub-tour elimination Combinatorial optimization Branch flow formulation |
| title | TSP solution using an exact model based on the branch flow formulation and automatic cases generation via the Julia software |
| title_full | TSP solution using an exact model based on the branch flow formulation and automatic cases generation via the Julia software |
| title_fullStr | TSP solution using an exact model based on the branch flow formulation and automatic cases generation via the Julia software |
| title_full_unstemmed | TSP solution using an exact model based on the branch flow formulation and automatic cases generation via the Julia software |
| title_short | TSP solution using an exact model based on the branch flow formulation and automatic cases generation via the Julia software |
| title_sort | tsp solution using an exact model based on the branch flow formulation and automatic cases generation via the julia software |
| topic | Traveling salesman problem (TSP) Mixed-integer linear programming (MILP) Sub-tour elimination Combinatorial optimization Branch flow formulation |
| url | http://www.sciencedirect.com/science/article/pii/S266672072400136X |
| work_keys_str_mv | AT oscardanilomontoya tspsolutionusinganexactmodelbasedonthebranchflowformulationandautomaticcasesgenerationviathejuliasoftware AT waltergilgonzalez tspsolutionusinganexactmodelbasedonthebranchflowformulationandautomaticcasesgenerationviathejuliasoftware AT luisfernandogrisalesnorena tspsolutionusinganexactmodelbasedonthebranchflowformulationandautomaticcasesgenerationviathejuliasoftware AT rubenivanbolanos tspsolutionusinganexactmodelbasedonthebranchflowformulationandautomaticcasesgenerationviathejuliasoftware AT jorgeardilarey tspsolutionusinganexactmodelbasedonthebranchflowformulationandautomaticcasesgenerationviathejuliasoftware |