基于中斷不確定的最可靠配送路徑選擇研究

孫仕豪，樊相宇，武小平 SUN Shihao,FAN Xiangyu,WU Xiaoping

（西安郵電大學 現代郵政學院，陜西 西安 710061）

0 引言

快遞服務中，快遞配送是與客戶直接接觸的終端服務。配送能否完成是快遞服務最基本條件。配送路線的可靠性是決定配送服務能否準時完成的先決條件。黃建華等[1]強調，快遞行業與其他行業有所不同的是，快遞行業不同時要求成本與效率同時最優，而是以承諾的服務時間為效率最優目標，即在效率方面只是要求快遞行業在承諾的服務時間范圍內為客戶完成快遞服務。設計了一套配送路線、配送成本、配送方式等都與時間閾有關的快遞路線設計方式。楊從平等[2]則進一步在最短路算法的基礎上，再對邊介數、節點介數進行加權求和得出快遞網絡邊的貨物流量和節點的貨物中轉量進行約束。構建帶有配送時間約束和節點最大流量約束的快遞網絡優化模型。

學者關于配送路線流量的算法，主要有遺傳算法、神經網絡、分層理論、灰色關聯模型等，這些算法都是在歷史數據基礎上進行的。由于配送路線上的社會車流量很難準確測量，且快遞配送網絡出現時間較晚、歷史數據不足，導致從問題抽象出圖的模型時，會將不精確信息反映在圖中。很多情況下，不精確信息表現為專家經驗數據的形式，可以借助不確定理論來進一步解決此類問題。劉寶碇[3]建立了不確定理論，提出了不確定測度，它是一個滿足規范性、對偶性、次可列可加性、乘積公理的集函數。高原等[4]應用不確定理論于網絡中，給出了不確定圖的定義和相關概念，并證明了不確定圖中常用的定理。接著從邊數、邊連通度和直徑等基本性質展開對不確定圖的研究。邊數在不確定圖中是一個不確定變量，給出了它的分布函數和期望，形成不確定網絡。Han S等[5]在不確定網絡的基礎上，提出了不確定網絡的最大流函數的概念，運用不確定理論研究了不確定網絡的最大流問題，給出了不確定網絡最大流的不確定分布。

配送路線可靠性[6]的研究大致分為基本可靠性和任務可靠性的研究。配送基本可靠性是從路徑的存在和數量來研究網絡傳輸流的能力，配送路線基本可靠性的度量測度包括路線的抗毀性和生存性，是基于路線連通的確定性測度和概率性測度。因此配送路線可靠性的測度對象都是可得到確定性測度的配送貨物或配送車輛。本文引入了不確定理論，配送路線可靠性的測度可變為不確定測度，研究配送路線的測度對象就可選擇社會車流量，建立一個更符合實際情況的快遞配送網絡最可靠路線模型。

1 問題描述與相關理論

關于不確定網絡模型的研究大多都是對普通網絡，未結合實際情況進行條件約束。本文以快遞網絡為背景，在不確定網絡的基礎上，以配送路線中斷為不確定測度、社會車流量為不確定流，結合各快遞網絡自身結構特點，構建中斷情形不確定的最可靠配送路線模型。

1.1 問題描述

已知配送網絡的起點s、終點t，所有配送路線vn的車容量c確定，所有配送路線上的社會車流量w不確定。任意配送路線的社會車流量與該路線的中斷程度都成正比，社會車流量越多，配送路線中斷的可能性越大。因為配送路線上的社會車輛w不確定，所以不能準確知道各配送路線的中斷情況p，進而不能確定選擇的配送路線是否會中斷。本文以配送路線出現中斷可能性最小為目標，在配送網絡的社會車流量最大時，選擇一條出現中斷可能性最小的路線作為最可靠配送路線，并給出該配送路線的社會車流量。

1.2 相關理論

Liu B[3]提出不確定測度的定義、不確定分布定義：

定義1 M是一個不確定測度，那么對于任意事件Λ，有0≤M｛Λ ｝≤1。

定義2 對于不確定變量ξ，它的不確定分布Φ定義為Φ（x）=M ｛ ξ≤ x ｝，?x∈R。

Liu W[7]提出不確定網絡的定義：

定義3 網絡N=（V,E, ）W 中，如果權重W為不確定變量，那么該網絡稱為不確定網絡。

劉寶碇在文獻[3]中提出E-99最大流法則，不確定分布Φ（x）中的不確定變量n可用E-99表表示。

定理1[8]如果網絡N=（V,A,w,s,t）存在不確定分布Φij，（i,j）∈A。那么網絡N最大流就是N'=（V,A,C,s,t）確定網絡的最大流，此時弧的容量為其反函數為

