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

基于遺傳算法轎車焊裝車間車輛路徑優(yōu)化

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

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

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

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

1 建立數(shù)學(xué)模型

1.1 問題描述

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

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

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

1.2 建立模型

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

2 遺傳算法的基本思想

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

圖1 標(biāo)準(zhǔn)遺傳算法的流程圖

（1）產(chǎn)生初始種群，并評價初始種群中每個個體的適應(yīng)度值。

（2）判斷收斂準(zhǔn)則是否符合條件。若符合，則輸出相應(yīng)的搜索結(jié)果；否則執(zhí)行以下步驟。

（3）根據(jù)適應(yīng)度大小按照一定方式執(zhí)行選擇操作。

（4）根據(jù)交叉概率Pc執(zhí)行相應(yīng)的交叉操作。

（5）根據(jù)變異概率Pm執(zhí)行相應(yīng)的變異操作。

（6）返回步驟 （2）。

3 實(shí)例計(jì)算

根據(jù)上述遺傳算法在Matlab中進(jìn)行編程，并針對某轎車焊裝車間為實(shí)例進(jìn)行求解。

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

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

表1 送貨點(diǎn)坐標(biāo)和貨物需求

①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 結(jié) 論

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

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

[2]Holland J.遺傳算法的基本理論與應(yīng)用[M].李敏強(qiáng),譯.北京：科學(xué)出版社，2003.

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

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

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

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

[7]米凱利維茨Z．演化程序——遺傳算法和數(shù)據(jù)編碼的結(jié)合[M].北京：科學(xué)出版社，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-），男，安徽亳州人，合肥四十三研究所碩士研究生，研究方向：物流管理及信息化。