基于優(yōu)化的粒子群算法的物流配送路徑問題研究(共42頁)

1、 43/43基于優(yōu)化的粒子(lz)群算法的物流配送路徑問題研究 摘 要隨著市場經(jīng)濟的突飛猛進與現(xiàn)代物流技術的發(fā)展,物流配送環(huán)節(jié)(hunji)正受到日益廣泛的關注,而配送中的物流配送路徑問題成為了物流配送中的核心問題。本文正是在這一背景下產(chǎn)生,文章重點研究了物流配送路徑優(yōu)化模型的建立(jinl)和粒子群算法的改進問題。本文對物流配送路徑問題進行了深入研宄,通過對多種不同目標的物流配送模型研究,分析總結(jié)模型建立的一般步驟,并建立了基于最短路徑的多個車場多個車輛的物流配送模型,同時從控制車輛行駛里程角度考慮,對車輛服務客戶數(shù)量加以限制,加入了新的約束條件。同時為了對模型進行計算,分析對比多種算法,最

2、后選擇粒子群算法做為研宄對象。通過對傳統(tǒng)粒子群算法缺點的研宄,設計了一種自適應變異的粒子群優(yōu)化算法。文章通過對現(xiàn)有一些改進方法的分析研究,對傳統(tǒng)算法進行了優(yōu)化,引入模糊分類、自適應變異機制、加入新的變異概率和可調(diào)節(jié)適應度方差,以達到對當前粒子進行自適應調(diào)整的目的,從而避免早熟收斂,形成新的自適應變異的粒子群優(yōu)化算法。同時本文給出一種編碼模式,降低了出現(xiàn)不可行解的概率。最后通過MatLab 2011a平臺對所做內(nèi)容進行仿真實驗,驗證相應結(jié)論,仿真內(nèi)容分別為用文章建立的多車場多車輛模型驗證優(yōu)化算法的可行性和優(yōu)越性,用前文給出的基于最短路徑最少車輛和基于顧客滿意度的兩個模型驗證基于不同目標前提下的配

3、送模型所得物流配送方案不同。仿真獲得兩個結(jié)論,分別為本算法在求解此類問題時具有優(yōu)于傳統(tǒng)粒子群算法的特征,既保持了較好的全局搜索能力,又可有效避免算法早熟收斂;基于不同最優(yōu)配送目標的物流配送模型,所得物流配送方案具有差異性。關鍵詞:物流配送問題;數(shù)學建模;粒子群算法;自適應目 錄摘要 IAbstract II目錄 Ill1緒論 11.1研宄的背景與意義11.2研宄現(xiàn)狀綜述11.2.1國內(nèi)外研究現(xiàn)狀21.2.2算法研宄現(xiàn)狀31.3研究內(nèi)容與研宄方法41.4本文的組織結(jié)構52物流配送模型建立與常見模型分析82.1物流配送路徑問題相關研究82.1.1 物流配送路徑問題定義82.1.2物流配送路徑問題分

4、類82.2物流配送路徑問題數(shù)學建模種類92.3模型舉例102.3.1 基于行駛距離最短和使用車輛最少的物流配送問題102.3.2基于開放式車輛路徑的物流配送問題112.3.3基于顧客滿意度的物流配送問題122.4模型建立思路總結(jié)142.5基于最短路徑的多車場多車輛配送模型建立153物流配送路徑問題(wnt)相關算法研究193.1物流配送路徑問題相關(xinggun)算法研究193.2常見(chn jin)現(xiàn)代優(yōu)化算法分析與對比203.2.1算法舉例203.2.2算法比較243.3傳統(tǒng)粒子群算法局限性分析253.3.1經(jīng)典PSO算法253.3.2傳統(tǒng)算法的流程263.3.3算法具體描述273.3

5、.4粒子群算法特點分析313.4已有粒子群算法的改進方法314一種改進的粒子群算法設計354.1改進后的自適應變異粒子群算法354.2粒子編碼374.3算法實現(xiàn)的具體步驟384.3.1算法實現(xiàn)步驟文字表述384.3.2 算法實現(xiàn)步驟的流程圖表述394.4優(yōu)化的粒子群算法與其他算法比較414.4.1優(yōu)化的粒子群算法與遺傳算法的比較414.4.2優(yōu)化的粒子群算法與傳統(tǒng)粒子群算法比較425 MatLab仿真與實驗445.1算法仿真環(huán)境445.2算法可行性與對比分析445.2.1仿真實驗數(shù)據(jù)445.2.2算法可行性研究455.2.3優(yōu)化算法與傳統(tǒng)算法的對比分析465.3基于不同目標模型的對比研究495

6、.3.1仿真實驗數(shù)據(jù)495.3.2 仿真結(jié)果495.4 仿真結(jié)果總結(jié)516 結(jié)論與展望536.1本文工作總結(jié)536.2研宄展望54參考文獻56作者簡歷59獨創(chuàng)性聲明60學位論文數(shù)據(jù)集611緒論1.1研究的背景與意義迅速發(fā)展的現(xiàn)代科學技術,加強了全球經(jīng)濟一體化的腳步,國家正面臨著前所未有的機遇和挑戰(zhàn),而物流對于經(jīng)濟活動的影響,越來越受到人們的重視。存儲的需求在現(xiàn)代物流配送過程中的重要性減弱,取而代之,配送成為最重要的環(huán)節(jié)。車輛的集貨、貨物配備和交貨流程、車輛配送路線的優(yōu)化是整個物流配送最核心的部分,它們對整個物流的成本、運輸速度和效益的影響都是非常重要的。根據(jù)中國倉儲協(xié)會對146企業(yè)協(xié)會調(diào)查顯示

7、,在整個物流費用中,用于運輸?shù)馁M用比例分別為:在成品物流在生產(chǎn)企業(yè)占73%,原料生產(chǎn)企業(yè)物流占58%,因此,對于分配環(huán)節(jié)的優(yōu)化方面,最重要的就是研宄配送路徑車輛調(diào)度問題,而對于集貨路線優(yōu)化、物品配送路線和裝備方式是對于配送車輛調(diào)度優(yōu)化的重要環(huán)節(jié),也是進行對配送環(huán)節(jié)進行優(yōu)化的重中之重。物流系統(tǒng)中物流配送是一個非常重要的環(huán)節(jié),它是整個對客戶服務過程中最后一個環(huán)節(jié)。因此,需要知道在物流過程中,物流配送的地位非常突出,所以企業(yè)經(jīng)營中必須實現(xiàn)快速、準確的物流配送,這是十分重要問題。物流配送路徑問題提出之后,很快便引起計算機學科(xuk)、運籌學、組合數(shù)學、應用數(shù)學、物流科學等學科專家的極大重視,并且一直

