# A branch-and-price algorithm for the windy rural postman problem

Hasan Murat Afsar; Nicolas Jozefowiez; Pierre Lopez

RAIRO - Operations Research (2012)

- Volume: 45, Issue: 4, page 353-364
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topAfsar, Hasan Murat, Jozefowiez, Nicolas, and Lopez, Pierre. "A branch-and-price algorithm for the windy rural postman problem." RAIRO - Operations Research 45.4 (2012): 353-364. <http://eudml.org/doc/222504>.

@article{Afsar2012,

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.},

author = {Afsar, Hasan Murat, Jozefowiez, Nicolas, Lopez, Pierre},

journal = {RAIRO - Operations Research},

keywords = {Branch-and-price; windy rural postman problem; branch-and-price},

language = {eng},

month = {3},

number = {4},

pages = {353-364},

publisher = {EDP Sciences},

title = {A branch-and-price algorithm for the windy rural postman problem},

url = {http://eudml.org/doc/222504},

volume = {45},

year = {2012},

}

TY - JOUR

AU - Afsar, Hasan Murat

AU - Jozefowiez, Nicolas

AU - Lopez, Pierre

TI - A branch-and-price algorithm for the windy rural postman problem

JO - RAIRO - Operations Research

DA - 2012/3//

PB - EDP Sciences

VL - 45

IS - 4

SP - 353

EP - 364

AB - 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.

LA - eng

KW - Branch-and-price; windy rural postman problem; branch-and-price

UR - http://eudml.org/doc/222504

ER -

## References

top- E. Benavent, A. Corberán, E. Piñana, I. Plana and J.M. Sanchis, New heuristic algorithms for the windy rural postman problem. Comput. Oper. Res.32 (2005) 3111–3128. Zbl1178.90332
- E. Benavent, A. Carotta, A. Corberán, J.M. Sanchis and D. Vigo, Lower bounds and heuristics for the windy rural postman problem. Eur. J. Oper. Res.176 (2007) 855–869. Zbl1103.90095
- N. Christofides, V. Campos, A. Corberán and E. Mota, An algorithm for the rural postman problem. Technical Report 5, Imperial College Report ICOR815 (1981). Zbl0596.90097
- N. Christofides, V. Campos, A. Corberán and E. Mota, An algorithm for the rural postman problem on a directed graph. Math. Program. Stud.26 (1986) 155–166. Zbl0596.90097
- A. Corberán and J.M. Sanchis, A polyhedral approach to the rural postman problem. Eur. J. Oper. Res.79 (1994) 95–114. Zbl0819.90119
- A. Corberán, A. Letchford and J.M. Sanchis, A cutting plane algorithm for the general routing problem. Math. Program.90 (2001) 291–316. Zbl0989.90026
- G.B. Dantzig and P. Wolfe, Decomposition principle for linear programs. Oper. Res.8 (1960) 101–111. Zbl0093.32806
- G. Ghiani and G. Laporte, A branch and cut algorithm for the undirected rural postman problem. Math. Program.87 (2000) 467–481. Zbl0987.90091
- M. Grötschel and Z. Win, A cutting plane algorithm for the windy postman problem. Math. Program.55 (1992) 339–358. Zbl0761.90082
- A. Hertz, G. Laporte and P. Nanchen, Improvement procedures for the undirected rural postman problem. Informs J. Comput.11 (1999) 53–62. Zbl1034.90525
- A. Hertz, G. Laport and M. Mittaz, A tabu search heuristic for the capacitated arc routing problem. Oper. Res.48 (2000) 129–135. Zbl1106.90384
- J.K. Lenstra and A.H.G. Rinnooy Kan, On general routing problems. Networks6 (1976) 273–280. Zbl0366.90092
- A.N. Letchford, Polyhedral results for some constrained arc-routing problems. Ph.D. thesis, Lancaster University (1996).
- E. Minieka, The chinese postman problem for mixed networks. Manage. Sci.25 (1979) 643–648. Zbl0423.90048
- C.S. Orloff, A fundamental problem in vehicle routing. Networks4 (1974) 35–64. Zbl0368.90130
- J.M. Sanchis, El poliedro del problema del cartero rural. Ph.D. thesis, University of Valencia (1990) (in Spanish).
- Z. Win, On the windy postman problem on eulerian graphs. Math. Program.44 (1989) 97–112. Zbl0671.90087

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.