謝金龍，武獻(xiàn)宇

（湖南現(xiàn)代物流職業(yè)技術(shù)學(xué)院，湖南 長(zhǎng)沙 410001）

應(yīng)急物流是以提供突發(fā)性自然災(zāi)害、突發(fā)性公共衛(wèi)生事件、戰(zhàn)爭(zhēng)等所需應(yīng)急物資為目的，以追求時(shí)間效益最大化和損失最小化為目標(biāo)的一種特殊的物流活動(dòng)[1]。因此，應(yīng)急物流以追求時(shí)間效益最大化和災(zāi)害損失最小化為目標(biāo)，具有突發(fā)性、不確定性、非常規(guī)性、弱經(jīng)濟(jì)性等突出特點(diǎn)。

為了保證應(yīng)急物資的調(diào)運(yùn)、縮短配送時(shí)間、滿足應(yīng)急物資調(diào)運(yùn)的時(shí)效性需求，應(yīng)急物資調(diào)運(yùn)信息系統(tǒng)具有重要的研究?jī)r(jià)值。目前對(duì)應(yīng)急物資調(diào)運(yùn)信息系統(tǒng)的研究工作大致可以分為兩大類：（1）利用定性分析方法，研究應(yīng)急物資調(diào)運(yùn)信息系統(tǒng)構(gòu)建的相關(guān)理論、系統(tǒng)概念模型的結(jié)構(gòu)和功能模塊分析，以及數(shù)據(jù)倉(cāng)庫(kù)、GIS等信息技術(shù)在應(yīng)急物流信息系統(tǒng)中的應(yīng)用等；（2）采用定量分析方法，通過數(shù)學(xué)模型分析，研究應(yīng)急物資調(diào)運(yùn)信息系統(tǒng)中的路徑優(yōu)化、物資分配、車輛優(yōu)化調(diào)度等核心問題[2]。在目前的研究中，兩大類別的研究工作相結(jié)合的文獻(xiàn)并不多見，而本文在此方面進(jìn)行了一定的探索。

針對(duì)應(yīng)急物流的特點(diǎn)和需求，本文以湖南省區(qū)域物流為研究對(duì)象，提出了一種基于Dijkstra算法和GIS（Geographic Information System）的應(yīng)急物資配送模型[3]，對(duì)應(yīng)急物流調(diào)運(yùn)中的優(yōu)化路徑選擇問題進(jìn)行探索和研究。

1 問題提出

在應(yīng)急物流調(diào)運(yùn)中，選取時(shí)間最短的運(yùn)輸路徑是其中的核心問題。在實(shí)際應(yīng)用中，主要包括距離最短，或時(shí)間最短、距離和時(shí)間的加權(quán)組合最短等問題[4]。

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

圖1 節(jié)點(diǎn)間關(guān)系的有向示意圖

2 研究基礎(chǔ)

2.1 GIS系統(tǒng)

地理信息系統(tǒng)（GIS）是以地理空間數(shù)據(jù)庫(kù)為基礎(chǔ)，在計(jì)算機(jī)軟硬件的支持下，對(duì)空間相關(guān)數(shù)據(jù)進(jìn)行采集、管理、操作、分析、模擬和顯示，并采用地理模型分析方法，適時(shí)提供多種空間和動(dòng)態(tài)的地理信息，為地理研究和地理決策服務(wù)建立起的計(jì)算機(jī)技術(shù)系統(tǒng)[5]。將GIS等現(xiàn)代信息技術(shù)應(yīng)用于應(yīng)急物流中，可以實(shí)現(xiàn)應(yīng)急物流系統(tǒng)的快速響應(yīng)、準(zhǔn)確定位和實(shí)時(shí)更新[6]。

GIS系統(tǒng)的功能：

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

（2）GIS地圖上，可以獲得應(yīng)急物流配送點(diǎn)和需求點(diǎn)的精確地理位置（用經(jīng)緯度表示）。由于應(yīng)急物流中心和需求點(diǎn)等空間實(shí)體已經(jīng)數(shù)據(jù)化，所以能方便地得到物資運(yùn)輸?shù)氐缆非闆r和運(yùn)輸條件，從而確定最優(yōu)路徑。

（3）GIS是一個(gè)動(dòng)態(tài)的系統(tǒng)，具有良好的動(dòng)態(tài)交互性，它強(qiáng)大的數(shù)據(jù)庫(kù)系統(tǒng)可以保持?jǐn)?shù)據(jù)的實(shí)時(shí)更新，地理空間上的任何變化，GIS都可以更新其數(shù)據(jù)庫(kù)以備調(diào)用。同時(shí)，利用GIS的空間查詢分析功能，在應(yīng)急物流配送過程中能很好地實(shí)現(xiàn)時(shí)效性，以保證應(yīng)急物流的實(shí)施。

