多車型混載低油耗車輛路徑問(wèn)題的混合算法.doc

1、 多車型混載低油耗車輛路徑問(wèn)題的混合算法蔡蕓程志文I,張利平2(1.武漢科技大學(xué)冶金裝備及其控制教育部重點(diǎn)實(shí)驗(yàn)室，式漢430081：2.式漢科技大學(xué)機(jī)械傳動(dòng)與制造工程湖北省重點(diǎn)實(shí)驗(yàn)室.式漢430081)摘要：為了實(shí)現(xiàn)低磯運(yùn)輸和擴(kuò)展多車型車輛路徑問(wèn)題求解方法，針對(duì)單車場(chǎng)有固定車輛數(shù)的多車型低油耗車 輛路徑問(wèn)題，建立了以最小化車輛油耗為目標(biāo)的優(yōu)化模型，在模型中考慮了與油耗密切相關(guān)的車輛實(shí)我量以 及混載問(wèn)題：混合算法將具有整數(shù)編碼的優(yōu)勢(shì)的遺傳算法與具有覓伶操作的人工魚(yú)群算法相結(jié)合，利用覓食 操作更好地優(yōu)化車輛對(duì)集貨點(diǎn)的訪問(wèn)順序。遺傳算法負(fù)責(zé)車輛和集貨點(diǎn)配對(duì)的全局搜索，而人工魚(yú)群算法負(fù) 責(zé)訪問(wèn)順序的局

2、部搜索。算例實(shí)鞭結(jié)果表明：利用該模型求得的最低油耗較最短路徑對(duì)應(yīng)的油耗節(jié)省30%以 上；在全局搜索能力上，混合算法依次比自適應(yīng)遺傳算法、人工魚(yú)群算法.蟻群算法強(qiáng)：當(dāng)問(wèn)題規(guī)模變大時(shí)， 其性能明顯優(yōu)于人工魚(yú)群算法、蟻群算法；但加入的人工魚(yú)群操作彩響了迢合算法的時(shí)效，算法混合策略還 有待改進(jìn)。關(guān)鍵詞：計(jì)算機(jī)應(yīng)用；混合算法：車輛路徑；車輛調(diào)度：低碳 中圖分類號(hào)：F224： TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：A hybrid algorithm for vehicle routing problem withmulti-vehicle mixed-loading and Minimum fuel

3、consumptionCAI Yun12, CHENG Zhiwen1, ZHANG Liping2(1 Key Laboratory of Metallurgical Equipment and Control Technology, Wuhan University ofScience and Technology, Wuhan 430081, China；2. Hubei Key Laboratoiy of Mechanical Transmission and Manufactunng Enineenn, WuhanUniversity of Science and Technolog

4、y, Wuhan 430081, China)Abstract: To realize low-carbon transport and explore the optimization method of the multi-type vehicle routing problem a minimum fuel consumption model is established for heterogeneous fixed fleet routing problem in a single-depot. The hybrid algorithm combined a genetic algo

5、rithm, which is good at handling integer coding* with an artificial fish swarm algorithm whose prey operation is helpful to optimize vehicle arrival sequence of collection nodes Genetic algorithm was responsible for the overall search of matching vehicles with collection notes, while artificial fish

6、 swarm algorithm was responsible for local search of vehicle arrival sequence For a test case, computational experimental results show that: the minimum fuel consumption in the above model is 30% less than that in a model of the shortest path problem. The global searching ability of the hybrid algor

7、ithm is stronger than adaptive genetic algorithm, artificial fish swarm algorithm and ant colony algorithm successively. Its performance is superior than artificial fish swarm algorithm and ant colony algorithm when the scale of the problem becomes larger, but the added operation of artificial fish

8、swarm algorithm increases the time consumption of the hybrid algorithnb hybrid strategies of algorithms need to be improvedKey words: computer applications; hybrid algorithm: vehicle routing; vehicle scheduling; low carbono引言中國(guó)政府承諾到2030年，單位國(guó)內(nèi)生產(chǎn)總值的二氧化碳排放量比2005年下降60% 65%o而對(duì)不斷變化的氣候和環(huán)境，實(shí)施低碳運(yùn)輸是減少碳排放的必然趨勢(shì)

