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

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

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

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

4、模型舉例102.3.1 基于行駛距離最短和使用車輛最少的物流配送問題102.3.2基于開放式車輛路徑的物流配送問題112.3.3基于顧客滿意度的物流配送問題122.4模型建立思路總結(jié)142.5基于最短路徑的多車場(chǎng)多車輛配送模型建立153物流配送路徑問題相關(guān)算法研究193.1物流配送路徑問題相關(guān)算法研究193.2常見現(xiàn)代優(yōu)化算法分析與對(duì)比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.4粒子群算法特點(diǎn)分析313.4已有粒子群算法的改進(jìn)方法314一種改進(jìn)的粒子群算法設(shè)計(jì)354

5、.1改進(jìn)后的自適應(yīng)變異粒子群算法354.2粒子編碼374.3算法實(shí)現(xiàn)的具體步驟384.3.1算法實(shí)現(xiàn)步驟文字表述384.3.2 算法實(shí)現(xiàn)步驟的流程圖表述394.4優(yōu)化的粒子群算法與其他算法比較414.4.1優(yōu)化的粒子群算法與遺傳算法的比較414.4.2優(yōu)化的粒子群算法與傳統(tǒng)粒子群算法比較425 MatLab仿真與實(shí)驗(yàn)445.1算法仿真環(huán)境445.2算法可行性與對(duì)比分析445.2.1仿真實(shí)驗(yàn)數(shù)據(jù)445.2.2算法可行性研究455.2.3優(yōu)化算法與傳統(tǒng)算法的對(duì)比分析465.3基于不同目標(biāo)模型的對(duì)比研究495.3.1仿真實(shí)驗(yàn)數(shù)據(jù)495.3.2 仿真結(jié)果495.4 仿真結(jié)果總結(jié)516 結(jié)論與展望536

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

7、占58%,因此,對(duì)于分配環(huán)節(jié)的優(yōu)化方面,最重要的就是研宄配送路徑車輛調(diào)度問題,而對(duì)于集貨路線優(yōu)化、物品配送路線和裝備方式是對(duì)于配送車輛調(diào)度優(yōu)化的重要環(huán)節(jié),也是進(jìn)行對(duì)配送環(huán)節(jié)進(jìn)行優(yōu)化的重中之重。物流系統(tǒng)中物流配送是一個(gè)非常重要的環(huán)節(jié),它是整個(gè)對(duì)客戶服務(wù)過程中最后一個(gè)環(huán)節(jié)。因此,需要知道在物流過程中,物流配送的地位非常突出,所以企業(yè)經(jīng)營(yíng)中必須實(shí)現(xiàn)快速、準(zhǔn)確的物流配送,這是十分重要問題。物流配送路徑問題提出之后,很快便引起計(jì)算機(jī)學(xué)科、運(yùn)籌學(xué)、組合數(shù)學(xué)、應(yīng)用數(shù)學(xué)、物流科學(xué)等學(xué)科專家的極大重視,并且一直是人工智能、應(yīng)用數(shù)學(xué)領(lǐng)域的前沿與熱點(diǎn)問題。在現(xiàn)實(shí)生產(chǎn)和生活中,網(wǎng)絡(luò)路由問題、郵政投遞問題、公共汽車調(diào)度

8、問題、管道鋪設(shè)問題等都可以抽象化為物流配送路徑問題。在物流配送業(yè)務(wù)中,物流配送問題需要考慮的因素比較多,涉及的面比較廣,同時(shí)對(duì)配送企業(yè)降低成本、提高服務(wù)質(zhì)量、增加經(jīng)濟(jì)效益的影響也比較大。然而目前研究發(fā)現(xiàn),我國(guó)在研究物流配送車輛調(diào)度方面成果較少,所獲得的進(jìn)展緩慢,并且對(duì)于仿生算法研究還有一定的欠缺性,對(duì)于算法自身的缺陷彌補(bǔ)不足,針對(duì)以上原因,本文將重點(diǎn)研究物流配送中車輛調(diào)度和路徑問題,并將物流配送中的算法進(jìn)行詳細(xì)研究,針對(duì)算法缺陷進(jìn)行改進(jìn),形成新的優(yōu)化算法,并根據(jù)最優(yōu)配送目標(biāo)和實(shí)際要求建立數(shù)學(xué)模型,進(jìn)行計(jì)算與仿真。1.2研究現(xiàn)狀綜述在現(xiàn)代物流體系中物流配送車輛路徑問題是一個(gè)重要組成部分,它是指在

