基于改進Dijkstra算法的醫藥物流配送網絡優化

羅威 張曉蓉 張甜

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

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算法;醫藥物流;路徑規劃

Key words： Dijkstra algorithm;pharmaceutical logistics;path planning

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

0? 引言

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

1? Dijkstra算法的改進

1.1 傳統Dijkstra算法的思路

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

1.2 改進的Dijkstra算法的設計

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

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

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

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

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

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

2? 改進的Dijkstra算法的應用

2.1 問題描述

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

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

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

2.2 結果及分析

利用物流節點間的時間權值，在Matlab軟件環境下運行程序得出配送路線為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。

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

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

3? 結論

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

參考文獻：

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

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

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

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

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