基于改進(jìn)禁忌搜索算法的藥房批量取藥路徑規(guī)劃研究

收稿日期：2023-08-04

基金項(xiàng)目：南京醫(yī)科大學(xué)康達(dá)學(xué)院科研發(fā)展項(xiàng)目（KD2023KYJJ025）

DOI：10.19850/j.cnki.2096-4706.2024.05.032

摘" 要：針對(duì)藥房批量取藥這一現(xiàn)實(shí)問題，在設(shè)計(jì)藥房整體環(huán)境布局和引入路徑規(guī)劃算法的基礎(chǔ)上，提出以重量加權(quán)的距離為目標(biāo)的旅行商問題TSP（Traveling Salesman Problem）。建立一個(gè)混合整數(shù)規(guī)劃模型，使用禁忌搜索算法進(jìn)行模型求解，使用曼哈頓距離作為兩點(diǎn)之間距離，在禁忌長(zhǎng)度等參數(shù)設(shè)置上使用動(dòng)態(tài)自適應(yīng)方法，并在算法中加入擾動(dòng)方法，避免算法陷入局部最優(yōu)，增加搜索目標(biāo)的多樣性。最后使用JAVA進(jìn)行了仿真模擬實(shí)驗(yàn)，可視化結(jié)果驗(yàn)證了算法的可行性和有效性。

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

中圖分類號(hào)：TP18;R95" " 文獻(xiàn)標(biāo)識(shí)碼：A" 文章編號(hào)：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" 引" 言

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

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

1.1" 藥房環(huán)境建模

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

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

圖1" 藥房環(huán)境模型示意圖

在藥房模型的基礎(chǔ)上對(duì)取藥過程做如下設(shè)定：

1）取藥過程中固定起點(diǎn)與終點(diǎn)，且起點(diǎn)和終點(diǎn)是同一個(gè)，一次完整的取藥過程需要從起點(diǎn)出發(fā)并最終返回起點(diǎn)。

2）取藥方式默認(rèn)單側(cè)僅可取該側(cè)藥品且只能在目標(biāo)藥柜正對(duì)面的取藥點(diǎn)取藥。

3）取藥時(shí)在藥房通道內(nèi)只能進(jìn)行直角轉(zhuǎn)向。

4）每次取藥可取多種藥品，且每種藥品數(shù)量確定，即在一次取藥過程中取完所有種類藥品的對(duì)應(yīng)數(shù)量后再返回起點(diǎn)。

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

1.2" 混合整數(shù)規(guī)劃模型

數(shù)學(xué)模型定義在一個(gè)有向圖G = （V，E），其中V = {0，1，2，…，n}是節(jié)點(diǎn)集合，包括起點(diǎn){0}、終點(diǎn){n}和取藥點(diǎn)集合A，E表示兩兩節(jié)點(diǎn)間可能的有向邊的集合。現(xiàn)要為每次取藥過程規(guī)劃出一條取藥路徑，目標(biāo)是使重量加權(quán)距離之和最小。

圖2" 取藥過程流程圖

1.2.1" 模型參數(shù)

表1定義了數(shù)學(xué)模型的參數(shù)及參數(shù)對(duì)應(yīng)的含義。

表1" 模型參數(shù)及含義

符號(hào) 含義

G = （V，E） 有向圖，其中V是節(jié)點(diǎn)集合，E是邊集合

0 起點(diǎn)

n 終點(diǎn)

A 取藥點(diǎn)集合，A ? V

dij 節(jié)點(diǎn)i，j間的距離，i，j ∈ V

qi 節(jié)點(diǎn)i的待取數(shù)量，i ∈ V，其中起點(diǎn)和終點(diǎn)的數(shù)量設(shè)為0

wi 節(jié)點(diǎn)i的單位重量，i ∈ V，其中起點(diǎn)和終點(diǎn)的單位重量設(shè)為0

M 一個(gè)大數(shù)

1.2.2" 模型決策變量

數(shù)學(xué)模型的決策變量有Xij、Yi，各變量對(duì)應(yīng)的含義如表2所示。

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

