A GRASP×ELS approach for the capacitated location‐routing problem

A GRASP×ELS approach for the capacitated location‐routing problem

0.00 Avg rating0 Votes
Article ID: iaor20123261
Volume: 37
Issue: 11
Start Page Number: 1912
End Page Number: 1923
Publication Date: Nov 2010
Journal: Computers and Operations Research
Authors: , , ,
Keywords: networks: flow, vehicle routing & scheduling, combinatorial optimization
Abstract:

This paper addresses the capacitated location‐routing problem (CLRP), raised by distribution networks involving depot location, fleet assignment and routing decisions. The CLRP is defined by a set of potential depot locations, with opening costs and limited capacities, a homogeneous fleet of vehicles, and a set of customers with known demands. The objective is to open a subset of depots, to assign customers to these depots and to design vehicle routes, in order to minimize both the cost of open depots and the total cost of the routes. The proposed solution method is a greedy randomized adaptive search procedure (GRASP), calling an evolutionary local search (ELS) and searching within two solution spaces: giant tours without trip delimiters and true CLRP solutions. Giant tours are evaluated via a splitting procedure that minimizes the total cost subject to vehicle capacity, fleet size and depot capacities. This framework is benchmarked on classical instances. Numerical experiments show that the approach outperforms all previously published methods and provides numerous new best solutions.

Reviews

Required fields are marked *. Your email address will not be published.