應(yīng)用混合遺傳算法的多集貨中心多車型整車路徑規(guī)劃研究

劉建勝，譚文越

（南昌大學(xué)機(jī)電工程學(xué)院，江西 南昌 330031）

1 引言

隨著汽車工業(yè)的發(fā)展，第三方整車物流（FVL）已成為汽車企業(yè)成品車物流的趨勢。作為第三利潤源泉，整車物流變得原來越重要，而配送方案的優(yōu)化則是降低物流成本的根本保證。

VRP 最早由文獻(xiàn)[1]于1959 年首次提出。根據(jù)研究的重點(diǎn)不同，VRP 有多種分類方式。如按特征分類，有裝貨問題、卸貨問題和裝卸混合問題；按車輛載貨情況分類，有滿載和非滿載問題[2]；按車場數(shù)目分類，有單車場[3]和多車場問題[4-5]；按運(yùn)輸車類型、商品車類型分類，有單車型[6]和多車型[7]問題等等。由于情況的不同，車輛路徑問題的模型構(gòu)造及算法會有很大差別。

VRP 屬于NP-hard 問題，在規(guī)模較大時(shí)很難求出精確解。其求解算法大體上可以分為精確算法、啟發(fā)式算法和智能優(yōu)化算法三大類。用于求解VRP 問題的啟發(fā)式算法有禁忌搜索、模擬退火、遺傳算法[8]、粒子群算法[9]、蟻群算法[10]等。每一種算法都有其優(yōu)勢，但是單獨(dú)工作都會存在一些缺陷；因此近些年的研究開始側(cè)重于構(gòu)造混合算法來解決實(shí)際問題。

綜上所述，與傳統(tǒng)的VRP 問題不同，著重研究具有多專業(yè)集貨中心、多種轎運(yùn)車型、多種運(yùn)輸車型，并考慮路線成本權(quán)重不同和配載幾何約束的整車運(yùn)輸車輛路徑規(guī)劃問題。同時(shí)設(shè)計(jì)出一種基于遺傳算法與粒子群算法的改進(jìn)混合遺傳算法，并通過實(shí)例仿真證實(shí)了該算法的高效性與收斂性。

2 整車批次運(yùn)輸優(yōu)化模型

2.1 問題描述

某汽車廠商的產(chǎn)業(yè)模式是集團(tuán)公司多專業(yè)集貨中心式。其在一個(gè)城市具有多個(gè)集貨中心，每一個(gè)集貨中心具有相同規(guī)格系列的商品車型。而某一物流公司在全國各地有若干個(gè)轎運(yùn)車車場，車場內(nèi)有多種轎運(yùn)車型，每種轎運(yùn)車型具有不同的載重量和規(guī)格，且一般規(guī)格大的轎運(yùn)車每單位公里的運(yùn)輸成本也會相對較高。此時(shí)汽車廠商接到一批訂單，客戶需要一批不同規(guī)格的商品車。物流公司接到汽車廠商的運(yùn)單后，根據(jù)客戶需求及實(shí)際情況，選擇一定數(shù)量相應(yīng)規(guī)格的轎運(yùn)車進(jìn)行配載，并制定每輛轎運(yùn)車的路徑規(guī)劃方案。方案制定后，如圖1 所示。轎運(yùn)車場派出若干輛轎運(yùn)車，每輛轎運(yùn)車都要按所分配任務(wù)前往各集貨中心裝載所需類型的商品車，然后運(yùn)輸至各個(gè)客戶點(diǎn)，完成運(yùn)輸任務(wù)的轎運(yùn)車回到公司的另一個(gè)轎運(yùn)車場等待下一次運(yùn)輸任務(wù)。

圖1 路徑示意圖Fig.1 Path Diagram

2.2 數(shù)學(xué)模型

2.2.1 模型假設(shè)

（1）考慮到集貨中心和客戶點(diǎn)規(guī)模對運(yùn)輸和裝卸貨成本的影響，將各中心和客戶地簡化為點(diǎn)。

