The American company Hexvarium, a next-generation developer, facilitator, and operator of broadband networks, chose LocalSolver to solve city-wide optic fiber design network design problems in minutes. Hexvarium is a broadband service provider using data-oriented methods to accurately identify, deliver, and connect profitable networks across the United States. Their innovative approach delivers sustainable networks, even in the most challenging circumstances, and enables investors, utilities, municipalities, and businesses to quickly determine how and where to build fiber networks for the highest possible impact and the best possible return to investors.
Hexvarium’s fiber network design problem
Hexvarium has been tasked with designing the whole optic fiber network of several cities across the United States. Building such a network requires connecting every client address to the city’s central office while routing the optic fiber cables in the best possible way.
The route connecting a given client to the central office is split into several sections, separated by splitter nodes of different sizes. Along this route, the cables have a higher fiber count when coming out of the central office and a lower fiber count as they get more specific and closer to the client’s address. The hierarchy followed by the different route sections is as follows. The city’s main central office is first connected to several secondary central offices across the city, using very thick cables with a high fiber count. The cables coming out of these secondary central offices still have a high fiber count and need to be split several times before being connected to the clients’ addresses, using primary and secondary splitter nodes. The cables coming out of the secondary splitter nodes are individual fibers and can be connected to separate client addresses.
The splitter nodes have very constrained fiber counts. For example, about eight fibers generally come out of each secondary splitter node. So as not to waste resources, most of those fibers have to be connected to a client address. However, a few fibers should remain unused to make the network more sustainable. Indeed, these unused fibers could be connected to new client addresses in the future.
The input data consists of a graph representing the city’s streets and roads. The city has up to 500,000 road segments for a cumulated length of 13,000 kilometers, which correspond to the edges of the graph. The nodes of the graph are the intersection points between those road segments. Up to 130,000 of these nodes are client addresses. Another node corresponds to the location of the main central office.
The fiber network design consists in deciding which road segments should be used to run the cables, and where to place the primary and secondary splitter nodes.
There are three types of constraints in the model. The splitter nodes hierarchy constraints must be respected: each cable coming out of the main central office has to go through a secondary central office, at least one primary splitter node, and a secondary splitter node before reaching a client address. There also are degree constraints on the splitter nodes, ensuring that the number of output cables is neither too high nor too low. Finally, the total length of the fiber connecting any client address to a secondary central office should not exceed a certain limit.
The objective consists in minimizing the total deployment cost, which depends on the number of splitter nodes and the total length of fiber in the network.
Hexvarium has already benefited from LocalSolver’s expertise on a scheduling problem for deployment operations and was very satisfied with the results. Besides, LocalSolver already has expertise in telecommunication deployment topics with Network Design for Bouygues Telecom. This motivated Hexvarium to choose LocalSolver to help them with their fiber network design problem.
Hexvarium’s team is delighted with LocalSolver’s ability to provide good solutions quickly. For example, the largest instance with 500,000 road segments and 130,000 client addresses was solved in only 10 minutes. They also greatly appreciate LocalSolver’s agile methodology. They appreciate how LocalSolver’s experts manage to iterate quickly on the design of the solution based on their operational feedback.
We have been working with the LocalSolver team for several years now. Their expertise in network design problems has allowed us to move forward with our fiber network design problem. In addition, LocalSolver’s agile methodology is very valuable, as it permits us to quickly iterate on the solution based on operational feedback.
Please look at our customers‘ webpage to discover more case studies in various industries. Are you interested in trying it out? Get free trial licenses here. In the meantime, feel free to contact us; we will be glad to exchange your optimization problems.