【文章內(nèi)容簡(jiǎn)介】 進(jìn)路線堵車事件，系統(tǒng)能夠繞開(kāi)堵車路段動(dòng)態(tài)規(guī)劃配送路線 d：需要滿足的 幾個(gè)約束條件： 1) 每條線路上的客戶點(diǎn)需求量之和不超過(guò)汽車載重量； 2) 每條配送路徑的總長(zhǎng)度不超過(guò)汽車一次配送的最大行駛距離； 3) 每個(gè)客戶點(diǎn)的需求必須且只能由一輛汽車來(lái)完成。 數(shù)學(xué)模型的建立 符號(hào)的定義 L： 需求 點(diǎn)總數(shù)； qi： 需求 點(diǎn) i的貨物需求量，其中 i=1， 2，?， L； dij：從 需求 點(diǎn) i到 需求 點(diǎn) j 的距離。 注： 當(dāng) i=j=0時(shí)， 表示起始地 ， K：車輛數(shù)量 Qk：車輛 k的最大 載重 ，其中 k=1， 2，?， K Dk：車輛 k的最 長(zhǎng) 行駛距離，其中 k=1， 2，?， K nk：車輛 k 需要 配送的 需求點(diǎn) 總數(shù)， nk=0 時(shí)，表示 該車 沒(méi)有 進(jìn)入線路 。 k=1，2，?， K Rk：車輛 k 配送的 需求 點(diǎn)的集合。當(dāng) nk=0 時(shí)， Rk=Φ；當(dāng) nk≠ 0 時(shí)，? ? ? ?LrrrR knkkkk ,2,1, 21 ?? ?? 中國(guó)礦業(yè)大學(xué) 2021 屆本科生畢業(yè)論文 第 13 頁(yè) 約束條件 根據(jù)前文對(duì)路徑優(yōu)化的描述 ， 需要注意的約束條件如下 ： 1)線路上的 需求 點(diǎn)需求量之和 不可以 超過(guò)汽車載重量： kni r Qqkik ???1， nk≠ 0 2)每條 路徑的總長(zhǎng)度不超過(guò)汽車一次配送的最大行駛距離： krni rr Ddd knkkikik ???? ? 01 1， nk≠ 0 3) 每個(gè) 需求 點(diǎn)的需 每次有 且只能由一輛汽車來(lái)完成： ??? 21 kk RR ， k1≠ k2 4) 配送 路徑 遍歷所有 需求 點(diǎn)： ? ?LnLnLRKkkkKkk???????110,2,1 ?? 優(yōu)化目標(biāo) 根據(jù) 需 優(yōu)化目標(biāo) ， 列出 所要 優(yōu)化目標(biāo)的數(shù)學(xué)形式： ? ?? ???? ???????? ????????? ?? ? ?? ??其他,11,0s g ns g nm i n1011kkkKkrnirrnnnddZ knkkikik 中國(guó)礦業(yè)大學(xué) 2021 屆本科生畢業(yè)論文 第 14 頁(yè) 優(yōu)化配送路線的蟻群算法 蟻群算法 的出現(xiàn)是根據(jù)自然界生物中螞蟻的覓食 行為啟發(fā)而產(chǎn)生的“自然”算法。 蟻群算法的最顯著的特點(diǎn)在于 蟻群中的螞蟻 是 以“信息素”（ pheromone）為 介質(zhì)的間接異步聯(lián)系方式 。螞蟻 的行為（尋找食物或者尋找回巢的路徑） ， 會(huì)在其走過(guò)的途中釋放一些化學(xué)物質(zhì)（即我們所說(shuō)的“信息”） 。 同一蟻群會(huì)發(fā)現(xiàn)這些信息素 ， 信息素作為一種特有信號(hào) 影響 蟻群 的行動(dòng)（ 具體表現(xiàn)為后者選擇走這些具有“信息”的路徑的可能性要大于選擇其他路徑的可能性 ），而后到者 會(huì)繼續(xù)在該“信息素”基礎(chǔ)上進(jìn)行加強(qiáng)，如此往復(fù)循環(huán) 。這樣， 該路徑走過(guò)的螞蟻越來(lái)越多，“信息素”也越來(lái)越多，后來(lái)者選擇此路徑的可能性也更大 （因?yàn)闅埩舻男畔舛容^大的緣故）。 這樣，在單位時(shí)間內(nèi)此路徑持續(xù)被更多的螞蟻選擇訪問(wèn)，信息素積累增多， 直到最后，幾乎所有的螞蟻都選擇這條最短的路徑 。 算法實(shí)現(xiàn) 我們用人工螞蟻代替車輛對(duì) 需求點(diǎn) 點(diǎn)進(jìn)行 “配送” ，螞蟻在 i 需求 點(diǎn)選擇的下一個(gè) 需求 點(diǎn) j 時(shí)，主要考慮 兩方面因素 ，一是 i， j 兩 需求點(diǎn)之間 關(guān)系的親密程度 （即可見(jiàn)度） ，記為 ?ij； 另一點(diǎn)則需要 考慮由 目前 的循環(huán)所得路徑 優(yōu)化 方案體現(xiàn)出來(lái)的由 i 到 j 的可行性（ 即信息素濃度 ），記為 ?ij。 在算法的初始時(shí)刻，將 m 只螞蟻隨機(jī)地放到 n 座城市，同時(shí)，將每只螞蟻的禁忌表的第一個(gè)元素設(shè)置為它當(dāng)前所在的城市。此時(shí)各路徑上的信息素量相等，設(shè)τ ij(0) = C（ C 為一較小的常數(shù)） 在 t時(shí)刻螞蟻 k 由 需求 點(diǎn) i轉(zhuǎn)移到 需求 點(diǎn) j 的概率： [ ( ) ] [ ][ ( ) ] [ ] i f ()0 ot he r wis eij ijk all owe d ik ikktkk tijj al l ow e dpt????????????? ??? ??? （ ） 其中， Jk(i)= {1， 2，??， n} tabuk 表示螞蟻 k 下一步允許選擇的城市集合。螞蟻 k 當(dāng)前走過(guò)的城市都記錄在列表 tabuk。當(dāng)每一座城市都加入到中國(guó)礦業(yè)大學(xué) 2021 屆本科生畢業(yè)論文 第 15 頁(yè) tabuk 中時(shí)，螞蟻 k 便完成了一次循環(huán)，此時(shí)螞蟻 k 所走過(guò)的路徑便是 TSP（旅行家問(wèn)題） 的一個(gè)可行解。 (2. 1)式中的η ij 表示一個(gè)啟發(fā)式因子，代表螞蟻從需求點(diǎn) i 轉(zhuǎn)移到需求點(diǎn) j 的期望程度。在 AS 算法中，η ij 通常取需求點(diǎn) i 與需求點(diǎn) j 之間距離的倒數(shù)。α和β分別表示信息素和啟發(fā) 式因子的相對(duì)重要程度。當(dāng)所有螞蟻完成一次循環(huán)后，信息素根據(jù)式（ 2. 2）更新。 ? ? ijijij tnt ???? ?????? )()1( (2. 2) ?? ??? mk kijij 1 ?? (2. 3) 其中ρ (0 ρ 1)是路徑上信息素的蒸發(fā)系數(shù)， 1ρ 表示信息素的持久性系數(shù)；△τ ij 表示本次迭代邊 ij 上信息素的增量?！鳓?kij 表示第 k 只螞蟻在本次迭代中留在邊 ij 上的信息素量。如果螞蟻 k 沒(méi)有經(jīng)過(guò)邊 ij，則△τ kij的值為零?！鳓?kij 表示為： , k i j0 , k KijQL????? ???若 螞 蟻 在 本 次 周 游 中 經(jīng) 過(guò) 邊 否 則 (2. 4) 其中， Q 為正常數(shù)， Lk 表示第 k 只螞蟻在本次周游中所走過(guò)路徑的長(zhǎng)度。 M. Dorigo 提出了 3 種 AS 算法的模型 ，式 ()稱為 antcycle，另外兩個(gè)模型分別稱為 antquantity 和 antdensity，其差別主要在 (2. 4) 式，即：在 antquantity 模型中為： , k i j0 , ijkijQd????? ???螞 蟻 在 時(shí) 刻 t 和 t+1 經(jīng) 過(guò) 邊否 則 (2. 5) 在 antdensity 模型中為： (2. 6) AS 算法實(shí)際上是正反饋原理和啟發(fā)式算法相結(jié)合的一種算法。在選擇路徑時(shí)，螞蟻不僅利用了路徑上的信息素，而且用到了城市間距離的倒數(shù)作為啟發(fā)式因子。 AS 算法的時(shí)間復(fù)雜度為Ο (NC*n2*m) 算法的空間復(fù)雜度為 S(n)=O(n2)+O(n*m) ，其中 NC 表示迭代的次數(shù)， n 為城市數(shù)， m為螞蟻的數(shù)目。 , k ij0 , kij Q? ??? ?? 螞 蟻 在 時(shí) 刻 t 和 t+1 經(jīng) 過(guò) 邊 否 則中國(guó)礦業(yè)大學(xué) 2021 屆本科生畢業(yè)論文 第 16 頁(yè) 問(wèn)題概述 TSP 問(wèn)題是旅行商問(wèn)題的簡(jiǎn)稱，簡(jiǎn)而言之，說(shuō)的是從前有一個(gè)商人，要從自己家開(kāi)始出發(fā)，途徑一些要求必須經(jīng)過(guò)的城市，最后回到家鄉(xiāng)，而且經(jīng)過(guò)的城市不能有所重復(fù)。旅行商要做的就是找到一條最短路徑達(dá)到目的地。該問(wèn)題在圖論下又叫做哈密頓圈問(wèn)題，最早是由一個(gè)叫 Euler 研究出其雛形。 基于蟻群算法求解旅行商問(wèn)題（ TSP）的基本流程 作為一個(gè)經(jīng)典的路徑尋優(yōu)問(wèn)題， TSP 問(wèn)題的理解并不難，但事實(shí)上至今也沒(méi)有準(zhǔn)確地答案。我們用一個(gè)帶權(quán)完全圖 G=（ N,A） 來(lái)闡述， N 是所有目標(biāo)城市點(diǎn)的集合， A是所有邊（路徑模型）的集合。首先對(duì)螞蟻數(shù)量、信息素等進(jìn)行初始化，同時(shí)將迭代次數(shù)初始化為零。禁忌表是為了記錄遍歷城市的一個(gè)表，算法開(kāi)始前其值為零，表示未訪問(wèn)任何城市。隨著算法的進(jìn)行，螞蟻會(huì)選擇城市出發(fā)并留下信息素，此時(shí)禁忌表值發(fā)生改變，同時(shí)信息素也會(huì)更新，當(dāng)超出最大迭代次數(shù)時(shí)，程序?qū)?huì)終止，否則迭代繼續(xù)，直至滿足條件。 具體流程如下： 設(shè)帶權(quán)圖 G=（ N， A）， N=（ 1， 2， 3， 4， 5? ,n） 表示城市的結(jié)點(diǎn)集合，各點(diǎn)的坐標(biāo)信息和距離 dij 已知。設(shè) Xij=1(當(dāng)（ i,j）在 最優(yōu)回路上時(shí) )； Xij=0（其他條件時(shí)） 因此可得旅行商問(wèn)題的數(shù)學(xué)模型如下： ???????? 這里我們規(guī)定丨 S 丨表示 s 中 G 的所有頂點(diǎn)數(shù)量。上述約束條件中， a、 b兩個(gè)約束條件的作用就是限制每個(gè)點(diǎn)僅有一條邊進(jìn)和一條邊出；而約束條件 c則保證搜索過(guò)程中不會(huì)出現(xiàn)回路解。滿足上述三個(gè)條件的所有解的回路就是哈密頓回路。同時(shí)出現(xiàn)新概念 — 對(duì)稱型 TSP，即滿足條件 dij=dji。 總結(jié)其數(shù)學(xué)模型下 TSP 問(wèn)題的 步驟為： 中國(guó)礦業(yè)大學(xué) 2021 屆本科生畢業(yè)論文 第 17 頁(yè) Begin 對(duì)蟻群初始化 Loop 構(gòu)造螞蟻路徑； 對(duì)某一個(gè)螞蟻進(jìn)行局部搜索法； 信息素更新； 未達(dá)到迭代次數(shù)，繼續(xù)轉(zhuǎn) loop； 找到最優(yōu)解并輸出； End 從 TSP 問(wèn)題的數(shù)學(xué)模型可以看出，需要特別注意兩個(gè)步驟：構(gòu)造螞蟻路徑以及信息素更新。蟻群算法之所以優(yōu)于其他算法，是因?yàn)槊恳淮蔚校畔⑺氐钠谕低鶗?huì)低于其初始值，其計(jì)算公式如下： 式中， m 表示螞蟻數(shù)量， Cnm 代表路徑長(zhǎng)度。選擇該初始值的初衷是因?yàn)椋坏┬畔⑺爻跏贾颠^(guò)小，搜索區(qū)域往往受到限制，大多搜索會(huì)過(guò)于集中 在初始有限的路徑中，即我們所說(shuō)的陷入局部搜索中，很難找到最優(yōu)解。相反地，如果讓信息素的初始值過(guò)大，就會(huì)無(wú)法發(fā)揮蟻群算法初始的多次迭代優(yōu)勢(shì)，這種效果會(huì)一直持續(xù)到信息素蒸發(fā)到很小的程度，此時(shí)更新的信息素才會(huì)指引搜索偏向性。 我們從構(gòu)建路徑個(gè)信息素更新兩方面剖析該問(wèn)題： 構(gòu)建路徑 在蟻群算法中，我們?cè)O(shè)初始有 m只螞蟻參與 TSP 路徑的構(gòu)建。將所有螞蟻隨機(jī)的選中的需求點(diǎn)中。在構(gòu)建路徑過(guò)程的每一步中，螞蟻會(huì)在規(guī)則概論下選擇其下個(gè)訪問(wèn)需求點(diǎn)，其選擇概論如下： 中國(guó)礦業(yè)大學(xué) 2021 屆本科生畢業(yè)論文 第 18 頁(yè) [ ( ) ] [ ][ ( ) ] [ ] i f ()0 ot he r wis eij ijk all owe d ik ikktkk tijj al l ow e dpt????????????? ??? ??? 上式中， ij? 是一個(gè)初始的啟發(fā)式信息， α 和 β 在前幾章解釋過(guò)，前者主要是影響信息素的產(chǎn)生，后者為啟發(fā)式信息的重要參數(shù)， allowedk 表示螞蟻們未訪問(wèn)過(guò)的需求點(diǎn)，換而言之，就是螞蟻下一個(gè)需要到達(dá)的點(diǎn)。我們分別對(duì) α 和β 取零值，可以發(fā)現(xiàn)，當(dāng) α 為 0時(shí)，此時(shí)會(huì)最大概論選出離 i點(diǎn)最近需求點(diǎn)，這滿足貪心算法的定義。而當(dāng)β =0時(shí)，此時(shí)對(duì)于概論 P 來(lái)說(shuō)，能夠改變它的只有信息素的放大系數(shù)，換句話說(shuō)，信息素并沒(méi)有發(fā)揮它該發(fā)揮的作用，即信息素沒(méi)有使用任何啟發(fā)式偏向性。此時(shí)的蟻群算法相對(duì)與其他智能算法沒(méi)有任 何優(yōu)勢(shì)可言，甚至不如其他算法，尤其是α大于 1時(shí)， AS 將會(huì)越來(lái)越緩慢，直至停滯運(yùn)行。此時(shí)的算法依舊會(huì)給出一條路徑，也就是多數(shù)螞蟻選擇的路徑，但其實(shí)已經(jīng)沒(méi)有任何研究的意義了，此路徑甚至算不上一個(gè)可行解。 在前幾章我們針對(duì)幾種智能算法做介紹的時(shí)候，提到過(guò)記憶儲(chǔ)存這個(gè)概念，其包括短期儲(chǔ)存和長(zhǎng)期儲(chǔ)存，事實(shí)上，在蟻群算法中，同樣有記憶儲(chǔ)存的概念。我們用 Mk 來(lái)表示螞蟻們共同維護(hù)的這個(gè)記憶儲(chǔ)存，類似與禁忌表，記憶儲(chǔ)存里面會(huì)給出已經(jīng)被訪問(wèn)過(guò)的需求點(diǎn)集合，并且這些需求點(diǎn)都是嚴(yán)格按照先后順序被存儲(chǔ)?？梢园l(fā)現(xiàn)，無(wú)論是 Mk，還是 Nik，都與訪問(wèn)路徑有關(guān)，事實(shí)上后者往往需要以前者 Mk給出的構(gòu)造規(guī)則來(lái)定義概論 P。除此之外，在計(jì)算構(gòu)造路徑 Tk的總長(zhǎng)度時(shí)，同樣要使用到記憶存儲(chǔ)。 我們用兩種方式可以實(shí)現(xiàn)可行解的構(gòu)建：第一種是并行構(gòu)建，也就是說(shuō)每一只螞蟻都可以