（2）每個(gè)集貨中心只有一種商品車，且數(shù)量足夠多。

（3）每個(gè)客戶點(diǎn)的訂單都是小批量，均只由一輛轎運(yùn)車一次性滿足，一輛轎運(yùn)車可以完成多個(gè)客戶點(diǎn)的配送任務(wù)；

（4）運(yùn)輸處于理想狀態(tài)，不考慮自然因素帶來的風(fēng)險(xiǎn)和損失。

2.2.2 模型建立

根據(jù)以上假設(shè)，建立多集貨中心多車型整車物流模型，目標(biāo)函數(shù)為：

約束條件為：

式中：Σl、Σw—商品車的總車身長和總車身重；Lmax、Wmax—容量最大類型的轎運(yùn)車所能裝載的最大車身長和車重；n1—集貨中心數(shù)量；n2—客戶點(diǎn)數(shù)量；rk—第k 輛轎運(yùn)車的車型；ki—車型為 i 的轎運(yùn)車數(shù)量；wi、li—車型為 i 的商品車的重量與車身長；K—轎運(yùn)車的總數(shù)；aij—集貨中心i 到j(luò) 的距離；bij—客戶點(diǎn) i 到 j 的距離—第 k 輛轎運(yùn)車最后一個(gè)到達(dá)的集貨點(diǎn)pk與第一個(gè)到達(dá)的客戶點(diǎn)qk的距離—對車型為rk的轎運(yùn)車來說，從集貨中心i 到j(luò) 和從客戶點(diǎn)i 到j(luò) 的單位距離路費(fèi)—對車型為rk的轎運(yùn)車來說最后一個(gè)到達(dá)的集貨點(diǎn)pk與第一個(gè)到達(dá)的客戶點(diǎn)qk的單位距離路費(fèi)—車型為rk的轎運(yùn)車的單位距離油費(fèi)、限載重量、限載總長度；Sik—第k 輛轎運(yùn)車在集貨中心i 裝載的車型為i 的商品車數(shù)量；Dij—客戶點(diǎn)i 對商品車型j 的需求量。

式（1）和式（2）為目標(biāo)函數(shù)，分別表示轎運(yùn)車數(shù)量最小，物流總成本最低；式（3）、式（4）、式（8）為（0～1）變量；式（5）表示集貨中心流量守恒；式（6）表示轎運(yùn)車數(shù)量之和；式（7）表示轎運(yùn)車的載重限制；式（8）表示轎運(yùn)車的裝載車長限制；式（10）表示每個(gè)客戶點(diǎn)有且僅有一輛轎運(yùn)車負(fù)責(zé)配送；式（11）和式（12）表示客戶點(diǎn)流量守恒；式（13）表示供應(yīng)與需求平衡。

3 混合遺傳算法設(shè)計(jì)

遺傳算法作為一種啟發(fā)式搜索算法，在處理不連續(xù)、不可微和非凸等問題上可以取得很好的效果，并且其具有良好的全局搜索能力，可以快速搜索解空間的全局解，而不會陷入局部最優(yōu)解的快速下降陷阱。遺傳算法不依賴于問題的具體領(lǐng)域，具有很強(qiáng)的魯棒性，因此被廣泛用來解決各種復(fù)雜的優(yōu)化問題。但遺傳算法也存在明顯的缺點(diǎn)，如收斂速度慢，局部搜索能力差，控制變量多等。粒子群算法（PSO）由文獻(xiàn)[11]提出。與遺傳算法類似，PSO 是一種迭代優(yōu)化算法。與遺傳算法相比，標(biāo)準(zhǔn)PSO 具有較少的控制變量。它遵循個(gè)體極值和全局極值進(jìn)行極值優(yōu)化，易于操作和快速收斂。然而，隨著迭代次數(shù)的增加，人口收斂時(shí)，粒子越來越相似，易于陷入局部最優(yōu)解。為解決以上問題，提出一種混合算法GA-PSO，該算法結(jié)合了遺傳算法的全局優(yōu)化型和粒子群算法的快速局部搜索性能。不同于傳統(tǒng)粒子群算法中通過單純的跟蹤極值來更新粒子位置，而是引入遺傳算法中的交叉和變異操作，通過染色體與個(gè)體極值和群體極值的交叉和自身變異的方式來搜索最優(yōu)解。算法步驟如下：

