计算机工程 ›› 2007, Vol. 33 ›› Issue (11): 13-14,2.doi: 10.3969/j.issn.1000-3428.2007.11.005

• 博士论文 • 上一篇    下一篇

基于Hamilton回路的车辆巡逻问题优化算法

刘 杨1,赵禹骅2,周小庄3,彭国雄1,云美萍1   

  1. (1. 同济大学道路与交通工程教育部重点实验室,上海 200092;2. 广西行政学院,南宁 530000;3. 同济大学经济与管理学院,上海 200092)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-06-05 发布日期:2007-06-05

Optimization Algorithm of Vehicle Patrol Problem Based on Hamilton Loop

LIU Yang1, ZHAO Yuhua2, ZHOU Xiaozhuang3, PENG Guoxiong1, YUN Meiping1   

  1. (1. Key Laboratory of Road and Traffic Engineering of Ministry of Education, Tongji University, Shanghai 200092; 2. Guangxi School of Administration, Nanning 530000; 3. School of Economics & Management, Tongji University, Shanghai 200092)
  • Received:1900-01-01 Revised:1900-01-01 Online:2007-06-05 Published:2007-06-05

摘要: 一类车辆巡逻问题可以归结为赋权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

中图分类号: