基于客戶(hù)軟時(shí)間窗的地下物流配送路徑優(yōu)化*

郭琪， 鄭長(zhǎng)江， 李銳

(河海大學(xué) 土木與交通學(xué)院， 江蘇 南京 210098)

隨著互聯(lián)網(wǎng)的蓬勃發(fā)展，現(xiàn)有地面交通供應(yīng)能力已無(wú)法滿足物流配送的需求。為追求更高效、更高品質(zhì)的服務(wù)，緩解交通壓力，文獻(xiàn)[1]利用地面與地下交通資源，提出軟時(shí)間窗條件下地下物流配送優(yōu)化模型。文獻(xiàn)[2]指出在物流配送壓力較大的城市，主要運(yùn)輸線路沿線大多開(kāi)通了地鐵，可在客流量不很大或非客運(yùn)時(shí)段選取固定時(shí)間對(duì)快件進(jìn)行通過(guò)運(yùn)輸，將貨運(yùn)中心、地鐵中轉(zhuǎn)站和客戶(hù)點(diǎn)連成一個(gè)整體，結(jié)合時(shí)間窗對(duì)物流配送路徑進(jìn)行優(yōu)化。由于硬時(shí)間窗的要求較嚴(yán)格，無(wú)法很好地處置貨物堆積、列車(chē)早晚點(diǎn)等突發(fā)情況，地下物流系統(tǒng)在軟時(shí)間窗下的路徑優(yōu)化成為主要研究課題。但研究集中在理論層面，實(shí)施難度較大。軟時(shí)間窗主要是指地鐵等嚴(yán)格遵守運(yùn)行時(shí)刻表的運(yùn)載工具在特定時(shí)間窗下進(jìn)行物流運(yùn)輸，時(shí)間窗主要為列車(chē)運(yùn)行時(shí)刻表。該文基于客戶(hù)軟時(shí)間窗建立地下物流成本最優(yōu)模型，采用遺傳算法進(jìn)行迭代分析，對(duì)地下物流配送路徑進(jìn)行優(yōu)化。

1 問(wèn)題描述與建模

1.1 問(wèn)題描述

以南京現(xiàn)有地鐵線路為基礎(chǔ)，考慮地下物流配送和地面車(chē)輛配送，使運(yùn)輸總成本最小，在尊重假設(shè)的前提下，運(yùn)用改進(jìn)遺傳算法計(jì)算軟時(shí)間窗下成本并與傳統(tǒng)運(yùn)輸模式下成本進(jìn)行對(duì)比，驗(yàn)證地下物流配送模式的可行性。

列車(chē)自配送中心起單方向運(yùn)行負(fù)責(zé)物流配送，且不接受新的貨物，到達(dá)相應(yīng)的出站點(diǎn)時(shí)，卸載并由地面配送車(chē)輛運(yùn)送至客戶(hù)，地鐵線路的貨物集散中心、出站點(diǎn)和客戶(hù)時(shí)間窗均已知，地面配送車(chē)輛容量及中轉(zhuǎn)時(shí)間固定。

1.2 模型假設(shè)

(1) 貨物配送中心可以有一個(gè)或多個(gè)，且同列貨物同時(shí)發(fā)出。

(2) 地鐵列車(chē)只負(fù)責(zé)配送貨物，不考慮返回過(guò)程。

(3) 貨物運(yùn)輸?shù)耐瑫r(shí)不會(huì)影響乘客服務(wù)質(zhì)量。

(4) 每趟列車(chē)及地面運(yùn)輸車(chē)的運(yùn)輸能力有限且已知，最大貨運(yùn)量不超過(guò)其容量。

(5) 每個(gè)地點(diǎn)的貨物需求量已知，且只能有一條線路服務(wù)。

(6) 模型中時(shí)間窗只針對(duì)末端客戶(hù)地鐵列車(chē)的開(kāi)行，地鐵列車(chē)的開(kāi)行配送均不考慮在其中。

(7) 地鐵車(chē)輛運(yùn)輸成本和車(chē)輛運(yùn)輸成本與距離成正比，且車(chē)輛成本固定。

1.3 模型建立

1.3.1 運(yùn)輸時(shí)間成本

貨物在地鐵列車(chē)及末端配送車(chē)輛上運(yùn)輸途中均不產(chǎn)生時(shí)間成本，只有在客戶(hù)時(shí)間窗外產(chǎn)生累積的情況下生成時(shí)間成本。具體情況如下：1) 在時(shí)間窗的最早時(shí)間之前送達(dá)，該批貨物會(huì)因客戶(hù)無(wú)法及時(shí)接受而堆積；2) 在時(shí)間窗最晚之后到站，客戶(hù)會(huì)消耗等待時(shí)間。以上2種情況均計(jì)算在時(shí)間成本內(nèi)，其他時(shí)間成本不計(jì)入模型中。時(shí)間成本模型如下：

1.3.2 車(chē)輛成本

假設(shè)車(chē)輛成本包括地鐵列車(chē)成本和地面物流車(chē)輛成本，均與開(kāi)行趟數(shù)相關(guān)，與列車(chē)開(kāi)行距離無(wú)關(guān)，則車(chē)輛成本為：

式中：Ccar為車(chē)輛成本；C1為每趟地鐵列車(chē)的固定開(kāi)行成本；C2為地面配送車(chē)輛每趟開(kāi)行成本；Nv為地面配送車(chē)輛的總開(kāi)行次數(shù)。

1.3.3 物流運(yùn)輸成本

物流運(yùn)輸成本包含地上和地下兩部分，將運(yùn)輸過(guò)程中產(chǎn)生的相關(guān)費(fèi)用平攤到運(yùn)輸單價(jià)中，且各相關(guān)配送點(diǎn)的快件需求量已知。運(yùn)輸成本模型如下:

