×

A branch-and-price algorithm for the windy rural postman problem. (English) Zbl 1235.90020

Summary: 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.

MSC:

90B06 Transportation, logistics and supply chain management
90C10 Integer programming
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[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. · Zbl 1178.90332 · doi:10.1016/j.cor.2004.04.007
[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. Zbl1103.90095 · Zbl 1103.90095 · doi:10.1016/j.ejor.2005.09.021
[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). · Zbl 0596.90097
[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. · Zbl 0596.90097 · doi:10.1007/BFb0121091
[5] A. Corberán and J.M. Sanchis, A polyhedral approach to the rural postman problem. Eur. J. Oper. Res.79 (1994) 95-114. · Zbl 0819.90119 · doi:10.1016/0377-2217(94)90398-0
[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. · Zbl 0989.90026 · doi:10.1007/s101070100219
[7] G.B. Dantzig and P. Wolfe, Decomposition principle for linear programs. Oper. Res.8 (1960) 101-111. · Zbl 0093.32806 · doi:10.1287/opre.8.1.101
[8] G. Ghiani and G. Laporte, A branch and cut algorithm for the undirected rural postman problem. Math. Program.87 (2000) 467-481. · Zbl 0987.90091 · doi:10.1007/s101070050007
[9] M. Grötschel and Z. Win, A cutting plane algorithm for the windy postman problem. Math. Program.55 (1992) 339-358. · Zbl 0761.90082 · doi:10.1007/BF01581206
[10] A. Hertz, G. Laporte and P. Nanchen, Improvement procedures for the undirected rural postman problem. Informs J. Comput.11 (1999) 53-62. · Zbl 1034.90525 · doi:10.1287/ijoc.11.1.53
[11] 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 · Zbl 1106.90384 · doi:10.1287/opre.48.1.129.12455
[12] J.K. Lenstra and A.H.G. Rinnooy Kan, On general routing problems. Networks6 (1976) 273-280. · Zbl 0366.90092 · doi:10.1002/net.3230060305
[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. · Zbl 0423.90048 · doi:10.1287/mnsc.25.7.643
[15] C.S. Orloff, A fundamental problem in vehicle routing. Networks4 (1974) 35-64. Zbl0368.90130 · Zbl 0368.90130 · doi:10.1002/net.3230040105
[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. · Zbl 0671.90087 · doi:10.1007/BF01587080
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.