考慮交通擁堵的物流配送路徑優(yōu)化

鄭喬芳

（南京交通職業(yè)技術(shù)學(xué)院 運(yùn)輸管理學(xué)院，江蘇 南京 211188）

1 引言

配送作為物流運(yùn)作中重要的環(huán)節(jié)，關(guān)乎整個(gè)物流系統(tǒng)的運(yùn)作效率以及客戶服務(wù)滿意度，物流配送路徑優(yōu)化也一直是企業(yè)和學(xué)術(shù)界研究的重點(diǎn)。物流配送路徑選擇不合理導(dǎo)致配送路徑重復(fù)、迂回，使得配送距離增加，配送道路擁堵使得配送時(shí)間延長，配送距離和配送時(shí)間的增加使得配送成本增加。以往的很多路徑規(guī)劃問題研究，主要以配送距離作為權(quán)重，本文考慮交通擁堵問題，并基于時(shí)間成本因素和距離成本因素，提出以有效距離作為權(quán)重規(guī)劃路徑，在降低成本的同時(shí)，提高客戶滿意度。

2 問題描述

研究一定區(qū)域內(nèi)單個(gè)配送中心、多輛配送車輛對(duì)多個(gè)配送站點(diǎn)的共同配送路徑問題。以配送中心和多個(gè)配送站點(diǎn)為節(jié)點(diǎn)，配送路徑為邊，用物流配送過程中投入的車輛行駛里程和時(shí)間產(chǎn)生的效用值來量化節(jié)點(diǎn)之間配送的有效性，應(yīng)用柯布-道格拉斯函數(shù)模型，物流配送里程和配送時(shí)間的投入以指數(shù)形式產(chǎn)出效用值，而不是以往研究中的線性形式增長，因?yàn)榕渌途嚯x和配送時(shí)間的增加不僅會(huì)增加燃油成本、加快車輛磨損和耗費(fèi)人工成本等，還會(huì)引發(fā)客戶滿意度降低、配送效率降低、庫存成本增加等問題。用這一效用值來定義有效距離，量化物流配送路徑的有效性，物流配送距離和配送時(shí)間越大，產(chǎn)生的距離效用值越大，有效距離越大，配送有效性越低，反之亦如此。以有效距離為邊的權(quán)重，用Floyd算法求解配送中心到其他所有物流節(jié)點(diǎn)的有效路徑。

3 模型建立

3.1 條件假設(shè)與參數(shù)說明

相關(guān)條件假設(shè)如下：

（1）本文假設(shè)任意兩物流節(jié)點(diǎn)之間存在往返路徑，且往返距離和時(shí)間相同。

（2）本文定義的有效距離并非實(shí)際物流配送網(wǎng)絡(luò)中節(jié)點(diǎn)之間的配送距離或地理距離，而是用來度量節(jié)點(diǎn)之間配送有效性的量，糅合了配送時(shí)間與配送距離的效用。

（3）本文假設(shè)的配送距離為路程而非位移，配送時(shí)間為平均耗用時(shí)間。

參數(shù)說明如下：

dij:表示相鄰兩個(gè)節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的有效距離，也是對(duì)應(yīng)邊上的權(quán)重，且dij=dji；

eij:表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的有效距離，當(dāng)節(jié)點(diǎn)i和節(jié)點(diǎn)j為相鄰節(jié)點(diǎn)時(shí)，dij=eij且eij=eji；

sij：表示車輛從節(jié)點(diǎn)i行駛到節(jié)點(diǎn)j的路程；

S：表示路程矩陣；

tij：表示車輛從節(jié)點(diǎn)i行駛到節(jié)點(diǎn)j的平均時(shí)間；

T：時(shí)間矩陣；

λ：表示距離效用系數(shù)；

θ：表示行駛車輛的性能指數(shù)；

D：表示有效距離初始矩陣，權(quán)值矩陣；

W：表示有效路徑矩陣；

Wιj：表示從i到j(luò)的最短路要經(jīng)過Wij點(diǎn)；