9、物流中心的貨物,通過交貨,將貨物送到收貨人的一系列活動(dòng)都需要按照用戶需求進(jìn)行設(shè)置。例如,你有一個(gè)中央貨場(chǎng)貨物需要交付給多個(gè)用戶,每個(gè)用戶都有不同的需求,貨物車輛在裝滿后運(yùn)輸貨物,它配送完每一個(gè)用戶后再回到貨場(chǎng),完成任務(wù),在這個(gè)過程中,如何滿足用戶的需求,以最小的成本費(fèi)用和車輛的路線進(jìn)行配送,那就是物流配送路徑問題。又如另一個(gè)例子,需要被運(yùn)送到中央倉(cāng)庫(kù)的一些廠家生產(chǎn)的產(chǎn)品,車輛從倉(cāng)庫(kù)開始向廠家裝車后,全額返還到倉(cāng)庫(kù),并滿足一些生產(chǎn)產(chǎn)品的制造商的要求,按照一定的路線,可以降低總費(fèi)用,這就是物流配送路徑問題。這兩個(gè)問題具有相同的實(shí)質(zhì),只是交付的任務(wù)或者集貨的任務(wù)存在差異。在物流和運(yùn)輸業(yè)務(wù)中,有很多的

10、優(yōu)化決策問題。合理選擇運(yùn)輸路徑,在提高服務(wù)質(zhì)量,加快交貨過程,提高經(jīng)濟(jì)效益,降低運(yùn)營(yíng)成本上都有較大的影響。1.2.1國(guó)內(nèi)外硏究現(xiàn)狀對(duì)于物流配送路徑優(yōu)化問題一度被提出后,國(guó)內(nèi)外學(xué)者都十分關(guān)注,分別從不同的方向、不同的角度對(duì)這一問題進(jìn)行了深入的研究,分別按照不同的標(biāo)準(zhǔn)對(duì)其進(jìn)行優(yōu)化和分類。本文為了方便描述,根據(jù)業(yè)務(wù)類型的不同簡(jiǎn)要將其分類描述。物流配送問題是預(yù)先設(shè)計(jì)好的一種路徑走向,可以將物流配送路徑問題簡(jiǎn)要的分成五個(gè)類別。分別是:(1)最簡(jiǎn)單的物流配送路徑優(yōu)化問題1。最簡(jiǎn)單的物流配送路徑優(yōu)化問題被抽象為有一個(gè)配送中心,有一輛配送車輛,且滿足相應(yīng)的約束條件進(jìn)行貨物配送。是最簡(jiǎn)單的一種路徑優(yōu)化向題2。(

11、2)基本的物流配送路徑優(yōu)化問題3。將前一種分類進(jìn)行推廣研究,就可以描述為一個(gè)中心,有多輛車,每輛車有固定載重,按照要求進(jìn)行配貨。其實(shí)這是一個(gè)標(biāo)準(zhǔn)的車輛路徑問題4,也可以說是車輛調(diào)度問題,一直是優(yōu)化學(xué)科和運(yùn)籌學(xué)的前沿?zé)狳c(diǎn)5。(3)根據(jù)實(shí)際設(shè)定約束的物流配送路徑優(yōu)化問題。目前條件下一共需要考慮的因素有以下幾種。1)客戶對(duì)時(shí)間有限制6。即可以描述為客戶對(duì)整個(gè)物流配送過程有時(shí)間窗的要求,包括硬時(shí)間和軟時(shí)間7;2)車輛對(duì)于運(yùn)輸?shù)木嚯x有相應(yīng)的限制8。即可以描述為車輛的最大行駛距離的有限性9;3)對(duì)于客戶由不確定的需求限制ieiu即客戶有隨機(jī)或模糊的需求11。(4)多樣性限制的物流配送路徑優(yōu)化問題。1)有多

12、種車型的配送方式12。即整個(gè)配送中心具有多種類的車型車輛進(jìn)行配送服務(wù)13;2)有多個(gè)車場(chǎng)的配送方式14。即多個(gè)車場(chǎng)同時(shí)服務(wù),進(jìn)行物流配送15;3)物流配送有多個(gè)目標(biāo)16,即配送中心所具有的優(yōu)化目標(biāo)含有幾個(gè)相互排斥的分目標(biāo)17。(5)其他種類配送路徑優(yōu)化問題。例如開放式的物流配送路徑優(yōu)化服務(wù)等18。1.2.2算法硏究現(xiàn)狀粒子群優(yōu)化算法是求解組合優(yōu)化問題的一種群體智能算法,其具有參數(shù)少、模型簡(jiǎn)單、收斂速度快等優(yōu)點(diǎn),常被運(yùn)用到神經(jīng)網(wǎng)絡(luò)問題中,用來(lái)解決實(shí)際問題。目前對(duì)于粒子群算法的優(yōu)化改進(jìn)主要集中在以下的幾個(gè)方面:(1)對(duì)粒子群算法結(jié)構(gòu)進(jìn)行改變;(2)對(duì)粒子群算法機(jī)理進(jìn)行分析;(3)研宄粒子群算法中參

