A Memetic Algorithm for the Bi-Objective Hub Location-Routing Problem
Xiao Yang  1, *@  , Nathalie Bostel  2, *@  , Pierre Dejax  3@  , Marc Paquet  4@  
1 : Equipe Systèmes Logistiques et de Production, LS2N  -  Website
Université de Nantes
Chemin de la Censive du Tertre, 44313 Nantes -  France
2 : Equipe Systèmes Logistiques et de Production, LS2N  -  Website
Université de Nantes
58 rue Michel Ange, BP 420 44606 Saint-Nazaire -  France
3 : Equipe Systèmes Logistiques et de Production, LS2N  -  Website
Ecole des Mines de Nantes
4 rue Alfred Kastler 44300 Nantes -  France
4 : Department of Automated Manufacturing Engineering, Ecole de Technologie Supérieure
* : Corresponding author

The bi-objective Hub Location-Routing Problem is an extension of the Hub Location-Routing Problem (HLRP) which copes with hub facility locations, routes vehicle tours and plans the inter-hub transportations to satisfy the suppliers-clients transportation demands. Besides the classic economic goals, we consider the impact of environmental factors , revealing the conflicting relations between minimizing costs and CO2 emissions. We present a bi-objective model of the Capacitated Single Allocation Hub Location-Routing Problem (CSAHLRP) for less-than-truck load (LTL) transport under the assumption of independent collection and delivery processes. To solve the bi-objective problem, a memetic algorithm (MA) combined with a steady state non-dominated sorting genetic algorithm (NSGAII) is developed to capture the trade-off between minimizing total cost and CO2 emissions and exhibit approximations of the Pareto front. The proposed bi-objective algorithm uses the NSGAII to sort and rank the population obtained with the memetic algorithm into different non-dominated levels. Instead of ranking all the individual solutions for each new generation, an efficient non-dominance level update (ENLU) method is employed to only update the necessary solutions each time by adding a new solution and eliminating an inferior solution if it is necessary, thus reducing the computational time effectively. Two different local search strategies are consecutively implemented on the hub location and vehicle routing parts, based on a crowded comparison operator. A computational experimentation is conducted and the results are compared with those that are obtained by the corresponding single-objective models, both with CPLEX and the MA.


Online user: 1 RSS Feed