Title: Two-stage heuristic algorithm for the large-scale capacitated location routing problem

Authors: Oualid Guemri; Bouziane Beldjilali; Abdelghani Bekrar; Ghalem Belalem

Addresses: LIO Laboratory, Department of Computer Sciences, Faculty of Exact and Applied Sciences, University of Oran 1 Ahmed Ben Bella, Oran, Algeria ' LIO Laboratory, Department of Computer Sciences, Faculty of Exact and Applied Sciences, University of Oran 1 Ahmed Ben Bella, Oran, Algeria ' LAMIH UMR 8201, University of Valenciennes and hainaut Cambrsis, Valenciennes, France ' LIO Laboratory, Department of Computer Sciences, Faculty of Exact and Applied Sciences, University of Oran 1 Ahmed Ben Bella, Oran, Algeria

Abstract: In this paper, we treat the capacitated location-routing problem (CLRP). The CLRP which combines the facility location problem with the routing problem is one of the most important problems in combinatorial optimisation field. In this study, we propose a new two-stage heuristic (2-SH) algorithm for the large-scale CLRP. In fact, our aim is to find high-quality solutions for very large-scale problems within a short computing time. The proposed method consists of two major stages. In the first, the routing sub-problem is solved using a tabu search. Then, in the second stage, to associate each route to a facility, the location-allocation sub-problem is treated by means of a simulated annealing method. Our proposed approach is evaluated on large-scale randomly generated instances and compared successfully with other two state-of-the-art algorithms from the literature.

Keywords: supply chain management; SCM; metaheuristics; local search; location routing problem; capacitated LRP; CLRP; facility location; combinatorial optimisation; tabu search; simulated annealing.

DOI: 10.1504/IJMMNO.2016.074375

International Journal of Mathematical Modelling and Numerical Optimisation, 2016 Vol.7 No.1, pp.97 - 119

Received: 06 Feb 2015
Accepted: 18 Sep 2015
Published online: 25 Jan 2016 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article