动态旅行商问题的研究  

Research on Dynamic Traveling Salesman Problem

作　　者：李树刚[1] 陈雪峰[1] 

机构地区：[1]上海交通大学工业工程与管理系,上海200240

出　　处：《计算机工程》2008年第10期187-189,共3页Computer Engineering

基　　金：国家自然科学基金资助项目(70501021)

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

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

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]