A variable neighborhood search approach for the two-echelon location-routing problem

Abstract

We consider the two-echelon location-routing problem (2ELRP), a well-known problem in freight distribution arising when establishing a two-level transport system with limited capacities. The problem is a generalization of the NP-hard location routing problem (LRP), involving strategic (location), tactical (allocation) and operational (routing) decisions at the same time. We present a variable neighborhood search (VNS) based on a previous successful VNS for the LRP, accordingly adapted as well as extended. The proposed algorithm provides solutions of high quality in short time, making use of seven di erent basic neighborhood structures parameterized with di erent perturbation size leading to a total of 21 speci c neighborhood structures. For intensi- cation, two consecutive local search methods are applied, optimizing the transport costs e ciently by considering only recently changed solution parts. Experimental results clearly show that our method is at least competitive regarding runtime and solution quality to other leading approaches, also improving upon several best known solutions.