# Solution Algorithms for the Capacitated Location Tree Problem with Interconnections
###### Abstract  
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. C pacs: 18.50.-c, 11.15.Mh, 11. Navigating this intricate scenario, an innovative algorithm takes center stage, poised to deftly address the complex challenge of strategically placing traction substations and managing their intricate interconnections. At its core, this algorithm fervently pursues the cardinal objective of minimizing the proliferation of necessary traction substations. Executed with meticulous precision, this endeavor is dedicated to optimizing energy efficiency and fortifying infrastructural integrity, constituting a cornerstone contribution to achieving the sustainability and operational excellence of burgeoning electric transportation systems [3]. Integral to this paradigm is the dynamic presence of traction current converter plants, serving as linchpins in the power supply network. These converter plants assume two principal forms: decentralized and centralized. In the decentralized model, a single plant directly supplies the overhead lines or third rail of the traction system without an intermediary feed into a traction current distribution network. Conversely, centralized converter plants play a dual role, supplying the traction power network while directly providing power to the overhead lines or third rail. This nuanced addition accentuates the multifaceted nature of the infrastructural landscape, where the strategic placement of traction substations harmonizes with the dual modality of traction current converter plants, orchestrating an intricate ballet of power distribution and efficiency in the realm of electric transportation [4]. This paper introduces the Capacitated Location Tree Problem with Interconnections (CLTPI). The problem arises from the need to optimally design electric transportation networks capable of partially functioning during disruptions. In the CLTPI, a subset of capacitated facilities (electrical substations) from a set of potential locations must be opened (built) to service a set of clients (traction substations) with a specific demand. Clients are serviced using a capacitated network that has to be established. There are costs associated with opening any of the potential facilities, as well as with the topological design of the network. A formulation and two metaheuristic solution methods are proposed and used to solve a set of benchmark test instances from the literature. The benchmark instances are derived from the Location Routing problem, which is closely related to the CLTPI. Computational experiments and the results obtained from the three proposed solution methods are presented and discussed. Section 2 presents a relevant literature review related to the CLTPI. Section 3 describes the problem and proposes a mixed-integer programming formulation.