【正文】 ............................ 25 功能要求 ...................................................................................................... 25 總體設(shè)計(jì) ....................................................................................................... 25 軟件架構(gòu) ...................................................................................................... 26 中國(guó)礦業(yè)大學(xué) 2021 屆本科生畢業(yè)論文 第 2 頁(yè) 測(cè)試文檔 ...................................................................................................... 26 第七章 總結(jié)語(yǔ) .............................................................................................................. 27 參考文獻(xiàn) .............................................................................................................. 29 中國(guó)礦業(yè)大學(xué) 2021 屆本科生畢業(yè)論文 第 3 頁(yè) 摘要： 本文所要探討的物流配送路徑優(yōu)化問(wèn)題 ， 是基于改進(jìn)蟻群算法的物流最優(yōu)路徑選擇系統(tǒng) ， 算法實(shí)際上是正反饋原理和啟發(fā)式算法相結(jié)合的一種算法。本系統(tǒng) 提供給合乎用戶需求的優(yōu)化路徑策略 ，如 路徑最短、時(shí)間最短 等進(jìn)行配送路線規(guī)劃 方案 。 如此龐大的數(shù)字，我們 如果 僅僅將它 降低 10％，一年就可以節(jié)約近 400億美元。數(shù)據(jù)顯示我國(guó) GDP 中物 流所占比持續(xù)偏高，甚至高于發(fā)達(dá)國(guó)家。 試想一下，用戶花費(fèi)較少的支出買了商品，卻需要在商品配送上另花費(fèi)更多的時(shí)間和金錢，這本身就是一個(gè)不合理的現(xiàn)象。多種不同的物流節(jié)點(diǎn)和聯(lián)結(jié)各點(diǎn)的線路構(gòu)成了整個(gè)物流網(wǎng)絡(luò)。此類問(wèn)題的解決方法有不少，傳統(tǒng)方法包括啟發(fā)式算法和精確算法。 這是該方法的優(yōu)勢(shì)所在。 在以往研究的基礎(chǔ)上，建立適合實(shí)際物流配送網(wǎng)絡(luò)路徑優(yōu)化的模型，并選擇使用有效的算法，為物流配送網(wǎng)絡(luò)路徑優(yōu)化問(wèn)題的研究和實(shí)踐提供理論依據(jù)和實(shí)際方法。 本文研究的意義 根據(jù) Ronald H． Ballo 的觀點(diǎn)，運(yùn)輸決策包括四種：運(yùn)輸方式的選擇、對(duì)運(yùn)輸路線的規(guī)劃、車輛調(diào)度以及集中運(yùn)輸?shù)取Ｆ渲?，運(yùn)輸問(wèn)題不屬于本文探討的范圍。高效率的物流中心配送作業(yè)具體而言就是：從配送中心使用多輛車向多個(gè)目的地送貨，假設(shè)每個(gè)需求點(diǎn)的位置和供量 確定，車輛載重一定，需要解決的就是合理安排車輛路線，以達(dá)到預(yù)定的目標(biāo) (即最少費(fèi)用，最短路徑，最少時(shí)間，最少車輛使用等 )。 本論文的主要工作 物流配送路徑優(yōu)化問(wèn)題簡(jiǎn)稱 VRP，本論文將重點(diǎn)就城市車輛路徑優(yōu)化問(wèn)題作為研究對(duì)象，針對(duì)目前路徑優(yōu)化研究的復(fù)雜性以及各類算法的使用，著重以蟻群算法為主要算法，在蟻群算法基礎(chǔ)上結(jié)合最大最小蟻群算法對(duì)其進(jìn)行改進(jìn)，從而是整個(gè)系統(tǒng)的尋優(yōu)速度更快、結(jié)果更準(zhǔn)確。針對(duì)五中算法的基本思路、優(yōu)缺點(diǎn)、以及實(shí)際應(yīng)用中產(chǎn)生的問(wèn)題與思考。 第六章屬于對(duì)路徑優(yōu)化系統(tǒng)的描述，主要有總體設(shè)計(jì)、功能要求以及界面的相關(guān)方面。由于這一問(wèn)題的理論涉及多學(xué)科 ，而且 應(yīng)用前景 可觀， 所以很快引起了應(yīng)用數(shù)學(xué)、物流學(xué)、運(yùn)籌學(xué)、計(jì)算機(jī)應(yīng)用 圖論與網(wǎng)絡(luò)分析、交通運(yùn)輸工程、管理科學(xué)與工程等學(xué)科的專家、工程技術(shù)人員的 極大關(guān)注 。配送路徑的選擇是否合理， 直接決定了配送速度是否迅捷、服務(wù)質(zhì)量能否有所提高、配送成本能否減少以及整個(gè)經(jīng)濟(jì)塊的利益能否最大化 。如何針對(duì)物流配送路徑優(yōu)化問(wèn)題的特點(diǎn)， 建立 運(yùn)算 復(fù)雜度低、 尋優(yōu)性能優(yōu)良的啟發(fā)式算法， 也是很多人深入 研究的課題。 第三章 各種智能優(yōu)化算法介紹 智能優(yōu)化算法 常見的用于解決路徑優(yōu)化問(wèn)題的方法有不少，例如遺傳算法、禁忌搜索算法、模擬退火算法、粒子群優(yōu)化算法等，但往往方法各有不足。 中國(guó)礦業(yè)大學(xué) 2021 屆本科生畢業(yè)論文 第 9 頁(yè) 禁忌搜索算法 1986 年，由 Glover 提出的禁忌搜索算法（ tabu search， TS）經(jīng)過(guò)后來(lái)學(xué)者的不斷完善，形成了一種比較完整的優(yōu)化算法。 禁忌搜索的過(guò)程實(shí)際上就是一個(gè)局部搜索過(guò)程，將所有的局部最優(yōu)解用一張禁忌表記錄，然后在一周的搜索中，從這些最優(yōu)解中選擇或禁止。 實(shí)際應(yīng)用中，搜索過(guò)程的短期記憶是 TS 運(yùn)用最廣的特征，稱為“簡(jiǎn)單禁忌搜索 ”。組合問(wèn)題的優(yōu)化過(guò)程類似于此，它的迭代過(guò)程分為三個(gè)步驟 —— 生成新解、判斷該解、是否接受 /放棄，并且迭代過(guò)程中遵循隨機(jī)接受準(zhǔn)則，這個(gè)準(zhǔn)則將會(huì)接受所有惡化解，使得得到惡化解的概率降低并無(wú)限接近零，最大程度上使得退火算法跳出局部極值，最終找出最優(yōu)解。六十年代時(shí)這個(gè)算法還處于萌芽狀態(tài)，算法相對(duì)簡(jiǎn)單的多；直到七十年代遺傳算法得到了發(fā)展探索，當(dāng)時(shí)的算法主要用于解決兩類問(wèn)題：（ 1）建立出一種尋找特定問(wèn)題解的系統(tǒng)； (2)理解如何求解這些問(wèn)題的過(guò)程。這種方式的缺點(diǎn)在于方向的不確定性，最終產(chǎn)生的結(jié)果無(wú)法保證是有意義的。 粒子群優(yōu)化算法 粒子群優(yōu)化算法 （ PSO）是由兩位美國(guó)博士 Kennedy（社會(huì)心理學(xué)博士）和Eleberhart（電子工程學(xué)博士）在觀察鳥類覓食過(guò)程中收到啟發(fā)而提出的。值得注意的是，例子算法是一種共生合作的算法。應(yīng)用優(yōu)點(diǎn)在于它可以獲得全局最優(yōu)解，相應(yīng)的算法無(wú)法避免局部極小問(wèn)題，收 斂對(duì)初值敏感以及收斂速度慢等問(wèn)題。 k=1，2，?， K Rk：車輛 k 配送的 需求 點(diǎn)的集合。 同一蟻群會(huì)發(fā)現(xiàn)這些信息素 ， 信息素作為一種特有信號(hào) 影響 蟻群 的行動(dòng)（ 具體表現(xiàn)為后者選擇走這些具有“信息”的路徑的可能性要大于選擇其他路徑的可能性 ），而后到者 會(huì)繼續(xù)在該“信息素”基礎(chǔ)上進(jìn)行加強(qiáng)，如此往復(fù)循環(huán) 。 在算法的初始時(shí)刻，將 m 只螞蟻隨機(jī)地放到 n 座城市，同時(shí)，將每只螞蟻的禁忌表的第一個(gè)元素設(shè)置為它當(dāng)前所在的城市。 (2. 1)式中的η ij 表示一個(gè)啟發(fā)式因子，代表螞蟻從需求點(diǎn) i 轉(zhuǎn)移到需求點(diǎn) j 的期望程度。 ? ? ijijij tnt ???? ?????? )()1( (2. 2) ?? ??? mk kijij 1 ?? (2. 3) 其中ρ (0 ρ 1)是路徑上信息素的蒸發(fā)系數(shù)， 1ρ 表示信息素的持久性系數(shù)；△τ ij 表示本次迭代邊 ij 上信息素的增量。 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é)合的一種算法。旅行商要做的就是找到一條最短路徑達(dá)到目的地。首先對(duì)螞蟻數(shù)量、信息素等進(jìn)行初始化，同時(shí)將迭代次數(shù)初始化為零。設(shè) Xij=1(當(dāng)（ i,j）在 最優(yōu)回路上時(shí) )； Xij=0（其他條件時(shí)） 因此可得旅行商問(wèn)題的數(shù)學(xué)模型如下： ???????? 這里我們規(guī)定丨 S 丨表示 s 中 G 的所有頂點(diǎn)數(shù)量。 總結(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)造螞蟻路徑以及信息素更新。 我們從構(gòu)建路徑個(gè)信息素更新兩方面剖析該問(wèn)題： 構(gòu)建路徑 在蟻群算法中，我們?cè)O(shè)初始有 m只螞蟻參與 TSP 路徑的構(gòu)建。而當(dāng)β =0時(shí)，此時(shí)對(duì)于概論 P 來(lái)說(shuō)，能夠改變它的只有信息素的放大系數(shù)，換句話說(shuō)，信息素并沒(méi)有發(fā)揮它該發(fā)揮的作用，即信息素沒(méi)有使用任何啟發(fā)式偏向性。我們用 Mk 來(lái)表示螞蟻們共同維護(hù)的這個(gè)記憶儲(chǔ)存，類似與禁忌表，記憶儲(chǔ)存里面會(huì)給出已經(jīng)被訪問(wèn)過(guò)的需求點(diǎn)集合，并且這些需求點(diǎn)都是嚴(yán)格按照先后順序被存儲(chǔ)。兩種方式?jīng)]有特別明確的界限，二者從根本上并沒(méi)有改變蟻群算法的特征。信息素的蒸發(fā)滿足下式： 中國(guó)礦業(yè)大學(xué) 2021 屆本科生畢業(yè)論文 第 19 頁(yè) 式中，ρ表示信息素蒸發(fā)率，其取值范圍為ρ（ 0,1]。 在后一章有關(guān)蟻群算法的改進(jìn)會(huì)提到有關(guān)選取合適參數(shù)以減少可行解誤差的論述，此處給出基本 ACO 的相關(guān)合理參數(shù)：α =1，β（ 2， 5），ρ =。 實(shí)際情況中需要考慮的約束條件如下： 限制容量。車輛不可能無(wú)限制的一直跑下去，其行駛總路長(zhǎng)受到油耗和油量的限制，即車輛的行駛路長(zhǎng)需要設(shè)定為一個(gè)合適的常數(shù)。我們稱這種限制為 VRPTW。 時(shí)間窗帶回程取貨。 第五章 蟻群算法的改進(jìn) 問(wèn)題描述 我們將具有容量限制的車輛路徑優(yōu)化問(wèn)題（ VRP）稱為 CVRP，即車輛所負(fù)重的需求量不得超過(guò)其最大容量。這個(gè)時(shí)候通常有兩個(gè)方法解決： 選擇較為合適的α和β值使得最優(yōu)解的誤差控制在可以接受的范圍內(nèi)； 結(jié)合其他算法來(lái)改進(jìn)蟻群算法。其實(shí)不是，這樣的路徑只能稱作較好的路徑而非最優(yōu)路徑。 最大最小蟻群算法的具體改進(jìn)如下： （ 1）更新信息素 當(dāng)螞蟻成功的構(gòu)建完成一條路徑時(shí)，根據(jù)信息素蒸發(fā)規(guī)則，最大最小蟻群算法將更新信息素。 （ 2）限制信息素 改進(jìn)后的最大最小蟻群算法中規(guī)定，每一條邊的信息素都在區(qū)間 [Imin， Imax]中，這樣可以有效的防止停滯狀態(tài)的發(fā)生。由于該方式可以連同一個(gè)信息素蒸發(fā)參數(shù)，導(dǎo)致各邊上的信息素差異的增加相對(duì)緩慢，因此在算法初期，該算法極具探索性。這是從算法本身出發(fā)而做出的改進(jìn)。 因此 如何在算法初期對(duì) ?進(jìn)行適當(dāng)改進(jìn)調(diào)整，可以幫我忙更快的找到最優(yōu)路徑，達(dá)到目的。 （ 2）確定性搜索和探索性搜索的選則 當(dāng)算法在初期找到較優(yōu)解后，需要加快 收斂 速度，盡快進(jìn)化，從而得到更優(yōu)解。 確定性搜索 解決了探索性搜索受限于 收斂速度 的問(wèn)題，通過(guò) 調(diào)整 合適的 q0，使探索性搜索和確定性搜索合理搭配 ， 從而 加快蟻群算法的收斂速度。 功能 要求 （ 1） 生成客戶數(shù)據(jù) ＊ 用戶可以在軟件界面上隨機(jī)標(biāo)注倉(cāng)庫(kù)與客戶的地址 (不少于 10個(gè)客戶 )； ＊ 客戶的地址表示采用 Window 設(shè)備坐標(biāo)系。在配送過(guò)程中可模擬前方行進(jìn)路線堵車事件，軟件能夠繞開堵車路段動(dòng)態(tài)規(guī)劃配送路線。 而且，事先通知系統(tǒng)擁擠路段后，系統(tǒng)可以選擇避開該路段的最優(yōu)路徑。 編程實(shí)現(xiàn)上，自定義兩個(gè)類， class WuLiu、 class Ant，其中 WuLiu 類用于實(shí)現(xiàn)軟件的外觀； Ant 類用于 實(shí)現(xiàn)算法。雖然會(huì)出現(xiàn)陷入局部最優(yōu)的情況，但是，測(cè)試發(fā)現(xiàn)由此造成的誤差會(huì)限制在一定范圍內(nèi)，這中誤差往往是可以接受的，另外可以通過(guò)選擇合適的 alpha、beta 值使得誤差進(jìn)一步減小。在信息素方面無(wú)論是信息素初始化更新，還是迭代時(shí)的重新初始化更新方面，改進(jìn)算法都具有優(yōu)勢(shì)，相應(yīng)的提高算法收斂速度和全局尋優(yōu)能力。并且給出了優(yōu)化路徑的數(shù)字表達(dá)，更直觀也更加滿足在現(xiàn)實(shí)環(huán)境中的路徑解決需要。 主要介紹改進(jìn)后的最大最小蟻群算法，列出在基本蟻群算法改進(jìn)的步驟、注意點(diǎn)，結(jié)合相關(guān)研究得出改進(jìn)后蟻群算法的優(yōu)勢(shì)所在。 研究展望 如上所說(shuō)，本文能夠在選題的要求下做出較為合適的系統(tǒng)，最終得出最優(yōu)解或者近似最優(yōu)。這會(huì)使得該系統(tǒng)更加完善，配送車輛在某一點(diǎn)時(shí)隨時(shí)可以根據(jù)具體情況改變方案。 動(dòng)態(tài)設(shè)計(jì)更優(yōu)化。 作者在技術(shù)和經(jīng)驗(yàn)上還有諸多不足，論文中難免有些許錯(cuò)誤，往各位老師能夠指 正，不