A branch‐and‐price algorithm for the windy rural postman problem

A branch‐and‐price algorithm for the windy rural postman problem

0.00 Avg rating0 Votes
Article ID: iaor20127595
Volume: 45
Issue: 4
Start Page Number: 353
End Page Number: 364
Publication Date: Oct 2011
Journal: RAIRO - Operations Research
Authors: , ,
Keywords: postman problem, branch and price
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.

Reviews

Required fields are marked *. Your email address will not be published.