9、，低碳車輛基金項(xiàng)目：國(guó)家自然科學(xué)基金(51305311 )作者簡(jiǎn)介：蔡蕓(1970-),女.副教授，研究方向?yàn)槲锪飨到y(tǒng)的仿真和優(yōu)化，E-mail: HYPERLINK mailto:caiyun caiyun 路徑問(wèn)題也備受學(xué)者關(guān)注。目前單車型低碳車輛路徑問(wèn)題模型的相關(guān)研究較為完善，模 型中除了考慮汕耗、碳排放等必要因素外，還會(huì)考慮綜合成本工。由于單車型車輛路徑問(wèn) 題研究的日趨完善，多車型車輛路徑問(wèn)題漸受關(guān)注，該類問(wèn)題模型常以運(yùn)營(yíng)成本最小為 優(yōu)化目標(biāo)叫此外，涉及到的因素有逍路網(wǎng)絡(luò)地貌、車場(chǎng)數(shù)疑、顧客需求的隨機(jī)性或時(shí) 間窗約束、車輛裝載情況制、運(yùn)營(yíng)成本外的優(yōu)化目標(biāo)圧。少數(shù)學(xué)者X”開(kāi)展了多車型低

10、碳路徑問(wèn)題研究，有的以車輛總的碳排放量最小為優(yōu)化目標(biāo)，有的將碳排放量與運(yùn)營(yíng)成 本波10-巴甚至顧客滿意度一起進(jìn)行了優(yōu)化川。多車型車輛路徑問(wèn)題屬于組合優(yōu)化問(wèn)題，也是NP-hard問(wèn)題，常見(jiàn)的求解算法有整數(shù) 規(guī)劃、構(gòu)造算法、下界生成算法、禁忌搜索算法、遺傳算法、進(jìn)化算法、列生成算法等匕：。 為了提髙求解能力，研究者常會(huì)對(duì)現(xiàn)有算法進(jìn)行改進(jìn)，或采用混合算法求解，以提高問(wèn) 題的求解效率和解的質(zhì)量，如文獻(xiàn)6用多起點(diǎn)策略改進(jìn)禁忌搜索算法的多樣化搜索能力, 文獻(xiàn)12為了提髙算法效率，將量子進(jìn)化算法和遺傳算法結(jié)合。但是，目前還沒(méi)有學(xué)者進(jìn) 行多車型車輛路徑問(wèn)題的混合人工魚(yú)群算法研究，只有單車型問(wèn)題的應(yīng)用研究，如文

11、獻(xiàn) 13將人工魚(yú)群算法與遺傳算法以串行混合的方式用于求解物流配送的一般車輛路徑問(wèn) 題，獲得了優(yōu)于自適應(yīng)蟻群算法，近似于蟻群遺傳混合算法的最優(yōu)解。人工魚(yú)群算法早期收斂快，使用其求解組合優(yōu)化問(wèn)題時(shí)，曾獲得較好的優(yōu)化效果山： 加之，遺傳算法及其混合算法在求解車輛路徑問(wèn)題時(shí)二工，不但表現(xiàn)良好而且其應(yīng)用研究 較為成熟，因此，本文確左研究嵌入式混合魚(yú)群遺傳算法，以文獻(xiàn)12中算例來(lái)驗(yàn)證混合 算法的有效性和可行性，并與自適應(yīng)遺傳算法、人工魚(yú)群算法、蟻群算法進(jìn)行算法性能比 較。另外，為了研究油耗il崔方法對(duì)路徑優(yōu)化結(jié)果的影響，沒(méi)有采用文獻(xiàn)12中通過(guò)實(shí)載 率計(jì)算油耗，而是采用了實(shí)載量計(jì)算。同時(shí)模型考慮了滿載和非滿

12、載的混合問(wèn)題，由于 一部分客戶需求或供應(yīng)的貨物數(shù)量大于或等于車輛的載重量，而另一部分客戶需求或供 應(yīng)的貨物數(shù)量小于車輛的裝載戢，造成一些配送車輛需要滿載運(yùn)行，而另一些車輛則經(jīng) 常處于不滿載狀態(tài)。綜上所述，本文研究的問(wèn)題是對(duì)以往多車型低碳路徑問(wèn)題的理論模 型和求解方法的擴(kuò)展，具有一定的理論和實(shí)踐研究意義。1問(wèn)題描述多車型車輛路徑問(wèn)題總體上分為車輛數(shù)固左和車輛數(shù)無(wú)限制的兩類多車型問(wèn)題。根 拯配送業(yè)務(wù)的不同，一般多采用多種車型混合（車型表現(xiàn)為不同的車輛形式、噸位、體 積）。本文研究的車輛數(shù)目固左的多車型車輛集貨問(wèn)題可描述為：已知有”個(gè)l,2,n） 集貨點(diǎn)，第f個(gè)集貨點(diǎn)的貨運(yùn)量為q. （/=lX-.n

