Cluster-based Hyper-Heuristic for Large-Scale Vehicle Routing Problem

摘要

One of the most known transportation problems, the Large-Scale Vehicle Routing Problem (LSVRP) requires more sophisticated methods to be solved due to the sheer amount of customers. Most current methods include manually designed heuristics and parameters, such as restrictions in the search space. Hyper-heuristics(HHs) appear as a counterpoint to the manually designed complex methods. This paper presents a preliminary study on adaptive search space based on clustering, utilizing a HH Selection framework with Genetic Algorithm (GA). The initial results show promise in having an adaptive search scope when compared to a fixed clustering approach. A comparison of the effects of having a route-first vs cluster-first initial solution is also presented, favouring the latter one, as well as a comparison between two types of chromosome decoding. Finally, the proposed method is compared to a manually designed algorithm, producing results with better quality. The method is shown to be significantly better for most scenarios, achieving solutions just as good as when no limits are applied, but in a much shorter time.