APP下载

改进混合蚁群算法求解关联旅行商问题

2014-08-16蔡延光汤雅连

网络安全与数据管理 2014年9期
关键词:关联信息

朱 君,蔡延光,汤雅连

(广东工业大学 自动化学院,广东 广州 510006)

旅行商问题 TSP[1-2](Traveling Salesman Problem)是运筹学领域中的经典优化组合问题,并且属于NP-Hard(NPH)问题,其计算复杂性随输入规模呈指数函数增长,其实际模型在连锁店的货物配送、电子地图、印刷电路板的钻孔路线方案、超大规模集成电路单元布局、网格布线、管道铺设等优化问题中有着广泛的应用。游客在访问城市时,会有各种约束,关联约束就是其中一种,由于两个或多个城市依次举行展会、博览会、艺术节、广交会及马拉松比赛等,这些演艺类、体育类、文化类及商业类的大型活动往往吸引着广大游客,游客会尽可能地参观或者参加节事旅游,比如3个旅游城市A、B和C依次举办大型活动,那么游客访问的次序应该是A→B→C,这就是关联旅行商问题ITSP(Incident Traveling Salesman Problem),由于该问题模型在现实生活中普遍存在,因而具有研究意义。

目前已经有很多求解TSP的算法。SILBERHOLZ J等人[3]研究了多彩TSP(Colourful Travelling Salesman Problem,CTSP),提出了两种新的启发式算法对其求解,并证明了所提出方法的有效性。ROY S[4]应用带单点交叉算子的遗传算法求解TSP,实验证明能搜索到最优解。MAVROVOUNIOTIS M[5]等人针对带交通因素的动态TSP,应用移民策略的蚁群优化算法ACO(Aat Colony Optimization)求解,实验证明提出的算法优于传统的ACO。SINGH H等人[6]应用遗传算法求解多旅行商问题 MTSP(Multiple Traveling Salesman Problem)。柳寅等人[7]基于模糊化处理和蜂群寻优的特点,提出一种模糊人工蜂群算法,通过对旅行商问题的仿真证明了该算法有良好的鲁棒性和有效性。王刚等人[8]应用多项式时间近似方案PTAS(PolynomialTimeApproxination Scheme)研究曲面上的TSP,一般性的深刻结论还有待研究。……

登录APP查看全文

猜你喜欢

关联信息
不惧于新,不困于形——一道函数“关联”题的剖析与拓展
“苦”的关联
“一带一路”递进,关联民生更紧
订阅信息
智趣
展会信息
语言学与修辞学:关联与互动
信息
健康信息
健康信息(九则)