13、數(shù)的設(shè)置;(4)研究粒子群算法的拓?fù)浣Y(jié)構(gòu);(5)研宄對(duì)粒子群算法進(jìn)行離散化的方法;(6)研究粒子群算法的并行版本;(7)對(duì)用于多目標(biāo)求解的粒子群算法進(jìn)行研究;(8)研究粒子群算法在實(shí)際問題中的應(yīng)用。Shi第一次在粒子群算法中引入了慣性權(quán)重系數(shù)19,通過調(diào)解原有速度和更新速度的關(guān)系,平衡粒子的局部搜索能力和全局搜索能力。Kennedy在粒子群算法中提出了帶鄰域拓?fù)?0,通過拓?fù)鋪?lái)延緩信息在種群中的交流速度,降低粒子群內(nèi)部粒子之間的相互影響,從而降低得到局部最優(yōu)值發(fā)生早熟的可能性,同時(shí)通過對(duì)各種鄰域拓?fù)浣Y(jié)構(gòu)對(duì)算法性能影響的分析,總結(jié)出指出馮諾依曼結(jié)構(gòu)具有最好的綜合性。Kennedy分析了速度更新公

14、式在粒子群算法中的作用,同時(shí)分析了無(wú)速度更新公式的粒子群算法21。Kennedy提出了動(dòng)態(tài)概率粒子群算法22。 Clerc在粒子群算法中引入了約束因子,用來(lái)確保粒子群算法局部的收斂性。曾建潮等提出了一種保證粒子群算法全局收斂的新方法。Bratton和Kennedy對(duì)粒子群算法的各種改進(jìn)提出了一個(gè)標(biāo)準(zhǔn)框架23,為各種PSO算法改進(jìn)研究提供了參照標(biāo)準(zhǔn)。Bergh等提出協(xié)作粒子群算法24。 Chen等將結(jié)合極值優(yōu)化引入到粒子群算法中,通過結(jié)合E0的開拓能力和PSO的探索能力來(lái)提高其性能。對(duì)粒子群算法參數(shù)的設(shè)置問題,本文研究主要包括,對(duì)于慣性權(quán)重W、社會(huì)因子C1、個(gè)人因子C2和速度上限Vniax的取值

15、策略以及研宄粒子群的規(guī)模。Chatterje和Shi分別提出了慣性權(quán)重的非線性變化和線性變化的粒子群算法王俊偉等通過實(shí)驗(yàn)研究,給出了設(shè)置慣性權(quán)重的指導(dǎo)性原則。彭宇等對(duì)于C1， C2和慣性權(quán)重W的設(shè)置通過方差分析手段對(duì)算法性能的影響分析,總結(jié)了針對(duì)參數(shù)設(shè)置的有哪些指導(dǎo)原則25。 Liu提出了一種中央粒子粒子群算法,實(shí)驗(yàn)證明該算法性能比傳統(tǒng)粒子群算法好26。除此之外,目前的研究熱點(diǎn)還包括將其他進(jìn)化計(jì)算方法融合到粒子群算法中將其改進(jìn)27。針對(duì)物流配送路徑問題和粒子群算法的現(xiàn)狀,文章對(duì)粒子群算法進(jìn)行深入研究,對(duì)其缺陷進(jìn)行分析,引入新的優(yōu)化手段,優(yōu)化現(xiàn)有粒子群算法,并根據(jù)需求加入相應(yīng)的約束條件建立物流配

16、送模型進(jìn)行求解,對(duì)于實(shí)際應(yīng)用起到相應(yīng)作用,也為下一步研究工作的展開奠定基礎(chǔ)。1.3 研究?jī)?nèi)容與研究方法本文首先介紹物流配送路徑的基本理論與相關(guān)算法,然后對(duì)物流配送路徑的問題進(jìn)行描述型定義、分類與建立數(shù)學(xué)模型。通過對(duì)傳統(tǒng)的解決物流配送問題的算法進(jìn)行分析與對(duì)比,了解其流程、特點(diǎn)與不足,針對(duì)問題和這些不足設(shè)計(jì)了一種改進(jìn)的可以自適應(yīng)的粒子群算法。最后進(jìn)行了仿真實(shí)驗(yàn)與結(jié)果分析。本文主要采用以下研究方法:(1)文獻(xiàn)調(diào)研文獻(xiàn)調(diào)研方法將當(dāng)前物流配送路徑問題和粒子群算法以及相關(guān)算法的現(xiàn)狀和問題進(jìn)行描述與分析,了解當(dāng)前最新研宄動(dòng)態(tài),獲取到相關(guān)的方法信息。(2)定性與定量分析所謂定性分析,是指不采用數(shù)學(xué)方法,僅采用