決策變量 含義

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

Yi 到達(dá)節(jié)點(diǎn)i時(shí)已取藥品的總重量（不包括節(jié)點(diǎn)i處的藥品重量）

1.2.3" 數(shù)學(xué)模型

建立如式（1）至式（7）所示的混合整數(shù)規(guī)劃模型：

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

s.t." " " "（2）

（3）

（4）

（5）

（6）

（7）

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

2" 改進(jìn)禁忌搜索算法的設(shè)計(jì)

2.1" 算法框架

禁忌搜索算法由美國(guó)科羅拉多大學(xué)教授Glover[12]提出，是一種全局搜索尋優(yōu)算法，具有全局逐步尋優(yōu)的能力，是局部搜索算法的優(yōu)化與發(fā)展[13]。本文使用一種改進(jìn)的禁忌搜索算法求解模型，基于傳統(tǒng)的禁忌搜索算法，使用曼哈頓距離作為兩點(diǎn)之間距離，在禁忌長(zhǎng)度等參數(shù)設(shè)置上使用動(dòng)態(tài)自適應(yīng)方法，并在算法中加入擾動(dòng)方法，避免算法陷入局部收斂，增加搜索多樣性。

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

1）初始化算法的各項(xiàng)參數(shù)，包括禁忌表、禁忌長(zhǎng)度、迭代次數(shù)等，計(jì)算曼哈頓距離作為兩點(diǎn)之間距離，隨機(jī)生成一個(gè)初始可行解，從初始解出發(fā)進(jìn)行鄰域搜索。

2）以當(dāng)前解為一次迭代的起點(diǎn)進(jìn)行鄰域搜索，每次鄰域搜索產(chǎn)生許多候選解，將不在禁忌表中的最優(yōu)候選解記為本次鄰域最優(yōu)解。

3）將本次鄰域最優(yōu)解與全局最優(yōu)解進(jìn)行比較，若優(yōu)于全局最優(yōu)解則將全局最優(yōu)解替換。然后進(jìn)行擾動(dòng)操作，隨機(jī)選擇鄰域解以跳出局部最優(yōu)，同時(shí)更新禁忌表和禁忌長(zhǎng)度，即如果禁忌表中存放的解的禁忌次數(shù)達(dá)到禁忌長(zhǎng)度，那么將這些解從禁忌表中解禁退出。

4）若達(dá)到算法終止條件，即迭代次數(shù)達(dá)最大迭代次數(shù)，則算法停止，輸出最優(yōu)解，否則回到Step2繼續(xù)進(jìn)行新一輪的鄰域搜索。

2.2" 算法核心模塊設(shè)計(jì)

2.2.1" 計(jì)算兩點(diǎn)之間的距離——曼哈頓距離

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

圖3" 算法流程圖

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

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

（8）

其中，點(diǎn)A坐標(biāo)（xi，yi），點(diǎn)B坐標(biāo)（xj，yj），dij表示點(diǎn)A和點(diǎn)B之間的曼哈頓距離。

2.2.2" 禁忌搜索主函數(shù)與禁忌長(zhǎng)度

禁忌搜索中的主函數(shù)也稱為評(píng)價(jià)函數(shù)，是用來(lái)評(píng)價(jià)鄰域解優(yōu)劣的衡量指標(biāo)。本文研究的藥房批量取藥問題考慮藥品重量，建立以重量加權(quán)距離之和為目標(biāo)函數(shù)的數(shù)學(xué)模型，因此本算法采用重量加權(quán)距離進(jìn)行評(píng)價(jià)，即重量加權(quán)距離之和越小則表示解越優(yōu)。

禁忌表的兩項(xiàng)主要指標(biāo)分別為禁忌對(duì)象和禁忌長(zhǎng)度，本算法以節(jié)點(diǎn)i為禁忌對(duì)象建立一維禁忌表；使用動(dòng)態(tài)自適應(yīng)方法設(shè)置禁忌長(zhǎng)度，對(duì)每個(gè)節(jié)點(diǎn)i設(shè)置參數(shù)Fi來(lái)記錄節(jié)點(diǎn)i在鄰域搜索中被訪問的次數(shù)，禁忌長(zhǎng)度的具體計(jì)算方法如式（9）所示：

