摘要： 一类车辆巡逻问题可以归结为赋权Hamilton回路最小化问题。该文采用一种局部优化的单点切割方法，优化了业已求得的Hamilton回路经典启发式算法，给出了算法基础定理的数学证明，通过算例说明了算法的实现过程。该算法改进了经典启发式算法的性能，在实践中取得了良好的效果。

关键词: Hamilton回路, 单点切割方法, 优化算法

Abstract: The vehicle patrol problem can be regarded as Hamilton loop, which possesses the minimum total weight. The paper solves the partial optimization of classical algorithm with single point cut method, also proves the algorithm basic principle. The example demonstrates the process of the algorithm. The arithmetic improves the ability of classical algorithm of Hamilton loop.

Key words: Hamilton loop, Single point cut method, Optimization algorithm

中图分类号: 

• TP18