圖2 算法流程圖Fig.2 Program Flow Diagram

3.1 染色體編碼

采用自然數(shù)編碼，編碼中的數(shù)組需要包含三個(gè)信息：集貨中心點(diǎn)、客戶點(diǎn)和轎運(yùn)車型號，這樣才能確定一輛轎運(yùn)車的路線方案。比如，比如：-3-1-2-6-4 16 10 M+1。這組數(shù)字表示車型為1的轎運(yùn)車從起始車場出發(fā)，先依次去集貨中心3、1、2、6 處裝載商品車，然后依次運(yùn)至客戶點(diǎn)16、10 處完成配送任務(wù)，最后回到終點(diǎn)車場。集貨中心序號前加負(fù)號是為了區(qū)分集貨中心和客戶點(diǎn)，M 代表一個(gè)絕對值很大的負(fù)數(shù)，一是為了區(qū)別于客戶點(diǎn)的數(shù)字，二是為了與下輛車的路線分割開來，且由于M 很小，所以很容易就能從數(shù)組中找到各個(gè)分割點(diǎn)；如果把上面的這串?dāng)?shù)字看成一組，那么代表一個(gè)可行解的染色體編碼就是由若干個(gè)組連接而成，一個(gè)組對應(yīng)一輛轎運(yùn)車的運(yùn)輸路線，有幾個(gè)組就代表了該方案總共用了幾輛轎運(yùn)車，很容易從編碼中得到我們所要的信息。

3.2 適應(yīng)度函數(shù)

遺傳算法使用適應(yīng)度函數(shù)值來評估個(gè)體并指導(dǎo)搜索，因此適應(yīng)度函數(shù)值的選擇非常重要，選擇不當(dāng)容易導(dǎo)致欺騙問題。其選擇標(biāo)準(zhǔn)是：規(guī)范性（單值、連續(xù)、嚴(yán)格單調(diào)），合理性（計(jì)算量?。┖途哂衅毡樾?。因此使用謝菲爾德遺傳算法工具箱中的“ranking（）”函數(shù)來獲取適應(yīng)度。經(jīng)過這樣處理后，成本較低的個(gè)體具有較大的適應(yīng)度值，并且群體的適應(yīng)度函數(shù)值將在區(qū)間（0，2）中分布更均勻。

式中：Nind—種群中個(gè)體的數(shù)量。每個(gè)個(gè)體的適應(yīng)度值根據(jù)它在排序種群中的位置Pos 計(jì)算出來；sp—指定壓差。

該算法首先對目標(biāo)函數(shù)值進(jìn)行降序排序。最小適應(yīng)度個(gè)體被放置在排序的目標(biāo)函數(shù)值列表的第一個(gè)位置。

3.3 種群初始化

要生成一定規(guī)模的種群，并且同時(shí)滿足所有的約束，應(yīng)該先生成客戶點(diǎn)，然后才能對應(yīng)生成集貨中心點(diǎn)和確定商品車需求量，具體生成有以下幾個(gè)步驟：

（1）先隨意生成一個(gè)1～20 的亂序數(shù)組

（2）選擇轎運(yùn)車車型，這里使用一個(gè)選擇結(jié)構(gòu)：

u=rand；if0＜u&u≤pau=1；

else if pa＜u&u≤pbu=2；

else u=3；

為了達(dá)到轎運(yùn)車數(shù)量最小的目標(biāo)，應(yīng)盡可能選擇容量大的轎運(yùn)車。而車型1 的容量最大，其次是車型2，因此參數(shù)pa 和pb應(yīng)根據(jù)每種轎運(yùn)車的運(yùn)載能力來確定。

