【正文】 J]. 中國公路學報， 2021,15(3)：7679.] [3] XU Ning, LI Chunguang, ZHANG Jian, et al. Studies on Some Modern Optimization Algorithms. SYSTEMS ENGINEERING AND 中國礦業(yè)大學 2021 屆本科生畢業(yè)論文 第 30 頁 ELECTRONICS. 2021 : 101104. [徐 寧，李春光，張健等 . 幾種現(xiàn)代優(yōu)化算法的比較研究 . 系統(tǒng)工程與電子技術， 2021 年，第 24 卷第 12 期： 101104.] [4] CHANG Yuntao, PENG Guoxiong. Urban arterial road coordinate control based on geic algorithm [J]. Journal of Traffic and Transportation Engineering, 2021, 3(2):106112. (in Chinese) [常云濤，彭國雄 . 基于遺傳算法的城市干道協(xié)調控制 [J]. 交通運輸工程學報，2021， 3(2)： 106112.] [5] LIN Yang, CAI Yuanli, HUANG Yongxuan. Dynamic origindestination matrix estimation for freeways [J]. Journal of Chang39。正如論文對基本蟻群算法的改進一樣，今后也一定會出現(xiàn)更好、更快的算法，我們要做的就是把這些運用到實際中，讓物流業(yè)的發(fā)展更進一步。 所以，在時間和技術允許的情況下，還可以做出一下幾個方面的研究拓展： GPS 導航技術的支持。 進入本論文重點需要應用和介紹的部門 —— 對基本蟻群算法的基本原理、數(shù)學模型和約束條件等做了論述，同時相應介紹 TSP、 CVRP 等問題，為后面的改進蟻群算法章節(jié)做了鋪墊。論文中，通過結合最大最小蟻群算法對基本蟻群算法做出改進，解決了基本蟻群算法收斂速度緩慢，優(yōu)化結果差等問題，同時基于改進后的算法本身也可以做到避免陷入局部搜索、算法停滯等問題。具體的，右欄可以顯示倉庫和客戶區(qū)位置（此軟件設置客戶區(qū)為 14 個）并且根據相應的操作描繪出最佳路線并模擬汽車行進。 ＊ 模擬車輛從倉庫出發(fā)，沿著規(guī)劃的配送路線行進，最后返回倉庫。 為此我們引入一個常量： q0?[0,1)，每當螞蟻在 選擇路徑之前， 都會先 產生一個 q?[0,1)， k 號螞蟻選擇規(guī)則如下 ： 由上式可以 看出 ，當 q?q0時， 將會使用基本蟻群算法進行搜索； 當 qq0時，是從 已經得到的 結果中，找出 最大概論 的路徑作為選擇， 屬于確定性搜索。相反，如果選擇的 ?值過小，收斂速度會減少。 未 更 新 信 息 素 之 前 ， 信 息 素 范 圍 區(qū) 間 極 值 定 義 式 如 下 ： I 更新信息素后極大值如下： （ 3）初始化和重新初始化信息素 算法開始前，會對信息素進行初始化，設定原則為信息素極大值之 上的一個估算值。最后，當出現(xiàn)以下條件：系統(tǒng)信息素增多導致系統(tǒng)堵塞，或者在迭代過程中不再出現(xiàn)優(yōu)化路徑，此時將會對信息素值初始化。使用第四章所述的基本蟻群算法解決VRP 或者 CVRP 問題會發(fā)現(xiàn)容易出現(xiàn)收斂速度慢、易陷入局部最優(yōu)的問題。這種限制稱為 VRPB。 路長限制。所有螞蟻在其選擇 的路徑上釋放信息素為： 根據上式不難總結出，在迭代次數(shù)允許的范圍內，該路徑的構建閱合適，信息素的釋放也越多。 我們用兩種方式可以實現(xiàn)可行解的構建：第一種是并行構建，也就是說每一只螞蟻都可以隨時從當前需求點出發(fā)向下個需求點；與之相反的一種方式稱為順序構建，我們可以理解為單線程的構建，即只有當一直螞蟻完成從所在點向下一個點構建完整路徑后，第二只螞蟻才被允許開始它的構建。我們分別對 α 和β 取零值，可以發(fā)現(xiàn)，當 α 為 0時，此時會最大概論選出離 i點最近需求點，這滿足貪心算法的定義。同時出現(xiàn)新概念 — 對稱型 TSP，即滿足條件 dij=dji。我們用一個帶權完全圖 G=（ N,A） 來闡述， N 是所有目標城市點的集合， A是所有邊（路徑模型）的集合。△τ kij 表示為： , k i j0 , k KijQL????? ???若 螞 蟻 在 本 次 周 游 中 經 過 邊 否 則 (2. 4) 其中， Q 為正常數(shù)， Lk 表示第 k 只螞蟻在本次周游中所走過路徑的長度。當每一座城市都加入到中國礦業(yè)大學 2021 屆本科生畢業(yè)論文 第 15 頁 tabuk 中時，螞蟻 k 便完成了一次循環(huán)，此時螞蟻 k 所走過的路徑便是 TSP（旅行家問題） 的一個可行解。螞蟻 的行為（尋找食物或者尋找回巢的路徑） ， 會在其走過的途中釋放一些化學物質（即我們所說的“信息”） 。 神經網絡算法 神經網絡算法（ ANN）起源已經很難考證了，其基本原理是模擬生物神經系統(tǒng)的一種人工智能的簡化，系統(tǒng)主要由三部分組成：系統(tǒng)功能、組織結構和處理方式。變異是新個體產生的主要方式。 遺傳算法 遺傳算法 是最初是由 美國 Michigan大學的 1975年提出的，其基本思想是將自然界優(yōu)勝劣汰的自然法則與組合優(yōu)化及其他機器學習等問題結合。為防止這種情況出現(xiàn)， TS 提出了新概念“渴望標準”來覆蓋某些移動的禁忌狀態(tài)，使得算法向 比目前最優(yōu)解更優(yōu)的解移動。為下一章會針對蟻群算法概念、算法思想、優(yōu)化步驟和相關數(shù)學模型等的進一步詳解做鋪墊。 但這些方法往往存在各種問題 ， 例如 節(jié)約法 很難做到組合點整齊 、 組合邊緣點 的問題， 且 掃描法 無法做到 漸進優(yōu)化等。 第二章 路徑優(yōu)化研究現(xiàn)狀與分析 研究現(xiàn)狀 物流配送路徑規(guī)劃問題的研究現(xiàn)狀： 車輛優(yōu)化調度問題及物流配送路徑選擇是整個物流配送體系 優(yōu)化中 很重要 的環(huán)節(jié)，也是電子商務活動 不可或缺 的內容。 第三章是幾種智能優(yōu)化算法的簡單介紹，主要包括禁忌搜索算法、遺傳算法、模擬退火算法、粒子群優(yōu)化算法和人工神經網絡算法。因此，實際應用中需要考慮的是如何設計合理、高效的配送方案以及減少車輛數(shù)中國礦業(yè)大學 2021 屆本科生畢業(yè)論文 第 6 頁 量和配送里程數(shù)。該解可允許有誤差，但誤差必須在可以接受的范圍內。相比之下，啟發(fā)式算法 就要合適的多，它 通常 可以 根據問題的特性而將其化為多個小問題， 以較為直觀的方式來求解各個支問題。 本文研究目的和意義 本文研究目的 物流配送網絡是指物流過程中相互聯(lián)系的設施及組織的集合。然而，就目前物流業(yè)發(fā)展可見，其發(fā)展己經成為 經濟發(fā)展過程中必須有效管理的問題 。在選擇路徑時，螞蟻利用了路徑上的信息素，不斷疊加，最終產生最優(yōu)路徑。 關鍵詞 ： 基本 蟻群算法； 最大最小蟻群算法； 物流配送； 蟻群系統(tǒng)； 路徑優(yōu)化； 第一章 緒論 研究背景 在美國，物流產業(yè) 鏈 被 人們 形象地 比作“尚未開發(fā)的 價值 400 億美元的金礦。 然而通過觀察以往的研究可以發(fā)現(xiàn)，我國現(xiàn)階段物流配送的發(fā)展依舊十分 落后，只配不送的 尷尬 現(xiàn)狀造成 物流配送 中出現(xiàn) 低效率、高成本、服務差等諸多問中國礦業(yè)大學 2021 屆本科生畢業(yè)論文 第 4 頁 題 ， 這已經嚴重影響到了電子商務在未來市場的長足發(fā)展 ，要知道，電子商務在網絡時代中占據著極其重要的經濟地位。物流配送路徑優(yōu)化需要解決的根本問題就是從生產區(qū)域到消費區(qū)域的空間轉移過程中對實現(xiàn)物品移動 (運輸 )途徑的優(yōu)化。 因此，本文研究的目的是： 通過對各種智能算法的介紹比較，找出它們的區(qū)別和優(yōu)缺點， 以及實際中國礦業(yè)大學 2021 屆本科生畢業(yè)論文 第 5 頁 應用中的可行度，討論出較為合適的算法。這就需要考慮到時間、財務、環(huán)境三方面的因素，即時間上的準時性以及快速響應；財務上則是各種運輸費用的節(jié)??；環(huán)境上要考慮行駛時間、交通問題以及各種環(huán)境污染問題。針對以往路徑優(yōu)化方案的研究，本文將建立該問題的數(shù)學模型，以蟻群算法為主要算法，建立出較為合適的路徑優(yōu)化系統(tǒng)，最終達到減少配送支出，提高對客戶服務質量等目的，從而有效提高利潤率，相應的緩解交通壓力。 第五章主要是針對基本蟻群算法，結合最大最小蟻群算法進行改進，提高算法的收斂速度，以及全局搜索能力。近二十年來 國內外對 物流配送路徑 優(yōu)化 問題 的研究給予了極大的關注 。 但根本性問題依舊存在，例如在搜索能力上遺傳算法局部搜索能力很弱 ，總體上可行解的質量 也不高 ，禁忌搜索算法 如果沒有一個比較合適的初始解其可行性也很低。記憶存儲包括短期和長期記憶存儲 。 模擬退化算法的基本原理是基于一般優(yōu)化問題與物理中的物質退火的相似性 ，即溫度上升到一定程度的自由運動粒子，隨著溫度的下降（下降速度保 持足夠慢），那么最終整個系統(tǒng)將會達到其自身最低狀態(tài)，稱為基態(tài)狀態(tài)。 遺傳算法的原理是基于初始種群的，即在當前種群中使用選擇策略選擇個體，其中該策略的標準是針對與適應值比例的，隨著一代代的雜交和變異，直到最終的期待條件出現(xiàn)為止。最開始的設想是基于單個個體組成的群體與環(huán)境和個體之間的反饋行為。 數(shù)學模型的建立 符號的定義 L： 需求 點總數(shù)； qi： 需求 點 i的貨物需求量，其中 i=1， 2，?， L； dij：從 需求 點 i到 需求 點 j 的距離。 這樣，在單位時間內此路徑持續(xù)被更多的螞蟻選擇訪問，信息素積累增多， 直到最后，幾乎所有的螞蟻都選擇這條最短的路徑 。α和β分別表示信息素和啟發(fā) 式因子的相對重要程度。 AS 算法的時間復雜度為Ο (NC*n2*m) 算法的空間復雜度為 S(n)=O(n2)+O(n*m) ，其中 NC 表示迭代的次數(shù)， n 為城市數(shù)， m為螞蟻的數(shù)目。隨著算法的進行，螞蟻會選擇城市出發(fā)并留下信息素，此時禁忌表值發(fā)生改變，同時信息素也會更新，當超出最大迭代次數(shù)時，程序將會終止，否則迭代繼續(xù)，直至滿足條件。選擇該初始值的初衷是因為，一旦信息素初始值過小，搜索區(qū)域往往受到限制，大多搜索會過于集中 在初始有限的路徑中，即我們所說的陷入局部搜索中，很難找到最優(yōu)解。此時的算法依舊會給出一條路徑，也就是多數(shù)螞蟻選擇的路徑，但其實已經沒有任何研究的意義了，此路徑甚至算不上一個可行解。起初，路徑上的信息素會按照一個常量減少，也就是信息素蒸發(fā)。該問題的研究往往不是單一的只針對某一個領域的研究，而是結合許多相關學科前沿和熱點，比如計算機科學，物流科學，數(shù)學，運籌學等。 時間窗。這種限制稱為 VRPBTW。 最大最小蟻群算法 本算法是在基本蟻群算法上做了如下幾項改進。信息素釋放的對象由至今最優(yōu)的螞蟻進行釋放，此時 ；或者由當前迭代最優(yōu)的螞蟻進行釋放，此時 。一般來說，重新初始化中國礦業(yè)大學 2021 屆本科生畢業(yè)論文 第 22 頁 的條件有兩個：算法達到或接近停滯，或者在達到迭代次數(shù)上限前依然沒有找到最優(yōu)路徑。 上 式中， r表示連續(xù)沒有進化的循環(huán)的次數(shù)， rmax為常數(shù) ， ??(0,1)也屬于 一個常量，控制 ?衰減速度， ?min是 ?的最小值，防止 ?過小影響收斂速度。在算法迭代的初期 ， q0 需要選擇 較大的初始值， 且確定性搜索 以較大的概率進行，這樣 做的目的是為了 加快尋找局部較優(yōu)路徑的速度；在算法的中期 q0 的值會以較小為準，增大探索性搜索的概率，繼而加大搜索空間；直到 算法的后期，恢復 q0 的初始值，加快收斂 速度。數(shù)據圖如下： 中國礦業(yè)大學 2021 屆本科生畢業(yè)論文 第 26 頁 軟件架構 在 B2C 農產品電子商務物流配送時，物流車裝載當日需要配送的貨品從倉庫出發(fā)，按照事先規(guī)劃好的最優(yōu)配送路徑為每一個客戶進行配送，最后返回倉庫。 測試中可能出現(xiàn)的問題： 對于同一批數(shù)據，兩次點擊 Route Shortest 按鈕生成的最優(yōu)路徑會有所不同，這是由于算法陷入局部最優(yōu)導致。本文的所有研究都是基于該前提條件進行的研究，實際應用方面更具考究。 對論文中算法的優(yōu)勢以及軟件部分的優(yōu)缺點進行總結，同時對未來物流的發(fā)展進行展望，也提出了針對本論文可以改進的地方。 建立真實情況 下客戶資源數(shù)據庫。an University (Natural Science Edition), 2021, 23(6): 8386. (in Chinese) [林 勇，蔡遠利，黃永宣 . 高速公路動態(tài) OD 矩陣估計 [J]. 長安大學學報 (自然科學版 )， 2021， 23(6)： 8386.] [