Orion/ORiON · 2005 · 30 citations · 23 references
Natural SciencesOperations ManagementOptimizationRural EconomicsRural PlanningCombinatorial OptimizationHeuristic OptimizationHeuristic SearchMetaheuristic OptimizationHeuristic AlgorithmsHeuristic Problem SolvingHeuristicsLocal SearchLocal Search AlgorithmsSearch HeuristicsTraveling Salesman ProblemTraveling Salesperson Problem
A local search framework for the (undirected) Rural Postman Problem (RPP) is presented in this paper. The framework allows local search approaches that have been applied successfully to the well–known Travelling Salesman Problem also to be applied to the RPP. New heuristics for the RPP, based on this framework, are introduced and these are capable of solving significantly larger instances of the RPP than have been reported in the literature. Test results are presented for a number of benchmark RPP instances in a bid to compare efficiency and solution quality against known methods.
23
A note on two problems in connexion with graphs
E. Dijkstra · Numerische Mathematik · 1959 · 23.8K citations
Computer Solutions of the Traveling Salesman Problem
Shen Lin · Bell System Technical Journal · 1965 · 2K citations
Matching, Euler tours and the Chinese postman
Jack Edmonds, Ellis L. Johnson · Mathematical Programming · 1973 · 987 citations