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

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

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

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

中图分类号：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]建立了以旅游费用最优和旅游体验最好为双目标的数学模型，为旅游路径制定了更为科学合理的行程安排。在实际生活的运用中，可以时常发现该研究的适用范围具有一定的局限性。例如一个快递员从家里出发，需要经过便利店、邮局、加油站、酒店、学校，最后回到家中。该情况可以直接套用旅行商问题的相关求解算法对其求解。而在大多数情况下，我们并不希望最后目的地是家，这时，将会面临着起点和终点不相同的难题，直接套用旅行商问题的相关求解算法显然不合适。本文通过研究仓库拣货作业优化实例，在该难题的基础上求解拣货员的最优路径。

1 问题描述与基本假设

问题描述：现有一仓库，该仓库有13个复核台，4排货架。其中每排有25组货架，每组的货架均有2列货架并列背对背式摆放，共50个货架，每个货架又包含15个货格。分布示意图如图1所示。一拣货员在其中一个复核台领取了任务单，该任务单要求从起点复核台出发，将物品送往相应的货格下架商品，最后回到13个复核台中的其中一个，具体的示意图如图2所示，需找到拣货员行走的最短路线。