羅芃瑜++左敏

摘要：隨著物流事業(yè)的蓬勃發(fā)展，物流運輸配送問題也不斷增加。路徑優(yōu)化問題作為物流運輸配送的基礎(chǔ)研究問題也一直受到學者們的重視。單一的智能優(yōu)化算法已經(jīng)不適合解決大規(guī)模，復雜度高的路徑優(yōu)化問題。在現(xiàn)有的混合智能算法中，基于人工魚群算法與蟻群算法混合的研究相對來說較少，因此該文對學者們提出的混合人工魚群-蟻群算法進行綜合研究分析，對現(xiàn)實中路徑優(yōu)化問題的求解有較大的理論意義與現(xiàn)實價值。

關(guān)鍵詞：VRP；魚群蟻群算法；智能優(yōu)化算法

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2015）11-0156-04

Review of VRP Optimization Based on AFSA-ACO

LUO Peng-yu， ZUO Min

（Depth of Computer and Information Engineering，Beijing Technology and Business University， Beijing 100048 China）

Abstract： With the vigorous development of the logistics industry， logistics distribution problems are increasing too. As the basis of logistics distribution， Path optimization problem have been brought to the attention of the scholars. A single intelligent optimization algorithm is not suitable for solving vehicle routing problems which of large-scale and high complexity. The research of VRP based on AFSA-ACO is relatively less nowadays. So in this paper， the author will research and analyze these optimization algorithms. This can create great theoretical and practical value on solving the vehicle routing problem.

Key words： VRP； AFSA-ACO； Intelligent optimization algorithms

在物流的配送優(yōu)化等問題中，常見的問題就是：存在一批客戶，并且已知客戶的地理坐標，每個客戶對貨物的需求量，運輸車輛的最大數(shù)量和運載能力等信息。在每輛運輸車都從倉庫出發(fā)，完成部分點的運輸任務(wù)后返回倉庫的前提下，尋求以最少車輛和最短總行程完成物流運輸?shù)淖顑?yōu)解。此類問題統(tǒng)稱為車輛運輸路徑問題，即Vehicle Routing Problem，VRP。

路徑優(yōu)化問題是現(xiàn)代物流供應(yīng)鏈優(yōu)化中的關(guān)鍵問題，車輛路徑問題的理論與算法依然是學者們重視的問題與研究的重點。對算法進行系統(tǒng)的研究不僅為物流運輸優(yōu)化提供更好的思路和方法，更加為構(gòu)建綜合物流系統(tǒng)，發(fā)展智能交通運輸系統(tǒng)等打下堅實的理論基礎(chǔ)。

1 車輛路徑問題

1.1 車輛路徑問題分類

車輛路徑的問題隨著相關(guān)學科的發(fā)展從最初的靜態(tài)的VRP、VRPTW、VRPPD等模型不斷衍生出隨機車輛路徑問題、模糊車輛路徑問題，到現(xiàn)在的動態(tài)車輛路徑問題。所以可以將車輛路徑問題歸為兩大類，一類是一般車輛路徑問題，而另一類則是衍生車輛路徑問題[1]，具體如下圖1所示。

圖1 車輛路徑問題分類

1.2 車輛路徑問題的一般模型

對于一般車輛運輸問題的優(yōu)化，為方便模型的建立，對貨物的物流運輸作以下幾點假設(shè)：

（1）僅考慮位置已知的一個倉庫，所有配送車輛起點和終點均是該倉庫。

（2）只考慮單個品種貨物的運輸，且每個需求點所需要的貨物劑不超過車輛的最大載重量。

（3）每個需求點的地理坐標位置和需求量都已知，其需求有且僅由一輛車輛一次送貨滿足。

（4）只有一種車輛，且車輛的載重量已知。

（5）車輛對每個需求點進行服務(wù)，途中只有卸貨而無裝貨。

（6）車輛的平均行駛速度已知，并且確定，行駛的路程與車輛行駛時間成正比。

以上述假設(shè)為前提，以配送成本最小化為目標，構(gòu)造出以下優(yōu)化模型。

[minZ=i=0j=0k=1dij?xijk （1） ]

式中，倉庫的編號為0，需求點的編號為[1，2，…，C]，[ xijk=1.0]取整數(shù)約束，1表示點i 到點 j由車輛 k來完成，否則為0；其中[yijk=1.0]取整數(shù)約束，1表示到點i由車輛 k來完成，否則為0。C為需求點的個數(shù)；m為車輛數(shù)；[dij（i，j=1，2，…，C）]為需求點i點與需求點j點之間的距離；[ ti]為車輛實際到達需求點的時間；[gi]為第i個醫(yī)療機構(gòu)的需求量； [q]為車的最大載重量；[k（k=1，2，…，m）]為車輛的編號。

約束條件為：

