Abstract | ||
---|---|---|
In this paper, we propose an exact solution method for the windy rural postman problem (WRPP). The motivation to study this problem comes from some real-life applications, such as garbage collecting in a predefined sector with hills, where the traversing or the servicing speed can change following the direction. We present a Dantzig-Wolfe decomposition and a branch-and-price algorithm to solve the WRPP. To the best of our knowledge, Dantzig-Wolfe decomposition has never been used to solve that problem. The numerical results show that optimal solutions are found in a very reasonable amount of time on instances with up to 100 nodes and 180 edges. |
Year | DOI | Venue |
---|---|---|
2011 | 10.1051/ro/2012004 | RAIRO-OPERATIONS RESEARCH |
Keywords | Field | DocType |
Branch-and-price,windy rural postman problem | Exact solutions in general relativity,Garbage,Mathematical optimization,Branch and price,Algorithm,Mathematics,Traverse | Journal |
Volume | Issue | ISSN |
45 | 4 | 0399-0559 |
Citations | PageRank | References |
0 | 0.34 | 9 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Hasan Murat Afsar | 1 | 0 | 0.68 |
Nicolas Jozefowiez | 2 | 348 | 21.58 |
Pierre Lopez | 3 | 0 | 0.34 |