Abstract: The Village Postman Problem(VPP) is NP-complete problem. Most of the algorithms for it are intelligence algorithm and linear programming. Aiming at basic Quantum Evolution Algorithm(QEA) is easy to trap into local deceptive optima, an improved QEA is proposed. Experimental result demonstrates the improved algorithm can get better solution to the VPP than basic algorithm. It has better diversity and global search capacity. It indicates the algorithm is effective to solve the VPP.

Key words: Quantum Algorithm(QA), Quantum Evolutionary Algorithm(QEA), Village Postman Problem(VPP), Hamilton circle

摘要： 乡村邮递员问题属于NP完全问题，对它的近似求解方法主要是智能算法及线性规划，但其中的基本量子进化算法易陷于局部最优解。为此，提出一种新的量子进化算法，结合城市垃圾运输问题，对算法进行测试。结果表明，该算法在全局寻优能力及种群多样性方面均比传统算法有所改进，是求解乡村邮递员问题的一种有效算法。

关键词: 量子算法, 量子进化算法, 乡村邮递员问题, Hamilton圈

CLC Number: 

• TP311.52