6533b82dfe1ef96bd1291bd9
RESEARCH PRODUCT
A computational study of several heuristics for the DRPP
Vicente CamposJ. V. Savallsubject
Set (abstract data type)Connected componentComputational MathematicsMathematical optimizationControl and OptimizationHeuristicApplied MathematicsHeuristicsUpper and lower boundsAlgorithmArc routingCutting-plane methodMathematicsdescription
The problem of designing a route of minimum length for a postman that starts and finishes at his office and has to deliver the mail along a set of streets in a city is known as the Rural Postman Problem. When the postman has to obey the directions of the streets, we have the directed version of this problem. Finding an exact solution, in the general case, is intractably difficult. Hence, we have implemented three heuristic algorithms for approximately solving this problem and a procedure for obtaining a lower bound to the optimal length. Also, we present numerical experimentations based on a collection of random instances with up to 30 connected components, 240 vertices and 801 arcs. A lower bound for the optimal DRPP value is obtained by using cutting plane techniques, producing an optimal solution in 21 out of 60 instances. The main purpose of this work is to compare these three algorithms. We also give guidelines concerning the performance of the algorithms depending on the characteristics of the problem to solve.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1995-01-01 | Computational Optimization and Applications |