張新敏，張 卉，蕭綺琪 ZHANG Xinmin,ZHANG Hui,XIAO Qiqi

（沈陽工業(yè)大學(xué) 機(jī)械工程學(xué)院，遼寧 沈陽 110870）

基于混合遺傳算法的框架式物流車配送路徑優(yōu)化

張新敏，張 卉，蕭綺琪 ZHANG Xinmin,ZHANG Hui,XIAO Qiqi

（沈陽工業(yè)大學(xué) 機(jī)械工程學(xué)院，遼寧 沈陽 110870）

框架式物流車是一種承載量高、配送物品多樣化、配送過程穩(wěn)定、裝卸物品方便、節(jié)省能耗的物流配送車輛。對于節(jié)拍性較強(qiáng)、生產(chǎn)工位需求多樣且需求量大的生產(chǎn)現(xiàn)場物料需求特點，框架式物流車無疑是最佳選擇。文章針對一條定時配送的裝配生產(chǎn)線以成本最小為目標(biāo)進(jìn)行配送路徑優(yōu)化。由于配送過程中還要進(jìn)行廢品料箱的回收且與物料配送不同時進(jìn)行，所以優(yōu)化后的配送路徑不唯一。對于優(yōu)化過程中遺傳算法易陷入局部最優(yōu)解及易早熟的缺點，文章設(shè)計了一種混合式遺傳算法，將模擬退火法及遺傳算法相結(jié)合，以加快收斂速度得到全局最優(yōu)解，最后通過實際分析來驗證方法的可行性。

框架式物流車；定時配送；混合遺傳算法

0 引言

框架式物流車具有轉(zhuǎn)彎半徑小、承載量高、配送物料多樣化、配送過程穩(wěn)定、裝卸物品方便、節(jié)能等優(yōu)點，因此在節(jié)拍性強(qiáng)，生產(chǎn)工位需求多樣且需求量大的汽車裝配生產(chǎn)車間成為一種重要的物料運(yùn)輸設(shè)備。對其路徑進(jìn)行科學(xué)合理規(guī)劃對保證生產(chǎn)物流需求、降低物流成本有重要意義。車輛路徑問題（VRP）的研究自Dantzig[1]首次提出以來一直受到關(guān)注。Juny[2]等人改進(jìn)了啟發(fā)式算法，避免了優(yōu)化過程中出現(xiàn)局部最優(yōu)解。Subramanian[3]等人提出將邊訪問次數(shù)作為新模型，構(gòu)造出Lazy約束來調(diào)整路徑，進(jìn)而增加解的可行性。Goksal[4]等人將PSO和VND方法進(jìn)行混合，用這種混合方法來求解VRP問題。國內(nèi)對于VRP問題的研究相比國外發(fā)展的較晚，錢艷婷[5]將時間點等時間窗的概念加入到動態(tài)車輛路徑問題中，并結(jié)合節(jié)約法和禁忌搜索法來高效地解決動態(tài)路徑規(guī)劃的問題。邢永峰[6]將正向和逆向物流結(jié)合成一個整體來看待，用自適應(yīng)算法求出最優(yōu)解，大大提高了運(yùn)算的效率。近年來也有許多學(xué)者研究了用改進(jìn)遺傳算法解決VRP問題[7-8]。與一般的VRP不同的是，框架式物流車在進(jìn)行生產(chǎn)物流配送時是多輛車對多個工位的求解問題，在其途經(jīng)的若干站點往往還要回收廢品物料且數(shù)量和與物料的正常配送時間間隔不同，即需要考慮廢料的產(chǎn)生與物料配送的關(guān)系，導(dǎo)致優(yōu)化路徑存在多樣性。本文的數(shù)學(xué)模型就是綜合以上多種因素結(jié)合以成本最小為目標(biāo)構(gòu)建的。遺傳算法是其求解的一種典型算法，針對遺傳算法的不足，本文設(shè)計了一種混合遺傳算法實現(xiàn)對多個框架式物流車的路徑規(guī)劃。

1 問題描述和數(shù)學(xué)模型建立