（9）

其中Ti表示節(jié)點(diǎn)i的禁忌長(zhǎng)度，iter表示當(dāng)前迭代次數(shù)，λ表示調(diào)整參數(shù)，需根據(jù)不同算例進(jìn)行調(diào)整設(shè)置。該動(dòng)態(tài)自適應(yīng)的方法能夠確保在鄰域搜索過程中被頻繁訪問的節(jié)點(diǎn)的禁忌長(zhǎng)度更大，防止出現(xiàn)由于禁忌長(zhǎng)度過長(zhǎng)導(dǎo)致計(jì)算量過大運(yùn)算時(shí)間慢以及禁忌長(zhǎng)度過短導(dǎo)致陷入局部收斂的問題。

2.2.3" 擾動(dòng)方法

在算法中加入擾動(dòng)方法，即一些隨機(jī)移動(dòng)和隨機(jī)搜索，可以避免算法陷入局部最優(yōu)以及陷入局部最優(yōu)后能夠快速跳出，同時(shí)也能增加搜索的多樣性。擾動(dòng)方法需設(shè)置擾動(dòng)長(zhǎng)度和擾動(dòng)次數(shù)兩個(gè)參數(shù)，在禁忌搜索的迭代過程中，當(dāng)最優(yōu)解未被更新的次數(shù)等于擾動(dòng)長(zhǎng)度時(shí)，觸發(fā)算法進(jìn)入擾動(dòng)步驟，開始進(jìn)行一定次數(shù)即擾動(dòng)次數(shù)的隨機(jī)搜索。

3" 仿真實(shí)驗(yàn)及可視化結(jié)果

3.1" 實(shí)驗(yàn)算例

基于圖1搭建的藥房模型并考慮實(shí)際取藥場(chǎng)景，設(shè)計(jì)三類實(shí)驗(yàn)算例對(duì)模型和算法進(jìn)行仿真實(shí)驗(yàn)，展示可視化結(jié)果并討論路徑規(guī)劃效果，三類實(shí)驗(yàn)場(chǎng)景分別為：

1）直線取藥，所有取藥點(diǎn)位于同一直線副通道上。

2）同側(cè)異路取藥，取藥點(diǎn)位于主干道一側(cè)且跨越多條副通道。

3）異側(cè)異路取藥，取藥點(diǎn)跨越主干道兩側(cè)且同時(shí)跨越多條副通道。

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

表3" 實(shí)驗(yàn)算例數(shù)據(jù)表

序號(hào) 名稱 X坐標(biāo) Y坐標(biāo) 待取數(shù)量 單位重量/ 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" 可視化結(jié)果展示及分析

仿真實(shí)驗(yàn)使用JAVA語(yǔ)言實(shí)現(xiàn)，基于Windows 10操作系統(tǒng)、IntelliJ IDEA開發(fā)平臺(tái)，使用JavaFX實(shí)現(xiàn)可視化效果。對(duì)3.1中設(shè)計(jì)的三類實(shí)驗(yàn)場(chǎng)景分別構(gòu)造多組不同規(guī)模的算例，進(jìn)行仿真實(shí)驗(yàn)并分析實(shí)驗(yàn)結(jié)果，通過可視化展示取藥路徑軌跡來(lái)驗(yàn)證算法的有效性和可行性。本文分別對(duì)每類場(chǎng)景選取一組算例詳細(xì)分析其實(shí)驗(yàn)結(jié)果。

3.2.1" 直線取藥