13、）,需將所有貨物運(yùn)往一個(gè)車場(chǎng)，由車場(chǎng) 派出車型為加（匸1,2,M）、載重量為0 （/n=l,2,.,M,且假設(shè)Q Q2 .Qm）的 貨車來(lái)承運(yùn)，求滿足貨運(yùn)需求的最低油耗行車線路。為了便于簡(jiǎn)化汁算，問(wèn)題假設(shè)條件為：（1）每個(gè)貨物點(diǎn)必須被訪問(wèn)且只能被訪問(wèn)一次; （2）車型以載重量分類且數(shù)目已知，車輛由一個(gè)車場(chǎng)空車發(fā)車，其配送路徑上的總載量不 允許超過(guò)其載重呈:，完成載貨后，回車場(chǎng)卸貨：（3）假設(shè)車輛沒(méi)有最大行駛距離限制：（4） 車輛汕耗量與車輛類型、載重和運(yùn)輸距離相關(guān)，且可由經(jīng)驗(yàn)公式求得。2問(wèn)題的數(shù)學(xué)模型2.1模型中的符號(hào)定義首先左義模型中符號(hào)含義如下：有向圖G = V,E為配送網(wǎng)絡(luò)，其中V=0,

14、l,2,n有n+1頂點(diǎn),其中0頂點(diǎn)表示車場(chǎng)，其余頂點(diǎn)組成集貨點(diǎn)集合V=V0； E =eV,i h j表示弧集;D丿為第i個(gè)集貨點(diǎn)到第/個(gè)集貨點(diǎn)的距離：G為集貨點(diǎn)i貨運(yùn)量，沱0：川為車型編號(hào)，”疋1,2,.21為車型的總數(shù)：R為車輛編號(hào),gl,2,-,K, K為車輛總數(shù);0耕為第m類車型的空重：0“為第加類車型的運(yùn)載能力，Q v 0 vv Q,:aMm為第加類車型的油耗計(jì)算系數(shù);的為離開(kāi)集貨點(diǎn)F后前往集貨點(diǎn)j的車輛已裝貨物總量；”為第加類車型的限制數(shù)量;_J1.牛輛從集貨點(diǎn)F行駛到集貨點(diǎn)j：”叫其他=集貨點(diǎn)凍貨由千輛R完成：九0其他2.2目標(biāo)函數(shù)和約束條件建立上述問(wèn)題的數(shù)學(xué)模型如下：M K n

15、ii TOC o 1-5 h z Obj： minZ=工工工工qX於心 +) + 】(1)fw=k=k=0 7=0S.t偷 Qmxijk, Vi J. m. k(2)土張 ijkZjQVWk(4)1=0戶0n kn kE E x0 jk =工 Z xiOk=U=Ir=l Xr=lxijk + xjik I.V/JgVW jyk(7)方一工甸=g ,巧W(8)；eV/eVzj=I=lMK = Xnm(10);?j=1承 NiwVNjwVNk(11)xijk =0或和=0或12譏(12) 式(1)表示目標(biāo)函數(shù)為最小化車輛總油耗：式(2)表示車的載重不大于它的載重能力：式(3) 表示每個(gè)客戶都會(huì)被服

16、務(wù)到：式(4)和式(5)表示集貨點(diǎn)有且僅被一輛車服務(wù)；式(6)表示離開(kāi) 配送中心的車輛和返回配送中心的車輛數(shù)量是一致的：式(7)表示兩個(gè)集貨點(diǎn)間的線路數(shù)不能 超過(guò)h式(8)滿足集貨點(diǎn)的取貨需求，同時(shí)消除子回路：式(9)保證返回車場(chǎng)的所有車輛取貨 總和等于所有集貨點(diǎn)的取貨需求總和：式(10)保證總車輛數(shù)等于各類車輛數(shù)總和：式(11) 保證離開(kāi)集貨點(diǎn)后車輛的載重不小于該點(diǎn)的貨運(yùn)量：式(12)用變量的取值，表示車輛與集貨 點(diǎn)間關(guān)系。該模型放寬了文獻(xiàn)9中剛從車場(chǎng)出發(fā)的車不會(huì)取貨和返回車場(chǎng)的車輛不再服務(wù)的約束， 允許車輛在車場(chǎng)卸貨后，再次被使用。車輛碳排放疑與車型、距離和路況、車速、載重量、駕駛狀況等因

