Uncertain Capacitated Arc Routing Problem (UCARP) is a classic combinatorial optimization problem with many important real-world applications. Genetic Programming (GP) is a powerful machine learning technique that has been successfully used as a Hyper-Heuristic (HH) approach to automatically evolving routing policies for UCARP. Interpretability is becoming an open issue in the field of UCARP. The GP-evolved routing policies are too complicated to be interpreted and understood by human operators. The practitioners may feel less confident of using the routing policies due to the lack of understanding of the inner mechanism, despite of their effectiveness shown on the training instances. Therefore, it is necessary to discover strategies that can improve the interpretability without weakening the effectiveness. The overall goal of this thesis is to develop novel GPHH-based methods that can automatically evolve both interpretable and effective routing policies for UCARP.