Branch-and-Price and Heuristic Algorithms for the Service Network Design and Hub Location Problem

The design of freight transport networks is becoming an even more relevant component in the context of the worldwide increasing popularity of e-commerce and increasing export volumes. The focus of this thesis is on a combined transport problem where multiple itineraries are possible for commodities with the same origin and destination locations. The problem targets both the strategic positioning of transshipment warehouses -- the so-called hubs -- and the tactical planning of freight transport. The aim is to achieve the best trade-off between operational costs and service performance. We consider, among others, important real-world conditions on the routing of goods: modular capacities on transfer links between hubs, maximum delivery times of goods, and limits on the number of transshipments. Overall, the whole combination of these problem characteristics has never been treated in the previous literature. For the considered problem, we propose two mathematical formulations and a Branch-and-Price algorithm. Besides, we introduce various heuristic approaches to obtain good-quality solutions with limited computational time. Extensive computational experiments show the effectiveness of the proposed algorithms in solving realistic instances, enabling strategic network design in real-world applications.