羅威 張曉蓉 張?zhí)?/p>

摘要：配送是醫(yī)藥物流的重要環(huán)節(jié)，時效性是衡量醫(yī)藥物流配送質(zhì)量的一個重要標(biāo)準(zhǔn)。省時、省力的配送路徑規(guī)劃對提高醫(yī)藥物流配送時效性問題具有決定性作用。本文應(yīng)用改進(jìn)Dijkstra算法使其能遍歷所有節(jié)點(diǎn)，并運(yùn)用Matlab軟件解決算法時間復(fù)雜度問題，在計算方法和搜索效率兩個方面提高醫(yī)藥物流運(yùn)作效率，以成都市醫(yī)藥物流配送案例加以論證和分析。改進(jìn)后的Dijkstra算法將能運(yùn)用于更多領(lǐng)域的配送路徑規(guī)劃問題的解決。

Abstract： Distribution is an important part of pharmaceutical logistics. Timeliness is an important criterion for measuring the quality of pharmaceutical logistics distribution. Time-saving and labor-saving distribution route planning plays a decisive role in improving the timeliness of pharmaceutical logistics distribution. In this paper， the improved Dijkstra algorithm is used to traverse all nodes， and Matlab software is used to solve the problem of time complexity of the algorithm. The efficiency of medical logistics operation is improved in both computational methods and search efficiency. The case of Chengdu pharmaceutical logistics distribution is demonstrated and analyzed. The improved Dijkstra algorithm will be applied to the solution of distribution path planning problems in more fields.

關(guān)鍵詞：Dijkstra算法;醫(yī)藥物流;路徑規(guī)劃

Key words： Dijkstra algorithm;pharmaceutical logistics;path planning

中圖分類號：F274? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號：1006-4311（2019）21-0121-02

0? 引言

據(jù)相關(guān)數(shù)據(jù)顯示，2017年我國人均衛(wèi)生費(fèi)用3712.2元并呈上升趨勢。人民對健康生活的需求極大促進(jìn)了醫(yī)藥行業(yè)的發(fā)展，但物流配送的時效性仍制約著行業(yè)更進(jìn)一步。醫(yī)藥物流路徑規(guī)劃優(yōu)化標(biāo)準(zhǔn)主要有最短距離、最少配送時間及最低配送費(fèi)用等[1]。因此Dijkstra算法及其改進(jìn)算法在醫(yī)藥物流配送路徑規(guī)劃的應(yīng)用中凸顯其重要性[2]。本文改進(jìn) Dijkstra 算法使得其遍歷所有節(jié)點(diǎn)[3]并以成都市醫(yī)藥物流配送案例加以論證，最終利用Matlab軟件求解。

1? Dijkstra算法的改進(jìn)

1.1 傳統(tǒng)Dijkstra算法的思路

Dijkstra算法是單源點(diǎn)的最短路徑算法，其主要特點(diǎn)是以原點(diǎn)為中心向外逐步擴(kuò)展，每次取最小距離直到擴(kuò)展到終點(diǎn)找出最短距離位置[4]。它局限于一個節(jié)點(diǎn)到其余某一個點(diǎn)的最短路徑，無法完成到多個點(diǎn)甚至遍歷整個網(wǎng)絡(luò)結(jié)構(gòu)結(jié)點(diǎn)的求解。

1.2 改進(jìn)的Dijkstra算法的設(shè)計

本文對Dijkstra算法進(jìn)行改進(jìn)設(shè)計時，解決了傳統(tǒng)Dijkstra算法無法遍歷所有節(jié)點(diǎn)的問題，并借助Matlab軟件解決了算法的時間復(fù)雜度問題，主要從計算方法和搜索效率兩個方面求解多節(jié)點(diǎn)配送的最短路徑。具體算法步驟如圖1。

①初始化。節(jié)點(diǎn)的標(biāo)記為Vj，且起點(diǎn)V0=0。

②輸入配送需求的醫(yī)藥物流節(jié)點(diǎn)，檢測節(jié)點(diǎn)數(shù)量并判斷已保存結(jié)果路線中是否包含輸入節(jié)點(diǎn)，且在線路中是否連續(xù)。如果已保存線路中包含輸入節(jié)點(diǎn)，且在線路中連續(xù)，輸出結(jié)果;否則，執(zhí)行下一步。

③運(yùn)算Dijkstra算法計算當(dāng)前節(jié)點(diǎn)到未計算節(jié)點(diǎn)時間權(quán)值，并取其最小值dijst（i），則最小總時間Dj=Dj+dijst（i），判斷是否經(jīng)過所有節(jié)點(diǎn)，如果沒有，循環(huán)執(zhí)行本步驟直至遍歷所有節(jié)點(diǎn)，得到最短時間D1=Dj+Dj0（Dj0為返程最短時間）及路線[5]。

④判斷節(jié)點(diǎn)數(shù)量是否大于2，如果是，則初始化數(shù)據(jù)，令Vj=V0，n=0逆向按照改進(jìn)后的Dijkstra算法循環(huán)運(yùn)算路線時間，得到逆向最短時間D2=Dj+Dj0及路線。

