動態(tài)路網(wǎng)下物流配送中心選址-路徑優(yōu)化算法及實現(xiàn)分析

徐穩(wěn)

（西北工業(yè)大學，陜西西安 710068)

0 引言

隨著中國經(jīng)濟的快速發(fā)展，物流產(chǎn)業(yè)成為促進地區(qū)經(jīng)濟發(fā)展的重要因素。物流中心的布局規(guī)劃、物流配送、車輛路徑的綜合優(yōu)化是物流系統(tǒng)的三個重要環(huán)節(jié)，選址優(yōu)化直接影響物流服務(wù)的整體效率和成本。同時，還能通過規(guī)?；\輸、優(yōu)化的庫存控制以達到企業(yè)節(jié)約成本的目的。傳統(tǒng)的LRP 問題算法無法處理的問題,是基于靜態(tài)網(wǎng)絡(luò)結(jié)構(gòu)過程中，始終具有爭議的時間問題，即在動態(tài)網(wǎng)絡(luò)結(jié)構(gòu)過程中的到達邊權(quán)時間,與抵達邊尾點的時間無關(guān)。

1 數(shù)學模型建立

1.1 動態(tài)路網(wǎng)的時間依賴函數(shù)

從車輛運輸理論模型的具體和實際應(yīng)用兩個角度進行分析。探討LRP 問題，提出基于時間依賴函數(shù)的假設(shè)和基本架構(gòu)（如圖1）。IKUGA 等人進行研究，并采用離散行進時間速度依賴時間函數(shù)。由于該離散運動依賴時間函數(shù)直接由動態(tài)行進依賴時間函數(shù)代替，所以該動態(tài)道路網(wǎng)絡(luò)函數(shù)是比較先進的先出準則[1]。

圖1 路網(wǎng)時間依賴函數(shù)

1.2 車輛行駛速度的分布

基于上述相關(guān)理論分析研究，為了更加全面、精確地獲得車輛在中國城市實際道路路網(wǎng)結(jié)構(gòu)形式上，所采用配送運輸模式的實際使用情況。

在LRP 模型的假設(shè)和應(yīng)用設(shè)計中，根據(jù)不同時段、不同路段的速度以及不同道路限速的情況，給出了假設(shè)條件。

當各個道路的交通密度差異很大時，也就是在城市的平均擁堵高峰時段，理論上，車速分布一定要遵循上述正態(tài)分布；在道路流量密度相對較高的路段，也就是通行高峰時段的平均車速分布，應(yīng)當遵循兩個對數(shù)的正常分配，如式（1）所示。

式（1）中:tn1為暢通時間段；tn2為一般時間段;tn3為高峰時間段；μ 為不同時期的期望車速值；σ 為不同時間范圍內(nèi)的標準速度差異。其中f[v(t)]為暢通時段、普通時段、高峰時段進行對比。

1.3 動態(tài)道路路網(wǎng)跨時段車輛行駛時間

給定路網(wǎng)G(V、A、T)。其中V 是非空結(jié)點集；A是有限邊集；用ωi、ωj表示從結(jié)點ωi到結(jié)點ωj的有向邊；Tn表示在tn時段結(jié)點ωi到結(jié)點ωj的行駛時間；設(shè)車輛從結(jié)點ωj由t0時刻出發(fā)到達結(jié)點ωin的過程中經(jīng)過了N 個時段,其中第N 個時段的端點為MN,MN+1;設(shè)ωi1與ωin之間的距離為d；tk時段車輛的行駛速度為en；由旅行速度時間依賴函數(shù)可得車輛行駛的總旅行時間為式（2）：

到達結(jié)點ωin時間為式（3）：

經(jīng)整理得到式（4）：

te為結(jié)點ωi1出發(fā)時刻t0的增函數(shù)，滿足FIFO準則。

1.4 路網(wǎng)靜態(tài)約束的影響

通過對近年來物流理論研究成果的分析，許多研究人員沒有認真考慮物流配送與運輸系統(tǒng)復雜的微觀現(xiàn)實物流地理結(jié)構(gòu)和整個物流網(wǎng)絡(luò)的布局，以及優(yōu)化規(guī)劃方法對物流車輛整體配送、對運輸計劃的潛在經(jīng)濟影響。在未來的實施方式中，由于距離矩陣當前是歐幾里得距離矩陣，所以在Cartesia 坐標中將配電網(wǎng)建模為各個點時，D=（dij）。因此，不能考慮交通管制的主要原因，如路面速度限制、轉(zhuǎn)向延遲、單向限制等。實際道路網(wǎng)絡(luò)中節(jié)點之間的實際距離比歐幾里得距離復雜。如圖2所示，實際距離1～2、2～5 是由于一個線路的限制。因此，OD 成本矩陣D=OD（i,j）被用作網(wǎng)絡(luò)距離矩陣。在建立網(wǎng)絡(luò)模型的連通策略之后，通過構(gòu)建混疊單元，將混疊延遲轉(zhuǎn)換成網(wǎng)絡(luò)的邊緣權(quán)重。此外，在定義一條線段的屬性之后，Dijkstra 算法獲得了富屬性網(wǎng)絡(luò)，其可以稱為道路網(wǎng)絡(luò)的源節(jié)點和目的節(jié)點之間的實際距離OD（i,j）。

