6533b854fe1ef96bd12aeb83
RESEARCH PRODUCT
A branch-and-cut algorithm for the Profitable Windy Rural Postman Problem
Thais ÁVilaÁNgel CorberánJosé M. SanchisIsaac Planasubject
Arc routingMathematical optimizationInformation Systems and ManagementGeneral Computer ScienceTotal costSnow removal0211 other engineering and technologies02 engineering and technologyManagement Science and Operations ResearchIndustrial and Manufacturing EngineeringProfit (economics)Polyhedron0502 economics and businessWindy rural postman problemMathematics050210 logistics & transportation021103 operations research05 social sciencesBranch-and-cut algorithmModeling and SimulationMATEMATICA APLICADAArc routingAlgorithmBranch and cutPolyhedronProfitsdescription
[EN] 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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2016-03-16 |