Algorithmic Solutions for Last-Mile Networks

Network design problems occur frequently in various practical areas, such as the designing of communication networks, the development of electronic circuits, the designing of fiber-optic networks or the development of district heating or water supply systems. The main problem we are focusing on is called Connected Facility Location in Multicommodity Networks, which represents a generalization of two well-known network design problems: First, the facility location problem and secondly, the Steiner tree problem in graphs. We are given a network with its set of customer and non-customer nodes, their traffic demands, potential facility locations and links between the nodes. The main goal is to open a subset of facilities, to assign each customer to exactly one of them and to connect open facilities by a Steiner tree. Costs of connecting the facilities and opening them need to be minimized. Additionally, in multicommodity networks, edge-costs depend on edge-capacities obeying economies of scale, in the sense that it is cheaper to buy a cable that can carry a larger capacity than many cables which sum to the same capacity. This is a combinatorial optimization problem that belongs to the class of NP-hard network design problems. The available techniques for these problems can be roughly classified into two main categories: exact and heuristic algorithms. Exact algorithms are guaranteed to find an optimal solution and to prove its optimality for every instance of a combinatorial optimization problem. Sometimes the guarantee of finding optimal solutions is sacrificed due to the exponential running times or memory requirements of exact algorithms, in favor of achieving acceptable solutions in a limited time and therefore we use heuristic algorithms. To solve the problem described above, its capacitated variants and corresponding sub-problems, we plan to develop new mixed-integer programming formulations and to design algorithmic frameworks for finding optimal solutions. In most instances, we aim to develop metaheuristic methods that obtain sub-optimal, high quality solutions and that provide optimality gaps as a measure of their quality. Our research relies on branch-and-cut methods, variable neighborhood search and promising variants of their combination.