Solving the Prize-collecting Rural Postman Problem
Julian Araoz (julian.araozupc.edu)
Abstract: In this work we present an algorithm for solving the Prize-collecting Rural Postman Problem. This problem was recently defined and is a generalization of other arc routing problems like, for instance, the Rural Postman Problem. The main difference is that there are no required edges. Instead, there is a profit function on the edges that must be taken into account only the first time that an edge is traversed. The problem is modeled as a linear integer program where the system has an exponential number of inequalities. We propose a solution algorithm where iteratively we solve relaxed models with a small number of inequalities, that provide upper bounds, and we propose exact separation procedures for generating violated cuts when possible. We also propose a simple heuristic to generate feasible solutions that provide lower bounds at each iteration. We use a two-phase method with different solvers at each phase. Despite the difficulty of the problem, the numerical results from a series of computational experiments with various types of instances assess the good behavior of the algorithm. In particular, more that 80% of the instances were optimally solved with the LP relaxation of the model. The remaining instances were optimally solved on a second phase, most of them in small computation times.
Keywords: arc routing, branch and cut.
Category 1: Integer Programming
Category 2: Integer Programming (Cutting Plane Approaches )
Citation: Research Report DR-2007/12, EIO Departament, Technical University of Catalonia (Spain).
Entry Submitted: 11/12/2007
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|