本文中物流車輛配送行駛路徑問題可以描述為：生產(chǎn)線有一個配送中心，共有m輛物流配送車，一共有n個工位需要進(jìn)行物料配送，即n（ n=0,1,2,…,n ）個需求點，工位i的需求量為qi，0≤qi≤Qk，i=1,2,3,…,n，k=1,2,3,…,m，其中Qk表示車輛k的承載能力，以配送成本最低為目標(biāo)建立的目標(biāo)函數(shù)為：

約束條件：

其中：P表示物流配送車的額定功率，ρr表示車輛行駛工況系數(shù)，ρk表示生產(chǎn)現(xiàn)場道路擁堵系數(shù)，Ce表示工業(yè)耗電單價，Cl表示單位里程輪胎磨損成本，Cb表示單位里程保修費用，Cz表示單位里程折舊費用，Cr表示人工每天成本，θij表示工位i到工位j的行駛速度，Dij表示工位i到工位j的行駛距離。

式（4）確保到達(dá)各工位的車輛最終會駛離，式（5）、式（6）確保每個工位只能被分配到一條路徑中，式（7）約束了每輛車的載重不能大于額定載重量。

2 混合遺傳算法

遺傳算法能以較大的概率搜索出最優(yōu)解，但是容易早熟。模擬退火法可避免陷入局部最優(yōu)解，能夠保證全局最優(yōu)解的可靠性。針對兩種算法的特點，將兩種算法結(jié)合，形成一種混合遺傳算法，結(jié)合后將遺傳算法的種群進(jìn)化變成單個個體進(jìn)行進(jìn)化，進(jìn)化過程由交叉和變異變成模擬退火的過程。具體步驟如下：

（1）對染色體編碼。編碼方法常用的有實數(shù)編碼和二進(jìn)制編碼。由于使用二進(jìn)制編碼在算法運(yùn)行時效率低，而且對混合算法的實現(xiàn)產(chǎn)生負(fù)面影響，所以本文采用實數(shù)編碼的方式，也就是將真實值作為編碼，把編碼按順序連接在一起，形成個體編碼串。需要解碼時只要將每個染色體基因座上的基因值按順序賦值給變量即可。

（2）適應(yīng)度函數(shù)。適應(yīng)度代表著最優(yōu)解的優(yōu)良程度，在運(yùn)算的交叉、變異等算子以及約束條件和目標(biāo)函數(shù)的共同作用下才能構(gòu)造出個體適應(yīng)度函數(shù)。在本文設(shè)計的混合遺傳算法中可以將退火罰因子加入到適應(yīng)度函數(shù)中：

其中：minC為目標(biāo)函數(shù)，αi為退火罰因子，隨著混合遺傳操作的進(jìn)行，溫度隨之降低，目標(biāo)函數(shù)越小，適應(yīng)度函數(shù)的值越大，適應(yīng)性越強(qiáng)，個體越優(yōu)秀，反之個體越差，而適應(yīng)度函數(shù)值越大的有更大的機(jī)會去繁殖后代個體，使優(yōu)秀的基因能夠遺傳下去。

（3）選擇操作。采用正規(guī)幾何排序選擇法。對目標(biāo)極大極小問題都適用，適應(yīng)度并不一定要求非負(fù)，不需要具體數(shù)據(jù)，只涉及個體適應(yīng)度大小順序?；舅悸肥前凑者m應(yīng)度大小對種群中的所有個體進(jìn)行排序，群體中各個個體被選中的概率為:

其中：q為最優(yōu)個體的可能性，在 0,0.（ ）1范圍內(nèi)變化，由編程后臺取得；r是個體的排序編號；M是種群規(guī)模。

（4）交叉操作。用非均勻算數(shù)交叉。將完成選擇后的個體進(jìn)行交叉運(yùn)算，非均勻算數(shù)交叉的具體方法如下：

假設(shè)現(xiàn)有兩個個體At和Bt，現(xiàn)進(jìn)行交叉，經(jīng)過非均勻算數(shù)交叉后的個體為：

其中：a=exp（-a0·T/t）；a0為非均勻交叉系數(shù)，a0的取值范圍雖然為 [0,1 ]，但是a0得取值越靠近1則交叉越均勻，所以a0的選擇不宜過大；T為進(jìn)化的最大代數(shù)；t為當(dāng)前進(jìn)化代數(shù)。

（5）變異操作。采用均勻變異，其過程為：

其中：U為變異過程中的變異算子，數(shù)值范圍為 [0,1 ]，Umax為變異能達(dá)到的最大值；Umax（xk）為當(dāng)前個體xk最大的變異值；c1,c2是均勻分布在 [0,1 ]上的隨機(jī)數(shù)，c1=1-c2，具體數(shù)值精確到小數(shù)點后一位。

（6）模擬退火操作。經(jīng)過遺傳算法的交叉變異操作后將新得到的個體帶入到模擬退火算子的計算中，以得到新的個體。

（7）動態(tài)的交叉和變異。當(dāng)遺傳算法進(jìn)化到不同時期時，如果交叉率和變異率始終取相同值會影響算法的進(jìn)化，尤其到了后期，個體的相似度較高，變異率應(yīng)該變大，交叉率而應(yīng)減小，以此來減輕交叉作用增強(qiáng)變異作用。

其中：Fmin是存活下來的個體的最小適應(yīng)度數(shù)值；F為存活下來所有個體的適應(yīng)度數(shù)值的平均數(shù)；F'是比較交叉后兩個個體的適應(yīng)度數(shù)值中較小的值；y和u是不同的調(diào)整系數(shù)，取值在 0,（ ）1之間。

（8）求得最優(yōu)解。

3 應(yīng)用實例

框架式物流車因其轉(zhuǎn)彎半徑小且子車可以根據(jù)生產(chǎn)現(xiàn)場需求狀況串聯(lián)使用而具有諸多優(yōu)點。且可以很好地彌補(bǔ)定時配送的缺點，提高配送效率。其外觀如圖1所示。

圖1 框架式物流車

在某發(fā)動機(jī)裝配車間現(xiàn)場有10個工位均有配送需求，計量單位均為kg，滿載的額定重量為100kg，各工位之間的配送距離用Dij表示，配送中心用0表示且位置固定，物流配送車從配送中心出發(fā)，車輛所裝的貨物總重量不能超過車輛的承載，每個工位最多可被一輛物流配送車服務(wù)，在滿足配送需求下，求出最小成本的路線。在本論文中的成本包括電力消耗、保修成本、折舊成本及人工成本。生產(chǎn)線的簡圖及最初行駛路線如圖2所示，增加的廢料箱更換及回收布局圖如圖3所示。

圖2 工位示意圖

圖3 加入物料箱后布局圖

現(xiàn)有行駛路線如表1所示。

表1 現(xiàn)有行駛路線

圖2所顯示的是route1的行駛配送路線；圖3的11、12、13、14工位為物料箱放置點，現(xiàn)有的行駛路線中每90分鐘單獨用一輛物流車對四個廢品料箱進(jìn)行統(tǒng)一更換。

各工位及各工位之間的相關(guān)情況如表2至表6所示：

表2 各工位所需零件重量

表3 各工位之間的距離 Dij（ ）

表4 工位之間的行駛速度 θij（）

表5 各工位之間的行駛工況系數(shù) ρr（）

表6 各工位之間的擁堵系數(shù) ρk（）

本文中的Cr、Ce、Cl、Cb、Cz是根據(jù)生產(chǎn)現(xiàn)場的實際情況給出的，Cr是將工人的月工資折合成天進(jìn)行計算180元/（天*人），Ce是工業(yè)耗電費用0.8896元/kwh，Cl為2元/km，Cb為8元/km，Cz為0.1元/km，P為2.8kw/h。

原路徑由于成本因素單一、數(shù)據(jù)對稱導(dǎo)致的成本差異如表7所示。

利用編程求出最優(yōu)解，其中設(shè)置迭代次數(shù)為300次；交叉概率為0.8；變異概率為0.1；種群規(guī)模為30；降溫次數(shù)為100；每個溫度迭代步長為3；初始溫度為250.00；降溫系數(shù)為0.98。經(jīng)過編程運(yùn)算得到結(jié)果如表8所示。

根據(jù)實際生產(chǎn)情況，生產(chǎn)配送的時間間隔為30min，需更換廢料箱的時間間隔為90min，所以在表8中有兩種配送方案，

表7 成本差異表

表8 優(yōu)化結(jié)果對比

第一種為每30min配送，第二種為每90min配送。而對比兩種方法的收斂曲線不難發(fā)現(xiàn)，混合遺傳算法要比普通的遺傳算法收斂速度快，最優(yōu)解要優(yōu)于遺傳算法，如圖4所示：