17、素有關(guān)，二氧化碳排 放量的計(jì)算由精確度要求和所采集的數(shù)據(jù)種類和精確度不同而不同，碳排放量與油耗成正比 例關(guān)系，油耗與行駛距離成正比例關(guān)系，與裝載量成正線性相關(guān)凹。因此，最小化車輛油耗 與最小化碳排放一致。為了使用文獻(xiàn)12中算例校驗(yàn)算法可行性，本文選擇了只考慮車輛載 重0、運(yùn)輸距離Q (km)的車輛油耗F (L)計(jì)算方法9,即F=D(aQ+b)(13)其中“、b分別為與車型對(duì)應(yīng)的燃油消耗參數(shù)。3求解問(wèn)題的混合算法3.1算法總體設(shè)計(jì)混合算法求解的基本思路是：為順序排列的集貨點(diǎn)隨機(jī)生成為其服務(wù)的編號(hào)車輛，歸 納每個(gè)編號(hào)車輛需要服務(wù)的集貨點(diǎn)集合，車輛按英集貨點(diǎn)從小到大的順序號(hào)服務(wù)，產(chǎn)生 可行路徑，即將

18、一個(gè)多車型路徑問(wèn)題分解為多個(gè)單車型路徑問(wèn)題解決。由于遺傳算法擅長(zhǎng)全局搜索但收斂速度慢，人工魚(yú)群算法前期收斂快速、擅長(zhǎng)微調(diào)但 常會(huì)陷入局部最優(yōu)。本文混合算法采用將局部搜索方法插入到遺傳算法主循環(huán)中的混合 形式。遺傳算法負(fù)責(zé)進(jìn)行種群中的全局搜索，而人工魚(yú)群算法負(fù)責(zé)局部搜索，進(jìn)行染色 體間的局部搜索?；旌蠒r(shí)將人工魚(yú)群算法作為遺傳算法基本循環(huán)的插件，讓其與變異算 子、交叉算子和選擇交算子一同工作，以執(zhí)行快速的局部搜尋，從而在對(duì)后代進(jìn)行評(píng)價(jià) 之前對(duì)其進(jìn)行改進(jìn)。令G是當(dāng)前世代t時(shí)的車輛和集貨點(diǎn)的對(duì)應(yīng)編碼,F(t)是當(dāng)前世代t的各車輛對(duì)集貨 點(diǎn)的訪問(wèn)序列，S是當(dāng)前世代t的解集(S由G和F構(gòu)成)。整個(gè)算法過(guò)程

19、歸結(jié)如下： 整個(gè)算法過(guò)程歸結(jié)如下：begint0；染色體初始化G(t)：人工魚(yú)群編碼初始化F(t)；S(t) -G(t)+ F(t):應(yīng)用適應(yīng)值函數(shù)評(píng)價(jià)S(t)：while終止條件不滿足dobegin對(duì)G進(jìn)行變異操作：對(duì)G進(jìn)行交叉操作：對(duì)F執(zhí)行人工魚(yú)群操作；S(t) -G(t)+ F(t):用適應(yīng)值函數(shù)評(píng)價(jià)S(t)；對(duì)G進(jìn)行選擇操作：t=t+l：endend3.2算法關(guān)鍵技術(shù)3.2.1編碼和解碼本模型的求解涉及兩個(gè)方面的決策，第一個(gè)方而是每個(gè)集貨點(diǎn)車輛類型的指派，第二個(gè) 方面是集貨點(diǎn)訪問(wèn)順序的決策。由于遺傳算法在整數(shù)編碼較為便捷，故將每個(gè)集貨點(diǎn)車輛類 型的指派用遺傳算法完成；又由于集貨點(diǎn)訪問(wèn)順

20、序存在大量的組合，人工魚(yú)群算法含有多次 嘗試覓食的算子，有利于順序?qū)?yōu)，因而將集貨點(diǎn)訪問(wèn)順序決策交與人工魚(yú)群算法執(zhí)行。算法染色體采用長(zhǎng)度為”的雙層編碼結(jié)構(gòu)。第一層編碼為集貨點(diǎn)的節(jié)點(diǎn)排序，采用自然 數(shù)編碼到“（”為集貨點(diǎn)數(shù)量），第二層編碼為對(duì)應(yīng)上層集貨點(diǎn)的服務(wù)車輛型號(hào)，采用自然數(shù) 編碼到M （M為車型總數(shù)），K輛服務(wù)車輛構(gòu)成這M類車型的車輛集合。以n=6, M=3時(shí)為例，圖1顯示一個(gè)染色體編碼的意義，第一行為集貨點(diǎn)編號(hào)，第二行為 遺傳算法操作的染色體，即服務(wù)車輛類型的排序，其意義為1型車為集貨點(diǎn)2服務(wù)，2型車為集 貨點(diǎn)1、3和6服務(wù)，3型車為集貨點(diǎn)4和5服務(wù)，每類車訪問(wèn)集貨點(diǎn)的順序交給人工魚(yú)群算