8、是人工智能、應用數(shù)學領域的前沿與熱點問題。在現(xiàn)實生產(chǎn)和生活中,網(wǎng)絡路由問題、郵政投遞問題、公共汽車調(diào)度問題、管道鋪設問題等都可以抽象化為物流配送路徑問題。在物流配送業(yè)務中,物流配送問題需要考慮的因素比較多,涉及的面比較廣,同時對配送企業(yè)降低成本、提高服務質(zhì)量、增加(zngji)經(jīng)濟效益的影響也比較大。然而目前研究發(fā)現(xiàn),我國在研究物流配送車輛調(diào)度方面成果較少,所獲得的進展緩慢,并且對于仿生算法研究還有一定的欠缺性,對于算法自身的缺陷彌補不足,針對以上原因,本文將重點研究物流配送中車輛調(diào)度和路徑問題,并將物流配送中的算法進行詳細研究,針對算法缺陷進行改進,形成新的優(yōu)化算法,并根據(jù)最優(yōu)配送目標和實際

9、要求建立數(shù)學模型,進行計算與仿真。1.2研究現(xiàn)狀(xinzhung)綜述在現(xiàn)代物流體系中物流配送車輛路徑問題是一個重要組成部分,它是指在物流中心的貨物,通過交貨,將貨物送到收貨人的一系列活動都需要按照用戶需求進行設置。例如,你有一個中央貨場貨物需要交付給多個用戶,每個用戶都有不同的需求,貨物車輛在裝滿后運輸貨物,它配送完每一個用戶后再回到貨場,完成任務,在這個過程中,如何滿足用戶的需求,以最小的成本費用和車輛的路線進行配送,那就是物流配送路徑問題。又如另一個例子,需要被運送到中央倉庫的一些廠家生產(chǎn)的產(chǎn)品,車輛從倉庫開始向廠家裝車后,全額返還到倉庫,并滿足一些生產(chǎn)產(chǎn)品的制造商的要求,按照一定的路

10、線,可以降低總費用,這就是物流配送路徑問題。這兩個問題具有相同的實質(zhì),只是交付的任務或者集貨的任務存在差異。在物流和運輸業(yè)務中,有很多的優(yōu)化決策問題。合理選擇運輸路徑,在提高服務質(zhì)量,加快交貨過程,提高經(jīng)濟效益,降低運營成本上都有較大的影響。1.2.1國內(nèi)外硏究現(xiàn)狀對于物流配送路徑優(yōu)化問題一度被提出后,國內(nèi)外學者都十分關注,分別從不同的方向、不同的角度對這一問題進行了深入的研究,分別按照不同的標準對其進行優(yōu)化和分類。本文為了方便描述,根據(jù)業(yè)務類型的不同簡要將其分類描述。物流配送問題是預先設計好的一種路徑走向,可以將物流配送路徑問題簡要的分成五個類別。分別是:(1)最簡單的物流配送路徑優(yōu)化問題1

11、。最簡單的物流配送路徑優(yōu)化問題被抽象為有一個配送中心,有一輛配送車輛,且滿足相應的約束條件進行貨物配送。是最簡單的一種路徑優(yōu)化向題2。(2)基本的物流配送路徑優(yōu)化問題3。將前一種分類進行推廣研究,就可以描述為一個中心,有多輛車,每輛車有固定載重,按照要求進行配貨。其實這是一個標準的車輛路徑問題4,也可以說是車輛調(diào)度問題,一直是優(yōu)化學科和運籌學的前沿熱點5。(3)根據(jù)實際設定約束的物流配送路徑優(yōu)化問題。目前條件下一共需要考慮的因素有以下幾種。1)客戶對時間有限制6。即可以描述為客戶對整個物流配送過程有時間窗的要求,包括硬時間和軟時間7;2)車輛對于運輸(ynsh)的距離有相應的限制8。即可以描述

12、(mio sh)為車輛的最大行駛距離的有限性9;3)對于客戶由不確定的需求限制(xinzh)ieiu即客戶有隨機或模糊的需求11。(4)多樣性限制的物流配送路徑優(yōu)化問題。1)有多種車型的配送方式12。即整個配送中心具有多種類的車型車輛進行配送服務13;2)有多個車場的配送方式14。即多個車場同時服務,進行物流配送15;3)物流配送有多個目標16,即配送中心所具有的優(yōu)化目標含有幾個相互排斥的分目標17。(5)其他種類配送路徑優(yōu)化問題。例如開放式的物流配送路徑優(yōu)化服務等18。1.2.2算法硏究現(xiàn)狀粒子群優(yōu)化算法是求解組合優(yōu)化問題的一種群體智能算法,其具有參數(shù)少、模型簡單、收斂速度快等優(yōu)點,常被運用

13、到神經(jīng)網(wǎng)絡問題中,用來解決實際問題。目前對于粒子群算法的優(yōu)化改進主要集中在以下的幾個方面:(1)對粒子群算法結(jié)構進行改變;(2)對粒子群算法機理進行分析;(3)研宄粒子群算法中參數(shù)的設置;(4)研究粒子群算法的拓撲結(jié)構;(5)研宄對粒子群算法進行離散化的方法;(6)研究粒子群算法的并行版本;(7)對用于多目標求解的粒子群算法進行研究;(8)研究粒子群算法在實際問題中的應用。Shi第一次在粒子群算法中引入了慣性權重系數(shù)19,通過調(diào)解原有速度和更新速度的關系,平衡粒子的局部搜索能力和全局搜索能力。Kennedy在粒子群算法中提出了帶鄰域拓撲20,通過拓撲來延緩信息在種群中的交流速度,降低粒子群內(nèi)部

14、粒子之間的相互影響,從而降低得到局部最優(yōu)值發(fā)生早熟的可能性,同時通過對各種鄰域拓撲結(jié)構對算法性能影響的分析,總結(jié)出指出馮諾依曼結(jié)構具有最好的綜合性。Kennedy分析了速度更新公式在粒子群算法中的作用,同時分析了無速度更新公式的粒子群算法21。Kennedy提出了動態(tài)概率粒子群算法22。 Clerc在粒子群算法中引入了約束因子,用來確保粒子群算法局部的收斂性。曾建潮等提出了一種保證粒子群算法全局收斂的新方法。Bratton和Kennedy對粒子群算法的各種改進提出了一個標準框架23,為各種PSO算法改進研究提供了參照標準。Bergh等提出協(xié)作粒子群算法24。 Chen等將結(jié)合極值優(yōu)化引入到粒子

15、群算法中,通過結(jié)合E0的開拓能力和PSO的探索能力來提高其性能。對粒子群算法參數(shù)的設置問題,本文研究主要包括,對于慣性權重W、社會因子C1、個人因子C2和速度上限Vniax的取值策略以及研宄粒子群的規(guī)模。Chatterje和Shi分別提出了慣性權重的非線性變化和線性變化的粒子群算法王俊偉等通過實驗研究,給出了設置慣性權重的指導性原則。彭宇等對于C1， C2和慣性權重W的設置通過方差分析手段對算法性能的影響分析,總結(jié)了針對參數(shù)設置的有哪些指導原則25。 Liu提出了一種中央粒子粒子群算法,實驗證明該算法性能比傳統(tǒng)粒子群算法好26。除此之外,目前的研究熱點還包括將其他進化計算方法融合到粒子群算法中

16、將其改進27。針對物流配送路徑問題和粒子(lz)群算法的現(xiàn)狀,文章對粒子群算法進行深入研究,對其缺陷進行分析,引入新的優(yōu)化手段,優(yōu)化現(xiàn)有粒子群算法,并根據(jù)需求加入相應的約束條件建立物流配送模型進行求解,對于實際應用起到相應作用,也為下一步研究工作的展開奠定基礎。1.3 研究(ynji)內(nèi)容與研究方法本文首先介紹物流配送路徑的基本理論與相關算法,然后對物流配送路徑的問題進行描述型定義、分類與建立數(shù)學模型。通過對傳統(tǒng)的解決物流配送問題的算法進行分析與對比,了解其流程、特點與不足,針對問題和這些不足設計了一種改進的可以自適應的粒子群算法。最后(zuhu)進行了仿真實驗與結(jié)果分析。本文主要采用以下研究

17、方法:(1)文獻調(diào)研文獻調(diào)研方法將當前物流配送路徑問題和粒子群算法以及相關算法的現(xiàn)狀和問題進行描述與分析,了解當前最新研宄動態(tài),獲取到相關的方法信息。(2)定性與定量分析所謂定性分析,是指不采用數(shù)學方法,僅采用研究者的直覺、感觀、經(jīng)驗對研究對象進行判斷,并結(jié)合以前的事實或者其他資料,對研究對象的性質(zhì)、趨勢、規(guī)律等作出感性判斷的一種方法,最后采用文字等方式進行描述表達。所謂定量分析,是指根據(jù)研究對象的各項指標特點與數(shù)值,采用概率模型、統(tǒng)計模型等進行適當?shù)臄?shù)據(jù)建模,并用規(guī)范的數(shù)學語言進行描述的一種方法。通過科學的定量分析,可以從本質(zhì)上了解事物的發(fā)展規(guī)律。定性分析和定量分析兩種方法是相互依存的,缺一

18、不可,定量分析以定性分析作為基礎,而定性分析要通過定量分析來具體化、精確化,只有將這兩種研究方法結(jié)合起來使用,才能達到較好的硏究效果。本文首先將所需解決的物流配送路徑問題定性化,選擇相應模型和算法,并對算法進行改進和優(yōu)化,同時建立所需模型,然后定量的仿真與計算。將定性與定量方法相結(jié)合,并運用其完成文章所需。(3)理論分析與實證研宄相結(jié)合理論分析是指運用粒子群理論、運籌學與計算機仿真理論對系統(tǒng)需求及實現(xiàn)進行了深入剖析。實證分析是指借助本文最后采用的對經(jīng)驗事實的描述通過訴諸事實來解決人們經(jīng)驗事實中所遇到的問題。它注重人的現(xiàn)實功利要求追求結(jié)果的時效性。(4)仿真實驗通過在MatLab 2011a上的

19、仿真實驗,驗證本文設計算法的科學性與有效性。1.4本文的組織結(jié)構本文包括以下六章:第一章緒論:介紹了本文的研究背景與意義,闡述了研究物流配送路徑問題的重大需求。然后論述了國內(nèi)外對于物流配送問題的研究現(xiàn)狀、算法的研究現(xiàn)狀及其發(fā)展情況,最后給出本文的主要研宄內(nèi)容和章節(jié)安排。第二章物流配送相關問題介紹和模型建立:對于物流配送問題進行了詳細介紹,并且介紹了多種物流配送問題可建立的模型,并進行模型總結(jié),同時介紹物流配送路徑的基本算法和分類,以及配送區(qū)域劃分算法的基本分類,同時建立多車場多車輛的物流配送模型,并加入新的約束條件。第三章物流配送問題相關算法研究:對傳統(tǒng)的粒子群算法進行介紹,并對其特點進行分析

20、,同時列舉出現(xiàn)有的幾種針對粒子群算法的改進方法。第四章應用(yngyng)于物流配送路徑(ljng)問題中的一種改進的自適應的粒子群算法設計:在前三章理論(lln)基礎上,通過對問題研究所需的粒子群算法的分析以及與其他算法的對比,論證其算法的不足,并結(jié)合己有的幾種優(yōu)化方法和改進方式設計了一種新的改進的自適應粒子群算法。第五章MatLab仿真實驗:在本文前幾章的理論分析和模型建立、算法優(yōu)化的基礎上,根據(jù)實驗數(shù)據(jù)設計了仿真實驗,通過對結(jié)果進行分析比較,驗證了本文算法的科學性和有效性,同時驗證不同最優(yōu)配送目標下物流配送的方案不同。第六章總結(jié)與展望:對本文的研究進行總結(jié),并對未來的工作做展望和建議。具

21、體研宄思路如圖1-1所示。1-1文章(wnzhng)思路圖Fig. 1-1 Articles ideas roadmap2物流配送模型建立與常見(chn jin)模型分析本章(bn zhn)著重研究物流配送路徑問題的模型分類,并總結(jié)建立模型的一般步驟。并根據(jù)自身對物流配送模型的理解,建立基于最短路徑的多車場多車輛的物流配送模型,并加入新的約束條件。在后續(xù)工作中需要對具有不同最優(yōu)配送目標的模型進行仿真,了解不同最優(yōu)配送目標下物流配送路徑之間的關系。2.1物流配送路徑(ljng)問題相關硏究2.1.1物流配送路徑問題(wnt)定義物流配送路徑問題最早是由學者Dantzig和Ramser于1959年

22、首次提出的,一般可定義為:對于一系列裝貨點和(或)卸貨點,組織合適的行車線路,使載貨車輛有序地通過它們,在滿足一定的約束條件(如貨物的發(fā)送量、貨物的需求量、運送(yn sn)貨物車輛容量限制、交發(fā)貨時間和運輸時間限制等)下,達到一定的目標(如運輸所用費用最少、運輸路程最短、使用車輛數(shù)量少、運輸時間少等)。2.1.2物流配送路徑問題分類由于實際情況不同可以根據(jù)不同的分類標準劃分成不同類型的物流配送路徑問題,其分類情況如表2-1所示:表2-1物流配送路徑優(yōu)化問題分類Tab.3-1 Logistics and distribution routing problem classification形態(tài)

