A generic formulation and a memetic algorithm for the hub location-routing problem

International audienceIn many logistic systems for less than truckload (LTL) shipments, transportation of goods from one origin to its destination is made through collection tours to a hub and delivery tours from the same or another hub, while the goods are shipped between two hubs using Full Truckload (FTL) shipments. The hub location-routing problem (HLRP), consists in determining the location of the hubs, the allocation of non-hub nodes, and the optimal collection and delivery routes within the network. The proposed mathematical model is a MIP based on the following assumptions: each supplier and customer is allocated to one hub; each vehicle route begins and ends at the same hub; vehicles are capacitated; and collection/delivery routes are distinguished. Based on different hypothesis for the hubs, we develop several variations of the model: fixed cost HLRP and p-HLRP with and without capacity. In these models, there are three main variables to determine: hub location variables, inter-hub flow variables and routing variables. The objective function minimizes the total fixed cost and transportation costs. We propose a memetic algorithm composed of a genetic algorithm (GA) combined with some local searches. Computational experiments are presented based on some randomly generated data sets and Australian Post data sets