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

Abstract

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

How to cite

top

Afsar, 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
  1. 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.  
  2. 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.  
  3. 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).  
  4. 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.  
  5. A. Corberán and J.M. Sanchis, A polyhedral approach to the rural postman problem. Eur. J. Oper. Res.79 (1994) 95–114.  
  6. A. Corberán, A. Letchford and J.M. Sanchis, A cutting plane algorithm for the general routing problem. Math. Program.90 (2001) 291–316.  
  7. G.B. Dantzig and P. Wolfe, Decomposition principle for linear programs. Oper. Res.8 (1960) 101–111.  
  8. G. Ghiani and G. Laporte, A branch and cut algorithm for the undirected rural postman problem. Math. Program.87 (2000) 467–481.  
  9. M. Grötschel and Z. Win, A cutting plane algorithm for the windy postman problem. Math. Program.55 (1992) 339–358.  
  10. A. Hertz, G. Laporte and P. Nanchen, Improvement procedures for the undirected rural postman problem. Informs J. Comput.11 (1999) 53–62.  
  11. A. Hertz, G. Laport and M. Mittaz, A tabu search heuristic for the capacitated arc routing problem. Oper. Res.48 (2000) 129–135.  
  12. J.K. Lenstra and A.H.G. Rinnooy Kan, On general routing problems. Networks6 (1976) 273–280.  
  13. A.N. Letchford, Polyhedral results for some constrained arc-routing problems. Ph.D. thesis, Lancaster University (1996).  
  14. E. Minieka, The chinese postman problem for mixed networks. Manage. Sci.25 (1979) 643–648.  
  15. C.S. Orloff, A fundamental problem in vehicle routing. Networks4 (1974) 35–64.  
  16. J.M. Sanchis, El poliedro del problema del cartero rural. Ph.D. thesis, University of Valencia (1990) (in Spanish).  
  17. Z. Win, On the windy postman problem on eulerian graphs. Math. Program.44 (1989) 97–112.  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.