一種關(guān)于旅行商問題適用范圍的優(yōu)化方法

呂武壕 林鎮(zhèn)滔 廖文星 蔣昌金

摘? 要： 針對(duì)旅行商問題適用范圍存在的局限性，結(jié)合實(shí)際的倉(cāng)庫(kù)揀貨作業(yè)優(yōu)化實(shí)例開展研究。考慮倉(cāng)庫(kù)內(nèi)各貨位點(diǎn)之間的相對(duì)位置關(guān)系以及揀貨員可能行走的路線，設(shè)計(jì)出關(guān)于揀貨員行走路線的分類算法;提出虛擬點(diǎn)的概念來解決旅行商問題求解時(shí)起點(diǎn)、終點(diǎn)不一致的問題;利用虛擬點(diǎn)，根據(jù)任務(wù)單要求找出揀貨員所有的最優(yōu)位置訪問順序;比較每一種情況，得到揀貨員的最優(yōu)路徑，以實(shí)現(xiàn)縮短揀貨總時(shí)間、減少人力和物力的總目標(biāo)，較好地提高揀貨效率。

關(guān)鍵詞： 旅行商問題; 倉(cāng)庫(kù)揀貨作業(yè); 圖論; 最短路徑; 虛擬點(diǎn)

中圖分類號(hào)：TP311.1? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ?文章編號(hào)：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]，是經(jīng)典的組合優(yōu)化中的一個(gè)NP難題，可以將它描述為：一個(gè)旅行商從給定的一個(gè)城市出發(fā)，遍歷完所有城市，同時(shí)確保遍歷過的城市不再重復(fù)經(jīng)過，最終再回到起始城市的最短路徑的問題。國(guó)內(nèi)外的學(xué)者采用多種算法對(duì)其進(jìn)行研究，目前主要有模擬退火算法[2]、禁忌搜索算法[3]、遺傳算法[4]、貪婪算法[5]和蟻群算法[6]等。

該問題的研究被廣泛應(yīng)用于實(shí)際生活中，夏令儒[7]等將其應(yīng)用于多無人機(jī)協(xié)同任務(wù)規(guī)劃，較好地解決了當(dāng)前無人機(jī)協(xié)同作戰(zhàn)的目標(biāo)分配問題。鄭博文[8]等設(shè)計(jì)了一種無人機(jī)特征點(diǎn)覆蓋搜索算法，能較好地提高無人機(jī)對(duì)特定目標(biāo)點(diǎn)的覆蓋搜索效率。牛悅誠(chéng)[9]建立了以旅游費(fèi)用最優(yōu)和旅游體驗(yàn)最好為雙目標(biāo)的數(shù)學(xué)模型，為旅游路徑制定了更為科學(xué)合理的行程安排。在實(shí)際生活的運(yùn)用中，可以時(shí)常發(fā)現(xiàn)該研究的適用范圍具有一定的局限性。例如一個(gè)快遞員從家里出發(fā)，需要經(jīng)過便利店、郵局、加油站、酒店、學(xué)校，最后回到家中。該情況可以直接套用旅行商問題的相關(guān)求解算法對(duì)其求解。而在大多數(shù)情況下，我們并不希望最后目的地是家，這時(shí)，將會(huì)面臨著起點(diǎn)和終點(diǎn)不相同的難題，直接套用旅行商問題的相關(guān)求解算法顯然不合適。本文通過研究倉(cāng)庫(kù)揀貨作業(yè)優(yōu)化實(shí)例，在該難題的基礎(chǔ)上求解揀貨員的最優(yōu)路徑。

1 問題描述與基本假設(shè)

問題描述：現(xiàn)有一倉(cāng)庫(kù)，該倉(cāng)庫(kù)有13個(gè)復(fù)核臺(tái)，4排貨架。其中每排有25組貨架，每組的貨架均有2列貨架并列背對(duì)背式擺放，共50個(gè)貨架，每個(gè)貨架又包含15個(gè)貨格。分布示意圖如圖1所示。一揀貨員在其中一個(gè)復(fù)核臺(tái)領(lǐng)取了任務(wù)單，該任務(wù)單要求從起點(diǎn)復(fù)核臺(tái)出發(fā)，將物品送往相應(yīng)的貨格下架商品，最后回到13個(gè)復(fù)核臺(tái)中的其中一個(gè)，具體的示意圖如圖2所示，需找到揀貨員行走的最短路線。