21、法確 定。集貨點(diǎn)編號(hào)：214356服務(wù)車編號(hào)：123032圖1遺傳算法染色體示意圖Fig. 1 A Sample Chromosome in GA人工魚(yú)群算法編碼長(zhǎng)度仍然為“（為集貨點(diǎn)數(shù)量），采用精確到小數(shù)點(diǎn)后兩位的實(shí)數(shù)編 碼。圖2所示的第一行是由1至“的集貨點(diǎn)編號(hào)，第二行是人工魚(yú)群算法的人工魚(yú)，人工魚(yú)碼 值是由軟件隨機(jī)生成的0,1區(qū)間實(shí)數(shù)，根據(jù)人工魚(yú)編碼值進(jìn)行擴(kuò)展升序排序后，產(chǎn)生“個(gè)集 貨點(diǎn)被服務(wù)的新序列及英服務(wù)車輛類型（如圖3所示）。圖3隱含了各類車輛對(duì)集貨點(diǎn)的訪問(wèn)序 列，其可解析為1類車訪問(wèn)順序?yàn)?20,2類車訪問(wèn)順序?yàn)?3亠60 3類車訪問(wèn)順序?yàn)?540集貨點(diǎn)編號(hào)：123456人工魚(yú)編

22、碼值：0.820.660.200.460.130.91圖2各集貨點(diǎn)對(duì)應(yīng)的人工魚(yú)編碼值Fig. 2 Artificial Fish Coded Values of Corresponding Collection Nodes534216030.200.460.660.820.91集貨點(diǎn)訪問(wèn)順用號(hào): 人工魚(yú)褊碼值：圖3以上集貨點(diǎn)的訪問(wèn)序列Fig. 3 The Arrival Sequence of Above Collection Nodes3.2.2遺傳算子的設(shè)計(jì)遺傳算法對(duì)染色體種群G處理時(shí)，不改變?nèi)旧w第一層的集貨點(diǎn)序列，只針對(duì)染色體 第二層的車輛型號(hào)。交叉算子分別對(duì)染色體的兩層編碼進(jìn)行交叉，

23、同時(shí)都采用兩點(diǎn)交叉。變 異算子分別對(duì)染色體的兩層編碼進(jìn)行變異，對(duì)第一層編碼采用兩點(diǎn)互易的變異策略，而對(duì)第二 層編碼采用單點(diǎn)變異的策略。選擇算子采用輪盤(pán)賭選擇。3.2.3人工魚(yú)群算子的設(shè)計(jì)人工魚(yú)群算法模擬魚(yú)群覓食的行為，每個(gè)備選解被稱為一條“人工魚(yú)”，初始化為一群人 工魚(yú)（隨機(jī)解），通過(guò)覓食、聚群及追尾等行為迭代搜尋最優(yōu)解，在人工魚(yú)群算法內(nèi)部的每次 迭代過(guò)程中，通過(guò)更新人工魚(yú)自己，從而實(shí)現(xiàn)尋優(yōu)14。該部分算子設(shè)訃使用文獻(xiàn)14的經(jīng)典 人工魚(yú)群算法動(dòng)作，不再贅述。算法適應(yīng)度值用目標(biāo)函數(shù)公式（1）計(jì)算獲得。另外，算法中 視距采用線性遞減策略（參見(jiàn)公式（14），使得算法前期視距大，有利于快速收斂，后期視

24、距 小，有利于提髙收斂精度。1（14）其中為當(dāng)前迭代次數(shù)為第M弋魚(yú)的視距，/為最大迭代次數(shù)Vnwc為最大視距，Vnun為 最小視距。3.2.4目標(biāo)函數(shù)的求解求解過(guò)程如下：1）首先通過(guò)遺傳算法獲取M類車倆服務(wù)的集貨點(diǎn)的對(duì)應(yīng)關(guān)系，得到集合G，G2,Gw,（如圖1 G = 2, G2=1,3,6, G=4.5）：然后，通過(guò)人工魚(yú)群算法的隨機(jī)賦 值方法（如圖2）,獲得人工魚(yú)編碼值，然后使用擴(kuò)展升序的方法，獲得各類車對(duì)集貨點(diǎn)訪 問(wèn)的新序列 F/，F(xiàn)2，F(xiàn)”，（如圖 3 的 F/ = 2 , =3,1,6, Fj=5,4）。2）根據(jù)巧，兄，F(xiàn)”，分割岀M種類型K輛車的車輛調(diào)度路徑，即獲取路徑卩，Sk，步驟