23、范圍車輛種類單一車種、多種車種車輛容量限制不同車有不同的限制、所有車輛統(tǒng)一的限制、不限制時間限制不同路線時間限制不同、所有路線時間限制相同、無時間限制路網(wǎng)方向性混合性路網(wǎng)、有方向性路網(wǎng)、沒有方向性路網(wǎng)里程限制不同車輛里程限制不同、所有車輛里程限制相同、無限制裝卸作業(yè)形態(tài)混合型、卸貨、裝貨配送中心單一的配送中心、多配送中心貨物類別貨物多種、貨物同種需求形態(tài)需求量隨機、需求量固定最優(yōu)化目標服務效用最大、路線成本小、車輛數(shù)量少、變動及固定成本小2.2 物流配送路徑問題數(shù)學建模種類對于物流分配模型建立有很多種模型可以使用,在物流分配中有針對時間最短確立,有根據(jù)費用最短確立,有根據(jù)路徑最短確立,各自模型

24、有所差異,下面介紹幾種物流分配的數(shù)學模型。在前文國內(nèi)外現(xiàn)狀部分對物流配送路徑問題進行了分類,下面對分類進行描述,并選取其中有代表性的幾種分類進行舉例介紹。(1)最簡單的物流配送路徑優(yōu)化問題。在一個配送中心內(nèi)部由一臺容量為Q的車進行配送,配送點有n個,并滿足一定的條件:1)每個客戶都必須被訪問,且只能訪問一次;2)車輛從中心車場出發(fā),完成配送任務后必須回到中心車場;3)要用最短的物流配送路徑;4)每個客戶的需求必須滿足。(2)基本的物流配送路徑優(yōu)化問題。在一個(y )配送中心內(nèi)部有K輛容量為Q的車,配送點有n個,并滿足一定條件:1)每個客戶都必須被訪問,且只能訪問一次;2)車輛從中心(zhngx

25、n)車場出發(fā),完成配送任務后必須回到中心車場;3)要用最短的物流配送路徑;4)每個客戶的需求必須滿足。(3)根據(jù)實際設定(sh dn)約束的物流配送路徑優(yōu)化問題。以上都是基于數(shù)學方法理想化的物流配送問題,而實際工作中,物流配送限制因素有很多,物流問題所面臨的情況也是十分復雜的,研究人員在物流配送中必須要考慮很多的約束條件,例如車輛油量限制、車輛故障,道路故障等一些突發(fā)事故都會對車輛造成影響,因此在物流配送路線設計時,考慮很多因素。1)客戶對時間有限制2)車輛對于運輸?shù)木嚯x有相應的限制3)對于客戶由不確定的需求限制(4)多樣性限制的物流配送路徑優(yōu)化問題。以上所考慮的問題都是有相同的前提條件,即車

26、輛是同種類型,有確定的優(yōu)化目標,然而在實際情況下有很多因素是變化的。如車輛種類有很多,可裝載的貨物不同,車的容量限制也不同;配送中心有多個,即車輛從不同地方出發(fā);還有就是整個配送有很多優(yōu)化目標,這些優(yōu)化目標并不是相互獨立的,如距離最小、時間最短或者車輛等。目前研究中一般考慮的多樣性限制的物流配送路徑問題主要有:1)有多種車型的配送方式2)有多個車場的配送方式3)物流配送有多個目標(5)其他種類配送路徑優(yōu)化問題在實際生活中,物流需求是多種多樣的,也有很多種不同的變異方式,目前的物流配送問題,日趨貼近現(xiàn)實生活,例如多配送中心聯(lián)合的配送任務,即在同一個信息平臺內(nèi),多種車輛,多個中心為同一家客戶服務;

27、或者開放式的物流配送路徑優(yōu)化服務,即配送完成后車輛無需返回原有車場。隨著科技的進步和物流技術的發(fā)展,信息共享的加劇,物流配送向更加多樣化更加現(xiàn)代化不斷的進步。2.3模型舉例2.3.1基于行駛距離最短和使用車輛最少的物流配送問題基于行駛距離最短和使用車輛最少,物流配送問題可以表示成的數(shù)學模型如下:假定配送中心最多可以用K輛車對N個客戶進行物流配送,其中k=1,2K,用戶i=1,2N。其中i=0表示倉庫,每個車輛載重為q, g為每個客戶的需求,客戶i到客戶j的運輸成本為CV優(yōu)化的目標是行駛距離最短和使用車輛最少。定義變量:其數(shù)學模型如下表示: (式2-1) (式2-2) (式2-3) (式2-4)

28、 (式2-5) (式2-6)其中(2-2)控制每輛車的能力約束(yush)。(2-3)確保每個客戶都被服務到。(2-4)(2-5)確保每個客戶被一輛車服務。(2-6)消除子回路。2.3.2基于開放式車輛(chling)路徑的物流配送問題對于開放式車輛路徑的物流配送問題,可以表示為,第一階段:先把客戶分群,考慮(kol)一定的限制,將客戶群個數(shù)最小化,然后根據(jù)一些規(guī)則重新分配客戶,目的是最小化距離,用模型表述為,當車輛將所有客戶配送完成后,并不需要返回配送中心,這樣可以建立開放式車輛路徑數(shù)學模型,文章給出如下模型:假定配送中心最多可以用K輛車對N個客戶進行物流配送,其中k=l、2.K,用戶i=l

29、、2.N。其中i=0表示倉庫,每個車輛載重為q, g為每個客戶的需求,客戶i到客戶j的運輸成本為Cij,假設每輛車最后會回到虛擬的配送中心,配送中心于客戶間的距離為0,即Cio。定義變量: 其數(shù)學模型如下表示: (式2-7) (式2-8) (式2-9) (式2-10) (式2-11) (式2-12)其中(2-8)控制每輛車的能力(nngl)約束。(2-9)確保每個客戶都被服務到。(2-10)(2-11)確保每個客戶被一輛車服務。(2-12)消除子回路。第二階段:每個群被轉(zhuǎn)化成開放式線路(xinl),用最小生成樹算法來最小化線路2.3.3基于顧客(gk)滿意度的物流配送問題基于客戶的滿意程度,物

30、流的配送問題可以表示成的數(shù)學模型如下:假定配送中心最多可以用K輛車對N個客戶進行物流配送,其中k=l、2?K,用戶i=1,2N。其中i=0表示倉庫,每個車輛載重為q, g為每個客戶的需求,客戶i到客戶j的運輸成本為Cij。假設每輛車最后會回到虛擬的配送中心,配送中心于客戶間的距離為0,客戶i的時間窗是Ei, Li,到達客戶i并且開始服務的時間是ti,行駛時間是, wi為所需的等待時間,Si為服務時間, 表示客戶滿意度,I是很大的整數(shù)。定義變量:基于顧客的滿意程度可得求解目標有:第一步是最大化的平均客戶滿意度: (式2-13)其可以等價轉(zhuǎn)化為最小化的平均客戶不滿意度 （式2-14)第二步是最小化