每次為需求點運輸貨物的運輸量不能超過車輛的最大載重量；

[i=0giyki≤qi k∈1，m （2）]

任意需求點只有1輛車輛來訪；

[k=1yki =1 i∈0，C，k∈1，m （3）]

[i=0k=1xijk =1 j∈0，C，k∈1，m （4）]

[j=0k=1xijk =1 i∈0，C，k∈1，m （5）]

車輛行駛路線為閉合線路；

[i=0xijk=yki i∈0，C，k∈1，m （6）]

[j=0xijk=yki j∈0，C，k∈1，m （7）]

2 智能優(yōu)化算法的分類與比較

解決車輛路徑算法的種類很多從20世紀50年代起的精確算法開始，到之后的啟發(fā)式算法，以及現(xiàn)在學者們研究的最多的智能優(yōu)化算法。其中精確算法有：分支界定法（Branch and Bound Approach）、割平面法（Cutting Planes Approach）等，啟發(fā)式算法有：節(jié)約算法（C-W）、掃描算法（Sweep Algorithm）等，應(yīng)用最多的智能優(yōu)化算法有：禁忌搜索算法（Tabu Search）、模擬退火算法（Simulated Annealing）、遺傳算法（Genetic Algorithm）、蟻群算法（Ant Colony Optimization）、粒子群算法（Particle Swarm Optimization），另外還有人工魚群算法（Artificial Fish School Algorithm）、人工神經(jīng)網(wǎng)絡(luò)算法（Artificial Neural Networks）等智能優(yōu)化算法，都在車輛路徑問題的研究中有應(yīng)用。

隨著物流業(yè)的不斷發(fā)展，物流運輸配送遇到的問題范圍不斷的擴大，實際問題的規(guī)模與復雜性也不斷的增大，僅僅靠單一的算法來優(yōu)化解決問題的效果已經(jīng)越來越不理想，每個算法都有各自的缺陷，都面臨著時間性能和優(yōu)化性能等挑戰(zhàn)。如下表1是目前運用最多的智能優(yōu)化算法思想和優(yōu)缺點[2]。

表1 常見智能優(yōu)化算法及其特點

[智能優(yōu)化算法＼&基本思想＼&優(yōu)點＼&缺點＼&禁忌搜索優(yōu)化算法＼&通過建立Tuba表，記錄選擇已經(jīng)優(yōu)化的過程，逐步在全局領(lǐng)域內(nèi)尋找最優(yōu)解＼&分別通過禁忌準則和特赦準則避免迂回搜索與赦免部分被禁忌的優(yōu)良狀態(tài)保證搜索多樣性和實現(xiàn)全局最優(yōu)＼&對初始解依賴性強，初始解的選定會影響收斂速度＼&遺傳算法＼&模擬生物界優(yōu)勝劣汰、適者生存的遺傳和變異的進化機制＼&能全局并行搜索，有自適應(yīng)能力，可處理大量信息，對局部性能高的重點搜索，不易陷入局部最?。?amp;收斂性差，容易“早熟”，處理約束優(yōu)化問題較困難＼&模擬退火算法＼&基于物理中固體物質(zhì)退火過程，從高初溫出發(fā)，伴隨溫度下降，結(jié)合概率突跳特性，隨機尋找目標函數(shù)的全局最優(yōu)解＼&簡單、通用、易實現(xiàn)、運行效率高＼&對初值有依賴性，搜索速度受串行影響，對不同狀態(tài)下的抽樣有較高的要求＼&蟻群算法＼&模仿自然界螞蟻群體覓食過程中螞蟻間互相傳遞信息素在較短的時間內(nèi)通過最短的路程找到食物＼&分布式計算，并行性，全局搜索能力，自組織，正反饋＼&收斂速度慢，易早熟，容易陷入局部最優(yōu)解＼&粒子群算法＼&模仿鳥群捕食的行為，人工建立以有向圖為拓撲結(jié)構(gòu)的動態(tài)系統(tǒng)，對連續(xù)或斷續(xù)的輸入狀態(tài)做狀態(tài)相應(yīng)而進行的信息處理＼&操作簡單，快速收斂，適合實值型處理＼&容易陷入局部最優(yōu)解＼&人工魚群算法＼&通過一片水域中魚群聚集的數(shù)量判斷食物多少的特點，構(gòu)造人工魚，模仿魚群的覓食、聚群、追尾等行為，實現(xiàn)尋優(yōu)。＼&對初值敏感性小，并行性，簡單性，全局性，快速性，跟蹤性＼&計算量較大，后期收斂逐漸減慢，容易陷入局部最優(yōu)＼&]

基于上述現(xiàn)象及出發(fā)點，可將各種單一的算法取長補短，利用各算法的優(yōu)勢進行融合，構(gòu)造出新的優(yōu)化效率更高的混合算法。

3 魚群-蟻群算法

