A developmental solution to (dynamic) capacitated arc routing problems using genetic programming

A developmental, ontogenic approach to Capacitated Arc Routing Problems (CARPs) is introduced. The genotypes of this method are constructive heuristics specified as trees of mathematical functions which are evolved with Genetic Programming (GP). In a genotype-phenotype mapping, they guide a virtual vehicle which starts at the depot. The genotype is used to compute a heuristic value for each edge with unsatisfied demands. Local information such as the visiting costs from the current position, the remaining load of the vehicle, and the edge demands are available to the heuristic. The virtual vehicle then serves the edge with the lowest heuristic value and is located at its end. This process is repeated until all requirements have been satisfied. The resulting phenotypes are sets of tours which, in turn, are sequences of edges. We show that our method has three advantages: 1) The genotypes can be reused to seed the population in new GP runs. 2) The size of the genotypes is independent from the problem scale. 3) The evolved heuristics even work well in modified or dynamic scenarios and are robust in the presence of noise.