Optimization Online


Solving the Prize-collecting Rural Postman Problem

Julian Araoz (julian.araoz***at***upc.edu)
Elena Fernandez (e.fernandez***at***upc.edu)
Oscar Meza (meza***at***ldc.usb.ve)

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).

Download: [PDF]

Entry Submitted: 11/12/2007
Entry Accepted: 11/12/2007
Entry Last Modified: 11/14/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society