Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6896063 | European Journal of Operational Research | 2016 | 10 Pages |
Abstract
In this paper we study the profitable windy rural postman problem. This is an arc routing problem with profits defined on a windy graph in which there is a profit associated with some of the edges of the graph, consisting of finding a route maximizing the difference between the total profit collected and the total cost. This problem generalizes the rural postman problem and other well-known arc routing problems and has real-life applications, mainly in snow removal operations. We propose here a formulation for the problem and study its associated polyhedron. Several families of facet-inducing inequalities are described and used in the design of a branch-and-cut procedure. The algorithm has been tested on a large set of benchmark instances and compared with other existing algorithms. The results obtained show that the branch-and-cut algorithm is able to solve large-sized instances optimally in reasonable computing times.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Thais Ávila, Ángel Corberán, Isaac Plana, José M. Sanchis,