曹 巖，馬 健

(亳州職業(yè)技術(shù)學(xué)院 信息工程系,安徽 亳州 236800)

0 前 言

近年來，人們對(duì)中藥的需求不斷增加。公立醫(yī)院、民企醫(yī)療機(jī)構(gòu)和連鎖藥店的規(guī)模不斷擴(kuò)大。亳州作為中國(guó)四大藥都之一，具有深遠(yuǎn)的中藥材文化和中醫(yī)文化，中藥飲片企業(yè)和中藥生產(chǎn)企業(yè)已超過100家。中藥作為一種特殊的商品，與人的生活密切相關(guān)，它的使用應(yīng)嚴(yán)格按照醫(yī)生的建議，有時(shí)微小的錯(cuò)誤都將不可避免地影響到人的健康，甚至?xí)绊懙缴踩?。由于藥物本身的特殊性使藥品流通過程變得復(fù)雜，容易導(dǎo)致資源的浪費(fèi)和一些不良的社會(huì)影響。在保障中藥的質(zhì)量和供應(yīng)及減少醫(yī)療機(jī)構(gòu)的中藥的庫(kù)存積壓,中藥配送起到了至關(guān)重要的作用[1]。利用Bellman-Ford算法分析亳州地區(qū)中藥配送路徑，可以解決中藥配送的時(shí)間和減少配送的成本，提高中藥送達(dá)到醫(yī)療機(jī)構(gòu)的效率，從而促進(jìn)社會(huì)的發(fā)展。

1 亳州地區(qū)中藥配送問題

在國(guó)家政策方針的指導(dǎo)下，亳州市3縣1區(qū)大力建設(shè)各級(jí)各類醫(yī)院和社區(qū)衛(wèi)生服務(wù)機(jī)構(gòu)。目前，亳州市共有各級(jí)各類醫(yī)療機(jī)構(gòu)1 510家，包括醫(yī)院46家、衛(wèi)生院94家、社區(qū)衛(wèi)生服務(wù)中心(站)98家、村衛(wèi)生室1 267家、婦幼保健院(所)5家。其中，中心城區(qū)共有各級(jí)各類醫(yī)院20家，社區(qū)衛(wèi)生服務(wù)中心3家。這些與快速增長(zhǎng)的人口數(shù)量、日益增長(zhǎng)的群眾需求相比，仍然存在一定差距。所以，亳州市衛(wèi)計(jì)委在2020-2030年規(guī)劃中會(huì)繼續(xù)增加醫(yī)療機(jī)構(gòu)。

基層醫(yī)療機(jī)構(gòu)存在“小、散、多”的現(xiàn)象，對(duì)中藥的需求量也較少[2]。中藥配送企業(yè)要按時(shí)完成中藥配送任務(wù)，同時(shí)要考慮到中藥配送的成本，要合理規(guī)劃配送路徑，提高企業(yè)的利潤(rùn)。針對(duì)亳州3縣1區(qū)的醫(yī)療機(jī)構(gòu)分布情況和中藥需求情況，利用改進(jìn)的Bellman-Ford算法計(jì)算中藥配送最優(yōu)路徑，完成企業(yè)對(duì)中藥的配送任務(wù)。

2 Bellman-Ford算法分析

Bellman-Ford算法是對(duì)所有的邊進(jìn)行V輪降距操作，不再對(duì)所有節(jié)點(diǎn)劃分為2個(gè)集合S和V-S。該算法由美國(guó)數(shù)學(xué)家查德·貝爾曼和小萊斯特·福特發(fā)明[3]。

對(duì)于1個(gè)有向圖G(V，E),是由從1，2，…，n個(gè)點(diǎn)、m條表組成，其中設(shè)定1位起始點(diǎn)，w(i,j)位有向邊(i,j)的權(quán)，dk(i)為點(diǎn)i在第k次迭代后i點(diǎn)的距離標(biāo)號(hào)，那么Bellman-Ford算法步驟如下。

步驟1：將Ak作為k-1輪迭代中距離標(biāo)號(hào)減少的點(diǎn)的集合。

步驟2：初始化，將d0(1)=0,d0(i)=+∞, (2≤i≤n)， 將所有點(diǎn)存放到集合Ak中。

步驟3：對(duì)于任意點(diǎn)i(1≤i≤n)， 令dk(i)=dk-1(i)。

步驟5：執(zhí)行到集合Ak+1=?，則算法終止，那么d(i)就是最短距離；如果Ak+1≠?時(shí)，并且k=n-1時(shí)，可以得知負(fù)循環(huán)，算法終止；如果Ak+1≠?時(shí)，k

步驟6：將k=k+1，轉(zhuǎn)到步驟2，繼續(xù)執(zhí)行。

算法的偽代碼如下：

Bellman-Ford-SHORTEST-PATHS-II(G,S)

(1)d[s] ←0

Statistical downscaling forecast and reconstruction of spatial and temporal correlation of the precipitation

(2)for v∈V-{s} do d[v] ←∞

(3)for i←1 to V-1 do

(4) for edge(u，v)∈E do

(5) if d[v]> d[u]+w(u，v)then d[v]←d[u] +w(u，v)

算法的第1行將源點(diǎn)的距離設(shè)置為0，第2行將其他所有節(jié)點(diǎn)到源點(diǎn)的距離設(shè)置為無窮。從第3行開始，對(duì)圖中所有的邊進(jìn)行V輪降距操作[4]。第4行的內(nèi)循環(huán)依次對(duì)每條邊進(jìn)行考察，并根據(jù)情況進(jìn)行降距操作。第5行為實(shí)際的降距操作。

3 改進(jìn)的Bellman-Ford算法

