畢業(yè)論文----基于遺傳算法的車輛路徑問題研究

1、<p>　　基于遺傳算法的車輛路徑問題研究</p><p>　　中文摘要：近些年,物流作為“第三利潤源泉”受到國內(nèi)各行業(yè)的極大重視并得到較大的發(fā)展。物流的目標(biāo)就在于以最少的費(fèi)用滿足消費(fèi)者的需求。配送作為物流中一種特殊的、綜合的活動形式,在當(dāng)今社會經(jīng)濟(jì)發(fā)展中發(fā)揮著越來越重要的作用。配送的核心為配送車輛的調(diào)度、貨物配裝及送貨過程。進(jìn)行配送系統(tǒng)優(yōu)化,主要是配送車輛調(diào)度的優(yōu)化。對配送車輛進(jìn)行優(yōu)化調(diào)度,有利于提高

2、物流經(jīng)濟(jì)效益、實(shí)現(xiàn)物流科學(xué)化。本文主要對單車場非滿載無時(shí)間窗的車輛路徑問題和動態(tài)車輛路徑問題進(jìn)行了研究。論文首先對現(xiàn)有車輛優(yōu)化調(diào)度問題歸類分析。然后對車輛路徑問題的傳統(tǒng)求解算法的基本思想、性能、適用性進(jìn)行了分析,在此基礎(chǔ)上提出了采用掃描法和遺傳算法相結(jié)合的啟發(fā)式算法來求解物流配送車輛優(yōu)化調(diào)度問題的思想。在對遺傳算法中的選擇操作、鄰域結(jié)構(gòu)操作進(jìn)行改進(jìn)的基礎(chǔ)上,提出了一種求解車輛路徑問題的自適應(yīng)遺傳算法。應(yīng)用C語言編程進(jìn)行實(shí)例計(jì)算,結(jié)果表明

3、改進(jìn)的遺傳算法明顯增強(qiáng)了群體演化的質(zhì)量,提高了算法的收斂速度,得到了問題的滿意解。與傳統(tǒng)遺傳算法相比,掃描法和改進(jìn)遺傳算法的結(jié)合,其優(yōu)化能力、運(yùn)行效率、可靠性均有一定的提高。最后論文在對動態(tài)行駛時(shí)間車輛路徑問題進(jìn)行建模</p><p>　　關(guān)鍵詞：物流車輛路徑問題; 掃描法; 遺傳算法</p><p>　　Abstract:Recent years, logistics, taken as

4、 "the third profit resource", has been developing rapidly. The object of logistics is to satisfy the requirements of consumers with least cost. As an especial and integrated activity of logistics, physical dist

5、ribution plays an important role in modern society. Vehicle Routing Problem (VRP) is the main part of the distribution system optimizing. It is benefits to make economic benefits.This paper mainly studied a type of vehic

6、le routing problem with sing</p><p>　　Keyword: Vehicle Routing Problem; sweep method; genetic algorithm</p><p><b>　　1引言</b></p><p>　　車輛路徑問題（Vehicle Routing Problem，VRP）是

7、一類在物流配送調(diào)度中具有廣泛應(yīng)用的優(yōu)化組合問題，在現(xiàn)代物流中居于中心地位。 本文首先介紹了遺傳算法在解決簡單約束車輛路徑問題上的應(yīng)用，改進(jìn)了交叉算子，為研究有時(shí)間窗裝卸問題的遺傳算法作了充分準(zhǔn)備。本文詳細(xì)分析了有時(shí)間窗裝卸問題的數(shù)學(xué)模型，深入研究解決此問題的分組編碼遺傳算法，將禁忌思想用于產(chǎn)生可行解的啟發(fā)式插入搜索算法之中，并構(gòu)造出適用于多目標(biāo)的適應(yīng)度函數(shù)，設(shè)計(jì)新的數(shù)據(jù)結(jié)構(gòu)，對分組編碼遺傳算法進(jìn)行有效實(shí)現(xiàn)。</p><

8、;p>　　在分組編碼遺傳算法中提出路徑調(diào)整思想，設(shè)計(jì)出一種多策略分組編碼遺傳算法。采用多組通用算例測算，將多策略分組編碼遺傳算法與其它算法進(jìn)行比較，其求解結(jié)果和計(jì)算時(shí)間都有明顯改進(jìn)，驗(yàn)證了多策略分組編碼遺傳算法能夠有效穩(wěn)定地收斂到所求問題的解。VRP 最早由Dantzig 和Ramser 于1959 年提出，引起運(yùn)籌學(xué)、應(yīng)用數(shù)學(xué)、組合數(shù)學(xué)、圖論與網(wǎng)絡(luò)分析、物流科學(xué)、計(jì)算機(jī)應(yīng)用等學(xué)科研究人員的極大重視，成為運(yùn)籌學(xué)與組合優(yōu)化領(lǐng)域的熱點(diǎn)

9、問題。各國研究人員對該問題進(jìn)行了大量的理論研究及實(shí)驗(yàn)分析，取得了重大進(jìn)展，</p><p>　　其研究成果在運(yùn)輸系統(tǒng)、公交車輛路線設(shè)計(jì)、快遞收發(fā)系統(tǒng)、物資調(diào)配系統(tǒng)中都已得到了廣泛應(yīng)用。</p><p>　　研究車輛路徑問題的特點(diǎn)及算法具有重要的實(shí)際意義。本文重點(diǎn)研究解決有時(shí)間窗裝卸問題（PDPTW）的遺傳算法，作為前期準(zhǔn)備，本文作者對遺傳算法解決具有簡單約束條件的VRP（包括有容量約束的車

10、輛路徑問題CVRP 和有時(shí)間窗的車輛路徑問題VRPTW）進(jìn)行了初步研究。有容量約束的車輛路徑問題（Capacitated Vehicle routing problem，CVRP）是由一個(gè)服務(wù)中心（或車場）的若干車輛向多個(gè)客戶點(diǎn)進(jìn)行配送服務(wù)，在已知待服務(wù)客戶點(diǎn)和出發(fā)點(diǎn)的位置、客戶需求及車輛最大負(fù)載的前提下，設(shè)計(jì)車輛配送路徑，規(guī)劃設(shè)計(jì)方案，使運(yùn)輸成本最小化，即總代價(jià)最?。ㄊ褂密囕v盡量少，行車總距離盡量短）。CVRP 實(shí)際是多目標(biāo)組合優(yōu)化問

