單純形蟻群算法對帶時間窗車輛路徑優(yōu)化問題的研究

李永亮，王玉富，向長城

(1．湖北民族學(xué)院 理學(xué)院，湖北 恩施445000:2．鄭州測繪學(xué)校，河南 鄭州450015)

車輛路徑問題研究的是車輛的運輸優(yōu)化問題，通常會利用啟發(fā)式算法求解此類問題，并且在一定的搜索時間范圍內(nèi)獲得問題的近似解，再根據(jù)解的合理性，制定出合適的配送方案．在建模的過程中，不僅要使運輸?shù)某杀咀畹停夷軌虮M可能的滿足客戶的需求(在這里主要是滿足客戶的時間需求)．帶時間窗車輛路徑問題是在原來的車輛路徑問題基礎(chǔ)之上融入了時間窗的限制，即多了約束條件．目前大多是在理論上對VRP問題進行的研究，而且研究的主要是站點較少的VRP 問題，但在現(xiàn)實世界中，站點數(shù)目往往比較多，現(xiàn)有的方法難以很好地解決大規(guī)模車輛路徑問題，不能得到滿意解，處理這些問題時往往就不再適用了．如何有效解決大規(guī)模VRP 問題，尋求滿意的配送方案，成為如今物流企業(yè)著重需要解決的難題，對它進行研究，具有極其重要的理論意義和現(xiàn)實意義．

1 帶時間窗的車輛路徑優(yōu)化問題的分析與建模

研究帶時間窗的優(yōu)化問題實質(zhì)就是在含有運輸容量約束的車輛優(yōu)化路徑問題的基礎(chǔ)上，增加了時間窗的約束，則帶時間窗的車輛路徑問題描述為:車輛從倉庫出發(fā)去滿足每個站點的需求，完成站點的需求后依舊返回倉庫，規(guī)定每個站點只能被其中一輛車服務(wù)而且僅被服務(wù)一次，而且對站點的服務(wù)時間必須控制在站點事先規(guī)定的時間窗約束條件下進行，從而問題就是怎樣去選取合適的行車路線，使得在滿足時間窗和需求量的要求下，完成全部需求花費的總成本最?。?/p>

帶時間窗車輛路徑問題數(shù)學(xué)建模符號表示為:令G=(V，E)為一個無向圖，V表示頂點集，E為邊集．頂點v0表示配送中心，頂點v1，v2，v3，…，vi表示客戶位置，dij表示i，j兩點之間的距離長度，tij表示車輛從vi行駛到vj的所用的時間，運輸費運為cij，車輛容量為Q，所需車輛為k，客戶i的需求量為qi，客戶i的時間窗為［ETi，LTi］，車輛到達客戶i的時間為si，在時間窗的約束條件下，必須要滿足ETi≤si≤LTi．為此可以構(gòu)造數(shù)學(xué)模型，定義變量如下:

則可得到帶時間窗的車輛路徑問題的數(shù)學(xué)模型如下:

模型中，cij表示為從點i到j(luò)的距離運輸成本量，它是根據(jù)問題情況來確定，可以表示為距離、費用、時間等．式(1)表示目標函數(shù)使得所用費用最少;式(3)表示表示車輛k服務(wù)的所有客戶的需求量之和不大于車輛的載重量;式(2)表示客戶i只能被一輛車來服務(wù);式(4)表示時間窗約束．

2 改進單純形蟻群算法

2．1 單純形算法的簡介

單純形法在運算過程中，不僅僅計算量小、而且無需求導(dǎo)、優(yōu)化速度快等優(yōu)點的傳統(tǒng)的局部搜索算法，并且在運行時，不會有復(fù)雜的矩陣運算，因此它在運算的過程中內(nèi)存的消耗較小;但利用單純行算法進行計算時，由于初始值的不同，它會得到不同的搜索結(jié)果，急欲陷入局部收斂，很難保證得到全局最優(yōu)解．單純形法的基本原理是在n維空間中用n+1 個頂點構(gòu)成一個單純形，再根據(jù)單純性的相應(yīng)規(guī)則，不斷改變單純形的迭代的頂點，使它向適應(yīng)度函數(shù)最小的方向移動，直至找到函數(shù)最優(yōu)的近似解的值．求解過程為:首先需要找到適應(yīng)度函數(shù)值的最差點xh、次差點xd、最好點x1，其適應(yīng)度函數(shù)值分別為fh，fd，f1，然后需要求出除最差點外的其他的n個頂點的重心xg，則它的適應(yīng)度值為fg［1］．如果它的反射點的適應(yīng)度函數(shù)的值為frrx1的函數(shù)值f1，就這樣進行擴展，如果它的反射點的函數(shù)值大于xd的函數(shù)值，則需要在該方向上執(zhí)行一次向內(nèi)收縮，從而得到它的收縮點xn，使單純形更接近最優(yōu)點的值．單純形則在每一次迭代中進行反射、擴展、收縮的條件如下所示:

