基于復雜網絡的人道救援物流路徑優化研究

○孫玉壟 范林榜

（江蘇師范大學商學院 江蘇 徐州 221000）

一、引言

人道救援物流復雜網絡的研究是一門新的交叉學科，主要結合復雜科學、管理科學和計算機仿真技術。對于人道救援物流路徑問題的研究，目前已有學者將復雜網絡理論引入到物流領域進行研究，如文獻（俞峰，2009）系統研究了動態隨機復雜網絡的最短路徑問題；文獻（李靖、張永安，2011）在分析物流網絡特征的基礎上，探討了引入復雜網絡的合理性；文獻（唐晉韜、王挺、王戟，2011）基于現實網絡的拓撲特征，提出了一種適合于復雜網絡的最短路徑近似算法；文獻（后銳、楊建梅、姚燦中，2010）利用復雜網絡分析我國物流企業競爭關系網絡，發現其具有小世界特征與無標度特征。但總體來看，公開發表的基于復雜網絡理論來研究人道救援物流的成果仍然較少，而且這些研究通常是在考慮道路邊權的情況下，用最短路的方法來進行路徑優化，忽略了各節點的連接度和最大通行能力，很容易導致高連接度的節點負荷過重，從而造成交通堵塞。因此，本文主要從復雜網絡的角度研究人道救援物流網絡，通過分析節點度與交通負荷之間的關系，提出新的路徑優化策略，旨在讓人道救援車輛能夠及時繞開連接度較高的節點，緩解因交通堵塞而引起的救災延遲，提高救援效率。

二、人道救援物流網絡的復雜性分析

復雜網絡是指具有自相似性、自組織性、小世界屬性、吸引子屬性、無標度屬性中部分或全部性質的網絡。當前的主要研究方法是把各種復雜系統簡化為節點以及連接節點的邊的集合，其中系統的基本組成單位是各個節點，邊則用來表示各個節點之間的相互聯系，并通過計算機技術來分析網絡上的相關指標，用這些作為代表來描述整個網絡的性質。

1、節點度和度分布

節點的度就是指與這個節點直接相連的其他節點的數目，用ki來表示。該指標的作用是來衡量節點在網絡中的地位的，如果網絡中有許多節點都直接與其中的一個節點相連，那么該節點就擁有較高的度，對整個網絡的重要性也較高。

節點度是節點最基本的特性之一，通常更具廣泛性的特征就是節點的度分布，通常是用來表示網絡中度為K的節點在整個網絡中所占的比例。如果一個網絡中有Nk個度值為k的節點，網絡中所有的節點數為N，那么度值為k的節點的度分布可表示為：。

2、介數

介數主要是用來反映節點在網絡中重要程度的指標，如果一個節點在其他許多點對的最短路徑上，那么該點的介數就較大，它起到網絡中控制信息流的橋梁紐帶作用。若假設節點i和j之間有n條最短路徑，此時存在第三個節點k，該節點在它們的最短路之間，且n條最短路徑中有n（k）條經過此節點，用bij（k）來表示節點k對節點i、j之間來往的控制力，也就是k位于i、j最短路上的概率，則那么。節點k的介數就是把節點k相應于網絡中所有點對的中間度相加，可表示為：。

3、平均距離

網絡中連接這兩個節點的最短路徑上的邊權就是兩節點之間的距離d，網絡中任意兩個節點之間的距離的最大值就是該網絡的直徑，通常記為D，表達式為：D=maxd。

平均最短距離是在進行復雜網絡結構分析時最常考察的，可以理解為網絡中任意兩節點之間距離的平均值，可用公式表示為：

網絡的大小在一定程度上是由網絡的平均距離決定的。許多物理學家通過對現實的網絡的研究，發現了大多數網絡的平均距離較小的特性，這種現象被描述為小世界屬性。通過研究發現，世界上絕大部分的復雜網絡基本具有小世界屬性和無標度網絡結構特征，道路網絡也不例外，這就為從復雜網絡的角度來研究人道救援物流提供了可能。

三、改進的最短路徑策略

無標度網絡存在顯著的二八現象，體現的是一種非均勻的網絡，就拿道路網絡系統來說，80%的節點度值較小，只有20%的節點度值較大，Yang等通過研究認為多數網絡中節點的度值與介數正相關，即網絡中度值較大的節點其介數通常也比較大，因此節點往往處在網絡的中心位置，承載的負荷較大，容易形成交通堵塞。為了能夠及時規避這些負荷較大的節點，提出新的路徑優化策略：假設人道救援車輛需要從節點s運送救災物資到節點t，以其起始節點s為中心，搜索其鄰近節點的度值和道路邊權，接著以該鄰接節點的度值與其所有鄰接節點度值之和的比為權重調整起始點s與其鄰接節點的距離，并以該距離為基準選擇鄰接節點，按照傳統最短路算法（Dijkstra算法）逐層向外擴展，直到擴展到終點為止。可用公式表示為：

其中，L表示起點s到終點t之間的總距離；dij表示節點i到節點j的道路邊權；kj表示節點j的連接度值；表示與節點i相連的所有節點的度值總和。a為調節系數，當a=0時，則車輛按最短路徑行駛。

四、最短路徑策略仿真設計

