基于遺傳算法的配送中心路徑優化研究

任成渝，高賀云，王 霄 REN Chengyu,GAO Heyun,WANG Xiao

（1.西安中車永電捷力風能有限公司，陜西 西安 710018；2.陜西工業職業技術學院，陜西 咸陽 712000）

(1.Xi'an Jieli Electric Power Electronic Technology Co.,Ltd,Xi'an 710018,China;2.Shaanxi Polytechnic Institute,Xianyang 712000,China)

1 研究背景

伴隨著物流技術的不斷發展，人們對物流的效率問題日漸重視，時間成本成為制約物流發展的主要因素之一。為有效提高物流效率降低時間成本，增加客戶對物流服務的滿意度，合理安排配送時間是配送中心發展的當務之急，帶時間窗車輛路徑問題（Vehicle Routing Problem With Time Window,VRPTW）的研究，變得尤為重要[1]。

2 VRPTW模型的構建

在配送路徑優化過程中，引入時間窗的概念，不僅可以有效地貼合配送的時間需求，同時在VRPTW問題的研究過程中，成本的設定中，函數表示不僅考慮了運行成本，其中還包括了恰當時間到客戶所造成時間等待、以及服務時間[2]。

2.1 基本假設

據實際調研分析，對VRPTW分析過程中進行如下假設[3]：

（1）各需求點的地理位置坐標以及貨物需求量已知；

（2）不同的客戶同時滿足需求且配送時間區間已知；

（3）運輸車輛信息已知；

（4）配送過程中各需求點經過有且僅有一次。

2.2 懲罰函數

由實際情況分析，采用軟限制時間窗，在客戶特定的時間窗基礎上，適當擴大配送區間，超出此區間，客戶可拒絕簽收貨物，故設定極大懲罰函數，即p（t），避免超時間窗配送情況的發生，保證配送車輛在特定的時間區間到達[4]。

2.3 數學模型

建立數學模型，主要考慮兩方面成本，即時間成本最小和車輛數最少，不僅提高車輛配送效率，同時節省車輛，降低車輛相關的費用。數學模型如下所示：

其中：0表示配送中心，i（i=1,2,3,…,h）為客戶編號，s（s=1,2,…,k）車輛編號。事件發生取值為1，否則為0，式（1） 為目標函數，cij表示運輸成本，xijs表示車輛s由點i駛向點j；式（2） 和式（3） 中，yis表示客戶點i的貨運任務由車輛s來完成；式（4）中，qs表示車輛s的最大承重量；式（5）中保證了每個客戶點僅能由一輛車完成，而所有運輸任務則由k輛車協同完成。

3 案例分析

對蒲城某配送中心10家客戶，進行調研分析，各客戶的需求量為gi，服務時間ti和服務時間窗口a,［］b以及配送中心與各客戶間的距離如表1所示。車輛的載荷為10t，合理優化配送路線使總成本最小。

表1 配送任務特征描述

3.1 算法參數設置

根據本文的模型，在傳統遺傳算法的基礎上選擇合適的參數：a：運行單位時間成本取值8；b：啟用單位時間成本取值60；P：等待單位時間成本取值0.5；q：延誤單位時間成本取值為1.5。遺傳算法運行參數L：染色體長度取值50；N：種群規模取值100，pc：交叉概率取值為0.7；pm：變異概率取值0.04；Gen：終止進化代數取值100。車輛載重均為10t，車輛數s=4。

3.2 結果分析

為驗證解的有效性，本文對算例進行50次測試取得平均值，并采集實際運行數據進行比較，見表2。

上述遺傳算法算例實驗結果的最優解為使用4輛車，共生成由4條路徑組成的最優配送路徑組合，最小成本為12 518元，相比采集數據14 251元提高了13.8%。其中0代表配送中心，其他數字代表客戶，其行車方案為：0—2—9—0，0—7—8—0，0—1—3—10—0，0—4—5—6—0。

表2 實驗結果

圖1 GA多次運行均值收斂圖

圖1 為運行多次均值收斂圖，可以看出，在運行340代時趨于穩定，收斂效果好，運算速度快。

4 結論

本文根據實際調研數據分析，建立帶時間窗數學模型，并運用遺傳算法求解，通過多次實驗選擇合適參數，并將計算結果與實際采集數據進行比較，驗證所建模型和算法的可行性以及在解決蒲城某配送中心路徑優化問題上具有一定優勢。