基于遺傳算法轎車焊裝車間車輛路徑優化

馮愛軍， 胡小建 （合肥四十三研究所，安徽 合肥 230022）

基于遺傳算法轎車焊裝車間車輛路徑優化

馮愛軍， 胡小建 （合肥四十三研究所，安徽 合肥 230022）

遺傳算法是一種模擬自然進化過程搜索最優解的方法。通過建立某轎車焊裝車間車輛路徑問題數學模型，然后利用遺傳算法求解該問題，最后在Matlab軟件中進行編程求解，有效地求解出問題的最優解或近似最優解。

遺傳算法；Matlab；車輛路徑；焊裝車間

車輛路徑問題是指一定數量的顧客點，每個顧客點都有自己的貨物需求量，供貨中心需要向各個顧客點配送貨物，貨物配送需由一個車隊來負責，組織合適的車輛行進路線，并在滿足一定的約束條件下 （如客戶貨物的需求量，車輛載重量等），達到一定的目標 （如路程最短，成本最少，耗時最少等）。

1 建立數學模型

1.1 問題描述

車輛行進路徑的優化可描述為：從供貨中心使用多輛車向多個顧客點配貨，每個顧客點的位置和需求量都是一定的，車輛載重一定，要求合理安排車輛行進路徑，使總的行進路程最短，并要求滿足下列兩個條件：

①各個行進路徑上各顧客點的貨物需求量總和不能超過車輛的額定載荷；

②每個顧客點的需求必須能夠得到滿足，并且只能由其中一輛車進行配送。

1.2 建立模型

假設供貨中心擁有K輛車，每輛車的額定載量是Qk，它一次配貨的最大行進距離是Dh，需要向L個顧客需求點配貨，顧客點i的貨物需求量是qi，供貨中心到顧客點i的距離是doi，顧客點i到j的距離為dij，再假設nk為第K臺車配送貨物的顧客數 （nk=0指示為未使用第K臺車），使用集合Rk表示第k條路徑，它們中的元素rki表示顧客點rki在路徑k中的順序為i（不包括供貨中心），當rki=0表示供貨中心，則可建立以下優化物流車輛路徑的數學模型：

2 遺傳算法的基本思想

標準的遺傳算法包括3個基本的操作：選擇、交叉和變異。其步驟描述如下：

圖1 標準遺傳算法的流程圖

（1）產生初始種群，并評價初始種群中每個個體的適應度值。

（2）判斷收斂準則是否符合條件。若符合，則輸出相應的搜索結果；否則執行以下步驟。

（3）根據適應度大小按照一定方式執行選擇操作。

（4）根據交叉概率Pc執行相應的交叉操作。

（5）根據變異概率Pm執行相應的變異操作。

（6）返回步驟 （2）。

3 實例計算

根據上述遺傳算法在Matlab中進行編程，并針對某轎車焊裝車間為實例進行求解。

某轎車焊裝車間有一庫房供貨中心，該供貨中心坐標為 （74,10），供貨中心有5輛拖車，每個拖車最大載量為3個標準托盤，需要向15個點送貨，15個點的坐標和貨物需求量見表1。

實驗中采用下列參數；種群大小取80，交叉概率取值為0.65，變異概率取值為0.005，終止代數設置為200，在Matlab中隨機求解10次，第2次就獲得了最優解，最優解為1 524.2336m。各供貨點和倉庫坐標顯示如圖2，求解結果如圖3。因此車輛路徑具體安排如下：

表1 送貨點坐標和貨物需求

①1-7-11-16-1； ②1-15-9-8-1； ③1-14-4-5-1； ④1-2-13-6-1； ⑤1-20-3-12-1。

4 結 論

實驗結果表明，運用遺傳算法可以有效地快速地求得該轎車焊裝車間車輛路徑安排的最優解或近似最優解，很好地解決車輛路徑如何安排的問題。

[1]蔡希賢，夏士智.物流合理化的數量方法[M].武漢：華中工學院出版社，1985.

[2]Holland J.遺傳算法的基本理論與應用[M].李敏強,譯.北京：科學出版社，2003.

[3]李軍，郭耀煌.物流配送車輛優化調度理論與方法[M].北京：中國物資出版社，2001.

[4]趙剛.物流運籌[M].成都：四川人民出版社，2002.

[5]陳國良，王煦法，莊鎮泉,等.遺傳算法及其應用[M].北京：人民郵電出版社，1996．

[6]姜大立，楊西龍，杜文,等.車輛路徑問題的遺傳算法研究[J].系統工程理論與實踐，1999,19(6)：40-44.

[7]米凱利維茨Z．演化程序——遺傳算法和數據編碼的結合[M].北京：科學出版社，2000.

Optimizing of Vehicle Routing Problem of Car Welding Workshop Based on Genetic Algorithm

FENG Ai-jun,HU Xiao-jian(Hefei Institute 43.,Hefei 230022,China)

Genetic algorithm is a method which simulates natural evolution search optimal solution.By establishing a car welding workshop vehicle routing problem mathematical model,and by using the genetic algorithm to solve the problem,and finally we programme in Matlab software and effectively get the problem's optimal solution or approximate optimal solution.

genetic algorithm;matlab;VRP;welding workshop

F273

A

1002-3100(2011)10-0119-03

2011-08-22

馮愛軍（1986-），男，安徽亳州人，合肥四十三研究所碩士研究生，研究方向：物流管理及信息化。