基于遗传算法的多旅行商问题研究.pdf

第26卷第5期 计算机应用研究 V01．26No．5 20019年5月 Researchof Mav2009 ApplIcation Computers 基于遗传算法的多旅行商问题研究 王海龙，周辉仁，郑丕谔，唐万生 (天津大学系统工程研究所，．天津300072) 摘要：针对所有旅行商路径总和最小为优化标准的多旅行商一类问题，用遗传算法优化，并提出了矩阵解码 方法。对距离非对称的多旅行商问题的实例进行了仿真，并对不同交叉算子性能进行了比较。结果表明，该算 法是有效的，适用于距离对称和非对称的多旅行商问题求解。 关键词：遗传算法；多旅行商问题；优化；解码方法 中图分类号：T玛01．6；TPl8文献标志码：A 文章编号：1001—3695(2009)05．1726．03 on salesman basedon StudymultipletraVeling problem geneticalgorithm WANG Huj一呦，ZHENGPi．e，7rANG Haj-l∞g，ZHOU W鲫-sheng (加f矗眦矿跏幼酰咖e嘶，％咖￡触m毋，彻咖3000r72，傩讹) Abst均ct：Inordertos01ve M鸭P(multipletravelingsalesm蚰pmblem)thatemployedtotal—path·shonest鹊theevaluating used to itand method而th multi- mle，this geneticalgorithmopIirIlizeproposed matrix．Simulated晒ymm硎c paper decoding cms∞ver sales眦n thedj疗咨rent resuits methodisemcient．Itis6t pletmveling pmbJef|tsusing operato倦．The8ugges￡tha￡thjs for salesman solvingsymmetric肌d鹊ymmet—cmultipletmveling pmbleH塔． 1Cey method woIIds：genetica190rithm；multipIle溉veling8aJesm锄pmblem；optilIli枷∞；decoding 是有效的。 0 引言 1 多旅行商问题数学模型 旅行商问题(travelingsalesm粕pmblem，偈P)是一个典型 的组合优化难题，它在许多领域都有着广泛的应用，已被证明 以点0表示旅行商的出发城市，称为源点，点l，…，Z表示 属于NP问题uJ。鸭P是指：有，v个城市，要求旅行商到达每 m个旅行商需要访问的城市。 个城市各一次且仅一次，并回到起点，且要求旅行路线最短。 定义变量： 而多旅行商问题(M偈P)是指M个旅行商从同一个城市(或不 rl旅行商^通过弧(iJ) 同城市)出发