【正文】 B: Cyberics, VOL. 26, No. 1, Feb. 1996. [9] V. Maniezzo, A. Carbonaro. Ant Colony Optimization: an overview, in Essays and Surveys in Metaheuristics [J].Kluwer 2021: 2144. [10] MA Junjian, DONG Zengchuan, WANG Chunxia, et al. Advances in research of ant colony algorithm. JOURNAL OF HOHAI UNIVERSITY (NATURAL SCIENCES), 2021 : 139143. [馬軍建，董增川，王春霞等 . 蟻群算法研究進(jìn)展 . 河海大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2021 年 3 月，第 33 卷第 2 期：139143.] [11] GAMBARDELLA L M, DORIGO M. AntQ: a reinforcement learning approach to the traveling salesman problem [A]. Proceedings of ML95, Twelfth Intern Conf on Machining[C]. Man Kaufmann, 1995: 252260. [12] STUTZLE T, HOOS H H. MAXMIN ant system [J]. Future Generation Computer System, 2021, 中國(guó)礦業(yè)大學(xué) 2021 屆本科生畢業(yè)論文 第 32 頁(yè) 16(8): 889914. [13] Liu Lin, Zhu Jianrong. The Research of Optimizing Physical Distribution Routing Based on Geic Algorithm. Computer Engineering and Applications, 2021, Vol41 : 227229. [柳林，朱建榮 . 基于遺傳算法的物流配送路徑優(yōu)化 問題的研究 . 計(jì)算機(jī)工程與應(yīng)用， 2021 年第 41 卷第 27 期： 227229.] [14] YANG Ruichen, YUN Qingxia. STUDY OF IMPROVED ANT COLONY SYSTEM IN THE ROUTING OPTIMIZATION FOR PHYSICAL DISTRIBUTION IN MINES. CHINA MOLYBDENUM INDUSTRY, 2021, Vol. 28 No. 6: 1618. [楊瑞臣，云慶夏 . 改進(jìn)的蟻群算法在礦山物流配送路徑優(yōu)化中的研究 . 中國(guó)鑰業(yè)，2021 年 12 月，第 28 卷第 6 期： 1618.] Y N探索性搜索 確定性搜索 qq0 嗎 對(duì)最優(yōu)解進(jìn)行復(fù)制、交叉、變異 tabu={0}嗎 。 參考文獻(xiàn) [1] Bernd Bullnheimer, Richaxd F Hartl, Christine strauss. An improved Ant System algorithm for the Vehicle Routing Problem [J]. Annals of Operations Researeh, 89(1999)319328. [2] LANG Maoxiang. Study of the optimizing of physical distribution routing problem based on geic algorithm [J]. China Journal of Highway and Transport, 2021, 15(3): 7679. (in Chinese) [郎茂祥 . 基于遺傳算法的物流配送路徑優(yōu)化問題研究 [J]. 中國(guó)公路學(xué)報(bào)， 2021,15(3)：7679.] [3] XU Ning, LI Chunguang, ZHANG Jian, et al. Studies on Some Modern Optimization Algorithms. SYSTEMS ENGINEERING AND 中國(guó)礦業(yè)大學(xué) 2021 屆本科生畢業(yè)論文 第 30 頁(yè) ELECTRONICS. 2021 : 101104. [徐 寧，李春光，張健等 . 幾種現(xiàn)代優(yōu)化算法的比較研究 . 系統(tǒng)工程與電子技術(shù)， 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) [常云濤，彭國(guó)雄 . 基于遺傳算法的城市干道協(xié)調(diào)控制 [J]. 交通運(yùn)輸工程學(xué)報(bào)，2021， 3(2)： 106112.] [5] LIN Yang, CAI Yuanli, HUANG Yongxuan. Dynamic origindestination matrix estimation for freeways [J]. Journal of Chang39。本系統(tǒng)是可以避開事故路段重新規(guī)劃路徑的，然而這還是不夠的，如果進(jìn)一步對(duì)其動(dòng)態(tài)設(shè)計(jì)，還可以添加在行駛途中遭遇問題的規(guī)劃。 在系統(tǒng)中可以加入一個(gè)需求緊急度，即將客戶的需求分類，哪些需要重點(diǎn)、迅速的配送，哪些相對(duì)時(shí)間不急，這樣的安 排更具人性化。然而，本論文也是一些不足之處。 針對(duì)以上研究對(duì)基于 QT 界面制作的軟件部分做出相關(guān)介紹，包括軟件的總體設(shè)計(jì)、制作原理和功能要求。 本論文主要工作如下： 中國(guó)礦業(yè)大學(xué) 2021 屆本科生畢業(yè)論文 第 28 頁(yè) 開題介紹了論文研究的背景、目的、意義，以及對(duì)國(guó)內(nèi)外相關(guān)物流發(fā)展現(xiàn)狀和問題展開討論。 本文在驗(yàn)證方面選取的是經(jīng)典問題 —— 旅行商問題（ TSP），為了使得論文研究更具實(shí)際 價(jià)值，在車輛路徑問題（ VRP）的基礎(chǔ)上做出進(jìn)一步擴(kuò)充 —— 在容量方面做出基于現(xiàn)實(shí)的限制，也就是 CVRP。 第七章 總結(jié)語(yǔ) 本文的核心研究是基于改進(jìn)蟻群算法的物流配送路徑優(yōu)化問題。 測(cè)試文檔 測(cè)試方法： 軟件運(yùn)行后，點(diǎn)擊 Produce Data 按鈕可以生成隨機(jī)測(cè)試數(shù)據(jù)，如果數(shù)據(jù)不理想，可以繼續(xù)點(diǎn)擊該按鈕；點(diǎn)擊 Route Shortest 按鈕，右側(cè)欄會(huì)描繪最優(yōu)路中國(guó)礦業(yè)大學(xué) 2021 屆本科生畢業(yè)論文 第 27 頁(yè) 徑，同時(shí)左欄會(huì)顯示路徑中從倉(cāng)庫(kù)出發(fā)依次經(jīng)過的客戶區(qū)，同時(shí)顯示此條路徑的代價(jià)；對(duì)于時(shí)間最短的測(cè)試與上面類似；點(diǎn)擊 Drive，模擬汽車行進(jìn)；點(diǎn)擊 Exit，退出軟件。 軟件界面分為左右兩欄，左欄控制部分有 produce data、 route shortest、time shortest、 Drive、 exit 五個(gè)按鈕，分別用于產(chǎn)生隨機(jī)數(shù)據(jù)、選擇路線最短的路徑、選擇時(shí)間最短的路徑、模擬汽車行進(jìn)、退出軟件。 總體設(shè)計(jì) 本系統(tǒng)是基于蟻群算法的路徑優(yōu)化設(shè)計(jì)，主要作用是根據(jù) 所述的功能要求設(shè)計(jì)，在給出隨機(jī)需求點(diǎn)的坐標(biāo)數(shù)據(jù)后，輸入約束條件（即事故路段），通過數(shù)據(jù)計(jì)算，最終系統(tǒng)根據(jù)計(jì)算結(jié)果得出優(yōu)化后的路徑（長(zhǎng)度最短、時(shí)間最短）?？蛻舻刂烽g的距離采用設(shè)備坐標(biāo)像素間距模擬，坐標(biāo)之間行駛速度采用隨機(jī)算法生成。 通過 對(duì) q0 的取值進(jìn)行調(diào)整，我們發(fā)現(xiàn)： 當(dāng) qq0時(shí)，算法會(huì)選擇 采用確定性搜索，此時(shí)螞蟻以概率 q0 選擇最短路徑 ； 而 當(dāng) q≥ q0 時(shí)，算法會(huì)選擇 采用探索性搜索，此時(shí)螞蟻以概率 l q0 進(jìn)行隨機(jī)路徑選擇 。蟻群算法屬于 一種啟發(fā)式算法， 要想使得算法進(jìn)化就必須不斷進(jìn)行遍歷搜索；m i n m a xm a x [ ( t ) , ] ( t+ 1 ) ( t ) o th e r w is err? ? ?? ? ???? ??中國(guó)礦業(yè)大學(xué) 2021 屆本科生畢業(yè)論文 第 23 頁(yè) 但是不斷的搜索又會(huì)限制算法的收斂速度，進(jìn)而反過來導(dǎo)致加長(zhǎng)了最優(yōu)解的尋找時(shí)間，甚至忽略了最優(yōu)解。 在算法初期 算法找到都屬于次優(yōu)解，如果 ?值 要比較大， 需要對(duì) 信息濃度 進(jìn)行增大調(diào)整，加快 收斂速度； 如果算法進(jìn)入停滯階段 ，我們要減小 ?值 ， 進(jìn)而使 信息素對(duì)蟻群的影響 達(dá)到最小 ， 加大對(duì)全局的搜索以避免局部最優(yōu)。有時(shí)候我們還可以從算法參數(shù)、需求點(diǎn)選擇策略出發(fā)對(duì)其進(jìn)行改進(jìn)，這樣可以提高算法的自適應(yīng)性 。 我們知道，蟻群算法在運(yùn)行中對(duì)某些路徑的探索概論很小，為了解決這個(gè)問題，就需要在達(dá)到某些條件時(shí)對(duì)信息素進(jìn)行重新初始化。最重要的是這種限制可以使得需求點(diǎn)i 螞蟻選擇去需求的 j 的概率保持在區(qū)間 [pmin,pmax]內(nèi)。新的信息素如下： 其中， 。這個(gè)時(shí)候就有了第二個(gè)改進(jìn)方式：將信息素限定在一個(gè)范圍區(qū)間內(nèi) [Imin， Imax]。通常情況下第一種方法無法直接判定選值是否最合適，本章將著重介紹結(jié)合其他算法改進(jìn)后的蟻群算法，選擇算法為最大最小 蟻群算法。以下我們所要研究的問題都將以此為前提進(jìn)行。也就是結(jié)合了時(shí)間窗和回程取貨限制，需要將無用貨物在規(guī)定時(shí)間內(nèi)運(yùn)回原點(diǎn)。 中國(guó)礦業(yè)大學(xué) 2021 屆本科生畢業(yè)論文 第 20 頁(yè) 帶回程取貨。這種針對(duì)行駛路程限制或者說時(shí)間的限制稱為 DVRP?？蛻舻囊蠡蛘哒f需求量有大有小，有時(shí)候受到車輛本身的條件所限，是沒有辦法一次性全部裝載的，也就是說，車輛的要求負(fù)重不能大于車輛本身的最大載重。 VRP 相關(guān)問題論述 物流配送優(yōu)化問題的研究中，最常用也是最關(guān)鍵的問題是車輛路徑問題，簡(jiǎn)稱 VRP。該參數(shù)的重要性在于可以抑制信息素的無限積累，而且也可以使算法舍棄已選擇過的差解。 信息素的更新 信息素的更新會(huì)在全部的 螞蟻將路徑構(gòu)建好之后完成?？梢园l(fā)現(xiàn)，無論是 Mk，還是 Nik，都與訪問路徑有關(guān)，事實(shí)上后者往往需要以前者 Mk給出的構(gòu)造規(guī)則來定義概論 P。此時(shí)的蟻群算法相對(duì)與其他智能算法沒有任 何優(yōu)勢(shì)可言，甚至不如其他算法，尤其是α大于 1時(shí)， AS 將會(huì)越來越緩慢，直至停滯運(yùn)行。將所有螞蟻隨機(jī)的選中的需求點(diǎn)中。蟻群算法之所以優(yōu)于其他算法，是因?yàn)槊恳淮蔚?，信息素的期望值往往?huì)低于其初始值，其計(jì)算公式如下： 式中， m 表示螞蟻數(shù)量， Cnm 代表路徑長(zhǎng)度。上述約束條件中， a、 b兩個(gè)約束條件的作用就是限制每個(gè)點(diǎn)僅有一條邊進(jìn)和一條邊出；而約束條件 c則保證搜索過程中不會(huì)出現(xiàn)回路解。禁忌表是為了記錄遍歷城市的一個(gè)表，算法開始前其值為零，表示未訪問任何城市。該問題在圖論下又叫做哈密頓圈問題，最早是由一個(gè)叫 Euler 研究出其雛形。在選擇路徑時(shí)，螞蟻不僅利用了路徑上的信息素，而且用到了城市間距離的倒數(shù)作為啟發(fā)式因子。△τ kij 表示第 k 只螞蟻在本次迭代中留在邊 ij 上的信息素量。在 AS 算法中，η ij 通常取需求點(diǎn) i 與需求點(diǎn) j 之間距離的倒數(shù)。此時(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 下一步允許選擇的城市集合。這樣， 該路徑走過的螞蟻越來越多，“信息素”也越來越多，后來者選擇此路徑的可能性也更大 （因?yà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)需求量之和 不可以 超過汽車載重量： kni r Qqkik ???1， nk≠ 0 2)每條 路徑的總長(zhǎng)度不超過汽車一次配送的最大行駛距離： krni rr Ddd knkkikik ???? ? 01 1， nk≠ 0 3) 每個(gè) 需求 點(diǎn)的需 每次有 且只能由一輛汽車來完成：