摘要
本文提出了带风向投递员问题(WPP)的一整数线性规划形式,并由此给出了WPP的一个多项式1——近似算法。文中指出:当所给风向图是欧拉图时,由这一近似算法求得的投递员路线是最优的投递员路线。
This paper proposes an integer linear programming formulation for the windy postman problem (WPP). By making use of the formulation, we give out another polynomial 1—approximation algorithm for the WPP. It is also shown that the postman route obtained by this approximation algorithm is optimal if the given windy graph is Eulerian.
关键词
整数规划
近似算法
图论
integer linear programming, windy postman problem, minimum cost circulation, approximation algorithm.
