An exact method for the capacitated single allocation hub location-routing problem

International audienceThe hub location-routing problem (HLRP) with less-than-truckload (LTL) shipments considers the location of hub facilities concentrating flows and through which flows are routed from origins to destinations, together with the design of both collection and delivery routes associated to each hub. The state of the art includes only very few works directly addressing the HLRP, and they mainly focus on particular cases as postal services. In this research, we address the HLRP with distinct collections and deliveries tours, as it is practiced by general goods freight carriers. In this framework, we propose a new mathematical model for the capacitated single allocation hub location-routing problem (CASHLRP), and we develop a branch-and-cut algorithm inspired from Hà et al. (2013) to solve it. Our model considers capacities for hubs and vehicles and the objective is to satisfy the demands of transport between all origins and destinations while minimizing the total cost of the system, including fixed costs for establishing hubs, inter-hub transportation costs, and collection/delivery routing costs. To improve the efficiency of the branch-and-cut algorithm, some valid inequalities are generated to strengthen our model and the corresponding separation procedures are proposed. The algorithm is implemented in the C++ programming language and solved using the Concert Technology framework of CPLEX 12.5. Computational results based on instances inspired by the Australian Post data set (Ernst et al., 1999) show the efficiency of the proposed exact method. Main reference