25、為:a）根據(jù)人工魚(yú)群算法得到的某類車輛服務(wù)的集貨點(diǎn)的訪問(wèn)順序，從集貨節(jié)點(diǎn)集合的第 一個(gè)點(diǎn)開(kāi)始：b）達(dá)到一個(gè)節(jié)點(diǎn)后，判斷車輛是否可以裝載該點(diǎn)的全部貨物量，如果可以,那么裝載之, 淸空節(jié)點(diǎn)貨物量，轉(zhuǎn)d）,如果不能裝完，轉(zhuǎn)c）：c）去車場(chǎng)卸貨，更新節(jié)點(diǎn)的貨物量，再返回未裝節(jié)點(diǎn)，轉(zhuǎn)b）：d）判斷是否全部訪問(wèn)完畢，如果未訪問(wèn)完畢，駛往下一個(gè)廿點(diǎn)，轉(zhuǎn)b）,否則轉(zhuǎn)e）：e）輸出訪問(wèn)路徑和車輛裝載情況；3）根據(jù)2）得到的M類車輛集合內(nèi)的各車輛的裝載情況及訪問(wèn)路徑，通過(guò)各車型耗汕公式, 計(jì)算岀它們的總油耗，即目標(biāo)函數(shù)值。325適應(yīng)度函數(shù)由于求油耗最小化問(wèn)題，故適應(yīng)度函數(shù)設(shè)左為目標(biāo)函數(shù)的倒數(shù)，作為評(píng)價(jià)染色體好壞的

26、標(biāo)準(zhǔn)，即完成集貨任務(wù)的所有車輛汕耗越小，染色體越優(yōu)。具體的左義如下1（15）英中/為第i個(gè)染色體的適應(yīng)度，乙為第，個(gè)染色體采用（1）式計(jì)算得到的目標(biāo)函數(shù)值。4混合算法實(shí)驗(yàn)4.1最小化油耗與最短路徑油耗的比較實(shí)驗(yàn)在Matlab軟件平臺(tái)下，混合算法在Intel奔騰i5-2450M CPU 2.50GHZ , 4G運(yùn)行內(nèi)存的 計(jì)算機(jī)上運(yùn)行，采用文獻(xiàn)12中表3、表4數(shù)據(jù)，以最小化油耗為優(yōu)化目標(biāo)，計(jì)算獲得油耗是 1789.539L；文獻(xiàn)12以最短路徑為目標(biāo),獲取的計(jì)算路徑結(jié)果為文獻(xiàn)12中表5,依據(jù)此求 得的最低油耗在2563.5L以上，可見(jiàn)若以最低油耗規(guī)劃車輛路徑，可節(jié)省約30%的汕。但是， 量子遺傳算

27、法IB在求優(yōu)時(shí)平均搜索迭代次數(shù)15.42,而混合人工魚(yú)群算法平均搜索迭代次數(shù) 需要30次左右，混合算法收斂較慢。4.2算法性能比較實(shí)驗(yàn)為了分析混合人工魚(yú)群算法（HAFSA）對(duì)于求解以最低油耗（LFC）為目標(biāo)的多車型車輛調(diào) 度問(wèn)題的性能，本文采用經(jīng)典的人工魚(yú)群算法（AFSA）、自適應(yīng)遺傳算法（AGA）和蟻群算 法（ACO）進(jìn)行了算法實(shí)驗(yàn)對(duì)比。車型及油耗參數(shù)選擇如下:5t車型，a=0.72.b=15； 10t車型， a=O.52,b=18： 15t車型，a=O.313,b=22集貨點(diǎn)信息如表1所示。表1集貨點(diǎn)信息Tab. 1 Information of Collection Nodes編號(hào)坐標(biāo)/

28、km集貨fit編號(hào)坐標(biāo)/km集貨助1|41O.22O|2.518430.1280162卩 4&1178|319I465.890J183320.1003J420(375903211352,1050265|5OO.31O|2.5221700.78096|190704231800.11901871320.400424938.145078|55O.35O|925I646J590J391239.436626R67.326I810(1309,346|72711222.10352411I500.4S0)728|118&1230|5121600.530)1229|929J 28OJ1

