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

2008-12-31 00:00:00田秋榮李仲興

商場現代化 2008年11期

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

[關鍵詞] 多配送中心車輛調度最近距離分配法遺傳算法

一、引言

車輛調度是物流系統優化中關鍵的一環。對配送車輛的調度進行科學優化，可以降低運輸成本，提高物流企業經濟效益。根據配送中心數目的多少，配送車輛優化調度問題有單配送中心車輛調度問題和多配送中心車輛調度問題之分。目前，我國一些大中型城市的物流體系中存在有多個配送中心的情況。因此，對多配送中心車輛調度問題的研究有重要的現實意義。

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

二、多配送中心問題轉化成單配送中心的問題

本文采用最近距離分配法將多配送中心車輛調度問題轉化成單配送中心車輛調度問題。

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

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

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

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

1.自然數編碼

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

2.初始群體的生成

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

3.適應度函數

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

4.選擇操作

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

5.交叉操作

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

6.變異操作

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

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

四、實驗計算和結果分析

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

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

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

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

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

設定交叉概率pc=0.7，變異概率pm=0.001，使用遺傳算法分別對三個配送分區構成的單配送中心車輛調度問題隨機求解50代，得到的最優解分別是：

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

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

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

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

五、結束語

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

參考文獻: