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

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

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

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

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

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

框架式物流車(chē)；定時(shí)配送；混合遺傳算法

0 引言

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

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

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

約束條件：

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

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

2 混合遺傳算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 應(yīng)用實(shí)例

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

圖1 框架式物流車(chē)

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

圖2 工位示意圖

圖3 加入物料箱后布局圖

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

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

圖2所顯示的是route1的行駛配送路線；圖3的11、12、13、14工位為物料箱放置點(diǎn)，現(xiàn)有的行駛路線中每90分鐘單獨(dú)用一輛物流車(chē)對(duì)四個(gè)廢品料箱進(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)場(chǎng)的實(shí)際情況給出的，Cr是將工人的月工資折合成天進(jìn)行計(jì)算180元/（天*人），Ce是工業(yè)耗電費(fèi)用0.8896元/kwh，Cl為2元/km，Cb為8元/km，Cz為0.1元/km，P為2.8kw/h。

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

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

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

表7 成本差異表

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

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

圖4 算法收斂對(duì)比圖

4 結(jié) 論

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

[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] 錢(qián)艷婷.多動(dòng)態(tài)目標(biāo)車(chē)輛路徑問(wèn)題的算法研究[D].天津：天津大學(xué)（碩士學(xué)位論文），2011.

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

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

[8] 張瑞峰，汪同三.新型遺傳算法求解車(chē)輛路徑問(wèn)題研究[J].湖北大學(xué)學(xué)報(bào)，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-），男，吉林長(zhǎng)春人，沈陽(yáng)工業(yè)大學(xué)機(jī)械工程學(xué)院工業(yè)工程系主任，教授，工學(xué)博士，中國(guó)機(jī)械工程學(xué)會(huì)工業(yè)工程分會(huì)理事，研究方向：精益生產(chǎn)、計(jì)算機(jī)輔助監(jiān)控、管理信息系統(tǒng)、質(zhì)量管理與控制、設(shè)施規(guī)劃與物流分析；張 卉（1991-），女，遼寧沈陽(yáng)人，沈陽(yáng)工業(yè)大學(xué)機(jī)械工程學(xué)院碩士研究生，研究方向：設(shè)施規(guī)劃與物流分析。