29、113620,580)1030978.16301514|650.69()|1331|105& 16701815|690.1020|143211200.1780)20161760.11501933|13(X).193O1017525.131018在算法參數(shù)實(shí)驗(yàn)方面，實(shí)驗(yàn)結(jié)果表明：混合算法中的人工魚(yú)群算法參數(shù)設(shè)巻為種群數(shù)250, 迭代次數(shù)50,嘗試次數(shù)10,人工魚(yú)的最大視距3,人工魚(yú)最小視距1,擁擠度因子0.618,最大 移動(dòng)步長(zhǎng)2,變異概率0.3,交叉概率0.6,通常會(huì)獲得較優(yōu)的計(jì)算結(jié)果：人工魚(yú)群算法參數(shù)取 混合算法中相應(yīng)參數(shù)時(shí)，計(jì)算結(jié)果也較優(yōu)：自適應(yīng)遺傳算法的部分參數(shù)采用經(jīng)典設(shè)置，當(dāng)取 變異槪

30、率0.15,交叉概率0.6時(shí)，可以得到較優(yōu)的訃算結(jié)果。在算法尋優(yōu)效果方而，由表2可知，四種算:法求解的最低油耗值從小到大依次為混合人 工魚(yú)群算法、自適應(yīng)遺傳算法、人工魚(yú)群算法、蟻群算法，反映岀混合人工魚(yú)群算法的全局 搜索能力最強(qiáng)，自適應(yīng)算法次之，蟻群算法最弱。在算法收斂性能方而，由表2和圖4可知，單純使用人工魚(yú)群算法時(shí)，其前期收斂快，但 后期易陷于局部最優(yōu)，收斂速度慢，計(jì)算時(shí)間長(zhǎng)，求解的最低油耗平均值為1860.4L,平均收 斂次數(shù)為106次，相比自適應(yīng)遺傳算法，其求解結(jié)果和收斂性能都較差。蟻群算法前期收斂也 較快，相比人工魚(yú)群算法，更易擺脫局部最優(yōu)。當(dāng)使用人工魚(yú)群算法和自適應(yīng)遺傳算法結(jié)合而成

31、的混合算法時(shí)，由于自適應(yīng)遺傳算法的 加入，混合算法表現(xiàn)出了較強(qiáng)全局搜索能力及良好的魯棒性，這是由于遺傳算法通過(guò)自適應(yīng) 處理后，當(dāng)種群趨于收斂時(shí)，交叉概率會(huì)降低，變異槪率會(huì)提高，從而可以保持種群的多樣 性，避免“早熟“現(xiàn)象。此外，當(dāng)種群個(gè)體發(fā)散時(shí)，交叉槪率會(huì)提高，變異概率會(huì)降低，使得 種群趨于收斂，也提高了算法的收斂速度。此外，混合算法中的人工魚(yú)群算法也發(fā)揮了其前 期收斂快的優(yōu)勢(shì)，增強(qiáng)了混合魚(yú)群算法尋優(yōu)能力。綜上原因，由表2分析可知，混合算法相比 自適應(yīng)遺傳算法不僅可以取得很好的計(jì)算結(jié)果，而且苴計(jì)算效率也比經(jīng)典人工魚(yú)群算法有了 很大的提高，計(jì)算結(jié)果也很穩(wěn)左。實(shí)驗(yàn)結(jié)果表明：混合算法比自適應(yīng)遺傳算法

32、可以平均節(jié)省 約233.8L的燃油消耗,從而更好地達(dá)到節(jié)能環(huán)保的目的。表2仿頁(yè)結(jié)果分析Tab. 2 Analysis of Simulation Results以法名稱tfi/Ltll/L平均值/L計(jì)算時(shí)平均收斂次數(shù)/limesHAFS13471789.51568.3240.332AFSA1805.41915.31860.42362.7106AGA1786.91817.21802109.947ACO1932213620346759圖4四種算法的迭代圖Fig. 4 Iterative Graph of Four Algorithms當(dāng)車輛類型規(guī)模m取不同值時(shí)，由表3統(tǒng)汁的試驗(yàn)結(jié)果表明：對(duì)于小規(guī)模

