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

郭琪， 鄭長江， 李銳

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

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

1 問題描述與建模

1.1 問題描述

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

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

1.2 模型假設(shè)

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

(2) 地鐵列車只負責配送貨物，不考慮返回過程。

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

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

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

(6) 模型中時間窗只針對末端客戶地鐵列車的開行，地鐵列車的開行配送均不考慮在其中。

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

1.3 模型建立

1.3.1 運輸時間成本

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

1.3.2 車輛成本

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

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

1.3.3 物流運輸成本

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

1.3.4 總成本模型

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

minC=Ctime+Ccar+Ctrans

即：

模型約束條件如下：

(1)

?d′∈VD′，?d∈VD

(2)

(3)

(4)

(5)

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

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

2 求解算法

2.1 求解步驟

采用遺傳算法對模型進行求解，求解過程見圖1。

圖1 模型的計算過程

2.2 算法主要術(shù)語

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

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

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

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

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

3 實例計算與結(jié)果分析

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

表1 客戶時間窗

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

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

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

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

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

4 結(jié)語

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

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