17、研究者的直覺、感觀、經(jīng)驗(yàn)對(duì)研究對(duì)象進(jìn)行判斷,并結(jié)合以前的事實(shí)或者其他資料,對(duì)研究對(duì)象的性質(zhì)、趨勢(shì)、規(guī)律等作出感性判斷的一種方法,最后采用文字等方式進(jìn)行描述表達(dá)。所謂定量分析,是指根據(jù)研究對(duì)象的各項(xiàng)指標(biāo)特點(diǎn)與數(shù)值,采用概率模型、統(tǒng)計(jì)模型等進(jìn)行適當(dāng)?shù)臄?shù)據(jù)建模,并用規(guī)范的數(shù)學(xué)語(yǔ)言進(jìn)行描述的一種方法。通過科學(xué)的定量分析,可以從本質(zhì)上了解事物的發(fā)展規(guī)律。定性分析和定量分析兩種方法是相互依存的,缺一不可,定量分析以定性分析作為基礎(chǔ),而定性分析要通過定量分析來(lái)具體化、精確化,只有將這兩種研究方法結(jié)合起來(lái)使用,才能達(dá)到較好的硏究效果。本文首先將所需解決的物流配送路徑問題定性化,選擇相應(yīng)模型和算法,并對(duì)算法進(jìn)行

18、改進(jìn)和優(yōu)化,同時(shí)建立所需模型,然后定量的仿真與計(jì)算。將定性與定量方法相結(jié)合,并運(yùn)用其完成文章所需。(3)理論分析與實(shí)證研宄相結(jié)合理論分析是指運(yùn)用粒子群理論、運(yùn)籌學(xué)與計(jì)算機(jī)仿真理論對(duì)系統(tǒng)需求及實(shí)現(xiàn)進(jìn)行了深入剖析。實(shí)證分析是指借助本文最后采用的對(duì)經(jīng)驗(yàn)事實(shí)的描述通過訴諸事實(shí)來(lái)解決人們經(jīng)驗(yàn)事實(shí)中所遇到的問題。它注重人的現(xiàn)實(shí)功利要求追求結(jié)果的時(shí)效性。(4)仿真實(shí)驗(yàn)通過在MatLab 2011a上的仿真實(shí)驗(yàn),驗(yàn)證本文設(shè)計(jì)算法的科學(xué)性與有效性。1.4本文的組織結(jié)構(gòu)本文包括以下六章:第一章緒論:介紹了本文的研究背景與意義,闡述了研究物流配送路徑問題的重大需求。然后論述了國(guó)內(nèi)外對(duì)于物流配送問題的研究現(xiàn)狀、算法的

19、研究現(xiàn)狀及其發(fā)展情況,最后給出本文的主要研宄內(nèi)容和章節(jié)安排。第二章物流配送相關(guān)問題介紹和模型建立:對(duì)于物流配送問題進(jìn)行了詳細(xì)介紹,并且介紹了多種物流配送問題可建立的模型,并進(jìn)行模型總結(jié),同時(shí)介紹物流配送路徑的基本算法和分類,以及配送區(qū)域劃分算法的基本分類,同時(shí)建立多車場(chǎng)多車輛的物流配送模型,并加入新的約束條件。第三章物流配送問題相關(guān)算法研究:對(duì)傳統(tǒng)的粒子群算法進(jìn)行介紹,并對(duì)其特點(diǎn)進(jìn)行分析,同時(shí)列舉出現(xiàn)有的幾種針對(duì)粒子群算法的改進(jìn)方法。第四章應(yīng)用于物流配送路徑問題中的一種改進(jìn)的自適應(yīng)的粒子群算法設(shè)計(jì):在前三章理論基礎(chǔ)上,通過對(duì)問題研究所需的粒子群算法的分析以及與其他算法的對(duì)比,論證其算法的不足,

20、并結(jié)合己有的幾種優(yōu)化方法和改進(jìn)方式設(shè)計(jì)了一種新的改進(jìn)的自適應(yīng)粒子群算法。第五章MatLab仿真實(shí)驗(yàn):在本文前幾章的理論分析和模型建立、算法優(yōu)化的基礎(chǔ)上,根據(jù)實(shí)驗(yàn)數(shù)據(jù)設(shè)計(jì)了仿真實(shí)驗(yàn),通過對(duì)結(jié)果進(jìn)行分析比較,驗(yàn)證了本文算法的科學(xué)性和有效性,同時(shí)驗(yàn)證不同最優(yōu)配送目標(biāo)下物流配送的方案不同。第六章總結(jié)與展望:對(duì)本文的研究進(jìn)行總結(jié),并對(duì)未來(lái)的工作做展望和建議。具體研宄思路如圖1-1所示。1-1文章思路圖Fig. 1-1 Articles ideas roadmap2物流配送模型建立與常見模型分析本章著重研究物流配送路徑問題的模型分類,并總結(jié)建立模型的一般步驟。并根據(jù)自身對(duì)物流配送模型的理解,建立基于最短路

