動態路網下物流配送中心選址-路徑優化算法及實現分析

徐穩

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

0 引言

隨著中國經濟的快速發展，物流產業成為促進地區經濟發展的重要因素。物流中心的布局規劃、物流配送、車輛路徑的綜合優化是物流系統的三個重要環節，選址優化直接影響物流服務的整體效率和成本。同時，還能通過規模化運輸、優化的庫存控制以達到企業節約成本的目的。傳統的LRP 問題算法無法處理的問題,是基于靜態網絡結構過程中，始終具有爭議的時間問題，即在動態網絡結構過程中的到達邊權時間,與抵達邊尾點的時間無關。

1 數學模型建立

1.1 動態路網的時間依賴函數

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

圖1 路網時間依賴函數

1.2 車輛行駛速度的分布

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

在LRP 模型的假設和應用設計中，根據不同時段、不同路段的速度以及不同道路限速的情況，給出了假設條件。

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

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

1.3 動態道路路網跨時段車輛行駛時間

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

到達結點ωin時間為式（3）：

經整理得到式（4）：

te為結點ωi1出發時刻t0的增函數，滿足FIFO準則。

1.4 路網靜態約束的影響

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

圖2 有向富屬性網絡

2 實例分析與應用

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

圖3 富屬性網絡

2.1 基于空間連通性的動態路網路段阻抗設置

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

2.2 參數設置

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

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

表1 速度分布參數

2.3 試驗結果及分析

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

3 結語

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