11、題，一般以派出車輛最少（運(yùn)輸路線條數(shù)最少）為首要目標(biāo)，行車總距離最短，即總代價(jià)最小為次要目標(biāo)。CVRP 要求滿足以下條件及假設(shè)：</p><p>　?。?）所有的配送車輛以配送中心為起點(diǎn)并最終回到配送中心；</p><p>　?。?）每條配送路徑上各客戶點(diǎn)的需求量之和不超過車輛的負(fù)載量；</p><p>　?。?）每個(gè)客戶點(diǎn)的需求僅由一輛車一次滿足。</p&g

12、t;<p><b>　　2選題的目的</b></p><p>　　物流已被認(rèn)為是繼降低原材料消耗和提高勞動生產(chǎn)率之后的“第三利潤源”。通過優(yōu)化物流系統(tǒng),可以降低物流成本,從而增強(qiáng)企業(yè)的市場競爭能力。因此,研究物流系統(tǒng)中的優(yōu)化問題,具有十分重要的意義,是國內(nèi)外研究的一個(gè)熱點(diǎn)。 庫存成本與配送成本是物流系統(tǒng)的核心成本,在物流總成本中占據(jù)了很大的比例。如果能降低庫存成本與配送成本,就

13、能有效地降低物流成本。 遺傳算法是一種應(yīng)用很廣泛的智能優(yōu)化算法,本文對遺傳算法進(jìn)行了分析研究,針對遺傳算法的一些缺陷提出了相應(yīng)的改進(jìn)方法。在上述研究基礎(chǔ)上,本文基于遺傳算法,研究了物流系統(tǒng)中的庫存優(yōu)化問題及車輛路徑問題。本文將庫存仿真優(yōu)化問題與車輛路徑問題都看作是組合優(yōu)化問題,并應(yīng)用遺傳算法進(jìn)行求解。 本文的主要研究工作及貢獻(xiàn)可歸納如下: (1)對隨機(jī)庫存系統(tǒng)建立了基于離散事件系統(tǒng)的計(jì)算機(jī)仿真模型。用系統(tǒng)仿真方法求解最優(yōu)庫存策略時(shí),其難

14、點(diǎn)之一在于仿真的優(yōu)化。為此,本文將計(jì)算機(jī)仿真技術(shù)和遺傳算法相結(jié)合,應(yīng)用遺傳算法來優(yōu)化模型的控制參數(shù),即獲得最優(yōu)的庫存控制策略。針對隨機(jī)系統(tǒng)的特點(diǎn),設(shè)計(jì)了候選解收集器,它能夠收集在仿真優(yōu)化過程中產(chǎn)生的Pareto解;提出了M精英選擇算子,用于保護(hù)潛</p><p><b>　　3 問題描述</b></p><p>　　3.1車輛路徑問題定義</p><

15、;p>　　車輛路線問題（VRP）最早是由Dantzig和Ramser于1959年首次提出，它是指一定數(shù)量的客戶，各自有不同數(shù)量的貨物需求，配送中心向客戶提供貨物，由一個(gè)車隊(duì)負(fù)責(zé)分送貨物，組織適當(dāng)?shù)男熊嚶肪€，目標(biāo)是使得客戶的需求得到滿足，并能在一定的約束下，達(dá)到諸如路程最短、成本最小、耗費(fèi)時(shí)間最少等目的。 由此定義不難看出，旅行商問題（Traveling Saleman Problem,TSP）是VRP的特例，由于Gaer

16、y。已證明TSP問題是NP難題，因此，VRP也屬于NP難題。 車輛路線問題自1959年提出以來，一直是網(wǎng)絡(luò)優(yōu)化問題中最基本的問題之一，由于其應(yīng)用的廣泛性和經(jīng)濟(jì)上的重大價(jià)值，一直受到國內(nèi)外學(xué)者的廣泛關(guān)注。車輛路線問題可以描述如下（如圖1）： </p><p><b>　　圖1 路徑問題描述</b></p><p>　　設(shè)有一場站（depot），共有M 輛貨車，車輛容量為

17、Q，有N位顧客（customer），每位顧客有其需求量D。車輛從場站出發(fā)對客戶進(jìn)行配送服務(wù)最后返回場站，要求所有顧客都被配送，每位顧客一次配送完成，且不能違反車輛容量的限制，目的是所有車輛路線的總距離最小。車輛路線的實(shí)際問題包括配送中心配送、公共汽車路線制定、信件和報(bào)紙投遞、航空和鐵路時(shí)間表安排、工業(yè)廢品收集等。</p><p>　　3.2 車輛路徑問題的類型</p><p>　　一般而言

18、車輛路線問題大致可以分為以下三種類型（Ballou，1992）： </p><p>　　1、相異的單一起點(diǎn)和單一終點(diǎn)。 </p><p>　　2、相同的單一起點(diǎn)和終點(diǎn)。 </p><p>　　3、多個(gè)起點(diǎn)和終點(diǎn)。 </p><p>　　3.3 車輛路線問題研究現(xiàn)狀</p><p>　　經(jīng)過幾十年的研究發(fā)展，車輛路線問題

19、研究取得了大量成果。下面從車輛路線問題的現(xiàn)有研究型態(tài)和求解方法兩個(gè)方面介紹車輛路線問題的研究現(xiàn)狀。</p><p>　　3.3.1車輛路線問題型態(tài)</p><p>　　在基本車輛路線問題（VRP）的基礎(chǔ)上，車輛路線問題在學(xué)術(shù)研究和實(shí)際應(yīng)用上產(chǎn)生了許多不同的延伸和變化型態(tài)，包括時(shí)窗限制車輛路線問題（vehicle routing problems with time windows，VRPT

20、W）、追求最佳服務(wù)時(shí)間的車輛路線問題（VRPDT）、多車種車輛路線問題（fleet size and mix vehicle routing problems，F(xiàn)SVRP）、車輛多次使用的車輛路線問題（vehicle routingproblems with multiple use of vehicle，VRPM）、考慮收集的車輛路線問題（vehicle routingproblems with backhauls，VRPB）、隨機(jī)需