21、徑的多車場(chǎng)多車輛的物流配送模型,并加入新的約束條件。在后續(xù)工作中需要對(duì)具有不同最優(yōu)配送目標(biāo)的模型進(jìn)行仿真,了解不同最優(yōu)配送目標(biāo)下物流配送路徑之間的關(guān)系。2.1物流配送路徑問題相關(guān)硏究2.1.1物流配送路徑問題定義物流配送路徑問題最早是由學(xué)者Dantzig和Ramser于1959年首次提出的,一般可定義為:對(duì)于一系列裝貨點(diǎn)和(或)卸貨點(diǎn),組織合適的行車線路,使載貨車輛有序地通過它們,在滿足一定的約束條件(如貨物的發(fā)送量、貨物的需求量、運(yùn)送貨物車輛容量限制、交發(fā)貨時(shí)間和運(yùn)輸時(shí)間限制等)下,達(dá)到一定的目標(biāo)(如運(yùn)輸所用費(fèi)用最少、運(yùn)輸路程最短、使用車輛數(shù)量少、運(yùn)輸時(shí)間少等)。2.1.2物流配送路徑問題分

22、類由于實(shí)際情況不同可以根據(jù)不同的分類標(biāo)準(zhǔn)劃分成不同類型的物流配送路徑問題,其分類情況如表2-1所示:表2-1物流配送路徑優(yōu)化問題分類Tab.3-1 Logistics and distribution routing problem classification形態(tài)范圍車輛種類單一車種、多種車種車輛容量限制不同車有不同的限制、所有車輛統(tǒng)一的限制、不限制時(shí)間限制不同路線時(shí)間限制不同、所有路線時(shí)間限制相同、無(wú)時(shí)間限制路網(wǎng)方向性混合性路網(wǎng)、有方向性路網(wǎng)、沒有方向性路網(wǎng)里程限制不同車輛里程限制不同、所有車輛里程限制相同、無(wú)限制裝卸作業(yè)形態(tài)混合型、卸貨、裝貨配送中心單一的配送中心、多配送中心貨物類別貨物

23、多種、貨物同種需求形態(tài)需求量隨機(jī)、需求量固定最優(yōu)化目標(biāo)服務(wù)效用最大、路線成本小、車輛數(shù)量少、變動(dòng)及固定成本小2.2 物流配送路徑問題數(shù)學(xué)建模種類對(duì)于物流分配模型建立有很多種模型可以使用,在物流分配中有針對(duì)時(shí)間最短確立,有根據(jù)費(fèi)用最短確立,有根據(jù)路徑最短確立,各自模型有所差異,下面介紹幾種物流分配的數(shù)學(xué)模型。在前文國(guó)內(nèi)外現(xiàn)狀部分對(duì)物流配送路徑問題進(jìn)行了分類,下面對(duì)分類進(jìn)行描述,并選取其中有代表性的幾種分類進(jìn)行舉例介紹。(1)最簡(jiǎn)單的物流配送路徑優(yōu)化問題。在一個(gè)配送中心內(nèi)部由一臺(tái)容量為Q的車進(jìn)行配送,配送點(diǎn)有n個(gè),并滿足一定的條件:1)每個(gè)客戶都必須被訪問,且只能訪問一次;2)車輛從中心車場(chǎng)出發(fā),

24、完成配送任務(wù)后必須回到中心車場(chǎng);3)要用最短的物流配送路徑;4)每個(gè)客戶的需求必須滿足。(2)基本的物流配送路徑優(yōu)化問題。在一個(gè)配送中心內(nèi)部有K輛容量為Q的車,配送點(diǎn)有n個(gè),并滿足一定條件:1)每個(gè)客戶都必須被訪問,且只能訪問一次;2)車輛從中心車場(chǎng)出發(fā),完成配送任務(wù)后必須回到中心車場(chǎng);3)要用最短的物流配送路徑;4)每個(gè)客戶的需求必須滿足。(3)根據(jù)實(shí)際設(shè)定約束的物流配送路徑優(yōu)化問題。以上都是基于數(shù)學(xué)方法理想化的物流配送問題,而實(shí)際工作中,物流配送限制因素有很多,物流問題所面臨的情況也是十分復(fù)雜的,研究人員在物流配送中必須要考慮很多的約束條件,例如車輛油量限制、車輛故障,道路故障等一些突發(fā)事

