Hybrid construction heuristics for vehicle routing problem by parameter tuning process

Abstract

The vehicle routing problem (VRP) is very popular due to its practicality for modelling real-life optimisation problem in the areas of logistics and transportation. The various objectives and constraints that arise in different circumstances often lead to the development of new variants of the VRP, which requires the development of a solution method that is robust and flexible. It has been proven that VRP and its extension are NP-complete problems. Thus, VRPs with large sizes could usually only be solved by using non-exact algorithms, such as meta-heuristic algorithms. Meta-heuristic algorithms have high reusability components that make its implementation a straightforward task. However, choosing the right heuristic components of the meta-heuristic and their parameter setting is not easy. These problems are regarded as meta-heuristic algorithm configuration problems. There is a considerable quantity of well-established methodology to tackle the parameter tuning problem. This thesis attempts to solve the heuristic selection problem with a parameter tuning method that is available in the literature - the response surface methodology. The case study in this thesis is a construction heuristic for the VRP that considers problem characteristics. By employing a procedure called 'normalisation', this study was able to combine several heuristics into a new hybrid construction heuristic. The methodology proceeded in two stages. First, a screening experiment was conducted in order to choose the right combination of heuristics. Second, each chosen heuristic was given a weight based on the model developed in stage two. The results were then evaluated against a popular benchmark instance: VRP with time windows constraint (VRPTW). The computational results showed that the new heuristic performed better than the default setting in more than 80% of test cases. However, the experiment to incorporate the new heuristic into a higher-level framework - called 'adaptive large neighbourhood search' (ALNS) - indicated that further investigation is needed to achieve satisfying performance.