21、求車輛路線問題（vehicle routing problem with stochastic demand，VRPSD）等。 </p><p><b>　　3.3.2解決方法</b></p><p>　　1、求解方法演進(jìn) 綜合過去有關(guān)車輛路線問題的求解方法，可以分為精確算法（exact algorithm）與啟發(fā)式解法（heuristics），其中精密算法有分支界

22、限法、分支切割法、集合涵蓋法等；啟發(fā)式解法有節(jié)約法、模擬退火法、確定性退火法、禁忌搜尋法、基因算法、神經(jīng)網(wǎng)絡(luò)、螞蟻殖民算法等。1995年，F(xiàn)isher曾將求解車輛路線問題的算法分成三個(gè)階段。第一階段是從1960年到1970年，屬于簡單啟發(fā)式方式，包括有各種局部改善啟發(fā)式算法和貪婪法（Greedy）等；第二階段是從1970年到1980年，屬于一種以數(shù)學(xué)規(guī)劃為主的啟發(fā)式解法，包括指派法、集合分割法和集合涵蓋法；第三階段是從1990開始至今，

23、屬于較新的方法，包括利用嚴(yán)謹(jǐn)啟發(fā)式方法、人工智能方法等。 </p><p>　　2、啟發(fā)式算法 由于VRP是NP-hard問題，難以用精確算發(fā)求解，啟發(fā)式算法是求解車輛運(yùn)輸問題的主要方法，多年來許多學(xué)者對車輛運(yùn)輸問題進(jìn)行了研究，提出了各種各樣的啟發(fā)式方法。車輛運(yùn)輸問題的啟發(fā)式方法可以分為簡單啟發(fā)式算法、兩階段啟發(fā)式算法、人工智能方法建立的啟發(fā)式方法。 </p><p>　　簡單啟發(fā)式方法

24、包括節(jié)省法或插入法、路線內(nèi)/間節(jié)點(diǎn)交換法、貪婪法和局部搜索法等方法。節(jié)省法或插入法（savings or insertion）是在求解過程中使用節(jié)省成本最大的可行方式構(gòu)造路線，直到無法節(jié)省為止。交換法則是依賴其他方法產(chǎn)生一個(gè)起始路線，然后以迭代的方式利用交換改善法減少路線距離，直到不能改善為止。1960年，Clarke和Wrigh首先提出一種啟發(fā)式節(jié)省法（savings methods）來建立車隊(duì)配送路線。簡單啟發(fā)式方法簡單易懂、求解速

25、度快，但只適合求解小型、簡單的VRP問題。 </p><p>　　兩階段方法包括先分組后定路線（clusterfirst-route second）和先定路線后分組（routefirst-cluster second）兩種啟發(fā)式策略。前者是先將所有需求點(diǎn)大略分為幾個(gè)組，然后再對各個(gè)組分別進(jìn)行路線排序；后者則是先將所有的需求點(diǎn)建構(gòu)成一條路線，再根據(jù)車輛的容量將這一路線分割成許多適合的單獨(dú)路線。 </p>

26、<p>　　1990年以來，人工智能方法在解決組合優(yōu)化問題上顯示出強(qiáng)大功能，在各個(gè)領(lǐng)域得到充分應(yīng)用，很多學(xué)者也將人工智能引入車輛路線問題的求解中，并構(gòu)造了大量的基于人工智能的啟發(fā)式算法。禁忌搜索法（TS）基本上是屬于一種人工智能型（AI）的局部搜尋方法，Willard首先將此算法用來求解VRP ，隨后亦有許多位學(xué)者也發(fā)表了求解VRP的TS 算法。西南交通大學(xué)的袁慶達(dá)等設(shè)計(jì)了考慮時(shí)間窗口和不同車輛類型的禁忌算法，這種算法主要

27、采用GENIUS方法產(chǎn)生初始解，然后禁忌算法對初始解優(yōu)化。模擬退火方法具有收斂速度快，全局搜索的特點(diǎn)，Osman對VRP的模擬退火算法進(jìn)行了研究，他提出的模擬退火方法主要適合于解決路線分組。遺傳算法具有求解組合優(yōu)化問題的良好特性，Holland首先采用遺傳算法（GA）編碼解決VRPTW 問題?，F(xiàn)在多數(shù)學(xué)者采用混合策略，分別采用兩種人工智能方法進(jìn)行路線分組和路線優(yōu)化。Ombuk提出了用遺傳算法進(jìn)行路線分組，然后用禁忌搜索方法進(jìn)行路線優(yōu)化的

28、混合算法。Bent和Van Hentenryck則首先用模擬退火算法將車輛路線的數(shù)量最小化，然后用大鄰域搜索法（largneighborhood </p><p>　　總結(jié)幾種人工智能方法可以看出，TS算法所得到的解最接近最優(yōu)解，但其運(yùn)算時(shí)間也最長，是GA算法的2～3倍，SA算法的近20倍；由于GA算法也能較好的逼近最優(yōu)解，同時(shí)使運(yùn)算時(shí)間大大縮短，所以GA算法能兼顧運(yùn)算時(shí)間和效率兩方面，是具有較好的發(fā)展前途的方法

29、；SA算法求解速度非常快，也能提供一定程度上的優(yōu)化方案在求解較小規(guī)模問題上具有較好效果。 </p><p><b>　　4 遺傳算法介紹</b></p><p>　　遺傳算法簡稱 GA(Genetic Algorithm)，在本質(zhì)上是一種不依賴具體問題的直接搜索方法。它是根據(jù)生物進(jìn)化思想而啟發(fā)得出的一種全局優(yōu)化算法。遺傳算法的概念最早是由Bagley J.D 在196

30、7 年提出的；而開始遺傳算法的理論和方法的系統(tǒng)性研究的是1975 年，這一開創(chuàng)性工作是由Michigan 大學(xué)的J.H. Holland 所實(shí)行。當(dāng)時(shí)，其主要目的是說明自然和人工系統(tǒng)的自適應(yīng)過程。</p><p>　　遺傳算法是受生物進(jìn)化學(xué)說和遺傳學(xué)說啟發(fā)而發(fā)展起來的，基于適者生存思想的一種較通用的問題求解方法。利用遺傳算法進(jìn)行尋優(yōu)時(shí)，編碼、選擇、交叉、變異是四個(gè)重要步驟。遺傳算法作為一種全局優(yōu)化搜索方法，具有簡