直線取藥場(chǎng)景指所有取藥點(diǎn)位于同一直線副通道上。表4給出直線取藥場(chǎng)景其中一組算例的具體數(shù)據(jù)，該算例設(shè)置了5個(gè)取藥點(diǎn)，取藥點(diǎn)的位置如圖5所示，5個(gè)取藥點(diǎn)均在第三條副通道上且分布在主干道兩側(cè)，其中取藥點(diǎn)1、取藥點(diǎn)2、取藥點(diǎn)3位于主干道左側(cè)即圖5中顯示的主干道上方，取藥點(diǎn)4和取藥點(diǎn)5位于主干道右側(cè)即圖5中顯示的主干道下方。圖5為該算例的路徑可視化結(jié)果，算法求得的最佳路徑為0→5→4→1→2→3→6，可以看出該解準(zhǔn)確且可行。觀察和分析圖5中最優(yōu)路徑軌跡可以發(fā)現(xiàn)，規(guī)劃出的最佳路徑優(yōu)先到達(dá)取藥點(diǎn)4和取藥點(diǎn)5所在的主干道右側(cè)藥架，而且在同一藥架的取藥順序以離主干道更遠(yuǎn)的取藥點(diǎn)優(yōu)先，比如主干道左側(cè)藥架的取藥順序?yàn)?→2→3而主干道右側(cè)藥架的取藥順序?yàn)?→4，這是因?yàn)樗幏颗咳∷巻栴}考慮了藥品的重量加權(quán)距離，而主干道右側(cè)藥架待取藥品的總重量大于左側(cè)藥架待取藥品的總重量，且先揀取遠(yuǎn)端的藥品都能使得總的重量加權(quán)距離這一目標(biāo)函數(shù)更小。

3.2.2" 同側(cè)異路取藥

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

表4" 直線取藥場(chǎng)景算例數(shù)據(jù)

序號(hào) 名稱 X坐標(biāo) Y坐標(biāo) 待取數(shù)量 單位重量/ g

0 Start 0 6 0 0

1 999感冒靈顆粒 7 1 3 90

2 快克復(fù)方氨酚烷胺膠囊 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" 直線取藥場(chǎng)景算例的路徑可視化結(jié)果

圖6" 同側(cè)異路場(chǎng)景算例的路徑可視化結(jié)果

3.2.3" 異側(cè)異路取藥

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

圖7" 異側(cè)異路場(chǎng)景算例的路徑可視化結(jié)果

4" 結(jié)" 論

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

參考文獻(xiàn)：

[1] 劉麗萍，韓晉，謝進(jìn)，等.解放軍302醫(yī)院門診藥房自動(dòng)化調(diào)劑新模式的實(shí)踐 [J].藥學(xué)服務(wù)與研究，2007（6）：468-469.

[2] 金滔，任丹媛，孫潔，等.醫(yī)院發(fā)熱門診智慧藥房的構(gòu)建與應(yīng)用 [J].中國(guó)藥業(yè)，2022，31（7）：14-17.

[3] 王鶴靜，王麗娜.機(jī)器人路徑規(guī)劃算法綜述 [J].桂林理工大學(xué)學(xué)報(bào)，2023，43（1）：137-147.

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

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

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

[7] 巨雨亭.車間搬運(yùn)AGV系統(tǒng)設(shè)計(jì)與路徑規(guī)劃研究 [D].太原：中北大學(xué)，2023.

[8] 吉紅，趙忠義，王穎麗，等.復(fù)雜環(huán)境下多AGV路徑規(guī)劃與調(diào)度系統(tǒng)研究 [J].機(jī)械設(shè)計(jì)，2023，40（6）：110-115.

[9] 熊宇.非傳統(tǒng)布局倉(cāng)儲(chǔ)系統(tǒng)AGV調(diào)度研究與實(shí)現(xiàn) [D].南昌：南昌大學(xué)，2021.

[10] 潘成浩.倉(cāng)儲(chǔ)物流機(jī)器人揀選路徑規(guī)劃仿真研究 [D].太原：中北大學(xué)，2017.

[11] 陳明智，錢同惠，張仕臻，等.倉(cāng)儲(chǔ)物流機(jī)器人集群避障及協(xié)同路徑規(guī)劃方法 [J].現(xiàn)代電子技術(shù)，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.

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