31、的車輛(chling)數(shù): (式2-15)第三步是最小化的車輛(chling)行駛距離和等待時間: (式2-16) (式2-17)其有如下(rxi)的約束條件: i = l,2N (式2-18) (式2-19) (式2-20) (式2-21) (式2-22) (式2-23) (式2-24) (式2-25) (式2-26)以上(yshng)公式中,公式(2-18)可以保障每個客戶滿意程度不低于其中(qzhng)是決策者根據(jù)自身的實際經(jīng)驗給出相應的值,其中給每個客戶的值可以相同也可以不同,其是根據(jù)客戶的重要(zhngyo)程度進行劃分的。公式(2-19)用來保證每輛車的承載能力。公式(2-20)用

32、來確保每個客戶都被服務到。公式(2-21)(2-22)確保每個客戶只被一輛車服務.公式(2-23)用來消除子回路。公式(2-24)、 (2-25)、 (2-26)用來確?？蛻粼诖_定時間窗內(nèi)接受服務。2.4 模型建立思路總結(jié)根據(jù)前文介紹的幾種模型,總結(jié)出對于物流配送路徑問題建模的大致思路首先,自定義變量。大多是&和7,對所求變量進行初始條件設置,即變量為1時則為服務到,變量為0則為未服務到。如:第二步,設定最小化目標。如最小化的費用、最小化的時間或者最小化的路徑。如: 第三步,自定義滿足條件。如顧客滿意度、車輛分配總數(shù)或運輸時間等。如: 第四步,保證每個客戶都被服務到。如:第五步,保證每個客戶都

33、被服務一次。有時候第四步和第五步可以合并。如: 第六步,保證消除子回路。如: 第七步,保證車輛的承載能力。如: 對于模型思路和每一種約束條件的分析與總結(jié)十分必要,利于根據(jù)實際要求建立對應的所需模型,并根據(jù)自身的要求加入相應的約束條件,改進模型,使模型更加貼合實際要求。2.5 基于最短路徑的多車場多車輛配送模型建立根據(jù)前文對于(duy)模型建立的分析與總結(jié),運用前文的方法,建立一種基于最短路徑的多車場多車輛(chling)的配送(pi sn)模型,并加入新的約束條件。配送路徑中多個車場多個車輛的優(yōu)化問題可以描述為:某物流中心一共有M個車場,各自有Ki(K1, K2Km)臺配送車輛,每輛車容量都為

34、q,向N個客戶送貨,用戶i的貨物需求為gi, (i=l,2,.N)。要求合理安排車輛配送方案,使車輛總運輸成本最低,并滿足以下條件:(1)每輛車運送完后必須返回原車場;(2)每個客戶的需求必須滿足;(3)可以由任意一個車場的車輛服務,但只能由一臺配送車輛送貨;(4)對車輛的服務數(shù)量進行限制。根據(jù)以上條件,設全部用戶的編號分別為1,2, N;車場具有編號為N+l,N+2, N+M;定義變量 (式2-27)N:表示客戶的總數(shù)目;M:表示車場的總數(shù)目;dij:表示節(jié)點i與節(jié)點j之間的距離;km:表示車場m所擁有的車輛總數(shù);gi:表示客戶i的要求;q:車場m中車輛k載重負荷。以上可以建立數(shù)學模型如下:

35、 (式2-28)公式2-28用來保證最小化的車輛行駛路徑。也是整個問題的核心需求,是下步工作運用算法所需要完成的內(nèi)容,即適應值。接下來就要根據(jù)實際要求對運算加以限制,列出限制公式,以便于計算,獲得與實際相符的可行解。 (式2-29)條件2-29限制了從一個車場出發(fā)的車輛總數(shù)目,必須小于!。此條件用于限制計算時車輛的數(shù)量,因為一個車場所含有的車輛數(shù)是固定的,因此必須加以限制。 (式2-30)公式2-30保證了消除子回路。即不能出現(xiàn)路徑反復,出現(xiàn)誤差。 (式2-31) (式2-32)條件2-31和2-32保證了每個客戶僅被一輛車服務一次。該公式的目的(md)是控制每個客戶都被服務到,并且僅被一輛車

36、服務。 (式2-33)公式2-33表示每輛車的載重(zizhng)量不超過它的載重能力。由于每輛車的承載能力是固定的,因此必須對車輛總承載數(shù)加以(jiy)控制。同時在前文研究的基礎上發(fā)現(xiàn),大部分的約束條件都是從客戶的角度出發(fā),要求每個客戶都被服務到,每個客戶都被一輛車服務,但是如果車輛所經(jīng)過的客戶過多,就會對車輛的行駛里程產(chǎn)生一定要求,車輛行駛的距離與車輛狀態(tài)、儲油量和車輛使用年限等都有一系列的關系,對車輛要求很高,而車輛本身具有一定的局限性,基于以上原因,本文從車輛行駛里程考慮,對車輛服務客戶數(shù)量加以限制,加入了新的約束條件,如公式2-34所示: (式2-34)對于第mk車輛,它所經(jīng)歷的客戶

37、總數(shù)量控制在R以下,即最多為R客戶服務,這樣可以保證車輛的客戶服務數(shù),同時也能在一定的范圍內(nèi)對車輛行駛里程加以限制,確保車輛正常行駛并能將貨物送達每一個客戶。根據(jù)本章對物流配送路徑模型定義、分類的研究,了解物流配送問題建模的內(nèi)容與意義。本章中選擇三種常見的模型進行分析,分別是基于行駛距離最短和使用車輛最少的物流配送模型、基于開放式車輛路徑的物流配送模型和基于顧客滿意度的物流配送模型,對模型進行深入研究,并總結(jié)建立模型的相關思路。根據(jù)實際情況建立了一種基于最短路徑的多車場多車輛的物流配送模型,并從車輛行駛里程角度分析加入了新的約束條件,保證車輛的正常行駛,同時也保證車輛能將貨物送達每一位客戶。3

38、物流配送路徑問題相關算法研究物流配送算法主要的解決方案分為兩大類:人工智能算法和精確算法。人工智能算法包括有:掃描法、旅行商方法、分區(qū)配送算法、節(jié)約法以及一些現(xiàn)代優(yōu)化計算方法(禁忌搜索算法、遺傳算法、模擬退火算法等)。人工智能算法雖然比精確算法精度低,但在求解大規(guī)模VRP時,總可以求解,找到滿意的可行解或次優(yōu)解,這是精確算法無法做到的。因此,人工智能算法更廣泛的運用在實際生活中。精確算法可以這樣劃分:直接樹搜索算法、割平面法、分枝定界法、網(wǎng)絡流算法、整數(shù)線性規(guī)劃和動態(tài)規(guī)劃法。總的來說,精確算需要十分嚴格的數(shù)學手段,所以在可以求解的情況下,其解要比人工智能算法更加優(yōu)良。但由于需要嚴格的數(shù)學方法,