31、單、通用普適性強(qiáng)，適用于并行處理和應(yīng)用范圍廣等優(yōu)點(diǎn)。遺傳算法在優(yōu)化領(lǐng)域表現(xiàn)出了其強(qiáng)大的能力，遺傳算法仿照生物進(jìn)化和遺傳的規(guī)律，利用復(fù)制、交換和突變等操作，使優(yōu)勝者繁殖，劣敗者消失，一代代重復(fù)同樣的操作，最終找出最優(yōu)解。具有如下特點(diǎn)：(1) 遺傳算法運(yùn)算的是解集的編碼，而不是解集本身；(2) 遺傳算法的搜索始于解的一個(gè)種群，而不是單個(gè)解；(3) 遺傳算法只使用報(bào)酬信息（適值函數(shù)），不使用導(dǎo)數(shù)或其他輔助知識；(4) 遺傳算法采用概率

32、的，而不是確定的狀態(tài)轉(zhuǎn)移規(guī)則。 遺傳算法特別適用于傳統(tǒng)搜索方法難以解決的復(fù)雜的和非線性的問題，可廣泛用于組合優(yōu)化、自適應(yīng)控制、規(guī)劃設(shè)計(jì)和人工生命等領(lǐng)域。作為一種隨機(jī)優(yōu)化技術(shù)在解優(yōu)化問題中顯示了優(yōu)于傳統(tǒng)優(yōu)化算法的性能，遺傳算法的一個(gè)顯著優(yōu)勢是不需要目標(biāo)函數(shù)明確的數(shù)學(xué)方程和導(dǎo)數(shù)表達(dá)式，同時(shí)又是一種全局尋優(yōu)算法，不會象某些傳統(tǒng)算法易于陷入局部最優(yōu)解。 </p><p><b>　　1)參數(shù)編碼；

33、</b></p><p>　　2)初始群體的設(shè)定；</p><p>　　3)適應(yīng)度函數(shù)的設(shè)計(jì)；</p><p><b>　　4)遺傳操作設(shè)計(jì)；</b></p><p>　　5）控制參數(shù)設(shè)定(主要是指群體大小和使用遺傳操作的概率等)。</p><p>　　這5個(gè)要素構(gòu)成了遺傳算法的核心內(nèi)

34、容。</p><p>　　4.1 遺傳算法的基本思想</p><p>　　遺傳算法是受生物進(jìn)化學(xué)說和遺傳學(xué)說啟發(fā)而發(fā)展起來的，基于適者生存思想的一種較通用的問題求解方法。利用遺傳算法進(jìn)行尋優(yōu)時(shí)，編碼、選擇、交叉、變異是四個(gè)重要步驟。遺傳算法作為一種全局優(yōu)化搜索方法，具有簡單、通用普適性強(qiáng)，適用于并行處理和應(yīng)用范圍廣等優(yōu)點(diǎn)。遺傳算法在優(yōu)化領(lǐng)域表現(xiàn)出了其強(qiáng)大的能力，遺傳算法仿照生物進(jìn)化和遺傳的

35、規(guī)律，利用復(fù)制、交換和突變等操作，使優(yōu)勝者繁殖，劣敗者消失，一代代重復(fù)同樣的操作，最終找出最優(yōu)解。具有如下特點(diǎn)：(1) 遺傳算法運(yùn)算的是解集的編碼，而不是解集本身；(2) 遺傳算法的搜索始于解的一個(gè)種群，而不是單個(gè)解；(3) 遺傳算法只使用報(bào)酬信息（適值函數(shù)），不使用導(dǎo)數(shù)或其他輔助知識；(4) 遺傳算法采用概率的，而不是確定的狀態(tài)轉(zhuǎn)移規(guī)則。</p><p>　　4.2 遺傳算法流程圖</p>

36、<p>　　圖2 遺傳算法流程圖</p><p>　　5 模型建立求解及實(shí)例應(yīng)用</p><p><b>　　5.1車輛調(diào)度模型</b></p><p>　　根據(jù)上述對問題的描述，可以采用混合整數(shù)規(guī)劃方法對車輛調(diào)度進(jìn)行建模"設(shè)N為最小成本，則目標(biāo)函數(shù)為</p><p><b>　　滿足約束

37、條件1：</b></p><p>　　式中：K為所有車輛的集合， ；G為所有客戶的集合， </p><p>　　， ，其中{0}代表配送中心； 為由車輛k服務(wù)的客戶的集合； 為車輛到達(dá)客戶i的時(shí)間；為懲罰函數(shù)，車輛在時(shí)間 到達(dá)客戶i時(shí)所對應(yīng)的懲罰成本；為車輛從客戶i到客戶j的所有運(yùn)輸成本；為車輛從客戶i到客戶

38、j的行車時(shí)間；為客戶i的需求量；Q為車輛k的最大裝載量；為車輛在客戶i處的停留的時(shí)間。</p><p>　　另外，變量和的值為0或1。若車輛k為客戶i服務(wù)，則1，否則為0，即：此變量表示車輛分配方案，可用布爾矩陣表示；若車輛k經(jīng)由客戶i到客戶j，則為1，否則為0，即：，表示車輛路線安排。</p><p>　　約束條件2：保證每個(gè)客戶均被服務(wù)，而且每輛車都從配送中心出發(fā)；</p>

39、<p>　　約束條件3：表示每輛車負(fù)責(zé)的客戶點(diǎn)的貨物需求量總和不超過該車輛的最大裝載量；</p><p>　　約束條件4、5：表示對任一由k服務(wù)的客戶點(diǎn)j必定有另一(而且只有一個(gè))由k服務(wù)的客戶點(diǎn)(包括配送中心)I,車輛k從客戶點(diǎn)i到達(dá)客戶點(diǎn)j,而對由k服務(wù)的客戶點(diǎn)i同樣存在由k服務(wù)的另一客戶點(diǎn),車輛k是從該客戶點(diǎn)到達(dá)客戶點(diǎn)i的,依次類推；</p><p>　　約束條件6：保