定理2[9]網絡G是一個有n個弧的不確定網絡，f（ w1, w2,…,wn）是網絡G的最大流函數，此時f（ w1, w2,…,wn）是一個關于wi的連續單調遞增的函數，wi表示第i個弧的不確定分布的權重，i=1,2,…,n。

定理3[9]網絡G是一個有n個弧的不確定網絡，f（ w1, w2,…,wn）是網絡G的最大流函數，那么不確定網絡G的最大流函數f就是一個不確定變量ξ，其逆不確定值為：

此時εi表示第i個弧的不確定分布的權重，i=1,2,…,n。

定理4[9]網絡G是一個有n個弧的不確定網絡，f（ c1,c2,…,cn）是網絡G的最大流函數，εi表示不確定分布Φi（x）,i=1,2,…,n 中第 i個弧的不確定權重。那么最大流 ε=f（ ε1,ε2,…,εn）存在一個期望值dα。

定理5[3]網絡G是一個有n個弧的不確定網絡，f（ c ,c ,…,c）是網絡G的最大流函數，ε表示不確定分布Φ （x）,i

12nii=1,2,…,n中第i個弧的不確定權重。如果Ψ（x）是一個由E-99方法得到的最大流為ε不確定分布，那么最大流ε=f（ε1,ε2,…,εn）的期望值為當且僅當i=1,2,…,99。

2 模型建立

設快遞網絡為N=（V,A,w,s,t），本文用w為不確定變量（由不確定測度p表示配送路線的中斷程度。當p=0時，表示該路徑通暢狀態；當p=1時，表示該路徑為堵塞狀態），表示配送路線的車流量，V表示配送網絡的點集，A表示配送網絡的弧集。弧的大小表示配送路線的流量容量。在此基礎上，利用配送網絡自身結構特點，計算每條配送路線的容量介數b。其意義與邊介數相同，都表示該路線在整個網絡中作用與影響力。數值越高，該配送路線越不可靠。定義容量權數：

配送路線的車流量容量a在配送網絡擁堵時使該配送路線中出現中斷的可能性。

設網絡的路線中斷—車流量不確定分布函數為Φi（p），由于路線中斷與車流量成正比例關系，因此可以引用不確定理論[8]中的線性函數公式，設網絡的路線中斷—流量函數為：

應用定理1得到：

Φ wi（）=p的反函數為：

設該快遞網絡的最擁堵車流函數為f（ w1, w2,…,wn），根據定理1～3可得網絡的逆不確定最擁堵流值為Ψ-1（p）=f

劉寶碇在文獻[3]中提出E-99最大流法則，不確定分布Φ（x）中的不確定變量n的不確定最大流可用E-99表表示。

過程如下：

（1）確定網絡結構，確認發件地s、收件地t以及所有可能經過的節點vi、弧ai。

（2）給出每一條配送路線上可能出現的社會車流量w的范圍以及配送路線中斷p的判斷標準。

（3） 建立配送路線中斷—車流量Φ（ wi）（式1） 以及其反函數Φ-1（wi）（式2）。

（4） 建立快遞網絡的最擁堵車流函數f（ w1, w2,…,wn）與其反函數

（5）利用E-99最大流法則，對不配送路線中斷程度進行細分，p=0.01至p=0.99，再利用Fold-Fulkerson算法得到對應中斷的最大擁堵流值Ψ-1（）p，得到E-99最大流表。

（6）利用定理對E-99表進行驗證。

此時可以得到關于該配送網絡的路線中斷—車流量二維圖，由該圖可以求得任意中斷程度的最大車流量。

由E-99表可以得到各配送路線不同中斷程度的最大擁堵車流矩陣W，由配送網絡得到該網絡的容量介數矩陣B。結合Busacker-Gowan算法，得到不同最大社會車流量中出現最小中斷可能性的社會車輛流，即為不同中斷程度的最可靠配送可行流。

過程如下：

（1）選擇可能的中斷程度p，利用E-99遍得到對應的配送網絡流量矩陣W。

（2）已知配送網絡結構與各配送邊的流量容量，得到配送網絡的容量介數矩陣B。

（3） 借助 Busacker-Gowan[10]算法：

設網絡G（ V,E, ）C ，取初始可行流f為零流：

①構造有向賦權圖Gf=（V,Ef,）F ，對于任意的vivj∈E,Ef和F的定義如下：

ⅰ. 當 fij=0 時，vivj∈Ef，F（ vivj）=bij；

ⅱ. 當 fij=Cij，vivj∈Ef，F（ vivj）=-bij；

ⅲ. 當 0＜fij＜Cij，vivj∈Ef，F（ vivj）=bij。

②求出有向賦權圖Gf=（V,Ef,）F 中發點vs到收點vt的最短路μ，若最短路μ存在，則轉向③；

若所得的最大流量Wf大于或等于預定的流量值，則適當減少δ值，使Wf等于預定的流量值，故f就是所求的路線中斷可能性最小的車輛流，停止；否則轉向①。

轉化為線性規劃描述如下：

設fmax為最大流，若v（f）=v（ fmax），則就是該問題的解；若v（f ）＞v（ fmax），則無解。

（4）代入W與B矩陣，求得最可靠配送可行流F矩陣。

（5）由該矩陣得該中斷程度的最可靠配送路線。

3 算例分析

根據《城市區域環境振動標準》 （GB10070-88）中的“交通干線道路”是指平均車流量每小時100輛以上的道路。因為配送一般都為單向配送，所以設配送路線的平均車流量標準為每小時50輛以上的道路。設配送路線的車流量容量為配送路線路程與平均車流量的乘積。若不超過該道路車流量容量一半為暢通，P=0；若超過車流量流量的1.5倍則為堵塞。配送路長用l（km） 表示，l1=10、l2=8、l3=7、l4=5、l5=2、l6=4、l7=9、l8=11，配送路線的車流量容量為a1=500、a2=400、a3=350、a4=250、a5=100、a6=200、a7=450、a8=550。路徑的交通流量為w1=（250～750 ）、w2=（200～600 ）、w3（175～525 ）、w4（125～375 ）、w5（100～300 ）、w6（50～25 0 ）、w7（225～425 ）、w8（275～475 ）。利用公式1、定理、E-99算法，得到E-99表與路線中斷—車流量如表1、圖1、圖2。

表1

圖1

圖2

再根據定理，求得期望值E（）p≈689，p≈0.51在估值范圍之內，驗證該不確定分布可接受。

通過各配送路線的流量容量計算出各邊的容量介數，由MATLAB運算得b1=0.2,b2=0.3,b3=0.15,b4=0.25,b5=0.45,b6=0.45,b7=0.3,b8=0.2。則該配送網絡的容量介數矩陣為：

若選擇期望值下的最優路線，則配送網絡的流量矩陣為WP=0.51：

由Busacker-Gowan算法求得p=0.51時的最可靠最擁堵流F的矩陣F為：

由該可行流可得到具體的配送路線：1→2→5→6。

4 結論與展望

快遞企業在選擇快遞配送路線時，都以準時安全送達為基本要求。配送路線為配送任務完成的基礎條件，其可靠性是快遞業務完成的保證。關于快遞配送路線的可靠性研究，主要集中于指標確定的配送路線選擇，以及該配送路線服務水平與服務能力的評估。在考慮實際動態變化的方面，還有待于深入研究。本文基于不確定理論，以配送路線上的交通流量為不確定變量，結合邊介數與Fold-Fulkerson、Busacker-Gowan算法，形成一套不確定網絡的可靠性路線選擇模型。該模型有三方面優點：（1）不確定理論，更切合實際，使網絡適用于配送實際情況。（2）模型中的參數與數據，可根據實際情況進行調整，實用性更高。（3）Busacker-Gowan算法在一方面考慮社會車流量最大值的同時，也考慮了出現最少中斷的要求，更符合實際快遞配送設計要求。本文仍有未討論的方面，如：只考慮了道路流量，未考慮節點的各類情況，該方面需要進一步的補充與研究。

[1] 黃建華，黨延忠.具有社區結構和子核的快遞網絡優化方法[J].系統工程理論與實踐，2014(11):2826-2836.

[2] 楊從平，鄭世玨，黨永杰,等.基于配送時間及節點流量約束的快遞網絡優化[J].系統工程，2015,11:53-59.

[3] Liu B.Uncertainty Theory[M].2版.Berlin:Springer-Verlag,2007.

[4] 高原.不確定圖與不確定網絡[D].北京：清華大學（博士學位論文），2013:30-31.

[5] Han S,Peng Z,Wang S.The Maximum Flow Problem of Uncertain Network[J].Information Sciences,2014,265:167-175.

[6] 黃寧，伍志韜.網絡可靠性評估模型與算法綜述[J].系統工程與電子技術，2013(12):2651-2660.

[7] Liu W.Uncertain Programming Models for Shortest Path Problem with Uncertain Arc Lengths[C]//Proceedings of the First International Conference on Uncertainty Theory,Urumchi,China,2010:148-153.

[8] Han S,Peng Z,Wang S.The Maximum Flow Problem of Uncertain Network[J].Information Sciences,2014,265:167-175.

[9] Ding S.The α-Maximum Flow Model with Uncertain Capacities[J].Applied Mathematical Modelling,2015,2(7):2056-2063.

[10]王海英，黃強.圖論算法以及MATLAB實現[M].北京：北京航空航天大學出版社，2010:44-46,77-78.