|
A branch and cut algorithm for the Undirected Profitable Location Rural Postman Problem
|
Mostafa Khorramzadeh *    , Roghayeh Javvi |
| Shiraz University of Technology , m.khorrami@sutech.ac.ir |
|
|
Abstract: (4543 Views) |
This paper is concerned with presenting an exact algorithm for the Undirected Profitable Location Rural Postman Problem. This problem combines the profitable rural postman and facility location problems and also has some interesting real-life applications. Fixed costs are associated with end points of each profitable edge and the objective is to choose a subset of profitable edges such that the difference between the profit collected and the cost of opening facilities and traveling cost is maximized. A dominance relation is used to present an integer programming formulation for the problem and a branch and cut algorithm is developed for solving the problem and extensive numerical results on real-world benchmark instances are given to evaluate the quality of presented algorithms.
|
|
| Keywords: Rural Postman Problem, Branch and cut, Location Problem, Arc Routing Problem with Profits, Undirected Graph. |
|
|
Full-Text [PDF 616 kb]
(7622 Downloads)
|
Type of Study: Original |
Subject:
Mathematical Modeling and Applications of OR
Received: 2022/04/6 | Accepted: 2021/06/12 | Published: 2021/06/12
|
|
|
|
|
|
|
| Send email to the article author |
|
|
|
| Add your comments about this article |
|
|
|
