基于Dijkstra和GIS的湖南省應急物流模型研究

謝金龍，武獻宇

（湖南現代物流職業技術學院，湖南 長沙 410001）

應急物流是以提供突發性自然災害、突發性公共衛生事件、戰爭等所需應急物資為目的，以追求時間效益最大化和損失最小化為目標的一種特殊的物流活動[1]。因此，應急物流以追求時間效益最大化和災害損失最小化為目標，具有突發性、不確定性、非常規性、弱經濟性等突出特點。

為了保證應急物資的調運、縮短配送時間、滿足應急物資調運的時效性需求，應急物資調運信息系統具有重要的研究價值。目前對應急物資調運信息系統的研究工作大致可以分為兩大類：（1）利用定性分析方法，研究應急物資調運信息系統構建的相關理論、系統概念模型的結構和功能模塊分析，以及數據倉庫、GIS等信息技術在應急物流信息系統中的應用等；（2）采用定量分析方法，通過數學模型分析，研究應急物資調運信息系統中的路徑優化、物資分配、車輛優化調度等核心問題[2]。在目前的研究中，兩大類別的研究工作相結合的文獻并不多見，而本文在此方面進行了一定的探索。

針對應急物流的特點和需求，本文以湖南省區域物流為研究對象，提出了一種基于Dijkstra算法和GIS（Geographic Information System）的應急物資配送模型[3]，對應急物流調運中的優化路徑選擇問題進行探索和研究。

1 問題提出

在應急物流調運中，選取時間最短的運輸路徑是其中的核心問題。在實際應用中，主要包括距離最短，或時間最短、距離和時間的加權組合最短等問題[4]。

可以把交通網絡抽象為一個賦權有 向圖 G=（V，E，w）、V={vi|i=1，2， … ，n}為 交 叉 路口 構 成 的 點 集 ，E={eij|i，j1，…，n}為連接各交叉路口的邊集 ，w 為 權 值 函 數 ，w （ei，j）表示邊 ei，j的權值，如圖 1所示。

圖1 節點間關系的有向示意圖

2 研究基礎

2.1 GIS系統

地理信息系統（GIS）是以地理空間數據庫為基礎，在計算機軟硬件的支持下，對空間相關數據進行采集、管理、操作、分析、模擬和顯示，并采用地理模型分析方法，適時提供多種空間和動態的地理信息，為地理研究和地理決策服務建立起的計算機技術系統[5]。將GIS等現代信息技術應用于應急物流中，可以實現應急物流系統的快速響應、準確定位和實時更新[6]。

GIS系統的功能：

（1）具有地圖顯示功能，通過空間屬性信息查詢可以了解備選區域的地理位置、地形、地貌，從而準確地確定應急物流配送點的位置及線路。

（2）GIS地圖上，可以獲得應急物流配送點和需求點的精確地理位置（用經緯度表示）。由于應急物流中心和需求點等空間實體已經數據化，所以能方便地得到物資運輸地道路情況和運輸條件，從而確定最優路徑。

（3）GIS是一個動態的系統，具有良好的動態交互性，它強大的數據庫系統可以保持數據的實時更新，地理空間上的任何變化，GIS都可以更新其數據庫以備調用。同時，利用GIS的空間查詢分析功能，在應急物流配送過程中能很好地實現時效性，以保證應急物流的實施。

Map Info Professional 7.0 SCP軟件繪制的湖南省區域物流城市節點如圖2所示。

圖2 湖南省區域物流城市節點示意

本文以Visual Basic和GIS軟件MapInfo Professional 7.0 SCP作為開發工具，以長沙市為研究對象，利用MapX軟件模擬實現一定區域內應急物流的配送，其系統功能圖結構如圖3所示。

圖3 系統功能結構圖

2.2 算法實現

假定vs和vt分別為路徑的起點和終點，路徑集 Ps，t表示所有vs→vt的路徑，路徑p∈Ps，t的長度可以定義為：

其中，vi，j為構成路徑p的每一條邊。最短路徑問題則可表示為求解節點序列 po=（vs，…，vt）使其滿足：

Dijkstra算法是經典的單源最短路徑算法[8]，其算法思想為：

（1）把V分解為兩個子集S和T，初始狀態時S={vs}，T=V-S；

（2）對于每 個 viI T 計 算 l（vs，vi），根據 l（vs，vi）的值找出 T中距 vs最短的節點 vx，并用 vs→vx的最短路徑長度進行標記；

（3）設 S=S E{vx}，T=T-{x}， 若 T={f}，則 停 止 ；否 則重復（2）。

當算法執行完畢時，就可以求出起點vs到其余所有節點的最短路徑。如果僅需要求vs到指定節點vt的最短路徑，則在vt被從集合T中刪除時即可退出算法，對節點標記過程進行回溯即可得到相關的路徑。

3 仿真實驗

某地區突發公共衛生事件，需要對各個醫院運送藥品，物資配送中心為該地某醫藥公司。位置已知，有8個醫院需要緊急救援物資，物資種類有兩種，每個醫院編號以及需求量已知，各個需求點允許到達最晚時間已知。如表1所示，車輛運輸速度為60 km/h，車輛數為5，車輛載重量為10 t，配送中心以及各醫院間的距離如表2所示，配送中心對各醫院送貨，使每個醫院在規定時間之內得到物資，同時使配送時間最短。

表1 各醫院對物資的需求量

表2 配送中心到各醫院的距離及受災點間的距離/km

利用Dijkstra算法，采用Matlab 7.0編程對距離矩陣求解，得到 4條條路徑為：1-5-3-1、1-2-1、1-9-6-1、1-4-7-8-1。

因為在編程時將配送中心定義為編號1，醫院定義為編號 2～9，所以實際得出 4條路徑為：第一輛車的配送路徑為：配送中心-4-2-配送中心；第二輛車的配送路徑為：配送中心-1-配送中心；第四輛車的配送路徑為：配送中心-8-5-配送中心；第五輛車的配送路徑為：配送中心-3-6-7-配送中心。

針對應急物流追求時間效益最大化、災害損失最小化、災害救援時間緊迫性等特點，本文提出的基于Dijkstra算法和GIS的動態優化路徑選擇方法能實現災后應急物資調運路徑的優化選擇，較好地滿足了應急物資調運的時效性需求，對實際應急物流的實施也有一定的參考價值。

[1]謝金龍，翟玲英，段圣賢.物流地理[M].北京：高等教育出版社，2011.

[2]謝金龍，劉亞梅，王凱.物流信息技術與應用[M].北京：北京大學出版社，2011.

[3]嚴寒冰，劉迎春.基于GIS的城市道路網最短路徑算法探討[J].計算機學報，2000（2）.

[4]汪定偉，張國祥.突發性災害救援中心選址優化的模型與算法[J].東北大學學報，2005（10）.

[5]王占全，趙斯思，徐慧.地理信息系統（GIS）開發工程案例精選[M].北京：人民郵電出版社，2009.

[6]陳曦，傅明.GIS環境下物流配送中心選址模型與算法研究[J].計算機技術與自動化，2001（4）.

[7]Liu Houngzhi， Ou Jianjun， Li Wenzheng， et al.Research on public emergency rank.assesment based on BP neural network[C].The Second International Workshop on Education Technology and Computer Science，2010.

[8]Chang Meishiang， Tseng Yaling， Chen Jingwen.A scenario planning approach for the flood emergency logistics preparation problem under uncertainty[Z].Transportation Research Part E43， 2007.