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

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

（沈陽工業大學 機械工程學院，遼寧 沈陽 110870）

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

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

（沈陽工業大學 機械工程學院，遼寧 沈陽 110870）

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

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

0 引言

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

1 問題描述和數學模型建立

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

約束條件：

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

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

2 混合遺傳算法

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

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

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

其中：minC為目標函數，αi為退火罰因子，隨著混合遺傳操作的進行，溫度隨之降低，目標函數越小，適應度函數的值越大，適應性越強，個體越優秀，反之個體越差，而適應度函數值越大的有更大的機會去繁殖后代個體，使優秀的基因能夠遺傳下去。

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

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

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

假設現有兩個個體At和Bt，現進行交叉，經過非均勻算數交叉后的個體為：

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

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

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

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

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

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

（8）求得最優解。

3 應用實例

框架式物流車因其轉彎半徑小且子車可以根據生產現場需求狀況串聯使用而具有諸多優點。且可以很好地彌補定時配送的缺點，提高配送效率。其外觀如圖1所示。

圖1 框架式物流車

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

圖2 工位示意圖

圖3 加入物料箱后布局圖

現有行駛路線如表1所示。

表1 現有行駛路線

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

各工位及各工位之間的相關情況如表2至表6所示：

表2 各工位所需零件重量

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

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

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

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

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

原路徑由于成本因素單一、數據對稱導致的成本差異如表7所示。

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

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

表7 成本差異表

表8 優化結果對比

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

圖4 算法收斂對比圖

4 結 論

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

[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] 錢艷婷.多動態目標車輛路徑問題的算法研究[D].天津：天津大學（碩士學位論文），2011.

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

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

[8] 張瑞峰，汪同三.新型遺傳算法求解車輛路徑問題研究[J].湖北大學學報，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-），男，吉林長春人，沈陽工業大學機械工程學院工業工程系主任，教授，工學博士，中國機械工程學會工業工程分會理事，研究方向：精益生產、計算機輔助監控、管理信息系統、質量管理與控制、設施規劃與物流分析；張 卉（1991-），女，遼寧沈陽人，沈陽工業大學機械工程學院碩士研究生，研究方向：設施規劃與物流分析。