基于蚁群算法的带有时间约束旅行商问题求解  

Time Constrained Traveling Salesman Problem Solving Based on Ant Colony Algorithm

作　　者：李安颖 陈群[1] 宋荷 LI Anying;CHEN Qun;SONG He(School of Computer Science,Northwest Polytechnic University,Xi’an 710072,China)

机构地区：[1]西北工业大学计算机学院,陕西西安710072

出　　处：《自动化仪表》2019年第4期95-98,共4页Process Automation Instrumentation

摘　　要：为了实现物流行业的快速、有效配送,可以将问题转化为含时间约束的旅行商问题(TSP)。通过对物流配送环节的研究,构建了一种带有时间约束的TSP模型,并提出一种利用改进的MapReduce蚁群算法求解该模型。利用MapReduce的并行机制,对蚁群算法进行并行处理,使其运行在分布式环境中,增强了求解大规模问题的能力,提高了运行速度。试验证明,在用户预约了送货时间段的情况下,该方法能较好地解决数据运算规模大、算法运算时间长的问题,合理规划物流配送路径。In order to achieve fast and effective delivery in logistics industry,the problem can be transformed into a time-constrained traveling salesman problem(TSP).Through studying the logistics delivery link,a traveling businessman problem model with time constraints is constructed,and an improved MapReduce ant colony algorithm is proposed to solve the model.Using the parallel mechanism of MapReduce,the ant colony algorithm is processed in parallel to make it run in a distributed environment,which enhances the ability to solve large-scale problems and improves the running speed.Experiments verify that this method can solve the problems of large scale of data operation and longtime of arithmetic operation,and reasonably plan the logistics delivery path when the user has reserved a delivery time period.

关 键 词：MAPREDUCE 蚁群算法 物流配送 时间约束 旅行商问题 分布式处理 信息素 智能算法 

分 类 号：TH123[机械工程—机械设计及理论]