Solution Algorithms for the Capacitated Location Tree Problem with Interconnections
This paper addresses the Capacitated Location Tree Problem with Interconnections, a new combinatorial optimization problem with applications in network design. In this problem, the required facilities picked from a set of potential facilities must be opened to serve customers using a tree-shaped net...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-01-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/18/1/50 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832589394162221056 |
|---|---|
| author | Nidia Mendoza-Andrade Efrain Ruiz-y-Ruiz Suemi Rodriguez-Romo |
| author_facet | Nidia Mendoza-Andrade Efrain Ruiz-y-Ruiz Suemi Rodriguez-Romo |
| author_sort | Nidia Mendoza-Andrade |
| collection | DOAJ |
| description | This paper addresses the Capacitated Location Tree Problem with Interconnections, a new combinatorial optimization problem with applications in network design. In this problem, the required facilities picked from a set of potential facilities must be opened to serve customers using a tree-shaped network. Costs and capacities are associated with the opening of facilities and the establishment of network links. Customers have a given demand that must be satisfied while respecting the facilities and link capacities. The problem aims to minimize the total cost of designing a distribution network while considering facility opening costs, demand satisfaction, capacity constraints, and the creation of interconnections to enhance network resilience. A valid mixed-integer programming was proposed and an exact solution method based on the formulation was used to solve small- and medium-sized instances. To solve larger instances two metaheuristic approaches were used. A specific decoder procedure for the metaheuristic solution approaches was also proposed and used to help find solutions, especially for large instances. Computational experiments and results using the three solution approaches are also presented. Finally, a case study on the design of electrical transportation systems was presented and solved. |
| format | Article |
| id | doaj-art-40dc890379514411bd737d157aca9242 |
| institution | Kabale University |
| issn | 1999-4893 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj-art-40dc890379514411bd737d157aca92422025-01-24T13:17:37ZengMDPI AGAlgorithms1999-48932025-01-011815010.3390/a18010050Solution Algorithms for the Capacitated Location Tree Problem with InterconnectionsNidia Mendoza-Andrade0Efrain Ruiz-y-Ruiz1Suemi Rodriguez-Romo2Facultad de Estudios Superiores Cuautitlán, UNAM Universidad Autónoma de México, Ciudad de México 04510, MexicoTECNM Tecnológico Nacional de México, Instituto Tecnológico de Saltillo, Saltillo 25280, MexicoUNAM Facultad de Estudios Superiores Cuautitlán, Cuatitlán Izcalli 54740, MexicoThis paper addresses the Capacitated Location Tree Problem with Interconnections, a new combinatorial optimization problem with applications in network design. In this problem, the required facilities picked from a set of potential facilities must be opened to serve customers using a tree-shaped network. Costs and capacities are associated with the opening of facilities and the establishment of network links. Customers have a given demand that must be satisfied while respecting the facilities and link capacities. The problem aims to minimize the total cost of designing a distribution network while considering facility opening costs, demand satisfaction, capacity constraints, and the creation of interconnections to enhance network resilience. A valid mixed-integer programming was proposed and an exact solution method based on the formulation was used to solve small- and medium-sized instances. To solve larger instances two metaheuristic approaches were used. A specific decoder procedure for the metaheuristic solution approaches was also proposed and used to help find solutions, especially for large instances. Computational experiments and results using the three solution approaches are also presented. Finally, a case study on the design of electrical transportation systems was presented and solved.https://www.mdpi.com/1999-4893/18/1/50Capacitated Location Tree Problemlocationnetwork designBRKGAPSO |
| spellingShingle | Nidia Mendoza-Andrade Efrain Ruiz-y-Ruiz Suemi Rodriguez-Romo Solution Algorithms for the Capacitated Location Tree Problem with Interconnections Algorithms Capacitated Location Tree Problem location network design BRKGA PSO |
| title | Solution Algorithms for the Capacitated Location Tree Problem with Interconnections |
| title_full | Solution Algorithms for the Capacitated Location Tree Problem with Interconnections |
| title_fullStr | Solution Algorithms for the Capacitated Location Tree Problem with Interconnections |
| title_full_unstemmed | Solution Algorithms for the Capacitated Location Tree Problem with Interconnections |
| title_short | Solution Algorithms for the Capacitated Location Tree Problem with Interconnections |
| title_sort | solution algorithms for the capacitated location tree problem with interconnections |
| topic | Capacitated Location Tree Problem location network design BRKGA PSO |
| url | https://www.mdpi.com/1999-4893/18/1/50 |
| work_keys_str_mv | AT nidiamendozaandrade solutionalgorithmsforthecapacitatedlocationtreeproblemwithinterconnections AT efrainruizyruiz solutionalgorithmsforthecapacitatedlocationtreeproblemwithinterconnections AT suemirodriguezromo solutionalgorithmsforthecapacitatedlocationtreeproblemwithinterconnections |