40、證每輛車的行車路線的總耗時(shí)不超過一個(gè)事先定下的數(shù)值；</p><p>　　約束條件7：對某個(gè)客戶點(diǎn)，車輛到達(dá)時(shí)間限制在某一時(shí)間段內(nèi)。</p><p>　　根據(jù)實(shí)際情況，本文采用軟限制時(shí)間窗，其懲罰函數(shù)如圖2所示。其中，為客戶所要求的送貨時(shí)區(qū)，為時(shí)間窗，超過該范圍客戶將拒絕收貨，因此設(shè)定一個(gè)極大的懲罰成本以避免此情況的發(fā)生。</p><p><b>　　圖3

41、 懲罰函數(shù)</b></p><p>　　5.2 帶時(shí)間窗的物流配送問題優(yōu)化問題</p><p>　　帶時(shí)間窗 VRP（VRP with Time Windows，VRPTW）是帶裝載能力約束的CVRP(Capacitated VRP，CVRP)的擴(kuò)展。在該類問題中，有車輛裝載能力約束，且每個(gè)客戶i 都有一個(gè)與之相聯(lián)系的時(shí)間區(qū)間[ai ,bi]，稱為時(shí)間窗?？蛻舻姆?wù)必須在相應(yīng)的

42、時(shí)間窗內(nèi)開始，車輛必須在客戶點(diǎn)停留的時(shí)間長度為si。按客戶對物流中心違反時(shí)間窗約束規(guī)定時(shí)的接受程度，可分為硬時(shí)間窗、軟時(shí)間窗和混合型時(shí)間窗。硬時(shí)間窗(Hard Time Windows)：指配送車輛必須在特定時(shí)間區(qū)段，將貨物送達(dá)顧客手中，不論是遲到或早到都完全不予接受；軟時(shí)間窗(Soft Time Windows)：允許服務(wù)的開始時(shí)間有所偏離時(shí)間窗，則必須按照違反時(shí)間的長短施以一定的罰金或其他懲罰法則；混合型時(shí)間窗（Mixed Time

43、 Windows）：是指系統(tǒng)中有些客戶只接受硬時(shí)間窗服務(wù)，有些客戶接受軟時(shí)間窗服務(wù)，或者同一客戶，往往軟、硬兩種時(shí)間窗服務(wù)混合使用。</p><p>　　如問題為硬時(shí)間窗問題，則必須滿足到客戶i 的時(shí)間要比承諾到達(dá)時(shí)間早，即到達(dá)i 的時(shí)間≤到達(dá)i 的最晚時(shí)間限制；</p><p>　　如有緊急貨物（高優(yōu)先級客戶）時(shí)，則自動將優(yōu)先級高的貨物按優(yōu)先級順序排入隊(duì)列前端，然后將其它普通貨物再進(jìn)行優(yōu)

44、化；即如有N 個(gè)客戶，其中有一個(gè)為緊急運(yùn)單，則自動將其放在隊(duì)首，其他N-1 個(gè)客戶進(jìn)行優(yōu)化，即將問題降為N-1 階的路徑優(yōu)化問題；</p><p>　　任一客戶只由一臺運(yùn)輸車輛提供服務(wù)，即算法解決的是任一客戶的貨物需求均小于車輛最大負(fù)載（容積）的情況。如出現(xiàn)某客戶需求量大于車輛負(fù)載（容積）的情況時(shí)，需要先派車為其運(yùn)輸，直至該客戶剩余貨物需求量小于車輛最大負(fù)載（容積）即可參加優(yōu)化調(diào)度。</p><

45、;p>　　5.3帶時(shí)間窗的物流配送路徑問題的遺傳算法</p><p>　　5.3.1染色體結(jié)構(gòu)編碼</p><p>　　根據(jù)物流配送路徑優(yōu)化問題的特點(diǎn)，本文采用了簡單直觀的自然數(shù)編碼方法，用0表示配送中心，用1、2、…、L 表示各需求點(diǎn)。由于在配送中心有m 輛汽車，則最多存在m 條配送路徑，每條配送路徑都始于配送中心，也終于配送中心。為了在編碼中反映車輛配送的路徑，采用了增加m－1

46、個(gè)虛擬配送中心的方法，分別用L＋1、L＋2、…、L＋K－l 表示。這樣，l、2、…、L＋m－l 這L＋m－l 個(gè)互不重復(fù)的自然數(shù)的隨機(jī)排列就構(gòu)成一個(gè)個(gè)體，并對應(yīng)一種配送路徑方案。例如，對于一個(gè)有6 個(gè)需求點(diǎn)，用2 輛汽車完成配送任務(wù)的問題，</p><p>　　則可用0、2、…、6 (0 表示配送中心)這7 個(gè)自然數(shù)的隨機(jī)排列表示物流配送路徑方案。如個(gè)體0l26354 表示的配送路徑方案為：路徑1：0-1-2-6

47、，路徑2：3-5-4共有2條配送路徑；</p><p>　　5.3.2 種群的初始化</p><p>　　群體初始化時(shí)，采用兩種機(jī)制，一種是隨機(jī)生成個(gè)體，一種是按前相插入啟發(fā)式算法。本文采用隨機(jī)產(chǎn)生一種l～L＋m－l 這L＋m－l 個(gè)互不重復(fù)的自然數(shù)的排列，即形成一個(gè)個(gè)體。設(shè)群體規(guī)模為M，則通過隨機(jī)產(chǎn)生M 個(gè)這樣的個(gè)體，即形成初始群體。</p><p>　　5.3.

48、3 適應(yīng)度分析</p><p>　　初始種群形成以后，需要通過種群的適應(yīng)度函數(shù)，對種群中的每個(gè)染色體進(jìn)評價(jià)，并以此為標(biāo)準(zhǔn)選擇最優(yōu)解。由于適應(yīng)度函數(shù)通常越大越好，而物流車輛路徑優(yōu)化問題則是求最小經(jīng)濟(jì)成本，為了便于計(jì)算且增大區(qū)分度，算法采用的是目標(biāo)函數(shù)的倒數(shù)乘以區(qū)分度系數(shù)β作為適應(yīng)度函數(shù)，即</p><p>　　maxF = 1 / S * β (3-2-3-1)</p><

49、;p>　　5.3.4 遺傳算子</p><p><b>　　1. 遺傳選擇</b></p><p>　　選擇是用來確定重組或交叉?zhèn)€體，以及被選個(gè)體將產(chǎn)生多少個(gè)子代個(gè)體。新種群的產(chǎn)生是在上一代的基礎(chǔ)上對原有的各染色體按其適應(yīng)度大小進(jìn)行保留，并將其進(jìn)行交叉和變異形成新一代的個(gè)體；適應(yīng)度計(jì)算之后是實(shí)際的選擇，按照適應(yīng)度進(jìn)行父代個(gè)體的選擇，本文由輪盤賭算法進(jìn)行種子的選取