25、故都會(huì)對(duì)車輛造成影響,因此在物流配送路線設(shè)計(jì)時(shí),考慮很多因素。1)客戶對(duì)時(shí)間有限制2)車輛對(duì)于運(yùn)輸?shù)木嚯x有相應(yīng)的限制3)對(duì)于客戶由不確定的需求限制(4)多樣性限制的物流配送路徑優(yōu)化問題。以上所考慮的問題都是有相同的前提條件,即車輛是同種類型,有確定的優(yōu)化目標(biāo),然而在實(shí)際情況下有很多因素是變化的。如車輛種類有很多,可裝載的貨物不同,車的容量限制也不同;配送中心有多個(gè),即車輛從不同地方出發(fā);還有就是整個(gè)配送有很多優(yōu)化目標(biāo),這些優(yōu)化目標(biāo)并不是相互獨(dú)立的,如距離最小、時(shí)間最短或者車輛等。目前研究中一般考慮的多樣性限制的物流配送路徑問題主要有:1)有多種車型的配送方式2)有多個(gè)車場(chǎng)的配送方式3)物流配送

26、有多個(gè)目標(biāo)(5)其他種類配送路徑優(yōu)化問題在實(shí)際生活中,物流需求是多種多樣的,也有很多種不同的變異方式,目前的物流配送問題,日趨貼近現(xiàn)實(shí)生活,例如多配送中心聯(lián)合的配送任務(wù),即在同一個(gè)信息平臺(tái)內(nèi),多種車輛,多個(gè)中心為同一家客戶服務(wù);或者開放式的物流配送路徑優(yōu)化服務(wù),即配送完成后車輛無(wú)需返回原有車場(chǎng)。隨著科技的進(jìn)步和物流技術(shù)的發(fā)展,信息共享的加劇,物流配送向更加多樣化更加現(xiàn)代化不斷的進(jìn)步。2.3模型舉例2.3.1基于行駛距離最短和使用車輛最少的物流配送問題基于行駛距離最短和使用車輛最少,物流配送問題可以表示成的數(shù)學(xué)模型如下:假定配送中心最多可以用K輛車對(duì)N個(gè)客戶進(jìn)行物流配送,其中k=1,2K,用戶i

27、=1,2N。其中i=0表示倉(cāng)庫(kù),每個(gè)車輛載重為q, g為每個(gè)客戶的需求,客戶i到客戶j的運(yùn)輸成本為CV優(yōu)化的目標(biāo)是行駛距離最短和使用車輛最少。定義變量:其數(shù)學(xué)模型如下表示: (式2-1) (式2-2) (式2-3) (式2-4) (式2-5) (式2-6)其中(2-2)控制每輛車的能力約束。(2-3)確保每個(gè)客戶都被服務(wù)到。(2-4)(2-5)確保每個(gè)客戶被一輛車服務(wù)。(2-6)消除子回路。2.3.2基于開放式車輛路徑的物流配送問題對(duì)于開放式車輛路徑的物流配送問題,可以表示為,第一階段:先把客戶分群,考慮一定的限制,將客戶群個(gè)數(shù)最小化,然后根據(jù)一些規(guī)則重新分配客戶,目的是最小化距離,用模型表述

28、為,當(dāng)車輛將所有客戶配送完成后,并不需要返回配送中心,這樣可以建立開放式車輛路徑數(shù)學(xué)模型,文章給出如下模型:假定配送中心最多可以用K輛車對(duì)N個(gè)客戶進(jìn)行物流配送,其中k=l、2.K,用戶i=l、2.N。其中i=0表示倉(cāng)庫(kù),每個(gè)車輛載重為q, g為每個(gè)客戶的需求,客戶i到客戶j的運(yùn)輸成本為Cij,假設(shè)每輛車最后會(huì)回到虛擬的配送中心,配送中心于客戶間的距離為0,即Cio。定義變量: 其數(shù)學(xué)模型如下表示: (式2-7) (式2-8) (式2-9) (式2-10) (式2-11) (式2-12)其中(2-8)控制每輛車的能力約束。(2-9)確保每個(gè)客戶都被服務(wù)到。(2-10)(2-11)確保每個(gè)客戶被一

29、輛車服務(wù)。(2-12)消除子回路。第二階段:每個(gè)群被轉(zhuǎn)化成開放式線路,用最小生成樹算法來(lái)最小化線路2.3.3基于顧客滿意度的物流配送問題基于客戶的滿意程度,物流的配送問題可以表示成的數(shù)學(xué)模型如下:假定配送中心最多可以用K輛車對(duì)N個(gè)客戶進(jìn)行物流配送,其中k=l、2?K,用戶i=1,2N。其中i=0表示倉(cāng)庫(kù),每個(gè)車輛載重為q, g為每個(gè)客戶的需求,客戶i到客戶j的運(yùn)輸成本為Cij。假設(shè)每輛車最后會(huì)回到虛擬的配送中心,配送中心于客戶間的距離為0,客戶i的時(shí)間窗是Ei, Li,到達(dá)客戶i并且開始服務(wù)的時(shí)間是ti,行駛時(shí)間是, wi為所需的等待時(shí)間,Si為服務(wù)時(shí)間, 表示客戶滿意度,I是很大的整數(shù)。定義