α、β：表示路段阻抗函數(shù)中的待標(biāo)定參數(shù)；

Qij(t)：表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的交通量；

Cij:表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間路段的通行能力。

3.2 網(wǎng)絡(luò)模型

以配送中心、若干個(gè)配送站點(diǎn)為節(jié)點(diǎn)，以配送中心與配送站點(diǎn)之間的路徑為邊，構(gòu)建物流配送網(wǎng)絡(luò)，在物流配送網(wǎng)絡(luò)中，將相鄰節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的有效距離dij定義為：

式（1）中λ表示在物流配送網(wǎng)絡(luò)中其他條件不變的情況下，兩節(jié)點(diǎn)之間的配送路程增加1%，兩節(jié)點(diǎn)之間的有效距離對(duì)應(yīng)地增加λ%。1-λ是時(shí)間系數(shù)，表示在物流配送網(wǎng)絡(luò)中其他條件不變的情況下，配送時(shí)間增加1%，有效距離增加（1-λ）%。λ是可調(diào)參數(shù)，且0＜λ＜1；θ為車輛性能指數(shù)，且0＜θ＜1，θ越大表示物流配送車輛性能越好，反之亦然。當(dāng)物流企業(yè)對(duì)節(jié)約距離成本的關(guān)注度高于對(duì)節(jié)約時(shí)間成本的關(guān)注度時(shí)，可使得λ＞0.5，相應(yīng)地，當(dāng)物流企業(yè)對(duì)節(jié)約時(shí)間成本的關(guān)注度高于對(duì)節(jié)約距離成本的關(guān)注度時(shí)，可使得λ＜0.5。

考慮配送過程中的交通擁堵，通過路段使用的時(shí)間會(huì)比自由行駛時(shí)間長，因而引用路段阻抗函數(shù)（BRP）描述出行時(shí)間與路段流量和最大通行能力之間的關(guān)系，表示為：

式（2）中，α和β為待標(biāo)定參數(shù)，一般取值：α=0.15，β=4.0，tij表示實(shí)際通過該路徑所需時(shí)間表示通過該路徑自由行駛時(shí)間，Qij(t)為該路徑交通量，Cij表示該路徑的通行能力，二者之間有如下關(guān)系：

根據(jù)觀測的相鄰節(jié)點(diǎn)距離數(shù)據(jù)和計(jì)算的通行時(shí)間數(shù)據(jù)，分別構(gòu)建S矩陣和T矩陣。

其中，Sij=Sji，tij=tji,給定合適的參數(shù)，根據(jù)式（1）和式（2），計(jì)算并構(gòu)建相鄰節(jié)點(diǎn)間的有效距離矩陣D。

式中，dij=dji，配送時(shí)間和配送距離的減少都會(huì)以指數(shù)形式產(chǎn)生效用，以有效距離進(jìn)行度量，而路徑優(yōu)化的目標(biāo)是配送中心到任一配送站點(diǎn)之間的有效距離最短。

3.3 模型求解

以有效距離為權(quán)重，應(yīng)用Floyd算法對(duì)構(gòu)建的由一個(gè)配送中心和若干個(gè)配送站點(diǎn)構(gòu)成的規(guī)則網(wǎng)絡(luò)進(jìn)行最優(yōu)路徑的求解，并計(jì)算配送中心至各節(jié)點(diǎn)的有效距離，詳細(xì)步驟如下：

（3）按照第（1）和第（2）所描述的方法進(jìn)行依次插入頂點(diǎn)，一直到所有的頂點(diǎn)插入并計(jì)算完得到其中是從i到j(luò)的只允許以1、2、...、v作為中間點(diǎn)的最短路徑中最小的有效距離，即從i到j(luò)中可插入任何頂點(diǎn)的路徑中最小的有效距離，因此E(v)是節(jié)點(diǎn)之間最短有效距離矩陣，可由E(v)來查找任意兩個(gè)節(jié)點(diǎn)之間的最短有效距離。

