  Due to its direct relevance to post-disaster operations, meter reading and
civil refuse collection, the Uncertain Capacitated Arc Routing Problem (UCARP)
is an important optimisation problem. Stochastic models are critical to study
as they more accurately represent the real-world than their deterministic
counterparts. Although there have been extensive studies in solving routing
problems under uncertainty, very few have considered UCARP, and none consider
collaboration between vehicles to handle the negative effects of uncertainty.
This paper proposes a novel Solution Construction Procedure (SCP) that
generates solutions to UCARP within a collaborative, multi-vehicle framework.
It consists of two types of collaborative activities: one when a vehicle
unexpectedly expends capacity (\emph{route failure}), and the other during the
refill process. Then, we propose a Genetic Programming Hyper-Heuristic (GPHH)
algorithm to evolve the routing policy used within the collaborative framework.
The experimental studies show that the new heuristic with vehicle collaboration
and GP-evolved routing policy significantly outperforms the compared
state-of-the-art algorithms on commonly studied test problems. This is shown to
be especially true on instances with larger numbers of tasks and vehicles. This
clearly shows the advantage of vehicle collaboration in handling the uncertain
environment, and the effectiveness of the newly proposed algorithm.