Bellman-Ford算法在計(jì)算最短路徑優(yōu)化過程中具有很好的效率，但還存在不足，在計(jì)算距離數(shù)目上最多有n2個(gè)，而且還增加了算法的存儲(chǔ)空間[5]。本文提出了對(duì)Bellman-Ford算法的改進(jìn)，能有效地解決此問題[6]。改進(jìn)的Bellman-Ford算法執(zhí)行步驟如下。

步驟1：首先初始化，將d(1)=0,d(i)=+∞，(2≤i≤n)， 把所有點(diǎn)存放到A中。

步驟3：算法在執(zhí)行到偶數(shù)次迭代中，當(dāng)集合A=?時(shí)，算法停止，即可得到最短距離；當(dāng)A≠?，t=n-1時(shí)，可以得知負(fù)循環(huán)，算法停止；當(dāng)集合A≠?，k

步驟4：對(duì)于點(diǎn)i(1≤i≤n)， 當(dāng)d0(i)=d(i)，t=t+1， 算法直接轉(zhuǎn)到步驟2。

Bellman-Ford算法雖然可以應(yīng)對(duì)負(fù)權(quán)重，但是不能求解有負(fù)循環(huán)的所有最短路徑。如果負(fù)循環(huán)存在，在部分節(jié)點(diǎn)之間可能不存在最短路徑。如圖1所示，節(jié)點(diǎn)u，v之間因有1個(gè)負(fù)環(huán)路，所以不存在任何最短路徑。

圖1 負(fù)環(huán)路的u到v節(jié)點(diǎn)不存在最短路徑

根據(jù)圖1對(duì)Bellman-Ford算法進(jìn)行改進(jìn)，通過對(duì)v-1條輪降距操作，可以找出所有路徑，為了驗(yàn)證是否存在負(fù)環(huán)路，對(duì)Bellman-Ford算法結(jié)束后在增加一輪降距檢查，如果有d[v]>d[u]+w(u，v)的情況出現(xiàn)，則負(fù)循環(huán)存在。

改進(jìn)的Bellman-Ford算法的偽代碼如下：

Bellman-Ford-SHORTEST-PATHS-II(G,S)

(1)d[s]←0

(2)for v∈V-{s} do d[v]←∞

(3)for i←1 to V-1 do

(4) for edge (u，v)∈E do

(5) if d[v]> d[u]+w(u，v)then d[v]←d[u] +w(u，v)

(6)for edge (u，v)∈E do

(7) if d[v]> d[u] +w(u，v) then 報(bào)告負(fù)環(huán)路存在

4 改進(jìn)算法在中藥配送路徑中仿真分析

本文以亳州地區(qū)中藥連鎖店為例，首先算法開始選擇倉(cāng)庫(kù)作為配送路徑的出發(fā)點(diǎn)，分別將中藥配送到亳州市的3縣1區(qū)共4個(gè)地區(qū)，根據(jù)改進(jìn)的算法對(duì)其他節(jié)點(diǎn)的距離進(jìn)行初始化，并將幾個(gè)地點(diǎn)區(qū)域分別用字母表示(表1)。

表1 亳州三縣一區(qū)地點(diǎn)

根據(jù)改進(jìn)的Bellman-Ford算法對(duì)幾個(gè)地區(qū)的中藥配送路徑進(jìn)行選擇，找到最佳的路徑。改進(jìn)算法中的(3)是Bellman-Ford算法的核心，一共執(zhí)行了v-1次。算法第4行的內(nèi)循環(huán)依次對(duì)每條邊進(jìn)行考慮，并進(jìn)行相應(yīng)的降距操作。邊被考慮的次序是任意的，首先考慮的邊是{B，E}，由于B的距離是∞，E的距離也是∞，而w(B,E)=2,2+∞=∞，因此E的距離維持為∞。同理，第2條邊{D,B}也是同樣的結(jié)果。第3條邊是{B,D}，由于B的距離是無窮的，所以D的距離維持不變。第4條邊是{A,B}， 由于d[A]=0,d[B]=∞，w(A,B)=-1, 而0+(-1)=-1<∞， 因此， 將節(jié)點(diǎn)B的距離降低到-1， 即d[B]=-1。第5條邊是{A,C}，由于d[C]=∞,d[A]=0,w(A,C)=4, 而0+(4)=4<∞， 所以，調(diào)整d[C]=4。第6條邊是{D,C}，由于d[C]=4，d[D]=∞，w(D,C)=5， 而5+∞=∞>4，因此，d[C]的值維持不變。第7條邊是{B,C}， 由于d[C]=4，d[B]=-1，w(B,C)=3，而-1+3=2<4，因此，調(diào)整d[C]=2。第8條邊是{E,D}，由于d[D]=∞，d[E]=∞，w(E,D)=-3，而-3+∞=∞，因此，d[D]的值保持不變。所有的邊都考察了一次。第1輪循環(huán)結(jié)束。按照前面的順序繼續(xù)第2輪考察，再進(jìn)行第3輪和第4輪循環(huán)，節(jié)點(diǎn)的距離沒有發(fā)生任何改變，最終找到最短距離(圖2)。

圖2 最佳路徑選擇

5 結(jié)論與討論

中藥配送是藥品服務(wù)行業(yè)中必不可缺少的一部分，有助于改善整體藥品供應(yīng)鏈的運(yùn)行。本文對(duì)傳統(tǒng)的Bellman-Ford算法進(jìn)行了改進(jìn)。仿真結(jié)果表明，改進(jìn)的Bellman-Ford算法可以減少算法的存儲(chǔ)空間，優(yōu)化中藥配送路徑，從而降低配送成本，提高中藥企業(yè)的利潤(rùn)。