人道救援物流復雜網絡是由一系列低連接度和高連接度的節點構成的，當自然災害發生時，高連接度節點的交通流量較大，當負荷超過一定值就會形成交通堵塞，為了規避這些高連接度的節點，可以設置較高的a值。較高的a值雖然可以繞開連接度高的節點，緩解因交通堵塞而引起的救災延遲，但是人道救援車輛的行車路程會因為繞道而增加，所以應該綜合考慮等待時間和繞道增加時間之間的關系，這樣能夠找到一個合適的a值，為人道救援物流車輛路徑選擇提供決策支持。

為了找到合適的a值，本研究設計了一個仿真，在進行仿真之前，我們需要進行相關假設：

第一，道路網絡符合BA模型，且可以由BA模型生成；第二，計算機隨機產生每輛車的起始點；

第三，網絡中所有救援車輛的行車速度相等；

第四，Ci為節點i的設計通行量，當車流量超過該值就會發生堵塞；

第五，如果節點發生堵塞，按先到先服務的原則處理車流量；

第六，相鄰兩個路口之間的距離為L。

仿真流程描述如下：自然災害發生之后，如何將救災物資及時迅速的運往災區，讓受災民眾得到最快的救治是最重要的。在人道救援車輛出發之前，救援指揮中心需要根據已經掌握的信息來構建人道救援物流網絡，并通過數據分析與統計來了解該網絡的各種屬性；然后運用計算機技術模擬災害發生時人道救援物流網絡中產生的初始車流量，用R表示。其中，車輛的起始點是由計算機隨機產生的，并以最短路原則來選擇行使路徑。接著，通過控制時鐘，模擬車輛在該網絡中的行駛，記錄每個時刻每個節點的車流量，當節點i的瞬時流量超高其設計通行量Ci時，該節點發生堵塞，即滿足：

其中Li（t）表示節點i在時刻t的流量，V表示時刻t0的瞬時速度。最后，用計算機隨機生成一系列救援設施點和受災點，通過設置不同的a值模擬人道救援車輛在該網絡中的行車路徑，統計分析不同a值情況下人道救援車輛的平均行車時間，找出最合適的a值，為人道救援車輛路徑選擇提供決策依據。

五、人道救援網絡中最短路徑策略仿真分析

假設各個節點的設計通行量如表1所示。災害發生后，網絡中的初始車流量為R=10000輛；路口之間的距離L=50米；網絡中救援車輛行車速度v=5米/秒；網絡的最長距離為5，那么在沒有發生交通堵塞的情況，整個仿真的時間為50*5/5=50秒。初始網絡規模為m=4，當網絡的規模N=500時，仿真結束。

表1 各節點設計通行量

運用計算機在500個節點中隨機產生1000對救援設施點和受災點，通過設置不同的a值，模擬人道救援車輛在網絡中的救援路徑，通過統計得到不同a值下的平均行車時間，具體數據如表2所示。

表2 平均行駛時間統計表

由表2可知，隨著a值的逐漸增大，人道救援車輛的平均行駛時間先逐漸降低后逐漸增加。人道救援車輛平均行駛時間的先降低是由于車輛在行駛過程中為了繞過高連接度的節點，避免交通堵塞造成的等待時間；但是隨著a值的逐漸增大，人道救援車輛需要繞道的節點在逐漸增多，救援路程在一定程度上變大，所以平均行駛時間又開始增加。

為了驗證a=1在其它初始交通流的情況下依然存在帕累托最優解，調節R的取值，重復做以上實驗，得到的數據如表3所示。

表3 不同R值下的平均行駛時間

表3可以說明，無論R值如何變化，當a=1時，車輛根據新的路徑優化策略在網絡中行駛，所花費的平均行駛時間是最短的。

六、結論與展望

本文將復雜網絡理論引入到人道救援物流研究中，通過分析人道救援物流復雜網絡的含義及特點，從而選擇最貼近其特點的道路網絡系統作為主要研究對象，并分析其屬性。從規避連接度高的節點的角度出發，提出了一種新的路徑優化策略，新的路徑優化策略主要是在在繞道時間和等待時間之間進行選擇，通過調節變量a值來控制他們之間的關系。運用計算機仿真技術，找出了存在帕累托最優解時a值是1。

本文是在假設信息通暢和單目標的前提下做的相關研究，因此，在考慮信息局限性以及自然災害對道路造成不確定性影響的前提下，從多目標決策和占線問題的角度對人道救援物資運輸的路徑進行動態選擇將是下一步研究的重點。

[1]俞峰：復雜動態隨機網絡最短路徑問題研究[D].浙江大學，2009.

[2]李靖、張永安：復雜網絡理論在物流網絡研究中的應用[J].中國流通經濟，2011（5）.

[3]唐晉韜、王挺、王戟：適合復雜網絡分析的最短路徑近似算法[J].軟件學報，2011（10）.

[4]后銳、楊建梅、姚燦中：物流產業競爭關系復雜網絡模型研究[J].管理學報，2010（3）.

[5]JianmeiYang，LvpingLu，WangdanXie，GuanrongChen，Dong Zhuang：On competitive relationship networks：A new meth forindustriacompetitionanalysis[J].PHYSICAA，2007（382）.

[6]李建春：構建生命權利高于一切的災害應急物流體系研究[J].學術論壇，2014（5）.