50、；計(jì)算每個(gè)個(gè)體的相對適應(yīng)度值，以之作為概率，將[0,1]空間劃分成n 份。生成一個(gè)[0,1]范圍內(nèi)的隨機(jī)數(shù)，看它落在哪個(gè)區(qū)域，則選擇該個(gè)體。</p><p>　　2. 遺傳基因的交叉</p><p>　　對通過選擇操作產(chǎn)生的新群體，需要進(jìn)行配對交叉重組。簡單的說就是人為選取較好的一對染色體作為新染色體的父母，按染色體按長度分為前后兩段，取其中一個(gè)染色體的前半部分放在另一個(gè)染色體的前邊，再順

51、序遍歷新染色體的基因并剔除重復(fù)基因，從而得到新的染色體child1。同理，可以得到另一個(gè)新染色體child2。在得到新的兩個(gè)染色體后，為了使下一代染色體具有更高的適應(yīng)度，算法加入了淘汰機(jī)制，即比較兩個(gè)新染色體，保留較好的一個(gè)進(jìn)入下一代，同時(shí)將較差的一個(gè)舍棄。在此引入新的 CX 交叉算子。實(shí)施交叉操作。其操作方法如下：首先，隨機(jī)在父代染色體中選擇一個(gè)交配區(qū)域，如兩個(gè)父代染色體及交配區(qū)域選定為：</p><p>　　

52、A=3 5|6 2 9 8|4 7 1</p><p>　　B=8 3|2 9 5 4|1 6 7</p><p>　　其次，將B 的交配區(qū)域加到A 的前面，A 的交配區(qū)域加到B 的前面，得到：</p><p>　　'A=2 9 5 4|3 5 6 2 9 8 4 7 1</p><p>　　'B=6 2 9 8|8 3 2

53、9 5 4 1 6 7</p><p>　　最后在'A， 'B 中自交配區(qū)域后依次刪除與交配區(qū)域相同的自然數(shù)，得到最終的兩個(gè)后代：</p><p>　　C1=2 9 5 4 3 6 8 7 1</p><p>　　C2=6 2 9 8 3 8 4 1 7</p><p>　　3. 遺傳基因的變異</p><

54、p>　　基因的變異是在選出的染色體中按其變異概率隨機(jī)找出若干基因位置，再隨機(jī)產(chǎn)生一個(gè)基因替換原有位置基因，并查找因替換基因產(chǎn)生的此基因的另一重復(fù)位置，修改使之成為一個(gè)不重復(fù)基因染色體。為了使后代繼承更多的父代的基因信息，本文取變異概率Pm 為0.02 左右。</p><p>　　5.3.5 函數(shù)控制的終止條件</p><p>　　優(yōu)化算法的結(jié)束條件是系統(tǒng)設(shè)定的最大遺傳代數(shù)。即事先設(shè)置

55、一個(gè)最大代數(shù)，如當(dāng)前代數(shù)大于最大代數(shù)時(shí)，算法停止。判斷迭代的代數(shù)是否為要求代數(shù)maxt，若是，停止進(jìn)化，選性能最好的染色體所對應(yīng)的路徑集合，作為問題的優(yōu)化解輸出。</p><p><b>　　5.3.6 步驟</b></p><p>　　Step1：t=0，利用自然數(shù)編碼方式，采用前相插入啟發(fā)式算法和隨機(jī)的方式產(chǎn)生初始種群，并輸入控制參數(shù)；</p>&l

56、t;p>　　Step2：計(jì)算個(gè)體適應(yīng)度；</p><p>　　Step3：t <maxt，t=t+1，則轉(zhuǎn)Step4；否則停止計(jì)算，并輸出結(jié)果；</p><p>　　Step4：采用基于個(gè)體濃度的群體多樣性保持策略來選擇個(gè)體；</p><p>　　Step5：對個(gè)體進(jìn)行CX 交叉重組；</p><p>　　Step6：按照變異方法

57、對個(gè)體進(jìn)行變異；</p><p>　　Step7：重復(fù)步驟2-6；</p><p><b>　　6算法的建立和求解</b></p><p>　　車輛優(yōu)化調(diào)度問題由車輛分配和路線安排這兩個(gè)相互關(guān)聯(lián)的子問題組成，但關(guān)鍵是確定優(yōu)化的車輛分配方案（即求解變量）。一旦車輛分配方案確定，那么路線安排問題也就比較容易求解（即求解變量）?？梢圆捎眠z傳算法的思想

58、作為總體框架對該問題進(jìn)行求解，用遺傳算法求解變量，而變量則用啟發(fā)式算法求解。</p><p><b>　　6.1編碼操作</b></p><p>　　遺傳算法的關(guān)鍵之一是確定染色體并對它進(jìn)行編碼處理。對于車輛調(diào)度問題，可將求解變量看作染色體，因此，一條染色體就代表一種可能的車輛分配方案，然后可用布爾矩陣對該染色體的基因鏈進(jìn)行編碼。對于m輛車、n個(gè)客戶的車輛分配,可表示

59、成mn矩陣。例如，圖1的布爾矩陣為</p><p>　　即車輛1負(fù)責(zé)客戶1和2，車輛2負(fù)責(zé)客戶3、4和5.</p><p>　　6.2定義適配值計(jì)算函數(shù)</p><p>　　適應(yīng)度函數(shù)是遺傳算法中評價(jià)解集好壞的依據(jù),適配值高的個(gè)體優(yōu)先培養(yǎng)。在本問題中，對于種群數(shù)目為N的染色體群，其個(gè)體染色體i的適配值的值越小,則表示個(gè)體適配值越高。個(gè)體適配值為</p>

60、<p>　　式中，所以，目標(biāo)函數(shù)</p><p><b>　　生成初始染色體種群</b></p><p>　　初始化遺傳世代；每一代的染色體群的種群數(shù)目；交叉概率，變異概率 等參數(shù)。隨機(jī)產(chǎn)生初始車輛分配方案，并淘汰不符合約束條件的染色體,直到染色體群的種群數(shù)達(dá)N條。N的取值不宜過大或過小。過大不但增加計(jì)算量，而且不能有效地獲得迭代解。過小將不能保證分

