MIC 2011: The IX Metaheuristics International Conference S2-04–1 POPMUSIC for the World Location Routing Problem

The goal of this work is to show that the POPMUSIC methodology can be applied to large loca-tion routing problems (LRP). The size of instances currently considered in the litterature is limited to few dozens of customers and few depots, even for approaches based on metaheuristics. The size of practical problem can be much larger, typically several thousands of customers and hundreds of depots. This implies that the methods developped up to now cannot be used directly for practical problems. However, these methods can be embedded in POPMUSIC allowing much larger instances to be treated. Indeed, in POPMUSIC methodology, the solution improvement with a basic meta-heuristic such as tabu search is not the part that contributes most to the algorithmic complexity. This work deals with an instance 10,000 larger than those commonly treated in the litterature. Such an instance can be treated by a standard laptop in less than one CPU day. 1 The World Location Routing Problem The Location Routing Problem is a well known optimization problem [2]. Several versions of this prob-lem exist, and we have considered the following one in order to generate instances based on the World TS