最后，在求得有效距離矩陣的同時(shí)，建立有效路徑矩陣 W=(wij)n×n，wij表示從i到j(luò)的最短路要經(jīng)過wij點(diǎn)：初始值，在每求得一個(gè)有效距離矩陣E(k)時(shí)，按照以下方式產(chǎn)生對(duì)應(yīng)的新路徑矩陣W(k)：

3.4 數(shù)值模擬

假設(shè)有1個(gè)配送中心H需要向該區(qū)域內(nèi)20個(gè)配送站點(diǎn)共同配送貨物，分別用數(shù)字1～20進(jìn)行編號(hào)，配送中心H與各節(jié)點(diǎn)之間的配送距離s見表1，假設(shè)物流配送運(yùn)作過程中，對(duì)于配送距離和配送時(shí)間注重程度是一致的，引入?yún)?shù) λ=0.5，θ=0.9，α=0.15,β=4.0,選定時(shí)間窗、通行能力、交通量并計(jì)算出相鄰節(jié)點(diǎn)間有效距離數(shù)據(jù)見表2。

根據(jù)表2中相鄰節(jié)點(diǎn)間的有效距離作為權(quán)重，構(gòu)建權(quán)值矩陣D，運(yùn)用matlab，F(xiàn)loyd算法求解得出物流配送網(wǎng)絡(luò)中各節(jié)點(diǎn)間的有效距離，見表3。

同時(shí)，在配送時(shí)間因素和配送距離因素同等重視的情況下，λ=0.5，通過算法求解得出物流配送網(wǎng)絡(luò)中任意兩節(jié)點(diǎn)之間的有效路徑，其中配送中心H至各配送站點(diǎn)的有效路徑信息見表4，通過數(shù)值模擬，以有效距離作為權(quán)重求解得出的有效路徑更貼近實(shí)際需要，通過調(diào)節(jié)λ值可以調(diào)節(jié)有效路徑的選擇，當(dāng)面對(duì)配送及時(shí)性要求較高的客戶，可以適當(dāng)降低λ值，反之，可以適當(dāng)提高λ值?？紤]交通擁堵因素，量化為時(shí)間效用，作為路徑選擇參數(shù)，避開交通擁堵路段，更能提高配送效率。尤其在規(guī)劃大型物流配送網(wǎng)絡(luò)時(shí)，節(jié)點(diǎn)和邊較多，可以從宏觀角度規(guī)劃路徑，有效規(guī)避擁堵路徑，提高配送網(wǎng)絡(luò)的穩(wěn)定性，不易因交通擁堵而影響物流配送。

表1 物流配送網(wǎng)絡(luò)各節(jié)點(diǎn)配送距離

表2 路徑相關(guān)參數(shù)表

表3 節(jié)點(diǎn)間有效距離數(shù)據(jù)

表4 有效路徑

4 總結(jié)

以配送路徑選擇為基礎(chǔ)，考慮了實(shí)際運(yùn)作中的交通擁堵因素，將其量化為時(shí)間效用值，構(gòu)建有效距離函數(shù)，與以往對(duì)于配送距離、配送時(shí)間和成本之間構(gòu)建線性關(guān)系不同，以指數(shù)形式量化配送時(shí)間和配送距離對(duì)路徑選擇的影響效用，反映配送服務(wù)過程中，配送時(shí)間或配送距離的增加，都會(huì)以指數(shù)的增長影響到客戶滿意度，尤其是當(dāng)前互聯(lián)網(wǎng)電商平臺(tái)發(fā)展背景下，配送服務(wù)要求越來越高，以有效距離構(gòu)建權(quán)值矩陣，應(yīng)用Floyd算法求解得出配送網(wǎng)絡(luò)中各節(jié)點(diǎn)之間的優(yōu)化路徑。該路徑的選擇同時(shí)考慮了交通擁堵影響下的時(shí)間因素和距離因素，更貼近實(shí)際運(yùn)作，為路徑的優(yōu)化以及配送網(wǎng)絡(luò)的構(gòu)建提供借鑒和參考。