61、配方案的多樣性，本算法中取種群大小，交叉概率,變異概。</p><p>　　6.3用啟發(fā)式算法求解單一車輛排序問題</p><p>　　對變量的求解實(shí)質(zhì)上是一個(gè)帶時(shí)間約束的單一車輛排序問題，即對中的元素進(jìn)行排序，求解最小的，以滿足約束條件。該子問題可表示為</p><p><b>　　滿足約束條件：</b></p><p&g

62、t;　　本文采用文獻(xiàn)[3]中的啟發(fā)式方法進(jìn)行求解。首先對中的元素按照客戶要求到達(dá)的時(shí)間從小到大進(jìn)行排序，如果有兩個(gè)以上的客戶要求到達(dá)的時(shí)間相同，則對這些客戶按照配送區(qū)域（時(shí)區(qū)）從小到大進(jìn)行排序。淘汰不符合約束條件的解，調(diào)整次序重新搜索，直到找到較佳的可行解為止。對每一條染色體，求解變量，并計(jì)算每一條染色體的適配值：</p><p><b>　　!</b></p><p&g

63、t;　　6.4種群的選擇與復(fù)制</p><p>　　本算法采用與適配值成比例的概率方法，對種群的個(gè)體進(jìn)行選擇與復(fù)制。首先根據(jù)前面計(jì)算的計(jì)算個(gè)體i在下一代中應(yīng)復(fù)制自身的比例；定義選擇概率為個(gè)體適配值所占比例的反向排序$即適配值最小的車輛分配方案其選擇概率最大；依據(jù)選擇概率對種群中的個(gè)體進(jìn)行復(fù)制，選擇概率大的個(gè)體被重復(fù)復(fù)制的機(jī)會大，而選擇概率小的個(gè)體則趨向于減少或淘汰，直到復(fù)制N條染色體。</p>&l

64、t;p><b>　　6.5交叉操作</b></p><p>　　由于復(fù)制操作并沒有產(chǎn)生新的車輛分配方案，因此種群中最好的個(gè)體的適配值并沒有降低。對染色體群實(shí)施交叉操作crossover（）可以產(chǎn)生新的體。以概率對染色體群隨機(jī)地交換兩個(gè)個(gè)體的某些片段產(chǎn)生新的個(gè)體染色體，即對選定的需進(jìn)行交叉運(yùn)算的每一組布爾矩陣隨機(jī)設(shè)定交叉位置$通過交換布爾矩陣中的某些行或列的部分信息（二進(jìn)制位），其他位不

65、變，從而生成兩個(gè)新的布爾矩陣。交叉概率對算法的收斂有較大的影響，越大，優(yōu)秀的個(gè)體出現(xiàn)的幾率也越大，新舊個(gè)體替換快，算法收斂也快。的經(jīng)驗(yàn)值為,0.25~1.000.75效果較佳。</p><p><b>　　6.6變異操作</b></p><p>　　變異操作mutation（）以概率對染色體群中的某些染色體的某些位進(jìn)行變異，產(chǎn)生新的個(gè)體染色體、作為交叉運(yùn)算的補(bǔ)充，變異

66、操作可增加車輛分配方案的多樣性，克服求解可能出現(xiàn)的早熟和陷入局部最優(yōu)解的現(xiàn)象。變異概率取不同的值對算法性能的影響很大；過大，求解時(shí)間明顯增加$但算法收斂于局部最優(yōu)的可能性減少。本文中，取,0.3變異操作mutation（）采用反順序變異法改變布爾矩陣中的某些位（1變成0,0變成1），產(chǎn)生新的布爾矩陣。算法停止準(zhǔn)則的設(shè)計(jì)淘汰不符合約束條件2）、3）的染色體。如果，則轉(zhuǎn)啟發(fā)式算法求解，否則在染色體群中選擇最小的染色體，作為該問題的求解變量值

67、；與該變量相對應(yīng)的變量就是優(yōu)化的路線安排。由于該算法屬于種群非重疊&遺傳操作重疊結(jié)構(gòu)的SGA(simple genetic algorithm),并在選擇操作前保留當(dāng)前最好解:因此以概率收斂到全局最優(yōu)解。</p><p><b>　　6.7 實(shí)例分析</b></p><p>　　本文仍采用的經(jīng)典測試集。用上述的帶時(shí)間窗的遺傳算法，對一個(gè)有8 個(gè)客戶和1個(gè)配送中

68、心，兩輛車（容量均為8 噸）的配送系統(tǒng)的車輛路徑問題進(jìn)行求解。已知各客戶的需求和各客戶之間的距離如表 1(其中0 表示配送中心)，要求合理安排車輛的行駛路線，使總的運(yùn)距最短。</p><p><b>　　表1客戶間距離表</b></p><p>　　設(shè)置車輛數(shù)為 3，最大負(fù)載10，車輛容積30，最大行駛距離為200，運(yùn)輸成本系數(shù)4，平均時(shí)速為40，不考慮裝卸及休息時(shí)間

69、。種群設(shè)為40，最大代數(shù)為400，運(yùn)輸成本參數(shù)設(shè)為3，時(shí)間懲罰參數(shù)設(shè)為6，并且第4 次及第7 次實(shí)驗(yàn)中人為設(shè)置較高變異率（分別為0.089和0.100）,以達(dá)到人為增加變異次數(shù)避免局部最優(yōu)解的出現(xiàn)，共進(jìn)行了八次運(yùn)算，得到測試結(jié)果如下：</p><p><b>　　表2優(yōu)化結(jié)果表</b></p><p>　　最終優(yōu)化結(jié)果為需要調(diào)度兩臺車，得到的優(yōu)化路徑為O-A-C-E-

70、H-B-O 和O-F-G-D-O,運(yùn)輸長度為67.5，成本為202.5。可經(jīng)驗(yàn)證，該解正是問題的最優(yōu)解。</p><p>　　此實(shí)例引用了參考文獻(xiàn) 2 中的經(jīng)典案例，通過上面的具體實(shí)例，可以讓我們對遺傳算法在物流配送中的具體應(yīng)用有了更深的理解。在物流配送業(yè)務(wù)中，合理確定配送路徑是提高服務(wù)質(zhì)量、降低配送成本、增加經(jīng)濟(jì)效益的重要手段。由于物流配送路徑優(yōu)化問題是一個(gè)NP難題，因此，采用啟發(fā)式算法求解是一個(gè)重要的研究方向

