A Branch-and-Price algorithm for the windy rural postman problemReport as inadecuate

A Branch-and-Price algorithm for the windy rural postman problem - Download this document for free, or read online. Document in PDF available to download.

* Corresponding author 1 LOSI, Institut Charles Delaunay 2 LAAS-MOGISA LAAS - Laboratoire d-analyse et d-architecture des systèmes Toulouse

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.

Keywords : Branch-and-Price Windy Rural Postman Problem

Author: Hasan-Murat Afsar - Nicolas Jozefowiez - Pierre Lopez -

Source: https://hal.archives-ouvertes.fr/


Related documents