Heuristic Approaches for Location Routing Problem with a Single Depot

Abdullah Almouhanna, Banafsheh Khosravi, Djamila Ouelhadj, Angel Alejandro Juan Perez

Research output: Contribution to conferenceAbstractpeer-review


The Location Routing Problem (LRP) is a popular combinatorial optimisation problem which is crucial in affecting the distribution industry. As LRP is concerned with determining the optimal number, location of facilities, and the optimal set of routeing from each facility to serve customers. We consider a Mixed Integer Linear Programming (MILP) formulation for the capacitated LRP with a single depot where both depot and vehicles are capacitated. We propose four heuristics, namely: Two-stage clustering, Two-stage p-median, Two-stage clustering and p-median, and Iterated heuristics. In the first stage of the first three heuristics, namely two-stage clustering, two-stage p-median, and two-stage clustering and p-median heuristics, the location problem is solved by clustering technique, p-median, and clustering and p-median, respectively. In the second stage of the mentioned three heuristics, routing of customers is done with the extended version of Clarke & Wright Savings (CWS) heuristic which is called Biased Randomise Clarke & Wright (BRCW). The BRCW introduces biased randomness into the CWS algorithm by employing a pseudo-geometric distribution which generates the probabilistic parameter used to assign a probability of selection to each pair of routes in the savings list. In the iterated heuristic, a depot is chosen randomly in the first stage, and routing is solved in the second stage using the BRCW. The heuristic, then, iterates with another randomly chosen depot until all potential depots are checked. The algorithm keeps the best result in terms of both location and routing costs. The proposed heurists are implemented on 10 instances chosen from a well-known benchmark data set. The computational results show that the proposed iterated heuristic can provide the best result among the suggested heuristics. This means our approach is promising for further developments in terms of quality and computation time and extending the problem in terms of complexity and number of depots.
Original languageEnglish
Publication statusPublished - 6 Sept 2016
EventOR58 Annual Conference: The Operational Research Society Annual Conference 2016 - University of Portsmouth, Portsmouth, United Kingdom
Duration: 6 Sept 20168 Sept 2016


ConferenceOR58 Annual Conference
Country/TerritoryUnited Kingdom


Dive into the research topics of 'Heuristic Approaches for Location Routing Problem with a Single Depot'. Together they form a unique fingerprint.

Cite this