A Greedy Heuristic Algorithm for the Capacitated Location-Routing Problem

摘要

A greedy algorithm is developed to tackle the classic two-layer capacitated location-routing problem (CLRP) where three supply chain decisions, namely location, allocation, and routing problems, are taken into consideration at the same time. The algorithm solves the LRP in four main steps: initial solution, location-allocation improvement, allocation-routing improvement, and routing improvement. Throughout the first two steps, two customer allocation strategies of nearest and relative nearest are applied, and the best strategy is used. The location-allocation improvement step applies four local search procedures: "Drop", "Swap", "2-1 Exchange", and "2-2 Exchange". While the allocation-routing improvement step uses an "Insert" procedure, the routing improvement step uses a "Swap" procedure to improve the solution. The efficiency of the proposed algorithm is evaluated against three heuristic methods by solving benchmark problems. Results show the high quality of the solutions not only in terms of the network cost but also from the run time perspective. The results show that the proposed algorithm works very well for large-size problems.