吕武壕 林镇滔 廖文星 蒋昌金

摘  要： 针对旅行商问题适用范围存在的局限性，结合实际的仓库拣货作业优化实例开展研究。考虑仓库内各货位点之间的相对位置关系以及拣货员可能行走的路线，设计出关于拣货员行走路线的分类算法;提出虚拟点的概念来解决旅行商问题求解时起点、终点不一致的问题;利用虚拟点，根据任务单要求找出拣货员所有的最优位置访问顺序;比较每一种情况，得到拣货员的最优路径，以实现缩短拣货总时间、减少人力和物力的总目标，较好地提高拣货效率。

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

中图分类号：TP311.1          文献标识码：A     文章编号：1006-8228（2021）05-60-04

Method of optimizing the applicable scope of the traveling salesman problem

Lv Wuhao1， Lin Zhentao2， Liao Wenxing1， Jiang Changjin1

（1. School of Information Engineering， Shaoguan University， Shaoguan， Guangdong 512005， China;

2. School of Mathematics and Statistics， Shaoguan University）

Abstract： 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 pickers 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.

Key words： traveling salesman problem; warehouse picking operations; shortest path; virtual point

0 引言

旅行推銷员问题，又称旅行商问题（Traveling Salesman Problem，TSP）[1]，是经典的组合优化中的一个NP难题，可以将它描述为：一个旅行商从给定的一个城市出发，遍历完所有城市，同时确保遍历过的城市不再重复经过，最终再回到起始城市的最短路径的问题。国内外的学者采用多种算法对其进行研究，目前主要有模拟退火算法[2]、禁忌搜索算法[3]、遗传算法[4]、贪婪算法[5]和蚁群算法[6]等。

该问题的研究被广泛应用于实际生活中，夏令儒[7]等将其应用于多无人机协同任务规划，较好地解决了当前无人机协同作战的目标分配问题。郑博文[8]等设计了一种无人机特征点覆盖搜索算法，能较好地提高无人机对特定目标点的覆盖搜索效率。牛悦诚[9]建立了以旅游费用最优和旅游体验最好为双目标的数学模型，为旅游路径制定了更为科学合理的行程安排。……