基于遺傳算法的無時限多配送中心車輛調(diào)度問題研究

[摘 要] 針對多配送中心車輛調(diào)度問題的復(fù)雜性特點，提出用最近距離分配法和遺傳算法分兩步求解多配送中心車輛調(diào)度問題，并進行了試驗計算。

[關(guān)鍵詞] 多配送中心 車輛調(diào)度 最近距離分配法 遺傳算法

一、 引言

車輛調(diào)度是物流系統(tǒng)優(yōu)化中關(guān)鍵的一環(huán)。對配送車輛的調(diào)度進行科學優(yōu)化，可以降低運輸成本，提高物流企業(yè)經(jīng)濟效益。根據(jù)配送中心數(shù)目的多少，配送車輛優(yōu)化調(diào)度問題有單配送中心車輛調(diào)度問題和多配送中心車輛調(diào)度問題之分。目前，我國一些大中型城市的物流體系中存在有多個配送中心的情況。因此，對多配送中心車輛調(diào)度問題的研究有重要的現(xiàn)實意義。

本文提出了用最近距離分配法將多配送中心車輛調(diào)度問題分解為多個單配送中心車輛調(diào)度問題進行求解的策略，利用求解單配送中心車輛調(diào)度問題的遺傳算法，設(shè)計了求解多配送中心車輛調(diào)度問題的算法，最后通過案例計算驗證了該算法的良好性能。

二、多配送中心問題轉(zhuǎn)化成單配送中心的問題

本文采用最近距離分配法將多配送中心車輛調(diào)度問題轉(zhuǎn)化成單配送中心車輛調(diào)度問題。

根據(jù)距離最近原則，決定為某客戶提供服務(wù)的配送中心。鑒于多配送中心車輛調(diào)度問題以總配送里程最短為優(yōu)化目標，計算某客戶與各配送中心的距離，該客戶離那個配送中心最近，就將其分配到那個配送中心，由該配送中心為其提供服務(wù)。

三、混合遺傳算法求解單配送中心的車輛調(diào)度問題

遺傳算法是一種“生成+檢測”的迭代搜索算法。該算法以群體中的所有個體為操作對象，每個個體對應(yīng)研究問題的一個解。選擇，交叉和變異是遺傳算法的三個主要操作算子。該算法包括以下6個基本要素:（1）編碼;(2)初始群體生成;(3)適應(yīng)度評估;(4)選擇;(5)交叉;（6)變異。

針對單配送中心無時間窗車輛路徑優(yōu)化問題的特點，構(gòu)造了求解該問題的遺傳算法。

1.自然數(shù)編碼

本文采用表示比較直觀的，容易產(chǎn)生可行解的自然數(shù)編碼方法。這種方法是直接產(chǎn)生L個1~L間的互不重復(fù)的自然數(shù)的排列，該客戶排列就構(gòu)成一個解，并對應(yīng)一個配送路徑方案。

2.初始群體的生成

本文采隨機生成的方法生成初始群體

3.適應(yīng)度函數(shù)

本文以距離最短作為目標函數(shù)，適應(yīng)度函數(shù)為目標函數(shù)的倒數(shù)，顯然適應(yīng)度越大，距離越短，被選入下一代操作的機率就越大。

4.選擇操作

本文采用最優(yōu)個體保留與賭輪選擇相結(jié)合的方法。將每代群體中的N個個體按適應(yīng)度由大到小排列，排在第一位的個體性能最優(yōu)，將它復(fù)制一個直接進入下一代，并排在第一位。下一代群體的另N-1個個體需要根據(jù)前代群體的N個個體的適應(yīng)度，采用賭輪選擇法產(chǎn)生。

5.交叉操作

本文采用順序交叉(OX）。首先選擇一個匹配區(qū)域，設(shè)兩父代個體及其匹配區(qū)域為:A=58|742|361、B=25|831|746;然后根據(jù)匹配區(qū)域的映射關(guān)系，在其區(qū)域外的相應(yīng)位置標記H，得到:A’=5H|742|H6H、B’=H5|831|HH6；再移動匹配區(qū)域至起始位置，且在其后預(yù)留相等于匹配區(qū)域的空間（H的數(shù)目），然后將其余的碼按其相對次序排列在預(yù)留區(qū)后面，得到：A”=742|HHH|65、B”=831|HHH|65；最后將父串A、B的匹配區(qū)域相互交換，并放置到A”、 B”的預(yù)留區(qū)內(nèi)，即可得到兩個后代個體：A”’=74283165、B”’=83174265。

6.變異操作

物種變異的可能性較小，所以在遺傳算法中變異操作只起輔助作用。對每代種群以變異概率Pm=0.001進行染色體變異。在此引入一種新的變異策略：逆轉(zhuǎn)變異。具體過程如下：隨機產(chǎn)生一染色體E和兩個變異點，將變異段進行逆轉(zhuǎn)得新個體E1。

E=12|5836|29→E1=12|6385|29

四、 實驗計算和結(jié)果分析

案例:某城市有3個配送中心和33個客戶，分布在一個邊長為30km的正方形地域內(nèi)，每個客戶的貨物需求量都在2t及其以下，每個配送中心有4臺車輛，車輛的載質(zhì)量均為10t，車輛一次配送的最大行駛距離均為60km。其中3個配送中心的坐標分別是:配送中心1(9.56km，6.03km)配送中心2(6.44km，11.28km）配送中心3(21.14km，21.10km），33個客戶的坐標及其貨物需求量見表.要求合理安排配送車輛的行車路線，使配送總里程最短。為簡便起見，本文設(shè)各客戶相互之間及配送中心與客戶之間的距離按照公式dij=1.2[(xi-xj)2+(yi-yj)2]1/2(km)近似計算。

采用最近距離分配法，在MATLAB里通過編程計算得到如下的分區(qū)結(jié)果：

配送中心1為9個客戶服務(wù)，客戶編號為:30，2，4，7，1，27，16，21，23;

配送中心2為13個客戶服務(wù)，客戶編號為:17，31，12，8，29，25，26，13，15，18，14，32，9；

配送中心3為11個客戶服務(wù)，客戶編號為：3，6，24，20，22，33，5，28，10，11，19。

設(shè)定交叉概率pc=0.7，變異概率pm=0.001，使用遺傳算法分別對三個配送分區(qū)構(gòu)成的單配送中心車輛調(diào)度問題隨機求解50代，得到的最優(yōu)解分別是：

配送中心1:使用一輛車，對應(yīng)的配送路徑為配送中心1-21-23-30-2-4-7-1-27-16-配送中心1，配送路徑總長度為55.07km。

配送中心2:使用兩輛車，對應(yīng)的配送路徑分別為配送中心2-12-8-29-25-26-13-15-配送中心2和配送中心2-18-14-32-9-17-31-配送中心2，配送路徑總長度為81.68km.

配送中心3:使用兩輛車，對應(yīng)的配送路徑分別為配送中心3-10-11-19-3-6-24 -20-配送中心3和配送中心3-22-33-5-28-配送中心3，配送路徑總長度為80.75km.

將上述三個配送中心的最優(yōu)解合并，即可得到該多配送中心車輛調(diào)度問題的解，該解對應(yīng)的配送方案共使用了5輛車，5條配送路線的總長度為217.5km。

五、 結(jié)束語

本文首先用最近距離分配法將復(fù)雜的多配送中心車輛調(diào)度問題轉(zhuǎn)化為簡單的單配送中心車輛調(diào)度問題，然后用遺傳算法有效地求解了單配送中心車輛調(diào)度問題。這種求解策略將復(fù)雜的問題簡單化，提高了計算效率，適用于求解大規(guī)模的多配送中心車輛調(diào)度問題。

參考文獻:

[1]郎茂祥:多配送中心車輛調(diào)度問題的模型和算法研究[J].交通運輸系統(tǒng)工程與信息，2006(5）:65～69

[2]李 軍，郭耀煌:物流配送車輛優(yōu)化調(diào)度理論與方法[M].北京:中國物資出版社，2001.93～96

[3]陳國良 王熙法 莊鎮(zhèn)泉 王東生:遺傳算法及其應(yīng)用[M]. 北京:人民郵電出版社，1996，101～106

[4]周 明 孫樹棟:遺傳算法原理及應(yīng)用[M].北京：國防工業(yè)出版社，1999.18～58

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”