A Branch-and-Price algorithm for the windy rural postman problem

Hasan Murat Afsar (1) , Nicolas Jozefowiez (2) , Pierre Lopez (2)

1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels
2 LAAS-MOGISA

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.

Mots clés: Windy Rural Postman Problem; Branch-and-Price

Domaines: Recherche opérationnelle [math.OC]

Hasan Murat Afsar, Nicolas Jozefowiez, Pierre Lopez. A Branch-and-Price algorithm for the windy rural postman problem. RAIRO - Operations Research, 2011, 45 (4), p.353-364. ⟨hal-00676778⟩