Solving the rural postman problem using a genetic algorithm with a graph transformation
Myung-Ju Kang, Chi-Geun Han · 1998
This paper describes a genetic algorithm(GA) and proposes a structure of chromosome for Rural Postman Problem (RPP) which is to find a minimum cost tour that must pass through edges in E' (C E) at least once in a given graph G=(V, E).In this paper, we transform a graph of RPP into a Hamiltonian graph to construct chromosomes.Hence, we can reduce the length of a chromosome and the size of the solution space.In simulation, we compare a GA with the proposed chromosome structure with a GA with an exsisting chromosome structure.