作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2008, Vol. 34 ›› Issue (10): 187-189. doi: 10.3969/j.issn.1000-3428.2008.10.068

• 人工智能及识别技术 • 上一篇    下一篇

动态旅行商问题的研究

(上海交通大学工业工程与管理系,上海 200240)   

  1. (上海交通大学工业工程与管理系,上海 200240)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2008-05-20 发布日期:2008-05-20

Research on Dynamic Traveling Salesman Problem

(Department of Industrial Engineering and Management, Shanghai Jiaotong University, Shanghai 200240)   

  1. (Department of Industrial Engineering and Management, Shanghai Jiaotong University, Shanghai 200240)
  • Received:1900-01-01 Revised:1900-01-01 Online:2008-05-20 Published:2008-05-20

摘要: 传统的旅行商问题都是静态的,但在现实中许多问题是动态的。该文提出动态旅行商问题,问题的规模随时间不断变化。实时问题对算法的求解效率要求很高,为此设计了基于模糊规则的在线遗传算法,可以根据求解问题的变化,在线精炼模糊控制规则来控制算法的参数。仿真实验验证了算法的有效性。

关键词: 动态旅行商问题, 遗传算法, 模糊

Abstract: The common Traveling Salesman Problem(TSP) is static, but in actual life, most optimal problems are dynamic. This paper proposes the dynamic TSP, the size of the candidate city and the distance between cities may vary from time to time, while within the sample time these variables remain unchanged. That is a real time optimal problems and it is necessary to design the fast optimal tool. The fuzzy based genetic algorithm is proposed. Fuzzy rules are online extracted in the running process of algorithm, and these rules are used to adapt the parameter of genetic algorithm. Simulation results confirm the efficiency of the algorithm.

Key words: Dynamic TSP(DTSP), Genetic Algorithm(GA), fuzzy

中图分类号: