基于改進禁忌搜索算法的藥房批量取藥路徑規劃研究

收稿日期：2023-08-04

基金項目：南京醫科大學康達學院科研發展項目（KD2023KYJJ025）

DOI：10.19850/j.cnki.2096-4706.2024.05.032

摘" 要：針對藥房批量取藥這一現實問題，在設計藥房整體環境布局和引入路徑規劃算法的基礎上，提出以重量加權的距離為目標的旅行商問題TSP（Traveling Salesman Problem）。建立一個混合整數規劃模型，使用禁忌搜索算法進行模型求解，使用曼哈頓距離作為兩點之間距離，在禁忌長度等參數設置上使用動態自適應方法，并在算法中加入擾動方法，避免算法陷入局部最優，增加搜索目標的多樣性。最后使用JAVA進行了仿真模擬實驗，可視化結果驗證了算法的可行性和有效性。

關鍵詞：醫藥物流；路徑規劃；藥房批量取藥；旅行商問題；禁忌搜索算法

中圖分類號：TP18;R95" " 文獻標識碼：A" 文章編號：2096-4706（2024）05-0149-06

Research on Path Planning in Pharmacy Batch Picking Medicine Based on

Improved Tabu Search Algorithm

QIU Yuan， GONG Xingyu

（Kangda College of Nanjing Medical University， Lianyungang" 222000， China）

Abstract： Based on the design of the overall environment layout of pharmacies and the introduction of path planning algorithms， a Traveling Salesman Problem （TSP） with weight weighted distance as the objective is proposed to address the practical problem of pharmacy batch picking medicine. It establishes a mixed integer programming model， uses tabu search algorithm for model solving， uses Manhattan distance as the distance between two points， uses dynamic adaptive methods in setting parameters such as tabu length， and adds a shake method to the algorithm to avoid getting stuck in local optima and increase the diversity of search targets. Finally， simulation experiments are conducted using JAVA， and the visualization results have verified the feasibility and effectiveness of the algorithm.

Keywords： pharmaceutical logistics; path planning; pharmacy batch picking medicine; TSP; tabu search algorithm

0" 引" 言

目前國內藥房的藥品存儲方式主要為固定式貨架，平時藥房大量簡單重復的取藥工作耗費了很多不必要的人力物力，且在效率和準確率方面也有待提高[1，2]。在此背景下，本文將路徑規劃算法應用到藥房取藥問題中，在國內大部分藥房為固定式貨架的基礎上進行取藥路徑規劃的研究，首先搭建藥房環境模型并描述取藥過程，將藥房批量取藥問題轉換為一個考慮藥品重量的TSP問題，使用曼哈頓距離作為兩點之間距離，建立一個混合整數規劃模型，然后使用禁忌搜索算法規劃最優路線，基于傳統的禁忌搜索算法在參數自適應設置和增加擾動方法上進行改進，最后使用JAVA進行仿真模擬實驗，設計三類實驗算例包括直線取藥、同側異路取藥以及異側異路取藥，展示可視化結果并討論路徑規劃效果。將路徑規劃運用到藥房取藥工作中去，既能提高藥師的工作效率，減輕藥房管理工作的負擔，也能減少患者取藥的等待時間，提高患者的就診體驗，對醫療機構整體質量的提升具有實際意義；另外也希望本文的研究結果能夠為機器人自動取藥的研究[3-8]奠定一定基礎。

1" 藥房批量取藥問題描述與模型建立

1.1" 藥房環境建模

本文以藥房批量取藥為研究對象，首先需要對藥房環境進行建模。現如今普遍的藥房布局分為垂直式布局、傾斜式布局以及區別于前兩者的非傳統布局[9]，垂直式布局可細分為橫列式、縱列式以及縱橫式，特點是主副通道縱橫交錯，整體布局整齊美觀，便于存取盤點；而傾斜式布局能夠把存儲空間劃分為具有不同特點的區域，大致分為貨架傾斜式和通道傾斜式；非傳統布局的典型代表為V式貨架，可以區分需大量儲存和少量儲存的不同部分以便綜合利用，但這種布局形式復雜，路徑較多不好計算[10]。本文基于國內大部分藥房藥品存儲的固定式貨架，并借鑒Kiva系統倉庫模型[11]，假定藥房大小和藥架位置固定不變，藥架采用單側開式格子類，一個格子僅存放一種藥品，兩個單側藥柜背靠式排放，藥房通道采用傳統的縱橫式通道布局方法，由作為主通道的橫向通道和作為副通道的縱向通道組成的十字交叉通道，存放藥品的藥柜與主通道相垂直，設定副通道可作為多種藥品的取藥點。

藥房環境模型如圖1所示。藥房環境模型由藥柜、取藥人、取藥點、通道及隔離帶組成，其中黑點表示取藥人，圖1中黑點所在位置為取藥過程的起點和終點，矩形表示藥柜，藥柜中標灰的部分代表目標藥柜即所取藥品的所在位置，白點代表取藥點，實線表示隔離帶，一般為墻壁不可通行，其余為可通行區域。

圖1" 藥房環境模型示意圖

在藥房模型的基礎上對取藥過程做如下設定：

1）取藥過程中固定起點與終點，且起點和終點是同一個，一次完整的取藥過程需要從起點出發并最終返回起點。

2）取藥方式默認單側僅可取該側藥品且只能在目標藥柜正對面的取藥點取藥。

3）取藥時在藥房通道內只能進行直角轉向。

4）每次取藥可取多種藥品，且每種藥品數量確定，即在一次取藥過程中取完所有種類藥品的對應數量后再返回起點。

在本文建立的藥房模型中，取藥過程大致如圖2所示。模型建立在二維坐標系上，取藥人每次取藥需要從起點出發經過所有目標藥柜對應的取藥點進行取藥操作后再回到起點，思考如何規劃考慮藥品重量的取藥最優路線。因此，可以將藥房批量取藥問題轉換為起點終點固定、以重量加權的距離為目標的TSP問題。

1.2" 混合整數規劃模型

數學模型定義在一個有向圖G = （V，E），其中V = {0，1，2，…，n}是節點集合，包括起點{0}、終點{n}和取藥點集合A，E表示兩兩節點間可能的有向邊的集合。現要為每次取藥過程規劃出一條取藥路徑，目標是使重量加權距離之和最小。

圖2" 取藥過程流程圖

1.2.1" 模型參數

表1定義了數學模型的參數及參數對應的含義。

表1" 模型參數及含義

符號 含義

G = （V，E） 有向圖，其中V是節點集合，E是邊集合

0 起點

n 終點

A 取藥點集合，A ? V

dij 節點i，j間的距離，i，j ∈ V

qi 節點i的待取數量，i ∈ V，其中起點和終點的數量設為0

wi 節點i的單位重量，i ∈ V，其中起點和終點的單位重量設為0

M 一個大數

1.2.2" 模型決策變量

數學模型的決策變量有Xij、Yi，各變量對應的含義如表2所示。

表2" 模型決策變量及含義

決策變量 含義

Xij 0，1變量，1表示經過邊（i，j），否則為0

Yi 到達節點i時已取藥品的總重量（不包括節點i處的藥品重量）

1.2.3" 數學模型

建立如式（1）至式（7）所示的混合整數規劃模型：

min" " " " " " " " " " " "（1）

s.t." " " "（2）

（3）

（4）

（5）

（6）

（7）

式（1）為目標函數，表示最小化重量加權距離之和。式（2）至式（7）為約束條件，式（2）至式（4）為流平衡約束，式（2）表示如果到達某個取藥點，取完藥品后必須離開該點，式（3）（4）確保每個目標取藥點均被訪問且僅被訪問一次；式（5）表示在兩個連續節點的載重關系，即在到達取藥點時已取藥品的總重量等于到達上一個取藥點時已取藥品的總重量加上該取藥點的待取藥品重量；式（6）（7）為決策變量的定義域，Xij為0，1變量，Yi大于等于0。

2" 改進禁忌搜索算法的設計

2.1" 算法框架

禁忌搜索算法由美國科羅拉多大學教授Glover[12]提出，是一種全局搜索尋優算法，具有全局逐步尋優的能力，是局部搜索算法的優化與發展[13]。本文使用一種改進的禁忌搜索算法求解模型，基于傳統的禁忌搜索算法，使用曼哈頓距離作為兩點之間距離，在禁忌長度等參數設置上使用動態自適應方法，并在算法中加入擾動方法，避免算法陷入局部收斂，增加搜索多樣性。

圖3為改進禁忌搜索算法的算法流程圖，算法的大致步驟為：

1）初始化算法的各項參數，包括禁忌表、禁忌長度、迭代次數等，計算曼哈頓距離作為兩點之間距離，隨機生成一個初始可行解，從初始解出發進行鄰域搜索。

2）以當前解為一次迭代的起點進行鄰域搜索，每次鄰域搜索產生許多候選解，將不在禁忌表中的最優候選解記為本次鄰域最優解。

3）將本次鄰域最優解與全局最優解進行比較，若優于全局最優解則將全局最優解替換。然后進行擾動操作，隨機選擇鄰域解以跳出局部最優，同時更新禁忌表和禁忌長度，即如果禁忌表中存放的解的禁忌次數達到禁忌長度，那么將這些解從禁忌表中解禁退出。

4）若達到算法終止條件，即迭代次數達最大迭代次數，則算法停止，輸出最優解，否則回到Step2繼續進行新一輪的鄰域搜索。

2.2" 算法核心模塊設計

2.2.1" 計算兩點之間的距離——曼哈頓距離

曼哈頓距離（Manhattan Distance）是19世紀赫爾曼·閔可夫斯基所創詞匯，大部分使用在幾何度量空間中，表明兩個點在標準坐標系上的絕對軸距總和[14]。曼哈頓距離可以被理解為投影后的距離，如圖4所示，線①為歐氏距離即直線距離，線②為曼哈頓距離，線③和④代表等價的曼哈頓距離，這四條線雖然長短不一但理論上它們長度是等價的。毫無疑問兩點之間直線距離最短，但在實際情況中往往兩點之間會存在許多障礙物導致直線路線不可通行，此時則可以使用等價的曼哈頓距離。

圖3" 算法流程圖

圖4" 曼哈頓距離與歐式距離示意圖

本文模型建立在二維坐標系上，曼哈頓距離在二維坐標系上指兩點在縱軸上的距離與在橫軸上的距離之和，曼哈頓距離的計算方法如式（8）所示：

（8）

其中，點A坐標（xi，yi），點B坐標（xj，yj），dij表示點A和點B之間的曼哈頓距離。

2.2.2" 禁忌搜索主函數與禁忌長度

禁忌搜索中的主函數也稱為評價函數，是用來評價鄰域解優劣的衡量指標。本文研究的藥房批量取藥問題考慮藥品重量，建立以重量加權距離之和為目標函數的數學模型，因此本算法采用重量加權距離進行評價，即重量加權距離之和越小則表示解越優。

禁忌表的兩項主要指標分別為禁忌對象和禁忌長度，本算法以節點i為禁忌對象建立一維禁忌表；使用動態自適應方法設置禁忌長度，對每個節點i設置參數Fi來記錄節點i在鄰域搜索中被訪問的次數，禁忌長度的具體計算方法如式（9）所示：

（9）

其中Ti表示節點i的禁忌長度，iter表示當前迭代次數，λ表示調整參數，需根據不同算例進行調整設置。該動態自適應的方法能夠確保在鄰域搜索過程中被頻繁訪問的節點的禁忌長度更大，防止出現由于禁忌長度過長導致計算量過大運算時間慢以及禁忌長度過短導致陷入局部收斂的問題。

2.2.3" 擾動方法

在算法中加入擾動方法，即一些隨機移動和隨機搜索，可以避免算法陷入局部最優以及陷入局部最優后能夠快速跳出，同時也能增加搜索的多樣性。擾動方法需設置擾動長度和擾動次數兩個參數，在禁忌搜索的迭代過程中，當最優解未被更新的次數等于擾動長度時，觸發算法進入擾動步驟，開始進行一定次數即擾動次數的隨機搜索。

3" 仿真實驗及可視化結果

3.1" 實驗算例

基于圖1搭建的藥房模型并考慮實際取藥場景，設計三類實驗算例對模型和算法進行仿真實驗，展示可視化結果并討論路徑規劃效果，三類實驗場景分別為：

1）直線取藥，所有取藥點位于同一直線副通道上。

2）同側異路取藥，取藥點位于主干道一側且跨越多條副通道。

3）異側異路取藥，取藥點跨越主干道兩側且同時跨越多條副通道。

表3為實驗算例數據表，提供算例包含的數據信息。“序號”表示起點終點和取藥點的編號，其中序號0為起點，序號n為終點，序號1到n-1代表有n-1個取藥點，算法實現的結果使用節點序號組成的一條路徑來表示，舉例說明，若算法得出的最佳路徑表示為“0-gt;1-gt;n-1-gt;…-gt;2-gt;n”，則該條取藥線路為從起點0（X0，Y0）出發，先到達取藥點1（X1，Y1）揀取對應目標藥柜的藥品，接著去取藥點n-1（Xn-1，Yn-1）取藥，然后依次按照最佳路徑的序號次序到達對應取藥點，最后到達取藥點2（X2，Y2），取完取藥點2對應目標藥柜的藥品后，最終回到終點n（Xn，Yn）；“名稱”為藥品名稱，其中起點和終點的名稱設定為Start和End；“X坐標”和“Y坐標”表示起點終點和取藥點的位置信息，分別為坐標軸中各點的X、Y坐標，并根據X、Y坐標數據計算曼哈頓距離作為節點間的距離；“待取數量”表示藥品需要揀取的數量，其中起點和終點的數量設為0；“單位重量”表示單個藥品的重量，比如每盒重量、每瓶重量等，單位為克（g），其中起點和終點的單位重量設為0。

表3" 實驗算例數據表

序號 名稱 X坐標 Y坐標 待取數量 單位重量/ g

0 Start X0 Y0 0 0

1 Name1 X1 Y1 Q1 W1

2 Name2 X2 Y2 Q2 W2

3 Name3 X3 Y3 Q3 W3

… … … … … …

n-1 Namen-1 Xn-1 Yn-1 Qn-1 Wn-1

n End Xn Yn 0 0

3.2" 可視化結果展示及分析

仿真實驗使用JAVA語言實現，基于Windows 10操作系統、IntelliJ IDEA開發平臺，使用JavaFX實現可視化效果。對3.1中設計的三類實驗場景分別構造多組不同規模的算例，進行仿真實驗并分析實驗結果，通過可視化展示取藥路徑軌跡來驗證算法的有效性和可行性。本文分別對每類場景選取一組算例詳細分析其實驗結果。

3.2.1" 直線取藥

直線取藥場景指所有取藥點位于同一直線副通道上。表4給出直線取藥場景其中一組算例的具體數據，該算例設置了5個取藥點，取藥點的位置如圖5所示，5個取藥點均在第三條副通道上且分布在主干道兩側，其中取藥點1、取藥點2、取藥點3位于主干道左側即圖5中顯示的主干道上方，取藥點4和取藥點5位于主干道右側即圖5中顯示的主干道下方。圖5為該算例的路徑可視化結果，算法求得的最佳路徑為0→5→4→1→2→3→6，可以看出該解準確且可行。觀察和分析圖5中最優路徑軌跡可以發現，規劃出的最佳路徑優先到達取藥點4和取藥點5所在的主干道右側藥架，而且在同一藥架的取藥順序以離主干道更遠的取藥點優先，比如主干道左側藥架的取藥順序為1→2→3而主干道右側藥架的取藥順序為5→4，這是因為藥房批量取藥問題考慮了藥品的重量加權距離，而主干道右側藥架待取藥品的總重量大于左側藥架待取藥品的總重量，且先揀取遠端的藥品都能使得總的重量加權距離這一目標函數更小。

3.2.2" 同側異路取藥

同側異路取藥場景指取藥點位于主干道一側且跨越多條副通道。圖6路徑可視化結果中顯示了該算例起點終點和取藥點的位置分布，5個取藥點均在主干道右側且分布在四條不同的副通道上，其中取藥點1在第一條副通道上、取藥點2在第三條副通道上、取藥點3在第四條副通道上，取藥點4和取藥點5在第二條副通道上。算法求得的最佳路徑為0→3→2→5→4→1→6，同樣能夠發現規劃后的取藥路徑是按照不同副通道之間由遠至近、同一副通道之上先遠后近的順序。

表4" 直線取藥場景算例數據

序號 名稱 X坐標 Y坐標 待取數量 單位重量/ g

0 Start 0 6 0 0

1 999感冒靈顆粒 7 1 3 90

2 快克復方氨酚烷胺膠囊 7 3 2 100

3 川貝止咳糖漿 7 5 1 500

4 云南白藥氣霧劑 7 8 1 115

5 金嗓子喉片 7 11 5 24

6 End 0 6 0 0

圖5" 直線取藥場景算例的路徑可視化結果

圖6" 同側異路場景算例的路徑可視化結果

3.2.3" 異側異路取藥

異側異路取藥場景指取藥點跨越主干道兩側且同時跨越多條副通道。圖7為異側異路取藥場景算例的路徑可視化結果，11個取藥點的位置分布在主干道兩側和不同的副通道上，其中取藥點1和取藥點11的位置相同實則為同一取藥點，本文設定在同一副通道兩側呈水平的兩個藥柜可在同一取藥點進行取藥操作，這種設定符合實際的藥房取藥場景。算法求得的最佳路徑為0→9→10→8→7→2→6→5→4→3→1→11→gt;12，由圖7可以明顯看出該路徑合理且能夠按照路徑完成取藥任務。

圖7" 異側異路場景算例的路徑可視化結果

4" 結" 論

本文將路徑規劃算法運用到藥房取藥場景上，搭建了一個縱橫式布局的藥房環境模型，將藥房批量取藥問題轉換為一個考慮藥品重量的TSP問題，使用曼哈頓距離作為兩點之間距離，建立了一個以重量加權距離之和為目標函數的混合整數規劃模型，設計了一種改進的禁忌搜索算法方法求解該模型，最后通過三類實驗場景的仿真實驗，可視化展示并分析算法在取藥路徑上有較好的路徑規劃效果。本方法能夠有效地解決藥房批量取藥問題，可以運用到中小藥房和醫院藥房等醫療機構，但由于實際情況復雜，藥房取藥場景往往需要考慮更多現實要素，比如藥品體積、取藥的載重載容約束、以及多趟取藥問題等，另外本文的研究結果也為機器人自動取藥研究奠定了一定的基礎。基于本文后續可進行更深入和完善的研究，進一步提升現實意義。

參考文獻：

[1] 劉麗萍，韓晉，謝進，等.解放軍302醫院門診藥房自動化調劑新模式的實踐 [J].藥學服務與研究，2007（6）：468-469.

[2] 金滔，任丹媛，孫潔，等.醫院發熱門診智慧藥房的構建與應用 [J].中國藥業，2022，31（7）：14-17.

[3] 王鶴靜，王麗娜.機器人路徑規劃算法綜述 [J].桂林理工大學學報，2023，43（1）：137-147.

[4] 陳洋，林其岳，鄧志華，等.AGV路徑規劃算法研究進展 [J].機電技術，2022（5）：39-43.

[5] 陳鍵.無人快遞機器人路徑規劃算法研究綜述 [J].價值工程，2022，41（5）：166-168.

[6] 林韓熙，向丹，歐陽劍，等.移動機器人路徑規劃算法的研究綜述 [J].計算機工程與應用，2021，57（18）：38-48.

[7] 巨雨亭.車間搬運AGV系統設計與路徑規劃研究 [D].太原：中北大學，2023.

[8] 吉紅，趙忠義，王穎麗，等.復雜環境下多AGV路徑規劃與調度系統研究 [J].機械設計，2023，40（6）：110-115.

[9] 熊宇.非傳統布局倉儲系統AGV調度研究與實現 [D].南昌：南昌大學，2021.

[10] 潘成浩.倉儲物流機器人揀選路徑規劃仿真研究 [D].太原：中北大學，2017.

[11] 陳明智，錢同惠，張仕臻，等.倉儲物流機器人集群避障及協同路徑規劃方法 [J].現代電子技術，2019，42（22）：174-177+182.

[12] GLOVER F. Future paths for integer programming and links to articial intelligence [J].Computers amp; Operations Research，1986，13：533-549.

[13] CHANG W B，JI X P，XIAO Y Y，et al. Prediction of Hypertension Outcomes Based on Gain Sequence Forward Tabu Search Feature Selection and XGBoost [J].Diagnostics（Basel，Switzerland），2021，11（5）：792-792.

[14] LIU X，LIU X M，ZHANG R L，et al. Securely Computing the Manhattan Distance under the Malicious Model and its Applications [J].Applied Sciences，2022，12（22）：11705-11705.

作者簡介：邱媛（1995—），女，漢族，江蘇連云港人，助教，碩士，研究方向：車輛路徑問題、運籌優化算法、醫藥物流；龔星雨（2001—），女，漢族，上海崇明人，學士，研究方向：路徑規劃、醫學信息工程。