Map Info Professional 7.0 SCP軟件繪制的湖南省區(qū)域物流城市節(jié)點(diǎn)如圖2所示。

圖2 湖南省區(qū)域物流城市節(jié)點(diǎn)示意

本文以Visual Basic和GIS軟件MapInfo Professional 7.0 SCP作為開發(fā)工具，以長(zhǎng)沙市為研究對(duì)象，利用MapX軟件模擬實(shí)現(xiàn)一定區(qū)域內(nèi)應(yīng)急物流的配送，其系統(tǒng)功能圖結(jié)構(gòu)如圖3所示。

圖3 系統(tǒng)功能結(jié)構(gòu)圖

2.2 算法實(shí)現(xiàn)

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

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

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

（1）把V分解為兩個(gè)子集S和T，初始狀態(tài)時(shí)S={vs}，T=V-S；

（2）對(duì)于每 個(gè) viI T 計(jì) 算 l（vs，vi），根據(jù) l（vs，vi）的值找出 T中距 vs最短的節(jié)點(diǎn) vx，并用 vs→vx的最短路徑長(zhǎng)度進(jìn)行標(biāo)記；

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

當(dāng)算法執(zhí)行完畢時(shí)，就可以求出起點(diǎn)vs到其余所有節(jié)點(diǎn)的最短路徑。如果僅需要求vs到指定節(jié)點(diǎn)vt的最短路徑，則在vt被從集合T中刪除時(shí)即可退出算法，對(duì)節(jié)點(diǎn)標(biāo)記過程進(jìn)行回溯即可得到相關(guān)的路徑。

3 仿真實(shí)驗(yàn)

某地區(qū)突發(fā)公共衛(wèi)生事件，需要對(duì)各個(gè)醫(yī)院運(yùn)送藥品，物資配送中心為該地某醫(yī)藥公司。位置已知，有8個(gè)醫(yī)院需要緊急救援物資，物資種類有兩種，每個(gè)醫(yī)院編號(hào)以及需求量已知，各個(gè)需求點(diǎn)允許到達(dá)最晚時(shí)間已知。如表1所示，車輛運(yùn)輸速度為60 km/h，車輛數(shù)為5，車輛載重量為10 t，配送中心以及各醫(yī)院間的距離如表2所示，配送中心對(duì)各醫(yī)院送貨，使每個(gè)醫(yī)院在規(guī)定時(shí)間之內(nèi)得到物資，同時(shí)使配送時(shí)間最短。

表1 各醫(yī)院對(duì)物資的需求量

表2 配送中心到各醫(yī)院的距離及受災(zāi)點(diǎn)間的距離/km

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

因?yàn)樵诰幊虝r(shí)將配送中心定義為編號(hào)1，醫(yī)院定義為編號(hào) 2～9，所以實(shí)際得出 4條路徑為：第一輛車的配送路徑為：配送中心-4-2-配送中心；第二輛車的配送路徑為：配送中心-1-配送中心；第四輛車的配送路徑為：配送中心-8-5-配送中心；第五輛車的配送路徑為：配送中心-3-6-7-配送中心。

針對(duì)應(yīng)急物流追求時(shí)間效益最大化、災(zāi)害損失最小化、災(zāi)害救援時(shí)間緊迫性等特點(diǎn)，本文提出的基于Dijkstra算法和GIS的動(dòng)態(tài)優(yōu)化路徑選擇方法能實(shí)現(xiàn)災(zāi)后應(yīng)急物資調(diào)運(yùn)路徑的優(yōu)化選擇，較好地滿足了應(yīng)急物資調(diào)運(yùn)的時(shí)效性需求，對(duì)實(shí)際應(yīng)急物流的實(shí)施也有一定的參考價(jià)值。

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

[2]謝金龍，劉亞梅，王凱.物流信息技術(shù)與應(yīng)用[M].北京：北京大學(xué)出版社，2011.

[3]嚴(yán)寒冰，劉迎春.基于GIS的城市道路網(wǎng)最短路徑算法探討[J].計(jì)算機(jī)學(xué)報(bào)，2000（2）.

[4]汪定偉，張國(guó)祥.突發(fā)性災(zāi)害救援中心選址優(yōu)化的模型與算法[J].東北大學(xué)學(xué)報(bào)，2005（10）.

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

[6]陳曦，傅明.GIS環(huán)境下物流配送中心選址模型與算法研究[J].計(jì)算機(jī)技術(shù)與自動(dòng)化，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.