3.1 人工魚群算法

人工魚群算法（AFSA）是基于模仿魚群覓食、聚群和追尾等行為而衍生出的一種較新型智能優(yōu)化算法。這種算法具有并行性、快速性、較強的搜索全局性等特點。在人工魚群算法中，設(shè)人工魚當前所在的位置是[Xi=xi1，xi2，…，xiN]，[Xv=xv1，xv2，…，xvN]，其中N表示維數(shù)，Visual表示人工魚的視野范圍，[Xv]表示視野范圍內(nèi)的一個狀態(tài)。人工魚的步長用Step表示，人工魚要從當前狀態(tài)到一個更優(yōu)的狀態(tài)過程可以表示為：

[Xv=Xi+Visual*rand（）] （8）

[Xnext=Xv-XiXv-Xi*Step*rand（）] （9）

人工魚群算法還包括了一下幾個行為：（1）覓食行為。在人工魚的視野范圍內(nèi)選擇位置[Xv]，若[Xv]的適應(yīng)度[Yv]大于[Xi]的適應(yīng)度[Yi]，則該人工魚向[Xv]的方向移動一步，反之，則從新選擇一個位置。（2）聚群行為。在避免擁擠和逐步中心的規(guī)則下，執(zhí)行覓食行為或隨機游動。其中一個重要的參數(shù)叫做擁擠因子，用[σ表示]。

若[Ycnf>σYi]（其中），表示中心食物較多且不擁擠，人工魚向[Xc]方向移動一步，反之，則執(zhí)行覓食行為或隨機游動。（3）追尾行為。在優(yōu)化過程中，若[Yvnf>σYi]，表示在視野范圍內(nèi)，最優(yōu)狀態(tài)的伙伴位置為[Xv]，且食物濃度高，不擁擠，則[Xi]向[Xv]的方向移動一步，反之，則執(zhí)行覓食行為。（4）隨機移動。即人工魚在其視野范圍內(nèi)隨機移動一步。人工魚群算法的基本流程如下圖2所示。

圖2 人工魚群算法的基本流程

3.2 蟻群算法

蟻群算法（ACO）是一種在圖中尋找優(yōu)化路徑的隨機搜索型算法。它最開始是由Marco Dorigo于1992年提出的，后來由Bernd Bullnheimer等[3]率先應(yīng)用于解決VRP問題，即先通過蟻群算法搜索最優(yōu)路徑，再運用2-Opt法對其進行優(yōu)化，最后找出最優(yōu)解。蟻群算法的基本思想是模仿螞蟻覓食發(fā)現(xiàn)最優(yōu)路徑的行為，并以下面三個假設(shè)為前提：（1）螞蟻之間通過產(chǎn)生信息素進行相互通信；（2）螞蟻對環(huán)境的反應(yīng)由內(nèi)部的模式?jīng)Q定；（3）每只螞蟻的行為是隨機的且僅依照環(huán)境做獨立選擇，蟻群可以通過自組織形成高度有序的群體行為。

蟻群算法中關(guān)鍵的因素有以下幾個：

（1）信息素用[τijt]表示t時刻路徑上信息素的含量，隨著時間的推移信息素的含量不斷應(yīng)新舊信息素的加入和揮發(fā)而改變，當時刻變?yōu)閠+n后，各個路徑上的信息素變?yōu)椋海ㄆ渲衃ρ]信息素的揮發(fā)系數(shù)）

[τijt+n=1-ρ?τijt+?τijt （10）]

[τijt=k=1m?τijt （11）]

（2）啟發(fā)函數(shù)用來表示螞蟻從節(jié)點i轉(zhuǎn)移到節(jié)點j的期望程度，其計算公式為：

[ηijt=1dij （12）]

（3）狀態(tài)轉(zhuǎn)移概率，這里以[Pkijt]表示，其計算公式為：（其中[α]為啟發(fā)因子表示螞蟻在路徑中積累的信息的作用，值越大則意味著螞蟻間的協(xié)作性越強。[β]為期望啟發(fā)因子表示啟發(fā)信息在螞蟻路徑選擇中的重要程度，值越大則意味著該狀態(tài)下的轉(zhuǎn)移率越接近貪心規(guī)則。）

[Pkijt=τijtα?ηiktβs?allowedkτijtα?ηiktβ，若j∈allowedk0，若j?allowedk （13）]

蟻群算法求解VRP的基本流程，如下圖所示：

圖3 蟻群算法求解VRP基本流程

3.3 魚群蟻群混合算法

在解決VRP問題中，對魚群蟻群混合算法的研究還不是很多，現(xiàn)有的兩種算法可結(jié)合的方法主要分為加入改變擁擠因子，改變信息素更新機制兩種形式：