（3）將這個(gè)數(shù)組分隔開來。只要裝載重量或者長度超出轎運(yùn)車的限制，就插入一趨于負(fù)無窮的數(shù)；

（4）根據(jù)客戶的需求確定集貨中心點(diǎn)，然后生成一個(gè)無序數(shù)組，并在取相反的數(shù)字后將其插入到客戶點(diǎn)前面。

（5）重復(fù)步驟（2）～（4），直至所有的客戶點(diǎn)都分配好轎運(yùn)車。

3.4 更新染色體（粒子）

在每次迭代中更新個(gè)體極值和群體極值。

3.5 交叉操作

個(gè)體通過和個(gè)體極值和群體極值交叉來更新，交叉方法采用整數(shù)交叉法。首先刪除染色體中所插入的負(fù)數(shù)只留下代表客戶點(diǎn)的20 位數(shù)。然后隨機(jī)選擇兩個(gè)交叉位置，把個(gè)體和個(gè)體極值或者群體極值進(jìn)行交叉。為避免重復(fù)編碼，交換前應(yīng)刪除重復(fù)點(diǎn)，例如：

A=1 7 3［10 15 8 9］16 13 11 2 17 19 20 4 5 6 12 18 14

B=7 9 1［12 2 20 16］19 5 6 3 15 13 18 11 14 4 8 10 17

首先從A 染色體中去除重復(fù)的數(shù)字12，2，20，16 然后從B染色體中去除 10，15，8，9，然后我們得到：

A=1 7 3［10 15 8 9］13 11 17 19 4 5 6 18 14

B=7 1［12 2 20 16］19 5 6 3 13 18 11 14 4 17

接下來，將交換的染色體片段分別移到染色體最前端，可以得到：

A=12 2 20 16 1 7 3 10 15 8 9 13 11 17 19 4 5 6 18 14

B=10 15 8 9 7 1 12 2 20 16 19 5 6 3 13 18 11 14 4 17

然后我們重復(fù)初始化操作，插入表示運(yùn)輸車輛的集貨中心和車型的數(shù)字，從而生成一對新的染色體。

3.6 變異操作

遺傳算法常用的變異操作有基本位變異、均勻變異和高斯變異等。變異操作可以有效避免過早收斂，保持種群的多樣性。使用的多點(diǎn)變異屬于基本位變異的一種。具體操作如下：首先在種群中隨機(jī)選擇三個(gè)基因位點(diǎn)14、10、18，然后將三個(gè)基因位點(diǎn)之間的兩個(gè)染色體片段互換。例如：

P=13 17 16 4 15 8 2［14］11 1［10］6 7 3 20［18］9 5 12

變異后得到：

P′=13 17 16 4 15 8 2［6］7 3 20 18［14］11 1［10］9 5 12

3.7 精英選擇

我們按照染色體適應(yīng)度值從大至小進(jìn)行排序。我們將每代中具有最大適應(yīng)度值的個(gè)體定義為精英個(gè)體，在通過交叉和變異操作產(chǎn)生的種群中，具有較高適應(yīng)度值的個(gè)體被選擇并復(fù)制兩次傳給下一代，排在末位的個(gè)體則被舍棄。在迭代中，使用這種自適應(yīng)方法不僅可以有效的避免早熟和近親繁殖，還可以加快種群整體收斂速度。公式如下：

式中：m（i）—第 i 條染色體的適應(yīng)度值；num—種群大?。籒（i）—復(fù)制的第i 條染色體復(fù)制的次數(shù)。

4 算例仿真及結(jié)果分析

4.1 算例仿真

設(shè)某物流公司有三種轎運(yùn)車車型，車型規(guī)格，如表1 所示。各集貨中心坐標(biāo)和成品車的規(guī)格，如表2 所示。各客戶的坐標(biāo)和訂單，如表3 所示。本算例含有7 個(gè)集貨中心和20 個(gè)客戶點(diǎn)。

表1 轎運(yùn)車規(guī)格Tab.1 Relevant Data of Transport Vehicles

