基于遺傳算法的配送中心路徑優(yōu)化研究

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

（1.西安中車永電捷力風(fēng)能有限公司，陜西 西安 710018；2.陜西工業(yè)職業(yè)技術(shù)學(xué)院，陜西 咸陽 712000）

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

1 研究背景

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

2 VRPTW模型的構(gòu)建

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

2.1 基本假設(shè)

據(jù)實(shí)際調(diào)研分析，對VRPTW分析過程中進(jìn)行如下假設(shè)[3]：

（1）各需求點(diǎn)的地理位置坐標(biāo)以及貨物需求量已知；

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

（3）運(yùn)輸車輛信息已知；

（4）配送過程中各需求點(diǎn)經(jīng)過有且僅有一次。

2.2 懲罰函數(shù)

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

2.3 數(shù)學(xué)模型

建立數(shù)學(xué)模型，主要考慮兩方面成本，即時間成本最小和車輛數(shù)最少，不僅提高車輛配送效率，同時節(jié)省車輛，降低車輛相關(guān)的費(fèi)用。數(shù)學(xué)模型如下所示：

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

3 案例分析

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

表1 配送任務(wù)特征描述

3.1 算法參數(shù)設(shè)置

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

3.2 結(jié)果分析

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

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

表2 實(shí)驗結(jié)果

圖1 GA多次運(yùn)行均值收斂圖

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

4 結(jié)論

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