39、因而無法避開指數(shù)過多問題,所以該類算法有限制性,對于小規(guī)模的確定性VRP才能有效求解。3.1物流配送路徑問題相關算法研究(1)精確算法精確算法指可求出最優(yōu)解的算法,主要有分枝定界法、割平面法、網(wǎng)絡流算法、動態(tài)規(guī)劃法等。精確算法的計算量一般隨著問題規(guī)模的增大而呈指數(shù)增長,所以,多用于規(guī)模較小的問題。(2)啟發(fā)式算法通常情況下,通過自身發(fā)展的性質(zhì)和生物系統(tǒng),可以使許多復雜的問題得到令人滿意的解決方案,計算機科學家從生物系統(tǒng)的研究(ynji)中得到的靈感,、以模仿自然的世界,獲取新的方法來解決復雜的計算問題。在算法的設計過程中,設計靈感起源于或者是物理現(xiàn)象,或者是生物群體現(xiàn)象。如模擬退火算法模擬的固

40、體物質(zhì)從高溫度的不穩(wěn)定狀態(tài)的過程中向低溫度穩(wěn)定狀態(tài)過度;遺傳算法從大自然的優(yōu)勝劣汰的生存現(xiàn)象中獲得;蟻群算法模仿蟻群覓食的費洛蒙應用(yngyng),以便找到最短的覓食路徑。這些智能的優(yōu)化算法的出現(xiàn),一方面極大地豐富了優(yōu)化技術,為那些傳統(tǒng)的優(yōu)化技術無法處理的組合優(yōu)化問題提供了一個實用的解決方案,另一方面,他們也從另一個角度來探討生物世界的機制為實際運用提供新的工具和技術。雖然這些新的方法進行了優(yōu)化,并且每個機制是不一樣的,但它們有類似的特征。他們都是迭代算法,通過在不斷的迭代計算,一步一步從質(zhì)量差的解決方案,以更優(yōu)質(zhì)的解決方案逼近。因此,這些算法在多篇論文或其他著作被列為一類,概括起來,即啟發(fā)

41、式算法一一Heuristic Algorithm。啟發(fā)式算法,是一種定義在可以接受的花費(占用空間、計算時間等)下解決組合(zh)優(yōu)化問題的一個可行的解決方案,這種解決方案與最佳方案水平偏差不可預知。另一種定義指定啟發(fā)式算法是一種技術,使尋找最佳的解決方案在一個可接受的計算成本內(nèi),但不一定保證得到的解決方案是可行的和最優(yōu)的,或者甚至在大多數(shù)情況下,得到的解決方案不能逼近最優(yōu)解。在某些情況下,尤其是在實際問題,求解最優(yōu)算法的過程長,計算時間的難以承受,或因為問題的難度使計算時間的增加,如TSP問題,這個問題只能通過啟發(fā)式算法獲得一種可行的解決方案。(3)現(xiàn)代優(yōu)化算法現(xiàn)代優(yōu)化算法一般從初始解開始,

42、通過對當前解不斷進行局部擾動以達到較好的解。常見的算法除了本文研究的粒子群算法外,還有模擬退火算法、禁忌搜索算法、遺傳算法等。3.2常見現(xiàn)代優(yōu)化算法分析與對比下面詳細介紹幾種現(xiàn)代優(yōu)化算法,包括蟻群算法、遺傳算法、粒子群算法和局部搜索算法,分析幾種算法的優(yōu)點和缺點,并針對所需求解問題,選擇優(yōu)勢較明顯的算法解決問題,同時針對所用算法的缺陷與不足,展幵后續(xù)工作。3.2.1算法舉例(1)蟻群算法蟻群算法于20世紀90年代由意大利學者Dorigo.M等首先提出的,是一種用于解決復雜優(yōu)化,基于種群的模擬進化的全新啟發(fā)式算法。蟻群算法由許多螞蟻共同完成,每只螞蟻在候選解的空間中獨立地搜索,然后在所得的解上做

43、好標記,螞蟻傾向于朝著標記多的方向移動。本質(zhì)上仍是一種隨機搜索算法,它尋求最優(yōu)解是通過對候選解組成的群體的進化。因此,由大量螞蟻組成的蟻群的集體行為便表現(xiàn)出來一種信息正反饋現(xiàn)象:一條路上螞蟻經(jīng)過的多了,其他螞蟻就會逐漸向這條路靠攏,最后形成收斂。1)蟻群算法的優(yōu)點蟻群算法在搜索過程中不需要人工干預,并具有正反饋、并行性、健壯性等特點,顯著用于解決小規(guī)模(n30)的旅行商問題。2)蟻群算法的缺點但在初期的道路上,由于各種激素水平基本相等,螞蟻的搜索呈現(xiàn)出較大的盲目性,使解決較大規(guī)模旅行商問題性能迅速惡化,激素水平會呈現(xiàn)明顯的指導需要長時間的時間要求。此外,由于蟻群算法是一種正反饋算法,算法雖然收

44、斂快,但是容易陷入局部最優(yōu)。此外,蟻群算法中許多參數(shù)的設定都是基于經(jīng)驗的,沒有充足的證據(jù),螞蟻數(shù)量往往依靠實驗設置調(diào)整。因此,在運用算法時,需要先實驗,然后根據(jù)實驗結(jié)果調(diào)整參數(shù),進行搜索才能應用蟻群算法求解旅行商問題。3)蟻群算法(sun f)在TSP中的應用算法(sun f)如下:步驟:初始化各個(gg)點)之間的長度,即隨機賦予所有邊一個外激素水平初始值;步驟:將螞蟻放入其中;步驟:各個螞蟻根據(jù)外激素水平和相應距離選擇下一個走向;步驟:所有螞蟻完成搜索后更新外激素水平:螞蟻經(jīng)過次數(shù)多的邊,增加其外激素水平(分泌外激素);螞蟻經(jīng)過少的邊減少外激素水平(揮發(fā)性);然后判斷是否產(chǎn)生新的最優(yōu)路線,

45、如產(chǎn)生，則記錄到全局變量中;步驟:循環(huán)步驟,直至滿足條件退出。(2)遺傳算法遺傳算法是建立在孟德爾的遺傳學說和達爾文的生物進化論基礎上的算法,是一種模擬遺傳機制和自然選擇的尋優(yōu)方法,它是在60年代中期由美國密執(zhí)安大學HollandJ.H首先提出,隨后的工作由他和他的一批學生共同研究發(fā)展起來的。進化論中描述,每一個物種都是在不斷的開發(fā)過程中越來越適應環(huán)境,物種的個體的后代將繼承物種的基本特征,但未來的世代,并且不完全等同于父代,這些新變化如果適應環(huán)境,就會保留下來;否則,淘汰。在遺傳學中,遺傳基因作為基因代碼指令蘊藏在每個細胞中,并以染色體的形態(tài)存在,生物的特征由基因所控制。產(chǎn)生出來的個體對環(huán)境

