  


Solving the Prizecollecting Rural Postman Problem
Julian Araoz (julian.araozupc.edu) Abstract: In this work we present an algorithm for solving the Prizecollecting 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 twophase 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 DR2007/12, EIO Departament, Technical University of Catalonia (Spain). Download: [PDF] Entry Submitted: 11/12/2007 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  