（1）改變擁擠因子。文獻[4]在研究特殊醫(yī)療器械物流配送路徑優(yōu)化時，將魚群算法與基本蟻群算法相結(jié)合，把魚群算法中的擁擠因子概念引入到基本蟻群算法中，是算法整體增強尋優(yōu)能力，減少基本蟻群算法陷入局部最優(yōu)的可能性。其中設(shè)擁擠因子[σij]和擁擠度門限[δt]的計算公式分別如式（14）和式（15），其中[γ]為極值接近水平，[b]為閾值變化系數(shù)。其改進方法可以控制螞蟻集數(shù)量的多少，以此抑制螞蟻過早的聚集在高信息素的路徑上，從而減少早熟現(xiàn)象的發(fā)生幾率。但是該方法也存在不足，特別是在算法的后期會影響收斂速度。

[σijt=1-τijti≠jτij （14）]

[δt=γe-bt （15）]

文獻[5][6]也是研究人工魚群算法擁擠度的引入。部分區(qū)別在于擁擠因子的設(shè)置上如式（16）所示。同樣在算法的初期設(shè)置較強的門限，但是隨著迭代次數(shù)的增加，擁擠度閾值逐漸增大，信息素的濃度在指導蟻群選擇路徑的作用逐漸增強，最后蟻群完全由信息素和啟發(fā)因子來指導尋優(yōu)從而保證了算法能夠快速地收斂到最優(yōu)解上。

[σijt=2τijti≠jτijt （16）]

（2）改變信息素更新機制。文獻[7]在運用魚群蟻群混合算法解決模塊化產(chǎn)品配置問題中，提出了兩種算法動態(tài)融合策略。不是通過改變擁擠因子來進行優(yōu)化，而是通過設(shè)置魚群算法的迭代范圍，統(tǒng)計滿意的更新率，選擇魚群與蟻群融合的最佳轉(zhuǎn)換時機來進行尋優(yōu)。當人工魚群算法的優(yōu)化速度明顯減慢時便終止人工魚群算法，開始蟻群算法。同時文獻中改變了蟻群算法的信息素更新方程，將基本方程如式（10）改為式（16）。方程中[τijtmin]，[τijtmax]分別為信息素強度的上下限，尋求最優(yōu)解。

[τijt+n=τijtmax ，若τijt>τijtmax1-ρ?+?τijt，若τijtmin≤τijt≤τijtmin，若τijt>τijtmin τijtmax（17）]

文獻[8] 應(yīng)用人工魚群算法的追尾行為對蟻群在可行域上搜索到的可行解進行改進，將微分進化算法引入信息素的更新機制中，改變?nèi)斯~群算法的追尾公式，如式（18），其中[Xbest]表示當前最優(yōu)解，[Xki]表示螞蟻k的狀態(tài)[Xk]的第i個元素。之后再對修改過的新解進行信息素更新，從而加快收斂速度，快速達到全局最優(yōu)。

[Xnewkj=Xkj+randStepXbest-Xki/Xbest-Xk] （18）

4 結(jié)束語

本文總結(jié)了在物流業(yè)發(fā)展的大背景下，不斷衍生出的一系列路徑優(yōu)化問題，比較了各種智能優(yōu)化算法的優(yōu)缺點，得出改進單一智能優(yōu)化算法的重要性。進而研究了現(xiàn)今學者們在人工魚群蟻群混合算法求解VRP問題時的思路與方法。對混合魚群蟻群算法進行了整理歸類，對于完善路徑優(yōu)化問題的求解算法具有重要意義。

參考文獻：

[1] 吳斌. 物流配送車輛路徑問題及其智能優(yōu)化算法[M]. 北京：經(jīng)濟管理出版社，2013.

[2] 張建林. MATLAB&Excel定量預測與決策：運作案例精編[M]. 北京：電子工業(yè)出版社，2012.

[3] B. Bullnheimer，R.F. Hartl，C. Strauss. An improved Ant System algorithm for theVehicle Routing Problem[J]. Annals of Operations Research，1999，890.

[4] 費騰. 基于蟻群算法的醫(yī)療器械物流配送路徑優(yōu)化算法研究[D].太原：太原理工大學，2010.

[5] 修春波，張雨虹. 基于蟻群與魚群的混合優(yōu)化算法[J]. 計算機工程，2008，14：206-207，218.

[6] 鄒挺. 基于蟻群和人工魚群混合群智能算法在物流配送路徑優(yōu)化問題中的應(yīng)用研究[D].蘇州：蘇州大學，2011.

[7] 高德芳，趙勇，郭楊，趙海濤. 基于混合魚群-蟻群算法的模塊化產(chǎn)品配置設(shè)計[J]. 機械，2007（1）：7-10.

[8] 韓芳，邢曉哲，方婷婷，王成儒. 融合魚群和微分進化的蟻群算法的無功優(yōu)化[J]. 黑龍江電力，2011（2）：125-128.