Abstract
In this research work, we consider various classes of the Location Routing Problem namely: (1) Location Routing Problem with Single Depot (LRPSD), (2) Multi-Depot Vehicle Routing Problem (MDVRP), (3) Location Routing Problem with Multi-Depots (LRPMD), and (4) Green Location Routing Problem with Multi-Depot (G-LRPMD). These problems are NP-hard in terms of computational complexities. The interdependence between facility location and vehicle routing has been recognised by practitioners and academics. The LRP is to integrate these two decisions and solve them simultaneously. As both the facility location and the vehicle routing are NP-hard, LRP is also NPhard. Thus, exact methods are limited to solve the LRP of a practical size. Alternatively, heuristics and metaheuristics have been applied to solve more realistic problems.Biased Randomised technique has been combined with heuristics to successfully solve the Facility Location Problem (FLP) and the Vehicle Routing Problem (VRP) due to its simplicity, efficiency, and it is a parameter-free heuristic. However, to the best of our knowledge, it has not been combined with a heuristic to solve the LRP.
In this thesis, we have proposed four Biased Randomised heuristics to solve LRPSD, MDVRP, LRPMD and G-LRPMD. Moreover, we have developed a Biased Randomised Variable Neighbourhood Search (BR-VNS) metaheuristic in collaboration with our collaborators at the Internet Interdisciplinary Institute (IN3) in the Universitat Oberta de Catalunya in Spain and Universidad de La Sabana in Colombia.
The first solution method is to solve the LRPSD by a heuristic with four variations. Each variation of the heuristic solves the location by one of the following solution methods namely: clustering, p-median, clustering and p-median, and iterative method. However, in all variations of the heuristic, the routing decisions are made by combining Biased Randomised technique with Clark and Wright heuristic (CWH).
The second solution method is developed to solve the MDVRP by combining Biased Randomised technique with Extended Clark and Wright heuristic (ECWH), which we called Biased Randomised Extended Clark and Wright heuristic (BR-ECWH). The LRPMD is solved by extending the BR-ECWH to consider location decision. Finally, the G-LRPMD is solved by adapting the LRPMD solution method to include constrained distance.
The effectiveness of the suggested solution methods are tested by conducting extensive computational experiments using data sets from the literature. These data sets have many different sizes (such as number of customers, and number of depots) and characteristics (such as distribution of customers, and capacity of depots and vehicles) and are then compared to the best-known solutions in the literature.
The computational analysis indicates the efficiency of the proposed solution methods. The suggested solution methods are also shown to be flexible to solve other classes of the LRP.
| Date of Award | Jan 2019 |
|---|---|
| Original language | English |
| Supervisor | Banafsheh Khosravi (Supervisor) & Djamila Ouelhadj (Supervisor) |