圖4 算法收斂對比圖

4 結(jié) 論

以配送成本最小為目標(biāo)建立了生產(chǎn)線配送數(shù)學(xué)模型，將產(chǎn)生配送成本的因素加以整合，多種影響因素均轉(zhuǎn)化為車輛行駛的相應(yīng)系數(shù)并體現(xiàn)在成本中。通過所設(shè)計的混合遺傳算法求解該模型求出了成本最小的行駛路線。通過對普通遺傳算法和本文算法的對比表明，本文算法在速度，搜索范圍，局部搜索能力等方面均優(yōu)于普通遺傳算法。針對廢品料箱的更換與物料配送二者時間間隔不同的問題，運(yùn)用兩種配送方案進(jìn)行定時配送從而節(jié)省配送成本。針對生產(chǎn)線的工位需求超出物流車額定載荷的突發(fā)問題，提出了虛附加工序的方法并將其融入目標(biāo)函數(shù)中，求解結(jié)果在成本和路徑方面均優(yōu)于現(xiàn)有突發(fā)問題路徑方案，且提高了框架式物流車的利用率。

[1] Dantzig G B,Ramser J H.The truck dispatching problem[J].Managemant Science,1959(6):80-91.

[2] JUNY,KIMB.New best solutions to VRPSPD bench mark problems by a perturbationbased algorithm[J].Expert Systems with Applications,2012,39(5):5641-5648.

[3]SUBRAMANIAN A,DRUMMOND L M A,BENTES C,et al.A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery[J].Computers and Operations Research,2010,37(40):1899-1911.

[4] GOKSAL.FP,KARAOGLAN I,ALTIPARMAK F.A hybrid discrete particles warm optimization for vehicle routing problem with simultaneous pickup and delivery[J].Computers&Industrial Engineering,2013,65(1):39-53.

[5] 錢艷婷.多動態(tài)目標(biāo)車輛路徑問題的算法研究[D].天津：天津大學(xué)（碩士學(xué)位論文），2011.

[6] 邢永峰.電子商務(wù)物流系統(tǒng)中回程帶貨的車輛路徑問題研究[J].物流技術(shù)，2014(8):226-229.

[7] 王超，穆東.物料配送和廢舊產(chǎn)品回收的VRPSDP問題的并行模擬退火算法[J].北京交通大學(xué)學(xué)報，2014,38(6):19-26.

[8] 張瑞峰，汪同三.新型遺傳算法求解車輛路徑問題研究[J].湖北大學(xué)學(xué)報，2012,34(2):240-242.

Distribution Routing Optimization for U-frame Vehicle Based on Hybrid Genetic Algorithm

(School of Mechanical Engineering,Shenyang University of Technology,Shenyang 110870,China)

U-frame is a logistics vehicle which has high carrying capacity,diversification of distribution items,stable distribution process,energy-saving and it is easy to load and unload items.For the situation of workshop material distribution with distinct tact time,diverse requirements from different workstation and large demand of quantity,the U-frame is a suitable choice.The material distribution and discarded products recovery are not performed at the same time.The route is optimized with the object that the comprehensive cost is minimum.To solve the model,a combination of simulated annealing and genetic algorithm is presented to overcome defects in precocity and low convergence speed for conventional genetic algorithm.Therefore,high convergence speed and global optimal solution are obtained.At last,a route optimization is performed on material distribution to an auto assembly line to illustrate the effectiveness of the proposed method.

U-frame;regular distribution;hybrid genetic algorithm

F252.14

A

1002-3100(2017)08-0027-06

2017-05-15

張新敏（1964-），男，吉林長春人，沈陽工業(yè)大學(xué)機(jī)械工程學(xué)院工業(yè)工程系主任，教授，工學(xué)博士，中國機(jī)械工程學(xué)會工業(yè)工程分會理事，研究方向：精益生產(chǎn)、計算機(jī)輔助監(jiān)控、管理信息系統(tǒng)、質(zhì)量管理與控制、設(shè)施規(guī)劃與物流分析；張 卉（1991-），女，遼寧沈陽人，沈陽工業(yè)大學(xué)機(jī)械工程學(xué)院碩士研究生，研究方向：設(shè)施規(guī)劃與物流分析。