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

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

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

0 引言

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

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

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

1 問(wèn)題描述與相關(guān)理論

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

1.1 問(wèn)題描述

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

1.2 相關(guān)理論

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

定義1 M是一個(gè)不確定測(cè)度，那么對(duì)于任意事件Λ，有0≤M｛Λ ｝≤1。

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

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

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

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

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

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

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

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

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

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

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

2 模型建立

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

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

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

應(yīng)用定理1得到：

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

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

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

過(guò)程如下：

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

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

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

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

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

（6）利用定理對(duì)E-99表進(jìn)行驗(yàn)證。

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

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

過(guò)程如下：

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

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

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

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

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

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

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

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

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

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

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

設(shè)fmax為最大流，若v（f）=v（ fmax），則就是該問(wèn)題的解；若v（f ）＞v（ fmax），則無(wú)解。

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

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

3 算例分析

根據(jù)《城市區(qū)域環(huán)境振動(dòng)標(biāo)準(zhǔn)》 （GB10070-88）中的“交通干線道路”是指平均車流量每小時(shí)100輛以上的道路。因?yàn)榕渌鸵话愣紴閱蜗蚺渌?，所以設(shè)配送路線的平均車流量標(biāo)準(zhǔn)為每小時(shí)50輛以上的道路。設(shè)配送路線的車流量容量為配送路線路程與平均車流量的乘積。若不超過(guò)該道路車流量容量一半為暢通，P=0；若超過(guò)車流量流量的1.5倍則為堵塞。配送路長(zhǎng)用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)，驗(yàn)證該不確定分布可接受。

通過(guò)各配送路線的流量容量計(jì)算出各邊的容量介數(shù)，由MATLAB運(yùn)算得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)絡(luò)的容量介數(shù)矩陣為：

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

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

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

4 結(jié)論與展望

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

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

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

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

[4] 高原.不確定圖與不確定網(wǎng)絡(luò)[D].北京：清華大學(xué)（博士學(xué)位論文），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)絡(luò)可靠性評(pí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]王海英，黃強(qiáng).圖論算法以及MATLAB實(shí)現(xiàn)[M].北京：北京航空航天大學(xué)出版社，2010:44-46,77-78.