蟻群算法1…VRP的問題來源和研究現(xiàn)狀物流（Logistics）

1…物資的流通：來源于二戰(zhàn)時(shí)期軍隊(duì)的后勤保障系統(tǒng)2…現(xiàn)代企業(yè)的第三利潤來源：營運(yùn)成本與價(jià)格競爭力的強(qiáng)弱3…電子商務(wù)全面改變經(jīng)濟(jì)活動(dòng)：物流管理成為經(jīng)濟(jì)發(fā)展的重要課題1/13/20232/23通常意義下的VRP的提法為：已知一批客戶，每個(gè)客戶點(diǎn)的位置和貨物需求已知，車輛的負(fù)載能力一定，每輛車都從起點(diǎn)(depot)出發(fā)，完成若干客戶點(diǎn)的運(yùn)送任務(wù)后再回到起點(diǎn).假設(shè)每個(gè)客戶被而且只被訪問一次，每輛車所訪問的城市的需求總和不能超過車輛的負(fù)載能力.問題是使所有客戶需求都得到滿足，且總旅行成本最小.1…VRP的問題來源和研究現(xiàn)狀車輛路徑問題（VehicleRoutingProblem，簡記VRP）是物流配送優(yōu)化中關(guān)鍵的一環(huán)1.提高物流經(jīng)濟(jì)效益、實(shí)現(xiàn)物流科學(xué)化2.是管理科學(xué)的一個(gè)重要研究課題3.其優(yōu)化技術(shù)是現(xiàn)代物流配送的一項(xiàng)關(guān)鍵技術(shù).1/13/20233/23VRP已經(jīng)被證明是NP—hard問題

目前提出的求解算法很多1/13/20234/231…VRP的問題來源和研究現(xiàn)狀求解方法（Solution）精確算法（ExactAlgorithm）

1.動(dòng)態(tài)規(guī)劃方法;2.割平面法;3.網(wǎng)絡(luò)流算法;4.分支定界法構(gòu)造啟發(fā)式算法（StructuralHeuristicAlgorithm）

1.掃描法;2.節(jié)約算法;3.最鄰近法;4.最近插入法智能啟發(fā)式算法（IntelligentHeuristicsAlgorithm

） 1.遺傳算法;2.模擬退火法;3.禁忌搜索算法; 4.蟻群算法;5.微粒群算法;6.神經(jīng)網(wǎng)絡(luò)算法1/13/20235/232…蟻群算法及其在VRP中的具體應(yīng)用蟻群算法與VRP蟻群覓食，會(huì)選擇一條從蟻穴到食物源的最短路徑.

1/13/20236/232…蟻群算法及其在VRP中的具體應(yīng)用螞蟻選擇最短路徑的原理：信息素信息素濃度越高螞蟻越容易選擇經(jīng)過時(shí)間越長信息素?fù)]發(fā)越多螞蟻選擇較短路徑1/13/20237/232…蟻群算法及其在VRP中的具體應(yīng)用代表路徑上的信息素濃度對選擇概率的影響，信息素濃度越高，選擇該路徑的機(jī)率就越大.故實(shí)際上就是蟻群的正反饋機(jī)制.吃午飯了，去一食堂還是二食堂呢？大家都去一食堂吃飯，我也去一食堂吧！代表路徑上的啟發(fā)因子，，為路徑間的距離，即距離越小選擇該路徑的機(jī)率就越大.故啟發(fā)因子實(shí)際代表螞蟻的能見度.要吃午飯了，去一食堂還是二食堂呢？二食堂比較近，去二食堂吧。為隨機(jī)因子，即在選擇路徑時(shí)給與螞蟻適當(dāng)擾動(dòng).

要吃午飯了，今天到底是去一食堂還是二食堂呢？隨便選一個(gè)吧。1/13/20238/232…蟻群算法及其在VRP中的具體應(yīng)用對于蟻群算法中的等相關(guān)參數(shù)α、β、γ的選擇，目前還沒有成熟的理論可供參考，一般只能通過實(shí)驗(yàn)進(jìn)行選擇.

信息素?fù)]發(fā)：本文中，信息素更新策略采用最大-最小螞蟻系統(tǒng)MMAS算法，因?yàn)榻?jīng)大量學(xué)者實(shí)驗(yàn)驗(yàn)證，這種更新機(jī)制有較好的效果.