46、有一定的適應能力,基因突變和基因雜交可能產(chǎn)生對環(huán)境適應性強的后代。最后通過自然選擇,優(yōu)勝劣汰保存適應值高的基因結(jié)構。遺傳算法就是引用了隨機統(tǒng)計原理而形成的,并模擬了進化原理和生物的遺傳。在求解過程中,遺傳算法在最初給粒子賦予一個初始變量,然后逐代地尋找問題的最優(yōu)解,直到預先假定的迭代次數(shù)或滿足收斂判據(jù)為止,它是一種迭代式算法。1)遺傳算法的優(yōu)點算法重點搜索性能較高的部分,同時進行全空間并行搜索,目的是夠提高效率。算法具有全局尋優(yōu)能力強的特點,搜索不是從一個單一的個體開始,而是從一組解開始,且將并行搜索功能蘊藏其中,從而將陷入局部極小的可能性降低。算法具有內(nèi)在平行性,可以通過遺傳處理大量的模式,

47、并易于并行實現(xiàn)。2)遺傳算法缺點遺傳算法在搜索過程不斷進化,每一代保持一定的群體規(guī)模。如果規(guī)模小,包含信息也會比較少,不能充分發(fā)揮遺傳算法的功能;如果規(guī)模大,它包含的信息量大,會急劇的增加計算次數(shù),對遺傳算法的使用有一定的限制。該算法能夠存在的早熟現(xiàn)象,有多種原因造成這一現(xiàn)象,其原因如下:交叉算子使群體中的染色體局部相似,遺傳時染色體交換的信息量變小,使搜索停滯不前;此外,如果基因突變率太小,會導致搜索不能轉(zhuǎn)向其他的解空間進行。3)遺傳算法應用編碼目前多采用以遍歷于城市的次序排列進行編碼,在求解TSP問題的各種遺傳算法中,如串25413是指從城市2開始,逐次經(jīng)過城市5, 4, 1, 3,最后返

48、回城市2的過程路徑,這是一種自然的編碼方法,但是其有自身的缺陷,缺陷是引入交叉操作困難。選擇對當前群體中成員進行選擇,選擇優(yōu)良的個體,他們有機會(j hu)繁殖下一代,被選擇機會的大小由個體適應度的大小決定。變異(biny)策略在TSP運用中,交叉功能是遺傳算法主要強調(diào)的功能,從進化的角度遺傳算法,它是一種解決問題的進化方法,主要以交叉策略和選擇機制來完成,變異的選擇和交叉只是(zhsh)一些維修和補充。遺傳算法有幾種不同的變異操作,如移位變化、插入變異、交換變異、目標導向的變異。交叉策略它是遺傳算法中最主要的操作,由兩步進行,首先隨機的對群體中的個體進行配對;然后隨機設定交叉處在配對個體中,

49、使配對個體彼此交換部分信息。交叉的方法有多種,如單點交叉映射法、PMX法、類0X法、單點順序交叉法等。適應度函數(shù)取路徑長度Td的倒數(shù)為適應度函數(shù)常,即戶1 I Td。(3)粒子群算法概述粒子群算法,也被稱為粒子群優(yōu)化算法,簡稱為粒子群優(yōu)化算法,與遺傳算法相同,都是從隨機模型的最優(yōu)解的迭代開始,它是通過適應度來評價的解決方案,但它更簡單的規(guī)則比遺傳算法更加有利于實際應用,它沒有遺傳算法的交叉、變異操作,它通過遵循當前搜索到的最優(yōu)值來尋找全局最優(yōu)。粒子群優(yōu)化算法屬于一個的進化的算法,是近年來發(fā)展起來的一種新的算法。該算法具有精度高、易于實現(xiàn)和收斂快的優(yōu)點,在學術界顯示出解決實際問題的優(yōu)越性1)粒子

50、群算法優(yōu)點算法原理簡單,容易實現(xiàn);粒子間協(xié)同搜索,搜索策略是由群體全局信息和個體局部信息進行指導;算法不依賴于問題信息,通用性比較強;粒子群算法具有群體搜索和記憶的能力,能使種群和個體的最優(yōu)信息得到保留。2)粒子群算法缺點算法容易陷入局部最優(yōu),局部搜索能力比較差,且其搜索精度也不夠高;算法搜索性能對參數(shù)的依賴性較強;算法理論還不完善,特別是在算法具體應用時算法的設計缺少實用性指導原則。算法并不能保證一定得到全局最優(yōu)解,容易陷入局部極小解;(4)局部搜索算法局部搜索又稱鄰域搜索,它是一種迭代搜索技術在復雜函數(shù)優(yōu)化的過程中經(jīng)常采用,其基本原則是在當前的解決方案所形成的鄰域解中不斷迭代和優(yōu)化設計的目

51、標函數(shù),使之逐漸成為更好解,直到在鄰近的領域內(nèi)找不到比當前更好地解決方案為止。從最初的解決方案起,基于群體功能在當前解前提下,繼續(xù)搜索比它好解,如果能找到一個這樣的解決方案,則使它成為新解決方案,然后重復這個過程,如果沒有更好的終止搜索過程,當前的解決方案為最終解決方案。鄰域搜索算法主要包括確定局部搜索方式和設計鄰域函數(shù)。函數(shù)優(yōu)化中有比較直觀的鄰域函數(shù)概念,最常用的方式是利用距離的概念通過附加擾動來確定鄰域函數(shù)。鄰域函數(shù)的設計往往依賴于解的表達方式和問題的特性。對于鄰域函數(shù)的具體表現(xiàn)方式,組合優(yōu)化和函數(shù)優(yōu)化存在著明顯的差異。該算法的主要優(yōu)點是速度比較快、容易改進、相應的算法程序簡單、容易實現(xiàn)、

52、算法直觀。該算法的缺點:算法的搜索性能完全依賴于初始解和鄰域函數(shù),如果初始值選取不合適或者是設計不當,則算法將會有非常差的最終性能;在搜索過程中可能出現(xiàn)早熟,即可能會出現(xiàn)陷入局部極小的情況。3.2.2算法比較對于前文介紹(jisho)的各種算法的優(yōu)缺點,下面進行匯總,如表3-1所示。Tab 3-1 Algorithm contrast table操作難易搜索速度搜索性能搜索規(guī)模局部極小算法特點搜索特點存在早熟備注遺傳算法中等慢好較小低交叉,變異內(nèi)在平行性是算法基于遺傳和變異產(chǎn)生粒子群算法簡單快好中等 高適應度協(xié)同搜索算法有記憶性否算法理論不完善局部搜索算法簡單快低小中初始解和臨域函數(shù)現(xiàn)搜索性能