71、。所構(gòu)造的物流配送路徑優(yōu)化的遺傳算法，包括設(shè)計(jì)個(gè)體編碼方法、個(gè)體適應(yīng)度值的計(jì)算方法以及選擇、交叉和變異算子，對解決類似的組合優(yōu)化問題具有一定的參考價(jià)值。</p><p><b>　　7 結(jié)束語</b></p><p>　　隨著畢業(yè)日子的到來，畢業(yè)設(shè)計(jì)也接近了尾聲。經(jīng)過幾周的奮戰(zhàn)我的畢業(yè)設(shè)計(jì)終于完成了。在沒有做畢業(yè)設(shè)計(jì)以前覺得畢業(yè)設(shè)計(jì)只是對這幾年來所學(xué)知識的單純總結(jié)，但

72、是通過這次做畢業(yè)設(shè)計(jì)發(fā)現(xiàn)自己的看法有點(diǎn)太片面。畢業(yè)設(shè)計(jì)不僅是對前面所學(xué)知識的一種檢驗(yàn)，而且也是對自己能力的一種提高。通過這次畢業(yè)設(shè)計(jì)使我明白了自己原來知識還比較欠缺。自己要學(xué)習(xí)的東西還太多，以前老是覺得自己什么東西都會，什么東西都懂，有點(diǎn)眼高手低。通過這次畢業(yè)設(shè)計(jì)，我才明白學(xué)習(xí)是一個(gè)長期積累的過程，在以后的工作、生活中都應(yīng)該不斷的學(xué)習(xí)，努力提高自己知識和綜合素質(zhì)。</p><p>　　在這次畢業(yè)設(shè)計(jì)中也使我們的同

73、學(xué)關(guān)系更進(jìn)一步了，同學(xué)之間互相幫助，有什么不懂的大家在一起商量，聽聽不同的看法對我們更好的理解知識，所以在這里非常感謝幫助我的同學(xué)。</p><p>　　我的心得也就這么多了，總之，不管學(xué)會的還是學(xué)不會的的確覺得困難比較多，真是萬事開頭難，不知道如何入手。最后終于做完了有種如釋重負(fù)的感覺。此外，還得出一個(gè)結(jié)論：知識必須通過應(yīng)用才能實(shí)現(xiàn)其價(jià)值！有些東西以為學(xué)會了，但真正到用的時(shí)候才發(fā)現(xiàn)是兩回事，所以我認(rèn)為只有到真正

74、會用的時(shí)候才是真的學(xué)會了。</p><p>　　在此要感謝我的指導(dǎo)老師雷德明對我悉心的指導(dǎo)，感謝老師給我的幫助。在設(shè)計(jì)過程中，我通過查閱大量有關(guān)資料，與同學(xué)交流經(jīng)驗(yàn)和自學(xué)，并向老師請教等方式，使自己學(xué)到了不少知識，也經(jīng)歷了不少艱辛，但收獲同樣巨大。在整個(gè)設(shè)計(jì)中我懂得了許多東西，也培養(yǎng)了我獨(dú)立工作的能力，樹立了對自己工作能力的信心，相信會對今后的學(xué)習(xí)工作生活有非常重要的影響。而且大大提高了動手的能力，使我充分體會到

75、了在創(chuàng)造過程中探索的艱難和成功時(shí)的喜悅。雖然這個(gè)設(shè)計(jì)做的也不太好，但是在設(shè)計(jì)過程中所學(xué)到的東西是這次畢業(yè)設(shè)計(jì)的最大收獲和財(cái)富，使我終身受益。</p><p><b>　　8 參考文獻(xiàn)</b></p><p>　　[1] 鐘石泉，賀國光. 單車場復(fù)雜情況下的車輛調(diào)度[J]. 系統(tǒng)工程，2005,23(5):29-32.</p><p>　　[2]

76、 肖健梅，黃有方，李軍軍,等. 基于離散微粒群優(yōu)化的物流配送車輛路徑問題[J]. 系統(tǒng)工程，2005,23(4):97-100.</p><p>　　[3] 張建勇，郭耀煌，李軍. 基于顧客滿意度的多目標(biāo)模糊車輛優(yōu)化調(diào)度問題研究[J]. 鐵道學(xué)報(bào)，2003,25(2):15-17.</p><p>　　[4] 李軍，郭耀煌. 物流配送車輛優(yōu)化調(diào)度理論與方法[M]. 北京：中國物資出版社，2

77、001.</p><p>　　[5] 郭惠昕，車曉毅，肖偉躍. 混沌遺傳優(yōu)化算法及其在機(jī)械優(yōu)化設(shè)計(jì)中的應(yīng)用[J]. 機(jī)械設(shè)計(jì)，2003,20(10):23-25.</p><p>　　[6] Yung-Chien Lin, Feng-Sheng Wang, Kao-Shing Hwang. A hybrid method of evolutionary algorithms for mix

78、ed-integer nonlinear optimization problems[C] // Proceedings of the 1999 Congress on Evolutionary Computation, 1999:2160-2166.</p><p>　　[7] 李愛國. 多粒子群協(xié)同優(yōu)化算法[J]. 復(fù)旦大學(xué)學(xué)報(bào)，2004(6):87-90.</p><p>　　[8]

79、 陳一永，韓紅，龔延成. 帶時(shí)間約束的配載車輛調(diào)度問題研究[J]. 物流技術(shù)，2005,25(3):48-50.</p><p>　　[9] Savelsbergh M.Local search for routing problem with time windows. Annals of OperationsResearch,1985,16(4): 285-305.</p><p>　

80、　[10] 曾凡超. 車輛路徑問題的改進(jìn)遺傳算法[J]，重慶大學(xué), 2007.</p><p>　　[11] 徐天亮. 運(yùn)輸與配送[M]，北京：中國物資出版社, 2002.</p><p>　　[12] 晏夢君. 遺傳算法在配送線路優(yōu)化系統(tǒng)中的應(yīng)用[J], 吉林大學(xué), 2007.4.</p><p>　　[13]Laporte.GThevehieleroutingp