摘要
对于一个有2m个奇阶点的网络,中国邮路问题可转化为一个求m个奇阶点对的最优匹配问题。本文给出一种以有效的指派问题算法为基础的求解奇阶点最优匹配问题的分枝定界算法。对于一般规模(如100个奇阶点)的中国邮路问题,这个分枝定界算法是有效的。
The chinese-postman problem on a network with 2m odd-order-vert-exes can be changed into an optimum matching problem of finding m pairs of odd-order-vertexes, This paper gives a branch-bound algorithm for this optimum matching problem, based on the efficient algorithm for the assignment problem, The branch-bound algorithm is feasible for a medium-size,say 100 odd-order-vertexes, chinese-postman problem,
出处
《兰州铁道学院学报》
1992年第1期11-15,共5页
Journal of Lanzhou Railway University
关键词
邮递员问题
最短路
分配问题
chinese-postman problem, shortest path, assignment problem, branch-bound algorithm