30、變量:基于顧客的滿意程度可得求解目標(biāo)有:第一步是最大化的平均客戶滿意度: (式2-13)其可以等價(jià)轉(zhuǎn)化為最小化的平均客戶不滿意度 （式2-14)第二步是最小化的車輛數(shù): (式2-15)第三步是最小化的車輛行駛距離和等待時(shí)間: (式2-16) (式2-17)其有如下的約束條件: i = l,2N (式2-18) (式2-19) (式2-20) (式2-21) (式2-22) (式2-23) (式2-24) (式2-25) (式2-26)以上公式中,公式(2-18)可以保障每個(gè)客戶滿意程度不低于其中是決策者根據(jù)自身的實(shí)際經(jīng)驗(yàn)給出相應(yīng)的值,其中給每個(gè)客戶的值可以相同也可以不同,其是根據(jù)客戶的重要程度

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

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

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

34、載重負(fù)荷。以上可以建立數(shù)學(xué)模型如下: (式2-28)公式2-28用來(lái)保證最小化的車輛行駛路徑。也是整個(gè)問題的核心需求,是下步工作運(yùn)用算法所需要完成的內(nèi)容,即適應(yīng)值。接下來(lái)就要根據(jù)實(shí)際要求對(duì)運(yùn)算加以限制,列出限制公式,以便于計(jì)算,獲得與實(shí)際相符的可行解。 (式2-29)條件2-29限制了從一個(gè)車場(chǎng)出發(fā)的車輛總數(shù)目,必須小于!。此條件用于限制計(jì)算時(shí)車輛的數(shù)量,因?yàn)橐粋€(gè)車場(chǎng)所含有的車輛數(shù)是固定的,因此必須加以限制。 (式2-30)公式2-30保證了消除子回路。即不能出現(xiàn)路徑反復(fù),出現(xiàn)誤差。 (式2-31) (式2-32)條件2-31和2-32保證了每個(gè)客戶僅被一輛車服務(wù)一次。該公式的目的是控制每個(gè)客

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

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

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

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

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

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

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

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

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

44、傳算法遺傳算法是建立在孟德爾的遺傳學(xué)說和達(dá)爾文的生物進(jìn)化論基礎(chǔ)上的算法,是一種模擬遺傳機(jī)制和自然選擇的尋優(yōu)方法,它是在60年代中期由美國(guó)密執(zhí)安大學(xué)HollandJ.H首先提出,隨后的工作由他和他的一批學(xué)生共同研究發(fā)展起來(lái)的。進(jìn)化論中描述,每一個(gè)物種都是在不斷的開發(fā)過程中越來(lái)越適應(yīng)環(huán)境,物種的個(gè)體的后代將繼承物種的基本特征,但未來(lái)的世代,并且不完全等同于父代,這些新變化如果適應(yīng)環(huán)境,就會(huì)保留下來(lái);否則,淘汰。在遺傳學(xué)中,遺傳基因作為基因代碼指令蘊(yùn)藏在每個(gè)細(xì)胞中,并以染色體的形態(tài)存在,生物的特征由基因所控制。產(chǎn)生出來(lái)的個(gè)體對(duì)環(huán)境有一定的適應(yīng)能力,基因突變和基因雜交可能產(chǎn)生對(duì)環(huán)境適應(yīng)性強(qiáng)的后代。最后

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

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

47、引入交叉操作困難。選擇對(duì)當(dāng)前群體中成員進(jìn)行選擇,選擇優(yōu)良的個(gè)體,他們有機(jī)會(huì)繁殖下一代,被選擇機(jī)會(huì)的大小由個(gè)體適應(yīng)度的大小決定。變異策略在TSP運(yùn)用中,交叉功能是遺傳算法主要強(qiáng)調(diào)的功能,從進(jìn)化的角度遺傳算法,它是一種解決問題的進(jìn)化方法,主要以交叉策略和選擇機(jī)制來(lái)完成,變異的選擇和交叉只是一些維修和補(bǔ)充。遺傳算法有幾種不同的變異操作,如移位變化、插入變異、交換變異、目標(biāo)導(dǎo)向的變異。交叉策略它是遺傳算法中最主要的操作,由兩步進(jìn)行,首先隨機(jī)的對(duì)群體中的個(gè)體進(jìn)行配對(duì);然后隨機(jī)設(shè)定交叉處在配對(duì)個(gè)體中,使配對(duì)個(gè)體彼此交換部分信息。交叉的方法有多種,如單點(diǎn)交叉映射法、PMX法、類0X法、單點(diǎn)順序交叉法等。適應(yīng)

48、度函數(shù)取路徑長(zhǎng)度Td的倒數(shù)為適應(yīng)度函數(shù)常,即戶1 I Td。(3)粒子群算法概述粒子群算法,也被稱為粒子群優(yōu)化算法,簡(jiǎn)稱為粒子群優(yōu)化算法,與遺傳算法相同,都是從隨機(jī)模型的最優(yōu)解的迭代開始,它是通過適應(yīng)度來(lái)評(píng)價(jià)的解決方案,但它更簡(jiǎn)單的規(guī)則比遺傳算法更加有利于實(shí)際應(yīng)用,它沒有遺傳算法的交叉、變異操作,它通過遵循當(dāng)前搜索到的最優(yōu)值來(lái)尋找全局最優(yōu)。粒子群優(yōu)化算法屬于一個(gè)的進(jìn)化的算法,是近年來(lái)發(fā)展起來(lái)的一種新的算法。該算法具有精度高、易于實(shí)現(xiàn)和收斂快的優(yōu)點(diǎn),在學(xué)術(shù)界顯示出解決實(shí)際問題的優(yōu)越性1)粒子群算法優(yōu)點(diǎn)算法原理簡(jiǎn)單,容易實(shí)現(xiàn);粒子間協(xié)同搜索,搜索策略是由群體全局信息和個(gè)體局部信息進(jìn)行指導(dǎo);算法不依

49、賴于問題信息,通用性比較強(qiáng);粒子群算法具有群體搜索和記憶的能力,能使種群和個(gè)體的最優(yōu)信息得到保留。2)粒子群算法缺點(diǎn)算法容易陷入局部最優(yōu),局部搜索能力比較差,且其搜索精度也不夠高;算法搜索性能對(duì)參數(shù)的依賴性較強(qiáng);算法理論還不完善,特別是在算法具體應(yīng)用時(shí)算法的設(shè)計(jì)缺少實(shí)用性指導(dǎo)原則。算法并不能保證一定得到全局最優(yōu)解,容易陷入局部極小解;(4)局部搜索算法局部搜索又稱鄰域搜索,它是一種迭代搜索技術(shù)在復(fù)雜函數(shù)優(yōu)化的過程中經(jīng)常采用,其基本原則是在當(dāng)前的解決方案所形成的鄰域解中不斷迭代和優(yōu)化設(shè)計(jì)的目標(biāo)函數(shù),使之逐漸成為更好解,直到在鄰近的領(lǐng)域內(nèi)找不到比當(dāng)前更好地解決方案為止。從最初的解決方案起,基于群體

50、功能在當(dāng)前解前提下,繼續(xù)搜索比它好解,如果能找到一個(gè)這樣的解決方案,則使它成為新解決方案,然后重復(fù)這個(gè)過程,如果沒有更好的終止搜索過程,當(dāng)前的解決方案為最終解決方案。鄰域搜索算法主要包括確定局部搜索方式和設(shè)計(jì)鄰域函數(shù)。函數(shù)優(yōu)化中有比較直觀的鄰域函數(shù)概念,最常用的方式是利用距離的概念通過附加擾動(dòng)來(lái)確定鄰域函數(shù)。鄰域函數(shù)的設(shè)計(jì)往往依賴于解的表達(dá)方式和問題的特性。對(duì)于鄰域函數(shù)的具體表現(xiàn)方式,組合優(yōu)化和函數(shù)優(yōu)化存在著明顯的差異。該算法的主要優(yōu)點(diǎn)是速度比較快、容易改進(jìn)、相應(yīng)的算法程序簡(jiǎn)單、容易實(shí)現(xiàn)、算法直觀。該算法的缺點(diǎn):算法的搜索性能完全依賴于初始解和鄰域函數(shù),如果初始值選取不合適或者是設(shè)計(jì)不當(dāng),則算法將會(huì)有非常差的最終性能;在搜索過程中可能出現(xiàn)早熟,即可能會(huì)出現(xiàn)陷入局部極小的情況。3.2.2算法比較對(duì)于前文介紹的各種算法的優(yōu)缺點(diǎn),下面進(jìn)行匯總,如表3-1所示。Tab 3-1 Algorithm contrast table操作難易搜索速度搜索性能搜索規(guī)模局部極小算法特點(diǎn)搜索特點(diǎn)存在早熟備注遺傳算法中等慢好較小低交叉,變異內(nèi)在平行性是算法基于遺傳和變異產(chǎn)生粒子群算法簡(jiǎn)單快好中等 高適應(yīng)度協(xié)同搜索算法有記憶性否算法理論不完善局部搜索算法簡(jiǎn)單快低小中初始解和臨域函數(shù)現(xiàn)