多旅行商近似算法研究与应用
|
摘要
由旅行商问题(TSP)衍生出来多旅行商问题(M-TSP)是组合优化领域的经典问题之一,是人工智能中遇到的一个具有广泛的研究意义的课题.多旅行商问题的特点使其符合许多实际问题,现实中经常会出现类似多出发点多旅行商的问题,其环境的动态不确定性要求系统实时调整任务规划,算法的计算时间复杂度应该尽可能低.另外目前很多系统车载计算能力通常很有限.因此,有必要研究能满足多出发点多旅行商系统需要的任务规划方法.
本文通过对模型的处理和社团结构的分析,设计了一类多旅行商路径均衡近似算法并推广到多出发点多旅行商问题的求解,同时基于此算法应用于Ad hoc网络的多路径路由中,取得了显著的优化效果.
本文所做的主要工作如下：
类多旅行商路径均衡规划算法.本文研究了多个旅行商旅行多个城市的路径规划问题,提出了基于系统科学中的”吸引子”意义下的路径规划算法.路径规划的目标是均衡各旅行商的旅行路径长度并使得路径总和得到优化.为此提出了一种求解该问题的启发式算法思想,并结合邻近点和最短路径设计了算法,同时算法的复杂度分析知该算法的计算时间复杂度较以往的要低.
类多出发点多旅行商问题规划算法.本文提出了一种基于K-means聚类算法的多出发点多旅行商问题求解的新方法.算法定义了节点的吸引度,并通过节点吸引度矩阵进行子环游节点集的归类,然后对各子环游应用单旅行商启发式算法进行求解.针对多出发点多旅行商问题的实例进行实验表明此规划算法能很好的求解此类问题.
Ad hoc网络中基于多旅行商问题的多路径路由算法.提出一种基于旅行商问题的多路径路由算法(TSPMR算法),TSPMR算法是对Leach算法的扩展而进行多路径路由,把整个网络分成多个簇,通过簇首收集和传输信息,并不断地进行簇首确定来降低能耗,簇内进行多路径路由,保证了路由的稳定性.
the multiple traveling salesman problem (M-TSP) is one of the typical problems on the field of combinatorial optimization, deriving from the Traveling salesman problem,which is a significance research issue on the field of artificial intelligence. the characteristics of Multiple traveling salesman problem conform many practical problems, and the uncertainty of Multi-objective Traveling Salesman problem that we confront,requires system adjust mission planning timely, and the computation complexity should be as low as possible. Also the limited computing system is not enough to achieve the complexity process.So studing a new method to resolve this promblem is necessary.
Based on the model of the processing and analysis of community structure, designing a kind of Multi-objective Traveling Salesman problem Mission Planning Algorithm and promoting to A kind of mission planning algorithm with multidepot multisalesmen problem, obtaining remarkable optimization results applied in Ad hoc network.
The major work of this paper can be summarized as follows:
a kind of Multi-objective Traveling Salesman problem Mission Planning Algo-rithm with Balanced Paths.The paper presents a mission planning algorithm for Multi-objective traveling salesman problem with an objective to balance the length of traveling path and make the sum of path optimization.The travel mission involves several cities that need to be passed by traveling salesman.This algorithm is based upon the "attractors" of systems science.In this paper,combining with the neigh-boring points and the shortest path algorithm,we design a heuristic algorithm for solving the problem which balancing the length of traveling path and making the sum of path optimization,At the same time,the computation time complexity of the algorithm is lower than the past.
A kind of mission planning algorithm with multidepot multisalesmen problem. This paper presents a new solving method for multidepot multisalesmen problem based on K-means clustering algorithm. Algorithm defines the node attract and classies the set of the tour node according node attract matrix,then applies the heuristic algorithm of single traveling salesman to solve it.The experiments results with multidepot multisalesmen problem show that this mission planning algorithm can be effectively applied in solving such problems
multi-path routing algorithm of Ad hoc networks based on multiple travel-ing salesman problem. Traveling salesman problem multi-path routing algorithm (TSPMR algorithm), is a multi-path routing of expansion Leach algorithm,mul-tiple clusters in the whole network, determine the cluster head to reduce energy consumption by collecting and transporting information, executing multi-path rout-ing to ensure routing stability within the cluster.
本文通过对模型的处理和社团结构的分析,设计了一类多旅行商路径均衡近似算法并推广到多出发点多旅行商问题的求解,同时基于此算法应用于Ad hoc网络的多路径路由中,取得了显著的优化效果.
本文所做的主要工作如下：
类多旅行商路径均衡规划算法.本文研究了多个旅行商旅行多个城市的路径规划问题,提出了基于系统科学中的”吸引子”意义下的路径规划算法.路径规划的目标是均衡各旅行商的旅行路径长度并使得路径总和得到优化.为此提出了一种求解该问题的启发式算法思想,并结合邻近点和最短路径设计了算法,同时算法的复杂度分析知该算法的计算时间复杂度较以往的要低.
类多出发点多旅行商问题规划算法.本文提出了一种基于K-means聚类算法的多出发点多旅行商问题求解的新方法.算法定义了节点的吸引度,并通过节点吸引度矩阵进行子环游节点集的归类,然后对各子环游应用单旅行商启发式算法进行求解.针对多出发点多旅行商问题的实例进行实验表明此规划算法能很好的求解此类问题.
Ad hoc网络中基于多旅行商问题的多路径路由算法.提出一种基于旅行商问题的多路径路由算法(TSPMR算法),TSPMR算法是对Leach算法的扩展而进行多路径路由,把整个网络分成多个簇,通过簇首收集和传输信息,并不断地进行簇首确定来降低能耗,簇内进行多路径路由,保证了路由的稳定性.
the multiple traveling salesman problem (M-TSP) is one of the typical problems on the field of combinatorial optimization, deriving from the Traveling salesman problem,which is a significance research issue on the field of artificial intelligence. the characteristics of Multiple traveling salesman problem conform many practical problems, and the uncertainty of Multi-objective Traveling Salesman problem that we confront,requires system adjust mission planning timely, and the computation complexity should be as low as possible. Also the limited computing system is not enough to achieve the complexity process.So studing a new method to resolve this promblem is necessary.
Based on the model of the processing and analysis of community structure, designing a kind of Multi-objective Traveling Salesman problem Mission Planning Algorithm and promoting to A kind of mission planning algorithm with multidepot multisalesmen problem, obtaining remarkable optimization results applied in Ad hoc network.
The major work of this paper can be summarized as follows:
a kind of Multi-objective Traveling Salesman problem Mission Planning Algo-rithm with Balanced Paths.The paper presents a mission planning algorithm for Multi-objective traveling salesman problem with an objective to balance the length of traveling path and make the sum of path optimization.The travel mission involves several cities that need to be passed by traveling salesman.This algorithm is based upon the "attractors" of systems science.In this paper,combining with the neigh-boring points and the shortest path algorithm,we design a heuristic algorithm for solving the problem which balancing the length of traveling path and making the sum of path optimization,At the same time,the computation time complexity of the algorithm is lower than the past.
A kind of mission planning algorithm with multidepot multisalesmen problem. This paper presents a new solving method for multidepot multisalesmen problem based on K-means clustering algorithm. Algorithm defines the node attract and classies the set of the tour node according node attract matrix,then applies the heuristic algorithm of single traveling salesman to solve it.The experiments results with multidepot multisalesmen problem show that this mission planning algorithm can be effectively applied in solving such problems
multi-path routing algorithm of Ad hoc networks based on multiple travel-ing salesman problem. Traveling salesman problem multi-path routing algorithm (TSPMR algorithm), is a multi-path routing of expansion Leach algorithm,mul-tiple clusters in the whole network, determine the cluster head to reduce energy consumption by collecting and transporting information, executing multi-path rout-ing to ensure routing stability within the cluster.
引文
[1]刑文训,谢金星.现代优化计算方法.北京：清华大学出版社,2003.
[2]G.Reinelt.Traveling Salesman Problem Library ORSAJ.comput,1991,3(4):373-385.
[3]Belgium.Ant Colony System:A Cooperative Learning Approach to the Traveling Salesman Problem.Technical Report IRIDIA.1996.
[4]杨忠,鲍明,赵淳生.人机结合求解中国旅行商问题.模式识别与人工智能,1995,8(4)：373-376.
[5]Tang L X,Liu J Y.A multiple traveling salesman problem model for hot rolling schedule in Shang hai Baoshan Iron and steel Complex.European Journal of Operational Reseach,2000,124(2):267-282.
[6]Dotigo M. Ant Colony Optimization.Cambridge,MA:MIT Press,2004.
[7]Dorigo M,Di Caro G,Gambardella L M.Ant algorithms for distributed discrete optimization Artificial Life,1999,5(2):137-172.
[8]Gutjahr W J.graph-based ant system.future Generation Computing Sys-tems,2000.
[9]Holland J H.Adaptation in Natural and Artificial Systems.MA:MIT Press,1975.
[10]Grefenstette J J.Optimization of control parameters for genetic algo-rithms.IEEE Traps Syst Man and Cybern,1986,16(2):122-128.
[11]周明,孙树栋.遗传算法原理及应用.北京,国防工业出版社,1999.
[12]陈玉旺.基于极值动力学的自组织优化理论、算法与应用研究.上海交通大学大学博士论文,2007,10.
[13]Ballard D H.An Introduction to Natural Computation.MA:MIT press,1999.
[14]Manna.Self-organized critical models of earthquakes.physica A,2007,384(3):15-20.
[15]谢政.网络算法与复杂性理论.长沙：国防科技大学出版社,2003.
[16]杜端浦.运筹图论.北京：北京航空航天大学出版社,1994.
[17]刘水强.算法语言与计算方法基础.北京：科学出版社,2005.
[18]Tsai Huai-Kuang, Yang Jinn-Moon, Tsai Yuan-Fang, Kao Cheng-Yan. An evo-lutionar algorithm for large traveling salesman problems. IEEE Transactions on Systems, Man and Cybernetics, Part B,2004,34(4):1718-1729.
[19]Jin Hui-Dong, Leung Kwong-Sak, Wong Man-Leung,Xu ZB. An efficient self-organizing map designed algorithm for the traveling salesman problem. IEEE Transactions on Systems, Man and Cybernetics, Part B,2003,33(6):877-888.
[20]杨国兴.一种多出发点多旅行商问题到旅行商问题的转换.系统工程理论方法应用,1993,2(3)：66-68.
[21]杨超然,杨国兴.运筹与决策.成都：成都科技大学出版社,1992.
[22]卢厚清,王辉东,黄杰,李波.任务均分的多旅行商问题.系统工程,2005 23(2)：19-21.
[23]Lagoudakis M G, Berhault M, Koenig S, et al. Simple auctions with performance guarantees for multi-robot task allocation. In Proceedings of 2004. IEEE/RSJ International Conference on Intelligent Robots and Systems, Sendal, Japan, 2004,698-705.
[24]Somhom S, Modares A,Enkawa T. Competition-based neural network for the multiple traveling salesmen problem with minmar objective. Computes Opera-tion Research,1999,26(2):395-407.
[25]莫愿斌.一旅行商问题的综述教学研究.中国科教创新导报,2008,8(2)：93-94.
[26]黄斌.多目标问题的有效pareto最优集.计算机与数字工程,2009,37(2)：28-34.
[27]Cormen T H, Leiserson C E, Rivest R L. Introduction to Algorithms.MIT Press,1997.
[28]高平安.多机器人负载均衡任务规划算法.高技术通讯.2009,19(5)：501-505.
[29]陈继业.旅行商问题的近似算法研究.长沙：国防科技大学,2003.p.30-37.
[30]Chapman G H,Dufoet B.Using laser defect avoidance to build large-area FP-GAs.IEEE Design Test of Computers,1998,15(4):75-81.
[31]Hanchek F,Dutt S.Methodologies for tolerating cell and interconnect faults in FPGAs.IEEE Trans on Computers,1998,47(9):15-33.
[32]吕雄伟,赵达,李军.基于多态蚁群算法的多目标邮政物流车辆路径问题研究.计算机应用研究,2009,26(6)：2070-2078.
[33]李天龙.基于自组织优化算法的一类多旅行商问题.计算机应用,2010,30(2)：458-460.
[34]杨国兴.一种多出发点多旅行商问题到旅行商问题的转换.系统工程理论方法应用,1993,2(3)：66-68.
[35]Newman M E J,Gibvan M.Finding and evaluating community structure.Phys Rev E,2004,69(2):26-33.
[36]Han Jia-wei,Kanber M.Data mining:concepts and techiniques.San Fran-cisco:Morgan Kaufmann Publishers,2000.
[37]Ordonez C,Omiecinski E.Efficient disk-based K-means clustering for relational databases.IEEE Trans on Knowledge and Data Engineering,2004,16(8):909-921.
[38]赵凤霞,谢福鼎.基于K-means聚类算法的复杂网络社团发现新方法.计算机应用研究,2009,26(6)：2041-2044.
[39]Luca Maria Gambardella and Marco Dorigo.Solving symmetric and symmet-ric TSP's by ant colonies.proc.IEEE Int.conf.Evolutionary Computation,IEEE-ECp,1996.
[40]王金龙,王呈贵,吴启晖等.Ad hoc移动无线网络.北京：国防工业出版社,2004.
[41]刘水强.计算机网络应用基础.北京：科学出版社,2006.
[42]Zhang L F,Zhao Z H,Shu Y T,et al.Load balancing of multipath source in ad hoc networks//Proc of the IEEE Int'Conf on Communications(ICC 2002).New Orleans:IEEE,2002:3197-3201.
[43]Tsirigos A,Haas Z.Multipath routing in the presence of frequent topological changes.IEEE Communications Magazine,2001,39(11):132-138.
[44]郭磊,汪斌强,陈庶樵.一种面向关键点的多路径路由算法.计算机工程与应用,2008,44(26)：119-121.
[45]黄敏,刘琼,奚建清.一种基于生存时间的Ad hoc网络不相交多路径路由算法.计算机应用研究,2010,27(3)：1157-1160.
[46]王亚利,杨小影,于继明.Ad hoc网络中基于分簇的多路径路由协议.计算机工程与应用,2008,44(33)：131-134.
[47]Cidom I,Rom R,Shavitt Y.Analysis of multi-path routing.IEEE/ACM Trans-actions on Networking,1999,7(6):885-896.
[48]Chiang C C.routing in cluster multihop,mobile wireless networks with fading channel.proc IEEE Sicon'97,1997.
[49]沈波,张世永,钟亦平.无线传感器网络分簇路由协议.软件学报,2006,17(7)：126-133.
[50]王捷民,吴正宇,订刚毅.Ad hoc网络中一种稳定的网格多路径路由算法.兵工学报,2009,30(8)：1129-1133.
[2]G.Reinelt.Traveling Salesman Problem Library ORSAJ.comput,1991,3(4):373-385.
[3]Belgium.Ant Colony System:A Cooperative Learning Approach to the Traveling Salesman Problem.Technical Report IRIDIA.1996.
[4]杨忠,鲍明,赵淳生.人机结合求解中国旅行商问题.模式识别与人工智能,1995,8(4)：373-376.
[5]Tang L X,Liu J Y.A multiple traveling salesman problem model for hot rolling schedule in Shang hai Baoshan Iron and steel Complex.European Journal of Operational Reseach,2000,124(2):267-282.
[6]Dotigo M. Ant Colony Optimization.Cambridge,MA:MIT Press,2004.
[7]Dorigo M,Di Caro G,Gambardella L M.Ant algorithms for distributed discrete optimization Artificial Life,1999,5(2):137-172.
[8]Gutjahr W J.graph-based ant system.future Generation Computing Sys-tems,2000.
[9]Holland J H.Adaptation in Natural and Artificial Systems.MA:MIT Press,1975.
[10]Grefenstette J J.Optimization of control parameters for genetic algo-rithms.IEEE Traps Syst Man and Cybern,1986,16(2):122-128.
[11]周明,孙树栋.遗传算法原理及应用.北京,国防工业出版社,1999.
[12]陈玉旺.基于极值动力学的自组织优化理论、算法与应用研究.上海交通大学大学博士论文,2007,10.
[13]Ballard D H.An Introduction to Natural Computation.MA:MIT press,1999.
[14]Manna.Self-organized critical models of earthquakes.physica A,2007,384(3):15-20.
[15]谢政.网络算法与复杂性理论.长沙：国防科技大学出版社,2003.
[16]杜端浦.运筹图论.北京：北京航空航天大学出版社,1994.
[17]刘水强.算法语言与计算方法基础.北京：科学出版社,2005.
[18]Tsai Huai-Kuang, Yang Jinn-Moon, Tsai Yuan-Fang, Kao Cheng-Yan. An evo-lutionar algorithm for large traveling salesman problems. IEEE Transactions on Systems, Man and Cybernetics, Part B,2004,34(4):1718-1729.
[19]Jin Hui-Dong, Leung Kwong-Sak, Wong Man-Leung,Xu ZB. An efficient self-organizing map designed algorithm for the traveling salesman problem. IEEE Transactions on Systems, Man and Cybernetics, Part B,2003,33(6):877-888.
[20]杨国兴.一种多出发点多旅行商问题到旅行商问题的转换.系统工程理论方法应用,1993,2(3)：66-68.
[21]杨超然,杨国兴.运筹与决策.成都：成都科技大学出版社,1992.
[22]卢厚清,王辉东,黄杰,李波.任务均分的多旅行商问题.系统工程,2005 23(2)：19-21.
[23]Lagoudakis M G, Berhault M, Koenig S, et al. Simple auctions with performance guarantees for multi-robot task allocation. In Proceedings of 2004. IEEE/RSJ International Conference on Intelligent Robots and Systems, Sendal, Japan, 2004,698-705.
[24]Somhom S, Modares A,Enkawa T. Competition-based neural network for the multiple traveling salesmen problem with minmar objective. Computes Opera-tion Research,1999,26(2):395-407.
[25]莫愿斌.一旅行商问题的综述教学研究.中国科教创新导报,2008,8(2)：93-94.
[26]黄斌.多目标问题的有效pareto最优集.计算机与数字工程,2009,37(2)：28-34.
[27]Cormen T H, Leiserson C E, Rivest R L. Introduction to Algorithms.MIT Press,1997.
[28]高平安.多机器人负载均衡任务规划算法.高技术通讯.2009,19(5)：501-505.
[29]陈继业.旅行商问题的近似算法研究.长沙：国防科技大学,2003.p.30-37.
[30]Chapman G H,Dufoet B.Using laser defect avoidance to build large-area FP-GAs.IEEE Design Test of Computers,1998,15(4):75-81.
[31]Hanchek F,Dutt S.Methodologies for tolerating cell and interconnect faults in FPGAs.IEEE Trans on Computers,1998,47(9):15-33.
[32]吕雄伟,赵达,李军.基于多态蚁群算法的多目标邮政物流车辆路径问题研究.计算机应用研究,2009,26(6)：2070-2078.
[33]李天龙.基于自组织优化算法的一类多旅行商问题.计算机应用,2010,30(2)：458-460.
[34]杨国兴.一种多出发点多旅行商问题到旅行商问题的转换.系统工程理论方法应用,1993,2(3)：66-68.
[35]Newman M E J,Gibvan M.Finding and evaluating community structure.Phys Rev E,2004,69(2):26-33.
[36]Han Jia-wei,Kanber M.Data mining:concepts and techiniques.San Fran-cisco:Morgan Kaufmann Publishers,2000.
[37]Ordonez C,Omiecinski E.Efficient disk-based K-means clustering for relational databases.IEEE Trans on Knowledge and Data Engineering,2004,16(8):909-921.
[38]赵凤霞,谢福鼎.基于K-means聚类算法的复杂网络社团发现新方法.计算机应用研究,2009,26(6)：2041-2044.
[39]Luca Maria Gambardella and Marco Dorigo.Solving symmetric and symmet-ric TSP's by ant colonies.proc.IEEE Int.conf.Evolutionary Computation,IEEE-ECp,1996.
[40]王金龙,王呈贵,吴启晖等.Ad hoc移动无线网络.北京：国防工业出版社,2004.
[41]刘水强.计算机网络应用基础.北京：科学出版社,2006.
[42]Zhang L F,Zhao Z H,Shu Y T,et al.Load balancing of multipath source in ad hoc networks//Proc of the IEEE Int'Conf on Communications(ICC 2002).New Orleans:IEEE,2002:3197-3201.
[43]Tsirigos A,Haas Z.Multipath routing in the presence of frequent topological changes.IEEE Communications Magazine,2001,39(11):132-138.
[44]郭磊,汪斌强,陈庶樵.一种面向关键点的多路径路由算法.计算机工程与应用,2008,44(26)：119-121.
[45]黄敏,刘琼,奚建清.一种基于生存时间的Ad hoc网络不相交多路径路由算法.计算机应用研究,2010,27(3)：1157-1160.
[46]王亚利,杨小影,于继明.Ad hoc网络中基于分簇的多路径路由协议.计算机工程与应用,2008,44(33)：131-134.
[47]Cidom I,Rom R,Shavitt Y.Analysis of multi-path routing.IEEE/ACM Trans-actions on Networking,1999,7(6):885-896.
[48]Chiang C C.routing in cluster multihop,mobile wireless networks with fading channel.proc IEEE Sicon'97,1997.
[49]沈波,张世永,钟亦平.无线传感器网络分簇路由协议.软件学报,2006,17(7)：126-133.
[50]王捷民,吴正宇,订刚毅.Ad hoc网络中一种稳定的网格多路径路由算法.兵工学报,2009,30(8)：1129-1133.