Updating road network information requires determining an optimal path that visits all roads requiring data collection. This problem, known as the Rural Postman Problem (RPP), is traditionally addressed using relational databases. However, graph databases may offer advantages by more naturally representing network structures, where nodes represent junctions and edges represent roads. This study explores the novel representation of road networks using graph databases and its unique application in optimizing RPP algorithms. We implemented three existing algorithms—(a) Nearest Neighbor, (b) “Biased” Monte Carlo, and (c) Genetic algorithm—using Cypher and compared them with (d) a novel Cypher-only algorithm designed to compute the optimal path. The results show that the Nearest Neighbor algorithm was the fastest and produced the shortest paths among all algorithms. The Cypher-only algorithm could also identify optimal paths but failed to scale beyond five required edges. These findings highlight the limitations of using Cypher alone for solving the RPP but suggest that Neo4j and Cypher hold promise for further exploration.
Hasegawa et al. (Sat,) studied this question.