基于改進Dijkstra算法的醫(yī)藥物流配送網(wǎng)絡優(yōu)化

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

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

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

Key words： Dijkstra algorithm;pharmaceutical logistics;path planning

中圖分類號：F274? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標識碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號：1006-4311（2019）21-0121-02

0? 引言

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

1? Dijkstra算法的改進

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

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

1.2 改進的Dijkstra算法的設計

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

①初始化。節(jié)點的標記為Vj，且起點V0=0。

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

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

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

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

2? 改進的Dijkstra算法的應用

2.1 問題描述

成都市人口眾多，醫(yī)藥衛(wèi)生藥品的需求巨大。醫(yī)藥冷鏈運輸應用廣泛，為響應節(jié)能環(huán)保的號召，采用新能源汽車——純電力冷藏車運輸藥品，其運輸成本與運輸時間成正相關關系。因此采用改進后的Dijkstra算法根據(jù)節(jié)點間的時間權值求得最短時間路徑在醫(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é)點具有一定的代表性。

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

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

2.2 結果及分析

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

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

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

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

3? 結論

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

參考文獻：

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

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

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

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

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