①如果f1＜fr＜fd，則xc=xg+?(xr+xh);②如果fr＜f1，則xr=xg+β(xg+xh);

③如果fd＜fr＜fh，則xn=xg+o(xg－xr);④如果fr＞fh，則xn=xg－φ(xg－xh)．其中，?為反射因子;β 為擴張因子;o 為正向收縮系統(tǒng);φ 為反向收縮因子．

2．2 蟻群算法簡介

蟻群算法是根據(jù)自然界螞蟻在尋找地址的過程中，每一條螞蟻能夠在它所經(jīng)過的路徑上留下叫信息素的物質(zhì)來進行信息的傳遞，當其他的螞蟻在經(jīng)過此路徑的時候，能夠感知這種信息素和信息素的量，并且根據(jù)這條路徑上的信息素的量來判斷選擇這條路徑的概率，隨著螞蟻經(jīng)過這條路徑的數(shù)量越來越多，則這條路徑的信息素的量就越來越多，螞蟻選擇這條路徑的概率就會逐漸大．式(5)～(7)為蟻群算法的基本模型為:

式(5)p為螞蟻的轉(zhuǎn)移概率．m為螞蟻的總的數(shù)量;n表示的是迭代的次數(shù);i表示螞蟻當時所在位置;j為螞蟻接將要到達的位置;Λ 為螞蟻可以到達的所有的位置的集合;η 為啟發(fā)性的信息;式(6)τ 為由i到j(luò)的路徑中螞蟻釋放出的信息素的強度;式(7)Δτ 為螞蟻k由i到j(luò)的路徑上，螞蟻所留下的信息素的數(shù)量;L為路徑的長度;α，β 為啟發(fā)性的信息的權(quán)值;ρ 為路徑上信息素的蒸發(fā)系數(shù);Q為信息素的質(zhì)量的系數(shù)［2］．

2．3 改進的單純形的蟻群算法

對于N維向量的空間優(yōu)化問題，需要N+1 個單純形的頂點來產(chǎn)生一個N維空間的單純形．算法的基本流程為:

1)首先需要求出目標函數(shù)值最小頂點、次小頂點和最大頂點;并且還要計算出最小頂點之外的N個頂點的形心點的值;

2)計算出最大頂點關(guān)于形心點的反射點的值;在計算出反射點的目標函數(shù)值，如果大于次小頂點，則需要在該方向上向下執(zhí)行一次收縮運算;如果小于最大頂點值，則需要執(zhí)行一次擴張運算;

3)如果單純形整體收斂與最低點，則執(zhí)行下一次迭代，目的是為了利用單純形算法的局部搜索和蟻群算法的全局搜索能力，在螞蟻初始化時，采用單純形算法來進行初始生成，從而避免算法在初始化時的均勻生成的缺點．

為了利用單純形算法的局部搜索和蟻群算法的全局搜索能力，在螞蟻初始化時，采用單純形算法來進行初始生成，從而避免算法在初始化時的均勻生成的缺點．在算法進入迭代搜索的時，首先要利用蟻群算法對目標函數(shù)進行優(yōu)化，對相應(yīng)的迭代次數(shù)進行設(shè)置，當蟻群算法運行并且搜索到后期時，需要每隔10 代需要進行一次單純形的搜索，從而可以避免搜索所需要的時間過長，當單純行搜索完成后再繼續(xù)進行蟻群搜索［1－5］，圖1 為該算法的流程圖．

圖1 單純形的蟻群算法流程圖Fig．1 A simplex search－ant colony optimization algorithm flow chart

3 帶時間窗車輛路徑問題求解

3．1 容量約束的車輛路徑問題

首先考慮容量約束的車輛路徑問題，隨機生成一組坐標數(shù)據(jù)和容量限制，如圖2 所示．

圖2 站點坐標分布圖Fig．2 Coordinates of site map

利用了改進后的單純性蟻群算法進行了求解，用Matlab 軟件編程，得出如下結(jié)果如圖3 所示，圖4 為最優(yōu)收斂的路徑圖．

