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

（西安郵電大學 現(xiàn)代郵政學院，陜西 西安 710061）

0 引言

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

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

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

1 問題描述與相關理論

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

1.1 問題描述

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

1.2 相關理論

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

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

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

Liu W[7]提出不確定網(wǎng)絡的定義：

定義3 網(wǎng)絡N=（V,E, ）W 中，如果權(quán)重W為不確定變量，那么該網(wǎng)絡稱為不確定網(wǎng)絡。

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

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

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

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

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

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

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

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

2 模型建立

設快遞網(wǎng)絡為N=（V,A,w,s,t），本文用w為不確定變量（由不確定測度p表示配送路線的中斷程度。當p=0時，表示該路徑通暢狀態(tài)；當p=1時，表示該路徑為堵塞狀態(tài)），表示配送路線的車流量，V表示配送網(wǎng)絡的點集，A表示配送網(wǎng)絡的弧集?；〉拇笮”硎九渌吐肪€的流量容量。在此基礎上，利用配送網(wǎng)絡自身結(jié)構(gòu)特點，計算每條配送路線的容量介數(shù)b。其意義與邊介數(shù)相同，都表示該路線在整個網(wǎng)絡中作用與影響力。數(shù)值越高，該配送路線越不可靠。定義容量權(quán)數(shù)：

配送路線的車流量容量a在配送網(wǎng)絡擁堵時使該配送路線中出現(xiàn)中斷的可能性。

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

應用定理1得到：

Φ wi（）=p的反函數(shù)為：

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

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

過程如下：

（1）確定網(wǎng)絡結(jié)構(gòu)，確認發(fā)件地s、收件地t以及所有可能經(jīng)過的節(jié)點vi、弧ai。

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

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

（4） 建立快遞網(wǎng)絡的最擁堵車流函數(shù)f（ w1, w2,…,wn）與其反函數(shù)

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

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

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

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

過程如下：

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

（2）已知配送網(wǎng)絡結(jié)構(gòu)與各配送邊的流量容量，得到配送網(wǎng)絡的容量介數(shù)矩陣B。

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

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

①構(gòu)造有向賦權(quán)圖Gf=（V,Ef,）F ，對于任意的vivj∈E,Ef和F的定義如下：

ⅰ. 當 fij=0 時，vivj∈Ef，F(xiàn)（ vivj）=bij；

ⅱ. 當 fij=Cij，vivj∈Ef，F(xiàn)（ vivj）=-bij；

ⅲ. 當 0＜fij＜Cij，vivj∈Ef，F(xiàn)（ vivj）=bij。

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

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

轉(zhuǎn)化為線性規(guī)劃描述如下：

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

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

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

3 算例分析

根據(jù)《城市區(qū)域環(huán)境振動標準》 （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

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

通過各配送路線的流量容量計算出各邊的容量介數(shù)，由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。則該配送網(wǎng)絡的容量介數(shù)矩陣為：

若選擇期望值下的最優(yōu)路線，則配送網(wǎng)絡的流量矩陣為WP=0.51：

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

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

4 結(jié)論與展望

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

[1] 黃建華，黨延忠.具有社區(qū)結(jié)構(gòu)和子核的快遞網(wǎng)絡優(yōu)化方法[J].系統(tǒng)工程理論與實踐，2014(11):2826-2836.

[2] 楊從平，鄭世玨，黨永杰,等.基于配送時間及節(jié)點流量約束的快遞網(wǎng)絡優(yōu)化[J].系統(tǒng)工程，2015,11:53-59.

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

[4] 高原.不確定圖與不確定網(wǎng)絡[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] 黃寧，伍志韜.網(wǎng)絡可靠性評估模型與算法綜述[J].系統(tǒng)工程與電子技術(shù)，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實現(xiàn)[M].北京：北京航空航天大學出版社，2010:44-46,77-78.