表2 集貨中心位置和商品車規(guī)格Tab.2 The Information of Depot and Finished Vehicles

表3 各客戶點(diǎn)位置需求Tab.3 The Demand of Each Customer Point

優(yōu)化目標(biāo)是最小化運(yùn)輸成本。運(yùn)輸成本由路費(fèi)和油費(fèi)兩部分構(gòu)成。每單位距離的油費(fèi)與轎運(yùn)車型號有關(guān)，而路費(fèi)不僅取決于轎運(yùn)車車型還取決于具體的運(yùn)輸路線。

用Matlab2015b 針對算例進(jìn)行編程，并在一臺Intel3.7GHz，4GRAM 的電腦上進(jìn)行運(yùn)行實(shí)驗(yàn)，設(shè)定迭代次數(shù)為1000。從實(shí)驗(yàn)結(jié)果中可以看出：總的運(yùn)輸費(fèi)用為20824.363 元，所需轎運(yùn)車數(shù)量為8 輛。路由方案，如圖3 所示。詳細(xì)的路由及運(yùn)載方案如表4，算法迭代圖，如圖4 所示。

圖3 路徑優(yōu)化方案Fig.3 The Routing Solution

表4 轎運(yùn)車線路與配載明細(xì)Tab.4 Route and Loading Details

4.2 實(shí)驗(yàn)結(jié)果分析和算法對比

為了驗(yàn)證GA-PSO 算法有效性，將GA-PSO 與GA 分別進(jìn)算了十次。在兩種算法中采用了相同的編碼，初始種群大小設(shè)定為100，遺傳算法中，交叉概率設(shè)定為0.8，變異概率設(shè)定為0.05。兩種算法的最優(yōu)解迭代圖，如圖4、圖5 所示。實(shí)驗(yàn)最優(yōu)解在GAPSO 的341 代中得到。兩種算法的對比結(jié)果，舉出了每次試驗(yàn)中的各算法最差值和平均值，如表5 所示。通過比較兩種算法，GAPSO 收斂速度更快，優(yōu)化結(jié)果更好。最重要的是GA-PSO 的運(yùn)行時(shí)間只是GA 的5%左右。實(shí)驗(yàn)表明，我們提出的GA-PSO 算法具有更好的性能，可以快速的找到最優(yōu)解或者近似最優(yōu)解。為了充分驗(yàn)證此算法的有效性與效率，進(jìn)行了多次實(shí)驗(yàn)。在下面這些測試案例中，模型和假設(shè)不變，測試算例的位置坐標(biāo)仍然是隨機(jī)生成。隨著算例規(guī)模的增加（集貨中心數(shù)量和訂單數(shù)量），兩種算法的運(yùn)行時(shí)間差異愈發(fā)明顯，如表6 所示。

圖4 混合算法迭代圖Fig.4 Optimization Iteration Figure of GA-PSO

圖5 遺傳算法迭代圖Fig.5 Optimization Iteration Figure of GA

表5 算法結(jié)果比較Tab.5 Two Algorithm Comparison

表6 測試算例算法性能對比Tab.6 Algorithm Comparison of Test Cases

5 結(jié)論

結(jié)合整車物流中的實(shí)際運(yùn)輸情況，綜合考慮了物流成本和物流公司人力成本等要求，針對多集貨中心、多轎運(yùn)車型、多商品車型的整車物流運(yùn)輸問題，建立了以物流總成本最低和車輛數(shù)最小為目標(biāo)的（0～1）整數(shù)規(guī)劃模型，包括運(yùn)輸?shù)穆焚M(fèi)成本、油費(fèi)成本等，并設(shè)計(jì)出一種基于遺傳和粒子群算法的算法GA-PSO 進(jìn)行求解，解決了此整車物流配送中的路徑優(yōu)化問題，并進(jìn)行了實(shí)例驗(yàn)證并將結(jié)果與遺傳算法實(shí)驗(yàn)結(jié)果進(jìn)行對比，結(jié)果說明此模型和算法具有可行性和實(shí)用性。