從結(jié)果得知總共需要5 輛車，才能滿足各個站點的需求，5輛車的路線如下表1．

表1 優(yōu)化路線結(jié)果排列Tab．1 Route optimization results

此時最佳路徑長度為642．294，由圖4 可知，該算法對多站點車輛路徑問題也有較強的適應(yīng)性．

3．2 帶時間窗車輛路徑問題求解

首先在帶時間窗車輛路徑問題數(shù)據(jù)庫中，找得一組數(shù)據(jù)源，用Matlab 畫出各個站點分布圖(圖5)．由圖5可知，共有26 個站點，其中包括一個車場0，同理，用Matlab 軟件基于最大最小螞蟻系統(tǒng)求解，取定參數(shù)α=1，β=2，ρ=0．02，螞蟻數(shù)目n為26，得出車輛路線行駛圖(圖6)．

圖3 站點路線優(yōu)化結(jié)果Fig．3 Optimization results of site map

圖4 平均和全局最短路徑長度Fig．4 The average and best path

圖5 站點坐標分布圖Fig．5 Coordinates of site map

圖6 站點路線優(yōu)化結(jié)果Fig．6 Optimization results of site map

從結(jié)果得知總共需要7 輛車，才能滿足各個站點的需求，七輛車的路線如表2．

表2 優(yōu)化路線結(jié)果排列Tab．2 Route optimization results

由程序結(jié)果可知，最短路徑為5 937．2，由此可知，單純形螞蟻系統(tǒng)對帶時間窗車輛路徑問題也有較好的適用性．將此結(jié)果和帶容量約束的車輛路徑問題相比，帶時間窗的車輛路徑問題所用車輛明顯多于帶容量約束的車輛路徑問題，因為加入時間窗的約束后，每輛車的行駛路程就會改變，這與實際中遇到的情況是吻合的．

［1］ 劉建，王益群，姜萬錄，等． 引入單純形算子的粒子群優(yōu)化算法在板形模式識別中的應(yīng)用［J］． 中國機械工程，2007，18(23):2977－2880．

［2］ 田明楊，周永杰，王媛 基于蟻群算法轉(zhuǎn)移概率的研究［J］． 硅谷，2010(3):95－95．

［3］ 李舟，向長城． 非線性單純形蟻群算法在垃圾運輸問題中的應(yīng)用［J］湖北民族學(xué)院學(xué)報:自然科學(xué)版，2011，29(3):271－273．

［4］ 汪祖柱，程家興，方宏兵，等．車輛路徑問題的混合優(yōu)化算法［J］．運籌與管理，2004，13(6):48－52．

［5］ 王進，周紹梅．一種基于MMAS 的具有獎罰機制的分組蟻群算法［J］．計算機應(yīng)用與軟件，2009，26(3):237－238．

［6］ 段海濱，王道波．一種快速全局優(yōu)化的改進蟻群算法及仿真［J］．信息與控制，2004，33(2):241－244．

［7］ 張曦煌，李巖，李彥中．求解VRP 問題的改進蟻群算法［J］．計算機工程與設(shè)計，2007，28(23):5694－5696．

［8］ 胡俊鵬．基于雙向選擇的蟻群相遇算法的優(yōu)化［J］．湖北民族學(xué)院學(xué)報:自然科學(xué)版，2013，31(1):60－64．

［9］ 杜衡吉，李勇．蟻群算法中參數(shù)設(shè)置對其性能影響的研究［J］．現(xiàn)代計算機，2012(9):3－7．

［10］ 張建秋．基于蟻群算法的TSP 的算法與研究［J］．科技信息，2010(25):71－71．

［11］ 冷畫屏，王明慧，余永權(quán)．最大－最小螞蟻系統(tǒng)及K－TSP 問題的求解［J］．計算機應(yīng)用與軟件，2008，25(2):242－244．

［12］ Stutzle T，Hoos H H．Improving the ant system:a detailed report on the MAX－MIN ant system［J］．Technical report AIDA－96－12，1996(32):309－314．

［13］ Stutzle T，Hoos H H．The MAX－MIN ant system and local search for the traveling salesman problem［C］//Proceedings of the 1997 IEEE International Conference on Evolutionary computation(ICEC'97)，1997:309－314．

［14］ 匡正，王智杰．解決二次分配問題的改進蟻群算法［J］．計算機工程與應(yīng)用，2006，42(16):89－91．