考虑工作量平衡的多旅行商问题及其求解  

Multiple traveling salesmen problem with workload balance and its resolution

作　　者：刘伟民[1,2] 李苏剑[1] 郑爱云[2] 赵方庚[3] 

机构地区：[1]北京科技大学机械工程学院物流工程系,北京100083 [2]河北理工大学机械工程学院,河北唐山063009 [3]汽车管理学院车管系,安徽蚌埠233011

出　　处：《计算机工程与应用》2010年第15期47-50,共4页Computer Engineering and Applications

摘　　要：根据多旅行商问题(MTSP)特点,针对最小化各旅行商最长路线这一优化目标,提出改进蚁群算法(IACO)。最小化各旅行商最长路线考虑各旅行商的工作量平衡,更具实际应用意义。算法中信息素更新与限制遵循最大最小蚁群算法(MMAS)框架,为提高算法性能设计混合局域搜索算法。利用文献中标准算例进行检验,结果表明,所设计蚁群算法与三种遗传算法相比表现出较强竞争性。An improved ant colony optimization（IACO） algorithm for the MTSP is proposed.The optimized objective is that minimizing the maximum tour length of each salesman which related with balancing the workload among salesmen.The minmax objective has more application meaning in practice.In the algorithm,the pheromone trail updating and limits follow the MAX-MIN Ant System（MMAS） scheme,and a hybrid local search procedure is designed to improve the performance of the algorithm.The proposed algorithm is tested using some benchmark instances in literatures and compared with three genetic algorithms（GA）.The experimental results show that the proposed algorithm is competitive.

关 键 词：蚁群算法 局域搜索算法 多旅行商问题 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]