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.
|Publication status||Published - 6 Sep 2016|
|Event||OR58 Annual Conference: The Operational Research Society Annual Conference 2016 - University of Portsmouth, Portsmouth, United Kingdom|
Duration: 6 Sep 2016 → 8 Sep 2016
|Conference||OR58 Annual Conference|
|Period||6/09/16 → 8/09/16|