圖2 有向富屬性網(wǎng)絡(luò)

2 實例分析與應(yīng)用

基于提出的算法，在杭州市實際路網(wǎng)數(shù)據(jù)上進行動態(tài)路網(wǎng)下LRP 問題的求解，建立的杭州市富屬性網(wǎng)絡(luò)模型(如圖3所示)中,結(jié)點數(shù)為88164,邊(edge)數(shù)為95883，其中主干道路段數(shù)為50193，支干道路段數(shù)為36969[2]。

圖3 富屬性網(wǎng)絡(luò)

2.1 基于空間連通性的動態(tài)路網(wǎng)路段阻抗設(shè)置

通過內(nèi)置的杭州富屬性路網(wǎng)模型設(shè)定區(qū)間屬性值，可以進一步計算節(jié)點之間的實際矢量距離，以及指定轉(zhuǎn)向符號所需的交點。單線邊界場的設(shè)定是在向量化方向與一條線的方向平行的情況下，設(shè)定為FT，否則設(shè)定為TF 屬性。在[道路質(zhì)量]（Road Quality）字段中指定3 個值：1、2、3，再利用Dijkstra 算法，求出源結(jié)點與目標結(jié)點間的最小時間傳輸費用為D(i，j，tn,ti)，并在t 周期的t 時刻從節(jié)點i 開始，由D(i,j,ti)到j(luò)。在優(yōu)化過程中，由于對時間t 未知，所以D(i,j,tn,ti）會隨著時間的推移而改變，而路網(wǎng)權(quán)值也不固定?；诖耍瑸榻鉀Q基于時間優(yōu)化的動態(tài)網(wǎng)絡(luò)模型的問題，引入一種在不同時期更新4OD 網(wǎng)絡(luò)的方法，點計數(shù)協(xié)議是針對任意斷點協(xié)議而構(gòu)成的。

2.2 參數(shù)設(shè)置

在以上分析的基礎(chǔ)上，提出一種基于該方法的協(xié)作式啟發(fā)式方法，并在此基礎(chǔ)上建立一種新的交通網(wǎng)絡(luò)模型，并給出新的LRP 問題。針對杭州市問題，一家大型跨國物流公司至少有10 個以上的國際物流中心的問題，建立了一個動態(tài)的選址中心-配送運營中心問題模型，并給出相應(yīng)的解決方案，要求必須在兩大公司至少10 家物流車輛配送營運中心中隨機選擇一個最合適的位置，選擇其中至少4 家公司為車輛配送運營中心，以便在動態(tài)交通條件下的車輛分配和運輸路線，對總的固定費用和總費用進行比較。

快速路、主干路、支路3 種類型的道路，其中，高速公路設(shè)計速度為70km/h，主干路為50km/h，支路為30km/h；該條款列出了各地區(qū)配送中心的平均每天工作時間窗口，分別設(shè)計為平均每天早晨8∶00 至次日20∶00，不應(yīng)僅考慮平均每個用戶點每日的卸貨工作時間。不需要單獨考慮平均每個用戶點日的平均工作時間窗，具體計算及參數(shù)設(shè)置形式均如表1所示；同時，50 家客戶點平均每日的貨物需求量，均如表1所示。在算法與參數(shù)的合理設(shè)置的基礎(chǔ)上，遺傳算法和種群規(guī)模大小各取前20；而染色體變異概率取0.5，精英個數(shù)取2。

表1 速度分布參數(shù)

2.3 試驗結(jié)果及分析

配送中心每年自農(nóng)歷1月份至10月份以來擁有并運營的固定運輸車輛數(shù)，每年平均每個月四輛車，發(fā)運每一輛的固定車次配送的運輸車輛的固定成本每年為平均每天約300 元，F(xiàn)=平均每月約300 元/輛；每次運輸車輛單位時間內(nèi)，每天消耗的實際物流運輸服務(wù)總成本大約為人民幣20 元/m3。在物流配送轉(zhuǎn)運中心，在每日上午8∶00 起開始進行對外物流營業(yè)輸送服務(wù)運營時，每增加一輛物流配送運輸車則每天的物流配送正常運營發(fā)車開始的具體時間點，都統(tǒng)一確定為每日早晨8∶00 左右；在這種情況下，用“星形”表示10 個待選擇的配送中心；“方形”代表50 個顧客點。

3 結(jié)語

著重對基于動態(tài)網(wǎng)絡(luò)模型的LRP 問題的設(shè)計進行深入而系統(tǒng)的研究，該設(shè)計是利用遺傳算法和螞蟻算法進行交互轉(zhuǎn)化協(xié)作的啟發(fā)式算法。通過分析試驗得出，該算法是在通過設(shè)計中，引入另一個基于NNC 算法的初始化策略后，在一定收斂性基礎(chǔ)上，進一步提高了算法本身的收斂率；同時，利用仿真退火的方法，對最大最小螞蟻系統(tǒng)進行動態(tài)修正，提升了物流優(yōu)化問題的簡單性，使其實現(xiàn)路徑優(yōu)化。