【正文】 一種定義指定啟發(fā)式算法是一種技術 ,使尋找最佳的解決方案在一個可接受的計算成本內(nèi) ,但不一定保證得到的解決方案是可行的和最優(yōu)的 ,或者甚至在大多數(shù)情況下 ,得到的解決方案不能逼近最優(yōu)解。因此 ,這些算法在多篇論文或其他著作被列為一類 ,概括起來 ,即啟發(fā)式算法一一 Heuristic Algorithm。 雖然這些新的方法進行了優(yōu)化 ,并且每個機制是不一樣的 ,但它們有類似的特征。蟻群算法模仿蟻群覓食的費洛蒙應用 ,以便找到最短的覓食路徑。如模擬退火算法模擬的固體物質(zhì)從高溫度的不穩(wěn)定狀態(tài)的過程中向低溫度穩(wěn)定狀態(tài)過度 。 (2)啟發(fā)式算法 通常情況下 ,通過自身發(fā)展的性質(zhì)和生物系統(tǒng) ,可以使許多復雜的問題得到令人滿意的解決方案 ,計算機科學家從生物系統(tǒng)的研究中得到的靈感 ,、以模仿自然的世界 ,獲取新的方法來解決復雜的計算問題。 (1)精確算法 精確算法指可求出最優(yōu)解的算法 ,主要 有分枝定界法、割平面法、網(wǎng)絡流算法、動態(tài)規(guī)劃法等?？偟膩碚f ,精確算需要十分嚴格的數(shù)學手段 ,所以在可以求解的情況下 ,其解要比人工智能算法更加優(yōu)良。因此 ,人工智能算法更廣泛的運用在實際生活中。 人工智能算法包括有 :掃描法、旅行商方法、分區(qū)配送算法、節(jié)約法以及一些現(xiàn)代優(yōu)化計算方法 (禁忌搜索算法、遺傳算法、模擬退火算法等 )。根據(jù)實際情況建立了一種基于最短路徑的多車場多車輛的物流配送模型 ,并從車輛行駛里程角度分析加入了新的約束條件 ,保證車輛的正常行 14 / 40 駛 ,同時也保證車輛能將貨物送達每一位客戶。 根據(jù)本章對物流配送路徑模型定義、分類的研究 ,了解物流配送問題建模的內(nèi)容與意義。由于每輛車的承載能力是固定的 ,因此必須對車輛總承載數(shù)加以控制。該公式的目的是控制每個客戶都被服務到 ,并且僅被一輛車服務。即不能出現(xiàn)路徑反復 ,出現(xiàn)誤差。此條件用于限制計算時車輛的數(shù)量 ,因為一個車場所含有的車輛數(shù)是固定的 ,因此必須加以限制。接下來就要根據(jù)實際要求對運算加以限制 ,列出限制公式 ,以便于計算 ,獲得與實際 相符的可行解。 以上可以建立數(shù)學模型如下 : 13 / 40 1 1 1 1m inN N M K m mkij iji j m kZ d x? ? ? ?? ???? (式 228) 公式 228用來保證最小化的車輛行駛路徑。 gi:表示客戶 i的要求 。 dij:表示節(jié)點 i與節(jié)點 j之間的距離 。定義變量 mkij 1 m k i jx= 0??? 車 場 的 車 從 用 戶 行 駛 到否 則 (式 227) N:表示客戶的總數(shù)目 。 根據(jù)以上條件 ,設全部用戶的編號分別為 1,2, ......N。(3)可以由任意一個車場的車輛服務 ,但只能由一臺配送車輛送貨 。要求合理安排車輛配送方案 ,使車輛總運輸成本最低 ,并滿足以下條件 :(1)每輛車運送完后必須返回原車場 。 基于最短路徑的多車場多車輛配送模型建立 根據(jù)前文對于模型建立的分析與總結 ,運用前文的方法 ,建立一種基于最短路徑的多車場多車輛的配送模型 ,并加入新的約束條件。如 : , 1n kiji j s s xs?? ??? ? ? 1,2...sN? 第七步 ,保證車輛的承載能力。有時候第四步和第五步可以合并。如 : Niii=11max tN ?? 第四步 ,保證每個客戶都被服務到。如 : K N N Kij ijK = 0 i= 1 j= 1m in Z= c x? ? ? 第三步 ,自定義滿足條件。如 : ki 1 iky= 0??? 客 戶 由 車 輛 配 送否 則 12 / 40 mkij 1 m k i jx= 0??? 車 場 的 車 從 用 戶 行 駛 到否 則 第二步 ,設定最小化目標。大多是 amp。公式 (224)、 (225)、 (226)用來確?？蛻粼诖_定時間窗內(nèi)接受服務。公式 (220)用來確保每個客戶都被服務到。定義變量 : ki 1 iky= 0??? 客 戶 由 車 輛 配 送否 則 mkij 1 m k i jx= 0??? 車 場 的 車 從 用 戶 行 駛 到否 則 基于顧客的滿意程度可得求解目標有 : 第一步是最大化的平均客戶滿意度 : Niii=11max tN ?? (式 213) 其可以等價轉化為最小化的平均客戶不滿意度 Niii= 11min 1 tN ????????? （式 214) 第二步是最小化的車輛數(shù) : KN k0jk=1 j=1min x?? (式 215) 第三步是最小化的車輛行駛距離和等待時間 : 11 / 40 K N N kij ijk=0 i=1 j=1min c x??? (式 216) Niii=1min t?? (式 217) 其有如下的約束條件 : iit i??? i = l,2… N (式 218) 1N ki i ki g y q? ?? (式 219) 1 1K kik y? ?? (式 220) 1N kkij ji xy? ?? (式 221) 1N kkij ij xy? ?? (式 222) , 1n kiji j s s xs?? ??? ? ? 1,2...sN? (式 223) ? ?m ax ,j j i i ijt E t s t? ? ? (式 224) ijtN? (式 225) ? ?( ) m ax 0,i j j jt t E? ?? (式 226) 以上公式中 ,公式 (218)可以保障每個客戶滿意程度不低于 i? 其中 i? 是決策者根據(jù)自身的實際經(jīng)驗給出相應的值 ,其中給每個客戶的值可以相同也可以不同 ,其是根據(jù)客戶的重要程度進行劃分的。其中 i=0表示倉庫 ,每個車輛載重為 q, g為每個客戶的需求 ,客戶 i到客戶 j的運輸成本為 Cij。 (212)消除子回路。 (29)確保每個客戶都被服務到。其中 i=0表示倉庫 ,每個車輛載重為 q, g為每個客戶的需求 ,客戶 i 到客戶 j 的運輸成本為 Cij,假設每輛車最后會回到虛擬的配送中心 ,配送中心于 客戶間的距離為 0,即 Cio。 (26)消除子回路。 (23)確保每個客戶都被服務到。其中 i=0表示倉庫 ,每個車輛載重為 q, g為每個客戶的需求 ,客戶 i到客戶 j的運輸成本為 CV 優(yōu)化的目標是行駛距離最 短和使用車輛最少。隨著科技的進步和物流技術的發(fā)展 ,信息共享的加劇 ,物流配送向更加多樣化更加現(xiàn)代化不斷的進步。目前研究中一般考慮的多樣性限制的物流配送路徑問題主要有 : 1)有多種車型的配送方式 2)有多個車場的配送方式 3)物流配送有多個目標 (5)其他種類配送路徑優(yōu)化問題 在實際生活中 ,物流需求是多種多樣的 ,也有很多種不同的變異方式 ,目前的物流配送問題 ,日趨貼近現(xiàn)實生活 ,例如多配送中心聯(lián)合的配送任務 ,即在同一個信息平臺內(nèi) ,多種車輛 ,多個中心為同一家客戶 服務 。配送中心有多個 ,即車輛從不同地方出發(fā) 。 以上所考慮的問題都是有相同的前提條件 ,即車輛是同種類型 ,有確定的優(yōu)化目標 ,然而在實際情況下有很多因素是變化的。 以上都是基于數(shù)學方法理想化的 物流配送問題 ,而實際工作中 ,物流配送限制因素有很多 ,物流問題所面臨的情況也是十分復雜的 ,研究人員在物流配送中必須要考慮很多的約束條件 ,例如車輛油量限制、車輛故障 ,道路故障等一些突發(fā)事故都會對車輛造成影響 ,因此在物流配送路線設計時 ,考慮很多因素。4)每個客戶的需求必須滿足。2)車輛從中心車場出發(fā) ,完成配送任務后必須回到中心車場 。 (2)基本的物流配送路徑優(yōu)化問題。3)要用最短的物流配送路徑 。 在一個配送中心內(nèi)部由一臺容量為 Q的車進行配送 ,配送點有 n個 ,并滿足一定的條件 :1)每個客戶都必須被訪問 ,且只能訪問一次 。 在前文國內(nèi)外現(xiàn)狀部分對物流配送路徑問題進行了分類 ,下面對分類進行描述 ,并選取其中有代表性的幾種分類進行舉例介紹。 物流配送路徑問題最早是由學者 Dantzig和 Ramser于 1959年首次提出的 ,一般可定義為 :對于一系列 裝貨點和 (或 )卸貨點 ,組織合適的行車線路 ,使載貨車輛有序地通過它們 ,在滿足一定的約束條件 (如貨物的發(fā)送量、貨物的需求量、運送貨物車輛容量限制、交發(fā)貨時間和運輸時間限制等 )下 ,達到一定的目標 (如運輸所用費用最少、運輸路程最短、使用車輛數(shù)量少、運輸時間少等 )。并根據(jù)自身對物流配送模型的理解 ,建立基于最短路徑的多車場多車輛的物流配送模型 ,并加入新的約束條件。具體研宄思路如圖 11所示。 第五章 MatLab仿真實驗 :在本文前幾章的理論分析和模型建立、算法優(yōu)化的基礎上 ,根據(jù)實 6 / 40 驗數(shù)據(jù)設計了仿真實驗 ,通過對結果進行分析比較 ,驗證了本文算法的科學性和有效性 ,同時驗證不同最優(yōu)配送目標下物流配送的方案不同。 第三章物流配送問題相關算法研究 :對傳統(tǒng)的粒子群算法進行介紹 ,并對其特點進行分析 ,同時列舉出現(xiàn)有的幾種針對粒子群算法的改進方法。然后論述了國內(nèi)外對于物流配送問題的研究現(xiàn)狀、算法的研究現(xiàn)狀及其發(fā)展情況 ,最后給出本文的主要研宄內(nèi)容和章節(jié)安排。 (4)仿真實驗 通過在 MatLab 2020a上的仿真實驗 ,驗證本文設計算法的科學性與有效性。 實證分析是指借助本文最后采用的對經(jīng)驗事實的 描述通過訴諸事實來解決人們經(jīng)驗事實中所遇到的問題。將定性與定量方法相結合 ,并運用其完成文章所需。 定 性分析和定量分析兩種方法是相互依存的 ,缺一不可 ,定量分析以定性分析作為基礎 ,而定性分析要通過定量分析來具體化、精確化 ,只有將這兩種研究方法結合起來使用 ,才能達到較好的硏究效果。 所謂定量分析 ,是指根據(jù)研究對象的各項指標特點與數(shù)值 ,采用概率模型、統(tǒng)計模型等進行適當?shù)臄?shù)據(jù)建模 ,并用規(guī)范的數(shù)學語言進行描述的一種方法。 本文主要采用以下研究方法 : (1)文獻調(diào)研 文獻調(diào)研方法將當前物流配送路徑問題 和粒子群算法以及相關算法的現(xiàn)狀和問題進行描述與分析 ,了解當前最新研宄動態(tài) ,獲取到相關的方法信息。通過對傳統(tǒng)的解決物流配送問題的算法進行分析與對比 ,了解其流程、特點與不足 ,針對問題和這些不足設計了一種改進的可以自適應的粒子群算法。 針對物流配送路徑問題和粒子群算法的現(xiàn)狀 ,文章對粒子群算法進行深入研究 ,對其缺陷進行分析 ,引入新的優(yōu)化手段 ,優(yōu)化現(xiàn)有粒子群算法 ,并根據(jù)需求加入相應的約束條件建立物流配送模型進行求解 ,對于實際應用起到相應作用 ,也為下一步研究工作的展開奠定基礎。 Liu 提出了一種中央粒子粒子群算法 ,實驗證明該算法性能比傳統(tǒng)粒子群算法好 [26]。 Chatterje和 Shi分別提出了慣性權重的非線性變化和線性變化的粒子群算法王俊偉等通過實驗研究 ,給出了設置慣性權重的指導性原則。 Chen等將結合極值優(yōu)化引入到粒子群算法中 ,通過結合 E0的開拓能力和 PSO的探索能力來提高其性能。 Bratton和 Kennedy對粒子群算法的各 種改進提出了一個標準框架 [23],為各種 PSO 算法改進研究提供了參照標準。 Clerc在粒子群算法中引入了約束 因子 ,用來確保粒子群算法局部的收斂性。 Kennedy 分析了速度更新公式在粒子群算法中的作用 ,同時分析了無速度更新公式的粒子群算法 [21]。 Sh