Solution Modification Heuristic for Location-Routing Problem: Numerical Evaluation of VNS and SALRP

In this thesis the author observes the existing heuristics to solve the capacitated location-routing problem, as it is important to not only consider the depot’s location in the facility location problem but also the possible tours from the existing customers, thus including the tour cost in the facility location problem. The author propose the well-known GRASP, SALRP and VNS heuristics and observe them to understand various ways to obtain a good suboptimal solution. The VNS and SALRP heursitics are then surveyed even further because of their proven reliability and good solution's quality. Both heuristics are tested on three sets of instances with varying instance’s size and the results from both of them are compared to interpret how the solution in each heuristic progresses to the suboptimal solution. Afterwards, experiments regarding the diversification and intensification phase are conducted in VNS and SALRP algorithms to see the impact of diversification phase to the solution’s quality and the importance to balance both diversification and intensification phase to obtain a good suboptimal solution in considerably good amount of time. From all of experiments done to the VNS and SALRP, it can be summarized that VNS clearly outperforms SALRP, because it searches for the suboptimal solution more intensely with its neighborhood local searches. Although with this good solution’s quality the required CPU time is also very high compared to SALRP. Therefore, it is also suggested in the end to develop SALRP algorithm futher by using the extended local searches from VNS to increase the solution’s quality but also maintaining its ability to solve LRP in considerable amount of time.