【正文】 劃計(jì)算時間 ，收斂速度極其緩慢，甚至算法會直接進(jìn)入停滯狀態(tài)。 因此，本文研究的目的是： 通過對各種智能算法的介紹比較，找出它們的區(qū)別和優(yōu)缺點(diǎn)， 以及實(shí)際中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)論文 第 5 頁 應(yīng)用中的可行度，討論出較為合適的算法。在此基礎(chǔ)上引出蟻群算法，將會重點(diǎn)闡述該算法的可行性和實(shí)用性，并作出改進(jìn)，使得算法能有在全局搜索和收斂速度上更具優(yōu)勢。 在以往研究的基礎(chǔ)上，建立適合實(shí)際物流配送網(wǎng)絡(luò)路徑優(yōu)化的模型，并選擇使用有效的算法，為物流配送網(wǎng)絡(luò)路徑優(yōu)化問題的研究和實(shí)踐提供理論依據(jù)和實(shí)際方法。 根據(jù)論文選題要求，結(jié)合論文中選擇的優(yōu)化算法，開發(fā)出物流配送路徑優(yōu)化系統(tǒng)， 要求該系統(tǒng)要嚴(yán)格遵守選題要求，可適當(dāng)做出改進(jìn)和拓展， 作為論文的實(shí)踐研究。 本論文最終要求開發(fā)出滿足實(shí)際應(yīng)用的軟件，能夠在 windows 系統(tǒng)上運(yùn)行，隨機(jī)數(shù)據(jù)生成后（位置坐標(biāo)），可以在符合約束條件的情況下，付出較小代價給出合理的路徑優(yōu)化解 —— 時間最短路徑、距離最短路徑。該解可允許有誤差，但誤差必須在可以接受的范圍內(nèi)。 本文研究的意義 根據(jù) Ronald H． Ballo 的觀點(diǎn)，運(yùn)輸決策包括四種：運(yùn)輸方式的選擇、對運(yùn)輸路線的規(guī)劃、車輛調(diào)度以及集中運(yùn)輸?shù)?。運(yùn)輸成本降低的重點(diǎn)在于對運(yùn)輸路徑進(jìn)行合理規(guī)劃，即優(yōu)化運(yùn)輸路徑。這就需要考慮到時間、財務(wù)、環(huán)境三方面的因素，即時間上的準(zhǔn)時性以及快速響應(yīng)；財務(wù)上則是各種運(yùn)輸費(fèi)用的節(jié)?。画h(huán)境上要考慮行駛時間、交通問題以及各種環(huán)境污染問題。這些問題往往可以通過改進(jìn)運(yùn)輸方式、優(yōu)化線路規(guī)劃等加以改善。其中，運(yùn)輸問題不屬于本文探討的范圍。而運(yùn)輸?shù)木€路規(guī)劃主要是利用 各種技術(shù)以 最低的運(yùn)營成本、最快捷的響應(yīng)速度、最短的配送運(yùn)輸時間，把貨物運(yùn)至用戶手中，達(dá)到節(jié)約費(fèi)用和節(jié)省客戶時間雙贏的目的 。實(shí)際中的物流配送尤其是從事城市配送的汽車貨運(yùn)工作往往需要考慮的問題更復(fù)雜，比如貨運(yùn)節(jié)點(diǎn)的多寡、物品種類是否繁雜、當(dāng)?shù)亟煌ňW(wǎng)絡(luò)是否暢通等等，甚至運(yùn)輸服務(wù)地區(qū)內(nèi)運(yùn)輸網(wǎng)點(diǎn)分布不均勻都會直接影響配送工作的進(jìn)行。因此，實(shí)際應(yīng)用中需要考慮的是如何設(shè)計(jì)合理、高效的配送方案以及減少車輛數(shù)中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)論文 第 6 頁 量和配送里程數(shù)。高效率的物流中心配送作業(yè)具體而言就是：從配送中心使用多輛車向多個目的地送貨，假設(shè)每個需求點(diǎn)的位置和供量 確定，車輛載重一定，需要解決的就是合理安排車輛路線，以達(dá)到預(yù)定的目標(biāo) (即最少費(fèi)用，最短路徑，最少時間，最少車輛使用等 )。為了便于問題的研究，規(guī)定遵守的條件有：要求車輛載重大于該路徑需求點(diǎn)的需求量；該路徑長度不得超過一次配送中最大行駛距離；單位需求點(diǎn)有且只由一輛車送貨。針對以往路徑優(yōu)化方案的研究，本文將建立該問題的數(shù)學(xué)模型，以蟻群算法為主要算法，建立出較為合適的路徑優(yōu)化系統(tǒng)，最終達(dá)到減少配送支出，提高對客戶服務(wù)質(zhì)量等目的，從而有效提高利潤率，相應(yīng)的緩解交通壓力。本文的研究對城市的配送研究可起一定的借鑒作用，追 求高利潤、低成本，降低社會經(jīng)濟(jì)物流總成本，并有效的提高車輛運(yùn)輸效率，強(qiáng)化服務(wù)質(zhì)量，提高更快更好的需求相應(yīng)，無論是城市物流本身，亦或是針對客戶群都是具有重要的參考價值。 本論文的主要工作 物流配送路徑優(yōu)化問題簡稱 VRP，本論文將重點(diǎn)就城市車輛路徑優(yōu)化問題作為研究對象，針對目前路徑優(yōu)化研究的復(fù)雜性以及各類算法的使用，著重以蟻群算法為主要算法，在蟻群算法基礎(chǔ)上結(jié)合最大最小蟻群算法對其進(jìn)行改進(jìn)，從而是整個系統(tǒng)的尋優(yōu)速度更快、結(jié)果更準(zhǔn)確。 本論文的研究工作主要包括： 第一章緒論部分主要以論文研究背景和目的方面為主，闡述了由國內(nèi)國際實(shí)際物流發(fā)展而產(chǎn)生的問題，引出本論文研究的必要性和重要性。 第二章會就路徑優(yōu)化研究的國內(nèi)外現(xiàn)狀為例展開分析，指出現(xiàn)階段路徑優(yōu)化問題的主要研究方法，由此引出下章針對這些研究方法的詳細(xì)討論。 第三章是幾種智能優(yōu)化算法的簡單介紹，主要包括禁忌搜索算法、遺傳算法、模擬退火算法、粒子群優(yōu)化算法和人工神經(jīng)網(wǎng)絡(luò)算法。針對五中算法的基本思路、優(yōu)缺點(diǎn)、以及實(shí)際應(yīng)用中產(chǎn)生的問題與思考。 第四章基于蟻群算法 — 系統(tǒng)開發(fā)基本思想，主要對研究 的數(shù)學(xué)模型、約束中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)論文 第 7 頁 條件以及基本蟻群算法的的原理、實(shí)現(xiàn)方式展開論述 。 第五章主要是針對基本蟻群算法，結(jié)合最大最小蟻群算法進(jìn)行改進(jìn)，提高算法的收斂速度，以及全局搜索能力。后面也會給出蟻群算法的其他改進(jìn)方式，以減少最優(yōu)解的誤差。 第六章屬于對路徑優(yōu)化系統(tǒng)的描述，主要有總體設(shè)計(jì)、功能要求以及界面的相關(guān)方面。 此章的所述以及最后的軟件部分都將作為論文的實(shí)物支持。 最后一章是對本論文的總結(jié)和展望，重點(diǎn)對本論文中的優(yōu)點(diǎn)和功能做出總結(jié)，同時就論文的不足結(jié)合現(xiàn)實(shí)技術(shù)做出進(jìn)一步的展望。 第二章 路徑優(yōu)化研究現(xiàn)狀與分析 研究現(xiàn)狀 物流配送路徑規(guī)劃問題的研究現(xiàn)狀： 車輛優(yōu)化調(diào)度問題及物流配送路徑選擇是整個物流配送體系 優(yōu)化中 很重要 的環(huán)節(jié)，也是電子商務(wù)活動 不可或缺 的內(nèi)容。由于這一問題的理論涉及多學(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)注 。 因此一度 成為 組合優(yōu)化領(lǐng)域和運(yùn)籌學(xué)的前沿 研究熱點(diǎn)，各學(xué)科專家 針對此類 問題進(jìn)行了大量的 學(xué)術(shù)探討和 試驗(yàn)分析 ，并 取得了很大進(jìn)展。近二十年來 國內(nèi)外對 物流配送路徑 優(yōu)化 問題 的研究給予了極大的關(guān)注 。 隨著市場經(jīng)濟(jì)的 進(jìn)步 和物流技術(shù)專業(yè)化水平的 不斷 提高，物流配送業(yè)得到了快速 發(fā)展。配送路徑的選擇是否合理， 直接決定了配送速度是否迅捷、服務(wù)質(zhì)量能否有所提高、配送成本能否減少以及整個經(jīng)濟(jì)塊的利益能否最大化 。配送路徑中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)論文 第 8 頁 的優(yōu)化問題是物流配送 體系 的一個 重要 問題，物流配送路徑的優(yōu)化 根本在于 以 最短的配送運(yùn)輸時間、 最低的 運(yùn)輸 成本、最 迅速 的響應(yīng)把貨物運(yùn)至 客戶 手中， 最短時間和最快速度兩者本身與最低運(yùn)輸成本相制約，嚴(yán)格地來說這 一個多目標(biāo)的優(yōu)化問題。 研究方法 路徑優(yōu)化的方法很多 ，常用的有 分區(qū)配送算法、 旅行商法、 掃描法、 動態(tài)規(guī)劃法、節(jié)約法等。 但這些方法往往存在各種問題 ， 例如 節(jié)約法 很難做到組合點(diǎn)整齊 、 組合邊緣點(diǎn) 的問題， 且 掃描法 無法做到 漸進(jìn)優(yōu)化等。如何針對物流配送路徑優(yōu)化問題的特點(diǎn)， 建立 運(yùn)算 復(fù)雜度低、 尋優(yōu)性能優(yōu)良的啟發(fā)式算法， 也是很多人深入 研究的課題。近年來 流行的 遺傳算法、禁忌搜索算法等 都在這方面取得了不同的成就 。 但根本性問題依舊存在，例如在搜索能力上遺傳算法局部搜索能力很弱 ，總體上可行解的質(zhì)量 也不高 ，禁忌搜索算法 如果沒有一個比較合適的初始解其可行性也很低。諸如此類 。 第三章 各種智能優(yōu)化算法介紹 智能優(yōu)化算法 常見的用于解決路徑優(yōu)化問題的方法有不少，例如遺傳算法、禁忌搜索算法、模擬退火算法、粒子群優(yōu)化算法等，但往往方法各有不足。蟻群算法的優(yōu)勢在于它利用并行計(jì)算機(jī)制，可以很好的與其他算法結(jié)合 ， 魯棒性特點(diǎn)尤為突出。本章將會對智能優(yōu)化算法做簡單介紹。為下一章會針對蟻群算法概念、算法思想、優(yōu)化步驟和相關(guān)數(shù)學(xué)模型等的進(jìn)一步詳解做鋪墊。 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)論文 第 9 頁 禁忌搜索算法 1986 年，由 Glover 提出的禁忌搜索算法（ tabu search， TS）經(jīng)過后來學(xué)者的不斷完善，形成了一種比較完整的優(yōu)化算法。禁忌搜索算法的基本工作原理是利用 記憶存儲 ， 并對其系統(tǒng)化使用，從而使搜索過稱順利進(jìn)行下去。記憶存儲包括短期和長期記憶存儲 。 長期記憶存儲通過引用其他解進(jìn)行鄰域擴(kuò)充；短期記憶存儲則不同，它是將當(dāng)前解的鄰域限制到一個子集中來 ， 子集含于這個鄰域。 禁忌搜索的過程實(shí)際上就是一個局部搜索過程，將所有的局部最優(yōu)解用一張禁忌表記錄，然后在一周的搜索中，從這些最優(yōu)解中選擇或禁止。出于對防止算法可能返回重復(fù)解的考慮， TS 可以將近期 訪問過的最優(yōu)解進(jìn)行顯式保存或者直接禁止這些解。但這就造成了算法很難向著那些未訪問過 的 解移動。為防止這種情況出現(xiàn)， TS 提出了新概念“渴望標(biāo)準(zhǔn)”來覆蓋某些移動的禁忌狀態(tài)，使得算法向 比目前最優(yōu)解更優(yōu)的解移動。 實(shí)際應(yīng)用中，搜索過程的短期記憶是 TS 運(yùn)用最廣的特征，稱為“簡單禁忌搜索 ”。 模擬退火算法 模擬退火算法的出現(xiàn)最早是由 Metropolis 在 1953 年提出的，嚴(yán)格意義上來說，屬于局部算法的延伸 ， 1983 年，該算法成功的應(yīng)用于組合優(yōu)化問題，尤其在 NPhead 問題中運(yùn)用更多。 模擬退化算法的基本原理是基于一般優(yōu)化問題與物理中的物質(zhì)退火的相似性 ，即溫度上升到一定程度的自由運(yùn)動粒子，隨著溫度的下降（下降速度保 持足夠慢），那么最終整個系統(tǒng)將會達(dá)到其自身最低狀態(tài)，稱為基態(tài)狀態(tài)。此時的基態(tài)可視為函數(shù)的全局最小點(diǎn)。組合問題的優(yōu)化過程類似于此，它的迭代過程分為三個步驟 —— 生成新解、判斷該解、是否接受 /放棄，并且迭代過程中遵循隨機(jī)接受準(zhǔn)則，這個準(zhǔn)則將會接受所有惡化解，使得得到惡化解的概率降低并無限接近零，最大程度上使得退火算法跳出局部極值，最終找出最優(yōu)解。 遵循上述準(zhǔn)則的模擬退火算法已經(jīng)脫離了局部搜索算法范疇，成為了一種全局尋找最優(yōu)解算法。此算法的優(yōu)勢在于，中間解可以一定程度上脫離局部極小中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)論文 第 10 頁 點(diǎn)，最終在退火溫度下找到 最優(yōu)解。 遺傳算法 遺傳算法 是最初是由 美國 Michigan大學(xué)的 1975年提出的，其基本思想是將自然界優(yōu)勝劣汰的自然法則與組合優(yōu)化及其他機(jī)器學(xué)習(xí)等問題結(jié)合。六十年代時這個算法還處于萌芽狀態(tài)，算法相對簡單的多；直到七十年代遺傳算法得到了發(fā)展探索，當(dāng)時的算法主要用于解決兩類問題：（ 1）建立出一種尋找特定問題解的系統(tǒng)； (2)理解如何求解這些問題的過程。發(fā)展到九十年代，遺傳算法的研究運(yùn)用在各方面得到深入。 遺傳算法的原理是基于初始種群的，即在當(dāng)前種群中使用選擇策略選擇個體，其中該策略的標(biāo)準(zhǔn)是針對與適應(yīng)值比例的，隨著一代代的雜交和變異，直到最終的期待條件出現(xiàn)為止。 對于旅行商問題（ TSP），遺傳算法中的雜交方式一般是將染色體標(biāo)記為序列，其中包含所有需求點(diǎn)。這種方式的缺點(diǎn)在于方向的不確定性，最終產(chǎn)生的結(jié)果無法保證是有意義的。所以需要保證旅行商問題雜交算子編碼的有效性。 遺傳算法的主要步驟為：（ 1）編碼；（ 2）生成初始群體；（ 3）檢測與評估適應(yīng)值；（ 4）選擇使用 /放棄；（ 5）交換，即信息交換；（ 6）變異。變異是新個體產(chǎn)生的主要方式。 粒子群優(yōu)化算法 粒子群優(yōu)化算法 （ PSO）是由兩位美國博士 Kennedy（社會心理學(xué)博士）和Eleberhart（電子工程學(xué)博士）在觀察鳥類覓食過程中收到啟發(fā)而提出的。例子群優(yōu)化算法同樣是起源于 生物社會系統(tǒng)的模擬。最開始的設(shè)想是基于單個個體組成的群體與環(huán)境和個體之間的反饋行為。 與其他算法相似之處在于粒子群優(yōu)化算法同樣是關(guān)于群體的迭代關(guān)系的算法，而不同之處則在于該算法并沒有設(shè)定交叉、復(fù)制和變異等算子，而是將群中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)論文 第 11 頁 體中的個體微化成無質(zhì)量無體積的粒子。值得注意的是，例子算法是一種共生合作的算法。 粒子群算法之所以會受到各界不同程度的關(guān)注，最重要在于針對復(fù)雜非線性問題，該算法具有比較強(qiáng)的尋優(yōu)能力，且簡單通用，魯棒性強(qiáng)。在函數(shù)優(yōu)化領(lǐng)域以及車間調(diào)度方面粒子群算法都用應(yīng)用 然而粒子群算法并不是完美的一種算法，它的缺點(diǎn)也是顯而易見，例如該算法的高搜索能力是建立在參數(shù)的合理程度之上的，也就是說，沒有一個合理的參數(shù)選擇，該算法的搜索性能很低；其次它的局部搜索能力同樣不高，搜索精度很低，這就導(dǎo)致了算法無法最終尋得全局最優(yōu)解。 神經(jīng)網(wǎng)絡(luò)算法 神經(jīng)網(wǎng)絡(luò)算法（ ANN）起源已經(jīng)很難考證了，其基本原理是模擬生物神經(jīng)系統(tǒng)的一種人工智能的簡化，系統(tǒng)主要由三部分組成：系統(tǒng)功能、組織結(jié)構(gòu)和處理方式。應(yīng)用優(yōu)點(diǎn)在于它可以獲得全局最優(yōu)解，相應(yīng)的算法無法避免局部極小問題，收 斂對初值敏感以及收斂速度慢等問題。 第 四 章 基于蟻群算法 — 系統(tǒng)開發(fā)基本思想 物流配送的 問題描述 一般配送路徑問題可描述如下： 已知條件：需求點(diǎn)（客戶）數(shù)量為 L； 需求點(diǎn)數(shù)量和坐標(biāo)； 預(yù)計(jì)可出現(xiàn)故障的路段； 要求： a：系統(tǒng)可根據(jù)使用者選擇的路徑規(guī)劃策略，如路徑最短、時間最中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)論文 第 12 頁 少等方式進(jìn)行配送路線規(guī)劃 b： 模擬車輛由倉庫出發(fā)，沿著規(guī)劃的配送路線行進(jìn)，最后返回倉庫 c：在配送過程中可模擬前方行