1/13/20239/233…VRP程序設(shè)計(jì)和求解分析本文求解VRP主要采取蟻群優(yōu)化2階段構(gòu)造算法（AntConstructiveAlgorithm）

即：第1階段，根據(jù)蟻群優(yōu)化準(zhǔn)則，每次將一個(gè)不在線路上的點(diǎn)增加進(jìn)線路，直到所有的點(diǎn)都被安排進(jìn)線路為止；第2階段，將得到的可行解進(jìn)行2-OPT變換優(yōu)化。1/13/202310/233…VRP程序設(shè)計(jì)和求解分析第1階段，根據(jù)蟻群優(yōu)化準(zhǔn)則，每次將一個(gè)不在線路上的點(diǎn)增加進(jìn)線路，直到所有的點(diǎn)都被安排進(jìn)線路為止；1/13/202311/233…VRP程序設(shè)計(jì)和求解分析從當(dāng)前點(diǎn)出發(fā)，根據(jù)選擇概率選擇下一個(gè)點(diǎn)即在選擇時(shí)，計(jì)算當(dāng)前點(diǎn)到所有可選點(diǎn)的選擇概率，加以比較，并選擇概率最大的點(diǎn)。1/13/202312/233…VRP程序設(shè)計(jì)和求解分析第2階段，將得到的可行解進(jìn)行2-OPT變換優(yōu)化。2-opt原理1/13/202313/233…VRP程序設(shè)計(jì)和求解分析以上為程序設(shè)計(jì)原理，具體程序流程如下：BEGINDO{FOR(i=0;i<最大螞蟻組數(shù);i++) { FOR(j=0,reach=1;reach<最大節(jié)點(diǎn)數(shù);j++)//j為螞蟻數(shù) { 初始化一只螞蟻，即將一只螞蟻放到起點(diǎn); WHILE(螞蟻沒有達(dá)到最大載重量且仍然有節(jié)點(diǎn)未經(jīng)訪問) { 螞蟻按照選擇概率公式（1）選擇下一節(jié)點(diǎn); reach++；//reach代表已經(jīng)訪問的節(jié)點(diǎn)數(shù) } reach--; } ant_n[i]=j;將這組螞蟻的螞蟻數(shù)記錄下來 nextant;轉(zhuǎn)到下一組螞蟻 }FOR(i=0;i<最大螞蟻組數(shù);i++) FOR(j=0;j<本組螞蟻數(shù);j++) 對每一只螞蟻進(jìn)行2-opt交換；比較得到的解選擇本次循環(huán)得到的最好螞蟻，將其與全局最好解進(jìn)行比較.按照全局最優(yōu)解根據(jù)公式（2）更新信息素nc++;}WHILE(nc<NC);迭代結(jié)束，輸出最優(yōu)解1/13/202314/233…VRP程序設(shè)計(jì)和求解分析程序流程圖BEGINEND螞蟻按照選擇概率公式選擇下一節(jié)點(diǎn)2-OPT優(yōu)化信息素更新1/13/202315/233…VRP程序設(shè)計(jì)和求解分析為了檢驗(yàn)算法的結(jié)果，求解實(shí)例全部采用osiris.tuwien.ac.at網(wǎng)絡(luò)公布的CVRP測試問題，下載網(wǎng)址為：http://osiris.tuwien.ac.at/~wgarn/VehicleRouting/neo/Problem%20Instances/CVRPinstances.html

各實(shí)例驗(yàn)證結(jié)果如下：VRP實(shí)例已知最優(yōu)解本文程序運(yùn)行結(jié)果偏離程度總行程（COST）車輛數(shù)總行程（COST）車輛數(shù)A-n33-k56615700.14855.92%A-n38-k57305796.59859.12%A-n54-k7116771268.3378.68%B-n34-k57885834.60355.91%A-n37-k694961104.39616.37%B-n50-k77417895.556720.85%1/13/202316/233…VRP程序設(shè)計(jì)和求解分析實(shí)例：A-n33-k5

實(shí)驗(yàn)時(shí)，取迭代次數(shù)為20次，選擇概率權(quán)重為信息素?fù)]發(fā)迭代次數(shù)12345路徑長度792.5831.036813.547730.671795.566與最優(yōu)解的差131.5170.036152.54769.671134.566迭代次數(shù)678910路徑長度778.556738.302732.822720.824714.067與最優(yōu)解的差117.55677.30271.82259.82453.067迭代次數(shù)1112131415路徑長度738.302738.302738.148750.682780.854與最優(yōu)解的差77.30277.30277.14889.682119.854迭代次數(shù)1617181920路徑長度761.337721.642738.302700.148745.092與最優(yōu)解的差100.33760.64277.30239.14884.0921/13/202317/233…VRP程序設(shè)計(jì)和求解分析將表格數(shù)據(jù)畫圖得：1/13/202318/233…VRP程序設(shè)計(jì)和求解分析得到的A-n33-k5具體運(yùn)輸路線1/13/202319/23謝謝觀賞結(jié) 束1/13/202320/231/13/202321/23◆分支定界法（BranchandBoundApproach）[6]分支定界法是一種應(yīng)用范圍很廣的搜索算法，它的基本思想是把給定問題分解為若干個(gè)較小的子問題，每個(gè)子問題又可繼續(xù)分解，直到子問題不能再分解或不能產(chǎn)生最優(yōu)解.根據(jù)問題的特點(diǎn)和不同的策略，把問題分解為子問題的過程稱之為分支.分支定界法求解VRP問題的基本思想是，以相應(yīng)的不含整數(shù)約束的VRP問題(B)的最優(yōu)解為出發(fā)點(diǎn)，若此解是整數(shù)解，那么這個(gè)解就是原VRP問題(A)的最優(yōu)解，否則以B的非整數(shù)解的相鄰整數(shù)作附加條件，形成2個(gè)分支，即2個(gè)子問題，進(jìn)行求解.若對上面2個(gè)子問題求出最優(yōu)解是整數(shù)解，則停止該子問題的分支，否則繼續(xù)分支求解.這種方法只能適用于求解小型VRP問題.Kolenatal曾利用此方法求解含時(shí)間窗約束的車輛巡回問題，發(fā)現(xiàn)當(dāng)節(jié)點(diǎn)數(shù)擴(kuò)大至12時(shí)，計(jì)算機(jī)有內(nèi)存不足的現(xiàn)象產(chǎn)生.1/13/202322/23◆割平面法（CuttingPlanesApproach）[6]割平面法求解VRP問題(A)的基本思想是，在求解相應(yīng)的不含整數(shù)約束的VRP問題(B)上，增加線性約束條件(幾何術(shù)語稱為割平面)，以將B的可行域切割掉一部分，使其切割掉的部分只包含非整數(shù)解，沒有切割掉任何整數(shù)可行解，直到切割后得到的可行域有一個(gè)整數(shù)坐標(biāo)的極點(diǎn)恰好是A的最優(yōu)解為止.由于割平面法求解時(shí)間過長，故不適用于大規(guī)模問題.1/13/202323/23◆網(wǎng)絡(luò)流算法（NetworkFlowApproach）[6]網(wǎng)絡(luò)流算法求解VRP問題的基本思想是，首先構(gòu)建VRP問題的網(wǎng)絡(luò)模型，找到網(wǎng)絡(luò)中需調(diào)量最大的弧，然后通過調(diào)節(jié)弧流量或弧兩端節(jié)點(diǎn)上的位勢，來減少弧上的需調(diào)量，直至所有弧的需調(diào)量都等于零.由于網(wǎng)絡(luò)模型的頂點(diǎn)數(shù)目和邊的數(shù)目會(huì)顯著影響網(wǎng)絡(luò)流算法時(shí)間效率，所以這種算法只適用于小規(guī)模的VRP問題.1/13/202324/23◆動(dòng)態(tài)規(guī)劃方法（DynamicProgrammingApproach）[6]動(dòng)態(tài)規(guī)劃法求解VRP問題的基本思路是，將VRP問題視為一個(gè)階段的決策問題，進(jìn)而將其轉(zhuǎn)化為依次求解具有遞推關(guān)系的單階段的決策問題，從而簡化計(jì)算過程.用這種方法可求得VRP的最優(yōu)解，但僅適用于較小規(guī)模的尋優(yōu)問題.此外，F(xiàn)isher(1985)、Jomstern(1986)、Madsen(1990)、Halse(1992)等人分別用不同的拉格朗日分