1.3.4 總成本模型

綜合時(shí)間成本、車(chē)輛成本和貨物運(yùn)輸成本，構(gòu)建總成本模型如下：

minC=Ctime+Ccar+Ctrans

即：

模型約束條件如下：

(1)

?d′∈VD′，?d∈VD

(2)

(3)

(4)

(5)

式(1)約束時(shí)間窗條件下時(shí)間早晚；式(2)表示2個(gè)變量均為0～1變量；式(3)表示每趟地鐵列車(chē)所運(yùn)輸?shù)呢浳锊坏贸^(guò)其單次最大載運(yùn)量；式(4)表示地面配送車(chē)輛每次配送的客戶(hù)需求總量不超過(guò)其最大載運(yùn)量；式(5)表示每個(gè)客戶(hù)只服務(wù)一次，即地面配送車(chē)輛只經(jīng)過(guò)一次。

該目標(biāo)函數(shù)為線性函數(shù)，目標(biāo)函數(shù)集為凸集，在可行域范圍內(nèi)存在最優(yōu)可行解。

2 求解算法

2.1 求解步驟

采用遺傳算法對(duì)模型進(jìn)行求解，求解過(guò)程見(jiàn)圖1。

圖1 模型的計(jì)算過(guò)程

2.2 算法主要術(shù)語(yǔ)

(1) 染色體。又稱(chēng)為基因型個(gè)體，一定數(shù)量的染色體組成群體。

(2) 適應(yīng)度。個(gè)體對(duì)所處環(huán)境的適應(yīng)程度，該算法中每個(gè)個(gè)體的適應(yīng)度通過(guò)輪盤(pán)賭選擇法獲取，生成[0,1]之間的隨機(jī)數(shù)作為適應(yīng)度值。

(3) 選擇。淘汰不好的個(gè)體，保留優(yōu)質(zhì)個(gè)體。

(4) 交叉。將父代個(gè)體的部分結(jié)構(gòu)加以替換重組，產(chǎn)生新個(gè)體。

(5) 變異。群體中某些個(gè)體(串)的基因值發(fā)生變動(dòng)。

3 實(shí)例計(jì)算與結(jié)果分析

南京南站是華東地區(qū)最大的高鐵站，每天會(huì)有大量快件到達(dá)南站，再由地面配送車(chē)輛送到客戶(hù)手中。借助南京南站現(xiàn)有地鐵資源，可在不影響客運(yùn)的前提下實(shí)現(xiàn)地下物流配送，減緩地面交通壓力。地鐵1號(hào)線經(jīng)停的中轉(zhuǎn)站有3個(gè)，分別為中華門(mén)站、珠江路站、邁皋橋站。3個(gè)車(chē)站服務(wù)的主要客戶(hù)共29個(gè)，且每個(gè)客戶(hù)每趟配送只有一次。統(tǒng)計(jì)客戶(hù)需求時(shí)間作為軟時(shí)間窗，即9：00—9：45和20：15—21:00，分別記為[0,45]、[45,90] min(見(jiàn)表1)。

表1 客戶(hù)時(shí)間窗

運(yùn)用上述模型，對(duì)相關(guān)參數(shù)進(jìn)行定義，采用遺傳算法對(duì)29個(gè)客戶(hù)進(jìn)行迭代求解，迭代次數(shù)為200次，種群規(guī)模為20個(gè)，交叉概率為0.8，變異概率為0.2。結(jié)合每個(gè)客戶(hù)的需求量和時(shí)間窗，計(jì)算得到10條配送優(yōu)化路徑(見(jiàn)表2、圖2)，優(yōu)化過(guò)程見(jiàn)圖3。由圖3可知：實(shí)現(xiàn)帶時(shí)間窗地下物流配送可有效節(jié)約配送時(shí)間，極大提高工作效率，緩解市區(qū)內(nèi)因物流配送導(dǎo)致的交通壓力。

表2 快件配送優(yōu)化線路

圖2 快件配送優(yōu)化路徑連線圖

圖3 路徑優(yōu)化過(guò)程

根據(jù)調(diào)查統(tǒng)計(jì)結(jié)果，近5年南京南站單獨(dú)使用貨車(chē)配送的平均配送時(shí)間為113.2 min/次，運(yùn)輸成本為21 039元/次。運(yùn)用上述優(yōu)化模型，采用地上、地下綜合配送模式的平均消耗時(shí)間為32 min/次，運(yùn)輸成本為11 044元/次，分別比貨車(chē)單獨(dú)配送降低71.73%、47.51%，而且有效緩解了物流帶來(lái)的運(yùn)輸壓力。

4 結(jié)語(yǔ)

該文主要研究客戶(hù)軟時(shí)間窗條件下地下物流配送的路徑優(yōu)化。通過(guò)構(gòu)建貨物運(yùn)輸成本、車(chē)輛成本和時(shí)間成本綜合最小的目標(biāo)函數(shù)，引入遺傳算法，采用MATLAB軟件實(shí)現(xiàn)選擇、交叉、變異等，得到優(yōu)化的物流配送路徑。與傳統(tǒng)貨車(chē)單獨(dú)運(yùn)輸比較，客戶(hù)軟時(shí)間窗下地下物流配送可節(jié)約配送時(shí)間、降低配送成本。

文中未涉及地鐵列車(chē)運(yùn)行的時(shí)間窗，無(wú)法最貼切反映配送過(guò)程。地下綜合物流配送系統(tǒng)模型還處于起步階段，如何將多條配送線路相協(xié)調(diào)，實(shí)現(xiàn)取送貨物雙向運(yùn)輸，是未來(lái)研究方向。