The Clustered Prize-Collecting Arc Routing Problem

Julián Aráoz (), Elena Fernández () and Carles Franquesa ()
Additional contact information
Julián Aráoz: Statistics and Operations Research Department, Technical University of Catalonia, 08034 Barcelona, Spain, and Simón Bolívar University, Caracas, 89000 Venezuela
Elena Fernández: Statistics and Operations Research Department, Technical University of Catalonia, 08034 Barcelona, Spain
Carles Franquesa: Computer Science Department, Technical University of Catalonia, 08034 Barcelona, Spain

Transportation Science, 2009, vol. 43, issue 3, 287-300

Abstract: Prize-collecting arc routing problems are arc routing problems where, in addition to the cost function, there is a profit function on the edges that must only be taken into account the first time that an edge is traversed. This work presents the clustered prize-collecting arc routing problem where there are clusters of arcs and it is required that all or none of the edges of a cluster be serviced. The paper studies properties and dominance conditions used for formulating the problem as a linear integer program. An exact algorithm for finding an optimal solution to the problem is also proposed. At the root node of the enumeration tree, the algorithm generates upper and lower bounds obtained from solving an iterative linear programming-based algorithm in which violated cuts are generated when possible. A simple heuristic that generates feasible solutions provides lower bounds at each iteration. The numerical results from a series of computational experiments with various types of instances illustrate the good behavior of the algorithm. Over 75% of the instances were solved at the root node, and the remaining instances were solved with a small additional computational effort.

Keywords: linear integer programming; arc routing problems (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1090.0270 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:43:y:2009:i:3:p:287-300

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().