摘要
If we restrict the postman to traversing each edge at most twice in the windypostman problem (WPP), we will get a new problem: 2WPP. An approximation algorithmhas been posed by M. Guan for the WPP. In the present paper, we improve the estimatederror given by M. Guan and show that we can estimate the error for the 2WPP by findinga minimum cost circulation. We also pose a new sufficient condition for the equivalencebetween WPP and 2WPP, which can be checked in polynomial time steps.
If we restrict the postman to traversing each edge at most twice in the windypostman problem (WPP), we will get a new problem: 2WPP. An approximation algorithmhas been posed by M. Guan for the WPP. In the present paper, we improve the estimatederror given by M. Guan and show that we can estimate the error for the 2WPP by findinga minimum cost circulation. We also pose a new sufficient condition for the equivalencebetween WPP and 2WPP, which can be checked in polynomial time steps.