33、的車輛調(diào)度問(wèn) 題，四種算法均能計(jì)算岀比較好的解，但是隨著規(guī)模的增大，人工魚(yú)群算法和蟻群算法的穩(wěn) 立性就開(kāi)始下降了，而混合算法卻依然能夠取得較好的結(jié)果，這得益于該算法是人工魚(yú)群算 法和自適應(yīng)遺傳算法同步演化，每一代的染色體和魚(yú)群位置都是變化的，提高了人工魚(yú)群算 法收斂速度、精度和全局搜索能力。表3不同算法在m取不同值時(shí)的LFC值Tab. 3 The Value of LFC of Different Algorithms in mmHAFSAAFSAAGAACO51680.21805.218722006.6101843.52147.31874.72020.8151897.22128.818442

34、089201897.32245.21836.32085251885.32264.71836.32136301863.62291.91868.5218291873.82205.9401909.923181983.92259.65結(jié)論本文在國(guó)家實(shí)施的一系列宏觀調(diào)控中，強(qiáng)力降低碳排放的背景下，提岀了一種由人工魚(yú) 群算法和自適應(yīng)遺傳算法組成的混合算法，并運(yùn)用到求解車輛汕耗受多車型、集貨點(diǎn)位宜、 貨物量、車輛混載等多邊因素影響的車輛調(diào)度問(wèn)題，這是該種混合算法在以最低油耗為目標(biāo) 的多車型混載車輛調(diào)度的首次應(yīng)用。算法實(shí)驗(yàn)結(jié)果證明了該混合算法性能明顯優(yōu)于單一的人 工魚(yú)群算法和蟻群算法

35、，同時(shí)也證明了混合算法求該問(wèn)題的有效性。但與自適應(yīng)遺傳算法的 時(shí)效相比，該混合算法還有不足，還需要在人工魚(yú)群算法的算法行為、參數(shù)，以及與自適應(yīng) 遺傳算法的結(jié)合方式上，做出進(jìn)一步的改進(jìn)。【參考文獻(xiàn)(References)fl|許茂增，余國(guó)印.周翔等綜合成本最小的低碳乍輛調(diào)度問(wèn)題及算法J|訃算機(jī)集成制造系 統(tǒng).2015,21(7):1906-1914.XU M Z.YU G Y, ZHOU X.et al. Low-carbon vehicle scheduling problem and algorithm with minimum-comprehensive-costlJ. Computer

36、Integrated Manufacturing Systems.2015.21(7) J906-19I4. (in Chinese)21羅平.多牟型輛路徑問(wèn)題研尤與應(yīng)用D成都：西南交通大學(xué),2014.LUO P. Research and application of fleet size and mix vehicle routing problem|D.Chengdu : Southwest Jiaotong University. 2014. (in Chinese)3| Bae H. Moon I. Multi-depot vehicle routing problem with l

37、ime windows considering delivery and installation vehicles. Applied Mathematical Modelling. 2016.40(14):36-49.Wang Z. Li Y. Hu X. A heurislic approach and a tabu search for the heterogeneous multi-type fleet vehiclerouling problem with time windows and an incompatible loading conslraintJl. Computers

38、& Industrial Engineering. 2015.89(5):162-176.Qu Y. Bard J F. The heterogeneous pickup and delivery problem with configurable vehicle capacity! J|.Transportation Research Emerging Technologies. 2013,32(3):1-20.Molina J C. Eguia I. Racero J, et al. Multi-objective Vehicle Routing Problem with Cost and

39、 Emission Functions)J. Procedia Social and Behavioral Sciences. 2014,160(6):254-263.7|李進(jìn)，傅培華.具有固定車輛數(shù)的多車型低碳路徑問(wèn)題及算法卩計(jì)算機(jī)集成制造系,2013,24(6)： 1351-1362.LI J. FU P H. Heterogeneous fixed fleet low-carbon routing problem and algorithm|J|. Computer Integrated Manufacturing Systems. 2013 24(6)： 290 1351-1362.

40、(in Chinese)8李淑琴楊斌趙磊，等.需求帯時(shí)間窗的環(huán)保女吃型組合配送路徑優(yōu)化卩廣西大學(xué)學(xué)報(bào)(自然科學(xué)版). 201333(02)： 388-394.LI S Q. YANG B. ZHAO L, et al. Environmental multi-model combination distribution routing optimization for demand with time windows|J. Journal of Guangxi University(Nat Sci Ed). 2013,13(02)： 388-394. (in Chinese)9|趙燕偉，李文，張景玲，等.多車型同時(shí)取送貨問(wèn)題的低碳路徑研尤|J浙江工業(yè)大學(xué)學(xué)