Knowledge Transfer Genetic Programming with Auxiliary Population for Solving Uncertain Capacitated Arc Routing Problem

The uncertain capacitated arc routing problem is an NP-hard combinatorial optimisation problem with a wide range of applications in logistics domains. Genetic programming hyper-heuristic has been successfully applied to evolve routing policies to effectively handle the uncertain environment in this problem. The real world usually encounters different but related instances due to events like season change and vehicle breakdowns, and it is desirable to transfer knowledge gained from solving one instance to help solve another related one. However, the solutions found by the genetic programming process can lack diversity, and the existing methods use the transferred knowledge mainly during initialisation. Thus, they cannot sufficiently handle the change from the source to the target instance. To address this issue, we develop a novel knowledge transfer genetic programming with an auxiliary population. In addition to the main population for the target instance, we initialise an auxiliary population using the transferred knowledge and evolve it alongside the main population. We develop a novel scheme to carefully exchange the knowledge between the two populations, and a surrogate model to evaluate the auxiliary population efficiently. The experimental results confirm that the proposed method performed significantly better than the state-of-the-art genetic programming approaches for a wide range of uncertain arc routing instances, in terms of both final performance and convergence speed.