⑤判斷并取值min（D1，D2）輸出最終最短時間D及路線，保存路線以便下次訪問。

2? 改進(jìn)的Dijkstra算法的應(yīng)用

2.1 問題描述

成都市人口眾多，醫(yī)藥衛(wèi)生藥品的需求巨大。醫(yī)藥冷鏈運(yùn)輸應(yīng)用廣泛，為響應(yīng)節(jié)能環(huán)保的號召，采用新能源汽車——純電力冷藏車運(yùn)輸藥品，其運(yùn)輸成本與運(yùn)輸時間成正相關(guān)關(guān)系。因此采用改進(jìn)后的Dijkstra算法根據(jù)節(jié)點(diǎn)間的時間權(quán)值求得最短時間路徑在醫(yī)藥物流配送路徑選擇具有重大意義。本案例選取國控四川醫(yī)藥物流中心（V0）及8個周邊區(qū)縣級人民醫(yī)院（雙流區(qū)第一人民醫(yī)院、天府新區(qū)人民醫(yī)院、龍泉驛區(qū)第一人民醫(yī)院、青羊區(qū)人民醫(yī)院、錦江區(qū)人民醫(yī)院、新都區(qū)人民醫(yī)院、青白江區(qū)人民醫(yī)院、郫都區(qū)人民醫(yī)院，分別記為Vj，j=1，2，…，8）作為醫(yī)藥物流配送節(jié)點(diǎn)具有一定的代表性。

假定路面暢通，車速一定，且無天氣等不可抗力因素影響的前提條件下，由國控四川醫(yī)藥物流中心使用純電力冷藏車向8個區(qū)縣級人民醫(yī)院配送同種藥物。

利用ArcGIS軟件得出醫(yī)藥物流配送節(jié)點(diǎn)交通道路電子地圖（如圖2），其次利用Dijkstra算法和百度地圖得出任意兩個節(jié)點(diǎn)間的最短時間權(quán)值（如表1）。

2.2 結(jié)果及分析

利用物流節(jié)點(diǎn)間的時間權(quán)值，在Matlab軟件環(huán)境下運(yùn)行程序得出配送路線為D1：V0→V8→V6→V7→V5→V4→V2→V1→V3→V0，總運(yùn)輸時間為413min。

將V3作為第一個配送點(diǎn)，逆向運(yùn)行程序得到D2：V0→V3→V5→V4→V6→V7→V8→V1→V2→V0，總運(yùn)輸時間為411min。

所以最終線路為國控四川醫(yī)藥物流中心→龍泉驛區(qū)第一人民醫(yī)院→錦江區(qū)人民醫(yī)院→青羊區(qū)人民醫(yī)院→新都區(qū)人民醫(yī)院→青白江區(qū)人民醫(yī)院→郫都區(qū)人民醫(yī)院→雙流區(qū)第一人民醫(yī)院→天府新區(qū)人民醫(yī)院→國控四川醫(yī)藥物流中心（如圖3）。

圖中路線雖然有閉環(huán)回路，造成配送里程加長，但本文著重于運(yùn)輸時間的最短化，且運(yùn)輸成本與運(yùn)輸時間呈正相關(guān)關(guān)系，所以運(yùn)輸成本減少，為醫(yī)藥物流企業(yè)盈利提供一定的指導(dǎo)意義。同時，采用純電動冷藏車配送藥品契合可持續(xù)發(fā)展的目標(biāo)。

3? 結(jié)論

本文在以規(guī)劃醫(yī)藥物流配送路徑為目的，在處理多節(jié)點(diǎn)問題中提出了新的解決途徑，即運(yùn)用任意物流節(jié)點(diǎn)間的運(yùn)輸時間權(quán)值，在Matlab軟件環(huán)境下運(yùn)行程序以改進(jìn)后的Dijkstra算法得出最短運(yùn)輸時間及運(yùn)輸路線，以達(dá)到減少運(yùn)輸成本，提高物流活動效率的目的。同時運(yùn)用純電力冷藏車配送符合綠色物流和可持續(xù)發(fā)展的要求，兼具經(jīng)濟(jì)效益和社會生態(tài)效益。

參考文獻(xiàn)：

[1]蘇永云，晏克非，黃翔，等.車輛導(dǎo)航系統(tǒng)的動態(tài)最優(yōu)路徑搜索方法研究[J].系統(tǒng)工程，2000，18（4）：32-37.

[2]彭定旭，冀肖榆.Dijkstra算法的java實(shí)現(xiàn)方式及優(yōu)化[J].黑龍江科技信息，2017（4）：166-167.

[3]韓海玲.基于城市路網(wǎng)的最短路徑算法研究與應(yīng)用[D].山西：中北大學(xué)，2017.

[4]石曉達(dá)，孫連英，葛娜.應(yīng)急資源配送中Dijkstra改進(jìn)算法的研究[J].北京聯(lián)合大學(xué)學(xué)報，2018，32（4）：61-66.

[5]李擎，宋頂立，張雙江，等.兩種改進(jìn)的最優(yōu)路徑規(guī)劃算法[J].北京科技大學(xué)學(xué)報，2005，27（3）：367-370.