A two-stage biased randomised heuristic for the green location routing problem with constrained distances

The introduction of electric vehicles (EVs) in modern fleets facilitates a shift towards greener road transportation. However, the driving ranges of EVs are limited by the duration of their batteries, which causes new operational challenges. Therefore, distance constraints are introduced into the Location Routing Problem (LRP), which is a natural extension of the LRP when EVs are utilised. The new problem is called Location Routing Problem with Constrained
Distance (LRPCD). We propose a two-stage biased-randomised heuristic to solve the green LRPCD, which combines biased-randomised techniques with the well-known Tillman's heuristic for the Multiple Depots Vehicle Routing Problem (MDVRP). During the first stage, a selection of ‘elite’ solutions is completed; during the second stage, these elite solutions are improved. Thus, in the first stage, an iterative approach is employed to choose the best solution with regard to the minimum location and routing cost for different combinations of depots. The second stage consists of two levels. In the global level, a biased-randomised extended savings heuristic is developed to improve the result of the MDVRP generated during the first stage. In the local level, we adapt a biased-randomized savings heuristic from the literature to solve the corresponding vehicle routing problem for each depot which is resulted from the global level. In both global and local levels, the biased randomisation is introduced by employing a geometric probability distribution, which generates a probability of selection for each pair of routes in the savings lists of the devised classical and extended savings heuristics. In order to evaluate the performance of the proposed algorithm, we have generated new data sets by adding distance constraints to three well-known LRP benchmarks. The computational results show that the proposed approach achieves good results in a reasonable computation time and it is promising for further developments in terms of quality.