53、依賴初始解和鄰域函數(shù)是算法容易操作程序間單,容易改進蟻群算法中等 快好小高外激素水平行正反饋并行性健壯性是算法不需要人工干預,用于解決小性規(guī)模旅行商問題如上表所示,粒子群算法具有操作簡單、搜索速度快、搜索規(guī)模適中的優(yōu)點,可以用于解決物流配送路徑問題,但是粒子群算法有自身的缺點,算法容易早熟,且理論缺少完善性,所以針對這一特點,文章選擇粒子群算法進行(jnxng)物流配送路徑問題研究,并將算法進行改進,以避免早熟收斂的情況(qngkung)發(fā)生。3.3 傳統(tǒng)粒子群算法局限性分析3.3.1 經(jīng)典PSO算法粒子群算法(PSO)是一種基于群體理論的智能優(yōu)化算法(J.Kennedy andR.C.Ebe

54、rhart, 1995),它將每個粒子都當成無體積的,在一定的搜索空間內(nèi)以不確定速度飛行,并且其速度是根據(jù)自身的歷史經(jīng)驗和同伴的經(jīng)驗進行實時調(diào)整的?；驹頌?設Xi= (Xii,Xi2, , Xin)為粒子i的當前位置,Vi=(Vi,Vi2,Vin)為粒子i的當前飛行速度,Pi=(Pi1,Pi2,Pin),為粒子i所經(jīng)歷的最佳位置,也就是粒子i所經(jīng)歷過的具有最好適應值的位置,稱為個體在時間k獲得的最好位置。對于最小化問題,目標函數(shù)值越小,對應的適應值越好。整個粒子群搜索到的最佳位置表示為Pg= (Pgl,Pg2,Pg3,Pgn),意義為整個粒子群到時間k位置搜索到的最佳位置。其中每個粒子新的

55、速度按式3-1進行更新： (式3-1)C1和C2:加速度系數(shù),( 是慣性權重系數(shù),一般取2,可以控制當前粒子速度受之前速度影響的大小。R1和r2為隨機數(shù)值,一般取值0到1之間。根據(jù)公式3-2,可計算出每個粒子更新位置。 (式3-2)通常為了避免在進化過程中粒子飛出搜索空間,公式3-2中的取范圍內(nèi)的數(shù),粒子以公式3-1飛向新位置,并循環(huán)此過程直至用戶定義的迭代條件不滿足。3.3.2傳統(tǒng)算法的流程在解決物流路徑問題時,傳統(tǒng)的算法的流程如下:Step 1:隨機初始化每個粒子的速度和位置,如果運用d維的搜索空間,那么每個粒子包含d個變量。Step 2:對評價種群中所有粒子,并將各粒子的目標和位置存于各

56、粒子的中, =所有中的個體具有最優(yōu)目標值的位置和目標。Step 3:按算法(sun f)原理中的公式將粒子的位置及速度進行更新。Step 4:對種群(zhn qn)中的所有粒子進行評價。Step5:將各個(gg)粒子的與當前目標值比較,從而更新粒子的。.Step 6:比較當前所有和更新。Step 7:若滿足終止準則(通常為達到一個預設最大迭代次數(shù)或足夠好的適應值),則輸出gbest及其目標值并停止算法,否則轉(zhuǎn)向Step 3。 28算法流程圖如圖3-1所示:Fig.3-1 The traditional particle swarm optimization algorithm flowchar

57、t to solve the problemsof logistics and distribution path3.3.3算法具體描述粒子群算法就是模擬一群鳥類尋食的過程,每個粒子都可以看做是一只鳥,也是求解問題的一種可行解,它們在尋找食物過程中不斷的更新自己的位置,用圖可以這樣表示。根據(jù)自身理解,將這個過程轉(zhuǎn)化為一個數(shù)學問題。令函數(shù)為,在0,4最大值。此函數(shù)圖形如圖3-2所示。圖3-2曲線圖Fig. 3-2 Diagram of curves當x=0.9350-0.9450,函數(shù)達到最大值y=1.3706。為了得到該函數(shù)的最大值,隨機在0, 4之間分布點,算法(sun f)的具體實現(xiàn)過程,

58、如圖3-3至圖3-7所示(1)初始化圖3-3初始(ch sh)圖Fig.3-3 The initial diagram(2)第一次位置(wi zhi)更新 圖3-4第一次更新(gngxn)圖Fig.3-4 The first updated map(3)第二次位置(wi zhi)更新圖3-5第二次更新(gngxn)圖Fig. 3-5 The second updated map(4)第21次更新(gngxn)圖3-6第二十一次更新圖Fig.3-6 The twenty-first updated map(4) 30次迭代(di di)結(jié)果圖3-7第三十次迭代(di di)結(jié)果Fig.3-7 T

59、he thirtieth iteration result整個算法的最后(zuhu)在最大值的地方,粒子集中。以上就是算法的過程描述。3.3.4粒子群算法特點分析在解決物流配送路徑問題時,傳統(tǒng)算法的局部改良能力和全局探索能力的平衡很大程度上決定了算法的搜索性能,這種平衡在控制參數(shù)上有很大程度上依賴性(包括最大代數(shù)、種群規(guī)模、慣性權因子、最大速度和加速常數(shù)等)。傳統(tǒng)算法與其他進化算法相比,他們需要調(diào)整的參數(shù)相對較少。總而言之,粒子群算法是一種隨機,平行的優(yōu)化算法,它不需要被優(yōu)化的函數(shù)連續(xù)、可微可導。它還具有算法簡單、快速收斂和易于編程實現(xiàn)的優(yōu)勢。短短幾年,粒子群算法己經(jīng)有了很大的發(fā)展,并己在某些

60、領域的應用。但粒子群算法有其自身的缺點:容易下降到局部極值點,無法獲得最佳解決方案,當粒子在參數(shù)選擇的多樣性不當,會導致優(yōu)化過程迅速消失,導致算法早熟收斂。因此,研宄人員已經(jīng)提出的各項改善措施。從基本的粒子群算法己開發(fā)許多不同的改進算法。下面對改進的粒子群優(yōu)化的簡要介紹。3.4已有粒子群算法的改進方法(1)標準算法將慣性權重引入算法,目的是為了更好的控制算法的開發(fā)能力和搜索改善基本粒子群算法的收斂性等方面,引入慣性權重在速度進化方程中,可得出以下公式:通常標準粒子群算法是將上面的式子與傳統(tǒng)的粒子群算法進行結(jié)合(jih)組成。在正常情況下,本文談論的粒子群優(yōu)化算法是指標準的粒子群算法。顯然,慣性