一种关于旅行商问题适用范围的优化方法  

Method of optimizing the applicable scope of the traveling salesman problem

作　　者：吕武壕 林镇滔 廖文星 蒋昌金 Lv Wuhao;Lin Zhentao;Liao Wenxing;Jiang Changjin(School of Information Engineering,Shaoguan University,Shaoguan,Guangdong 512005,China;School of Mathematics and Statistics,Shaoguan University)

机构地区：[1]韶关学院信息工程学院,广东韶关512005 [2]韶关学院数学与统计学院

出　　处：《计算机时代》2021年第5期60-63,72,共5页Computer Era

基　　金：韶关市科技计划项目(2019sn080);韶关学院重点专业-计算机科学与技术(230080990302)

摘　　要：针对旅行商问题适用范围存在的局限性,结合实际的仓库拣货作业优化实例开展研究。考虑仓库内各货位点之间的相对位置关系以及拣货员可能行走的路线,设计出关于拣货员行走路线的分类算法;提出虚拟点的概念来解决旅行商问题求解时起点、终点不一致的问题;利用虚拟点,根据任务单要求找出拣货员所有的最优位置访问顺序;比较每一种情况,得到拣货员的最优路径,以实现缩短拣货总时间、减少人力和物力的总目标,较好地提高拣货效率。Aiming at the limitations of the scope of application of the traveling salesman problem,the research is carried out with the combination of the actual example of optimizing warehouse picking operation.Considering the relative position relationship between the location points in the warehouse and the route that the picker may walk,a classification algorithm for the route of the picker is designed;By using virtual points,which is a concept proposed for solving the problem that the start point and the end point are different in the traveling salesman problem,all the picker’s optimal routes for accessing the location points according to the requirements of the task list can be found out;comparing the routes,the shortest path for the picker can be obtained,so as to achieve the overall goal of shortening the total time of picking goods,reducing manpower and material resources,which better improves the picking efficiency.

关 键 词：旅行商问题 仓库拣货作业 图论 最短路径 虚拟点 

分 类 号：TP311.1[自动化与计算机技术—计算机软件与理论]