1、本科學生畢業論文 基于遺傳算法的物流配送車輛調度問題 院系名稱： 數 學 系 專業班級： 信息與計算科學 學生姓名： 指導教師： 職 稱： 副 教 授 黑 龍 江 工 程 學 院二一一年六月The Graduation Thesis for Bachelors DegreeThe logistics of the vehicle scheduling problem based on genetic algorithm Candidate：Luo JieSpecialty：Information and Computing ScienceClass：07-02 Supervisor：Lectu

2、rer.Wu Chang Heilongjiang Institute of Technology2011-06Harbin摘 要 隨著科學技術的不斷進步，經濟的飛速發展，物流作“第三利潤源泉”在國內受到了極大的重視并得到飛速的發展。如何節約成本，提升自我競爭能力，是每個物流公司也是整個物流行業所面臨的實際問題。在物流配送業務中，配送車輛調度問題涉及面較廣，需要考慮的因素較多，對企業提高服務質量、降低物流成本、增加經濟效益的影響也較大，是物流系統優化中關鍵的一環。可以說對物流配送車輛調度問題進行系統研究是物流集約化發展、構建綜合物流系統、建立現代調度指揮系統、發展智能交通運輸系統的基礎。在現實

3、生產和生活中，郵政投遞問題、管道鋪設問題、電力調度問題、公交車行駛線路問題等都可以看做是物流配送車輛調度問題，是NP困難問題。但是由于問題約束條件的增多，參與計算數據規模的過大，求解時間呈幾何數字擴大，傳統的求解方式已不能滿足求解需求，所以我們用遺傳算法來解決此問題。本文首先分析了物流配送中車輛調度優化問題的概述，通過概述后建立了一個模擬的物流中心和一個客戶群，以及客戶群與物流中心彼此的位置關系，然后在對遺傳算法詳細介紹的基礎上，設置相應的運行參數，再對該模型應用MATLAB70實現了對遺傳算法效果的仿真，驗證了遺傳算法解決配送路徑優化問題的可行性。關鍵詞：物流配送，車輛調度，遺傳算法，最短路

4、問題，人工智能算法ABSTRACT Along with the science and technology unceasing progress, the rapid development of economy, the logistics as third profit source in the domestic received great attention and get rapid development. How to save cost and enhance self competition ability, is each logistics company also

5、 is the whole logistics in logistics and distribution services, the distribution vehicle scheduling problem in a wide range of factors needed more, for enterprises, and improve the service quality, reduce logistics cost and increase economic benefits is larger also, the influence of logistics system

6、 optimization is a key part of. Say the distribution vehicle scheduling problem of logistics system study is intensive development, constructing logistics comprehensive logistics system, establishing modern scheduling command system, developing intelligent transportation system foundation. In actual

7、 production and life, postal delivery problems, pipeline problem, power scheduling problem, buses driving circuit can be regard as problems concerning the distribution vehicle scheduling problem is logistics, is standard np-hard problem. But due to the constraint condition of increasing problems inv

8、olved in the calculated data, the excessive, solving time scale shows geometrical figure, the traditional way of solving the expanding already cannot satisfy solving demand, so we use genetic algorithm to solve the problem. Industry faces the actual problem. This paper first analyzes the logistics d

9、istribution vehicle scheduling optimization problem, after an overview of the overview established a simulated logistics center and a customer base, and customer base and logistics center of each other, and then to the position relations in the genetic algorithm based on detailed introduction, set u

10、p corresponding operation parameters of the model, and applied to genetic algorithm MATLAB7.0 realized the simulation proves effect of genetic algorithms to solve the feasibility of distribution path optimization problem.Key words: Logistics distribution，Vehicle scheduling，Genetic algorithm， The sho

11、rtest path problem，Artificial intelligence algorithm目 錄TOC o 1-3 h u HYPERLINK l _Toc295372074 摘 要 PAGEREF _Toc295372074 h I HYPERLINK l _Toc295372075 ABSTRACT PAGEREF _Toc295372075 h II HYPERLINK l _Toc295372076 目 錄 PAGEREF _Toc295372076 h 1 HYPERLINK l _Toc295372077 第1章 緒 論 PAGEREF _Toc295372077 h

12、 1 HYPERLINK l _Toc295372078 1.1課題研究背景與實際意義 PAGEREF _Toc295372078 h 1 HYPERLINK l _Toc295372079 1.2國內外研究現狀及分析 PAGEREF _Toc295372079 h 2 HYPERLINK l _Toc295372080 1.3本文的研究方法 PAGEREF _Toc295372080 h 3 HYPERLINK l _Toc295372081 第2章 物流配送車輛調度問題的綜述 PAGEREF _Toc295372081 h 4 HYPERLINK l _Toc295372082 2.1物流

13、配送車輛調度問題的概述 PAGEREF _Toc295372082 h 4 HYPERLINK l _Toc295372083 2.2物流配送車輛調度問題的分析 PAGEREF _Toc295372083 h 5 HYPERLINK l _Toc295372084 第3章 遺傳算法的概述與應用 PAGEREF _Toc295372084 h 8 HYPERLINK l _Toc295372085 3.1 遺傳算法理論概述 PAGEREF _Toc295372085 h 8 HYPERLINK l _Toc295372086 遺傳算法的起源于發展 PAGEREF _Toc295372086 h

14、8 HYPERLINK l _Toc295372087 遺傳算法的工作特點 PAGEREF _Toc295372087 h 9 HYPERLINK l _Toc295372088 3.2遺傳算法的運用 PAGEREF _Toc295372088 h 10 HYPERLINK l _Toc295372089 遺傳算法的步驟 PAGEREF _Toc295372089 h 10 HYPERLINK l _Toc295372090 遺傳算法的數學模型 PAGEREF _Toc295372090 h 11 HYPERLINK l _Toc295372091 第4章 基于遺傳算法的車輛調度模型 PAGE

15、REF _Toc295372091 h 14 HYPERLINK l _Toc295372092 4.1模型的建立 PAGEREF _Toc295372092 h 14 HYPERLINK l _Toc295372093 4.2模型的求解 PAGEREF _Toc295372093 h 18 HYPERLINK l _Toc295372094 4.2.1.確定染色體的編碼和初始群體 PAGEREF _Toc295372094 h 18 HYPERLINK l _Toc295372095 4.2.2.適應性函數 PAGEREF _Toc295372095 h 19 HYPERLINK l _To

16、c295372096 4.2.3.染色體的選擇 PAGEREF _Toc295372096 h 20 HYPERLINK l _Toc295372097 4.2.4.染色體的交叉 PAGEREF _Toc295372097 h 21 HYPERLINK l _Toc295372098 4.2.5.染色體的變異 PAGEREF _Toc295372098 h 22 HYPERLINK l _Toc295372099 4.2.3.控制參數 PAGEREF _Toc295372099 h 22 HYPERLINK l _Toc295372100 4.2.3.運行結果 PAGEREF _Toc2953

17、72100 h 23 HYPERLINK l _Toc295372101 4.3總結 PAGEREF _Toc295372101 h 23 HYPERLINK l _Toc295372102 主要參考資料 PAGEREF _Toc295372102 h 24 HYPERLINK l _Toc295372103 致 謝 PAGEREF _Toc295372103 h 25 HYPERLINK l _Toc295372104 附 錄 PAGEREF _Toc295372104 h 26第1章 緒 論1.1課題研究背景與實際意義在經濟全球化和信息化的推動下，現代物流業已從為社會提供傳統運輸服務，擴寬

18、到以現代科技、管理和信息技術為支柱的綜合物流系統。物流是在20世紀50年代新發展起來的一門實踐性很強的綜合性交叉學科，是當代最有影響的新科學之一，它全面融會了運籌學、經濟科學及管理科學，揭示了運輸、儲存、裝卸搬運、包裝、流通加工、物流信息等物流各要素的內在聯系，物流在經濟發達國家被視為繼原材料、勞動力以外的“第三利潤源泉”在現代物流集約化、一體化的發展中，車輛優化調度是直接與消費者相連的重要環節，涵蓋的面也比較廣其中包括配貨作業，即貨物的分揀過程，根據各個用戶的不同需求，在配貨中心將所需要的貨物迅速的挑選出來的過程，加大車輛調配執行的效率，這需要倉儲的優化：車載貨物的配裝，即在配送貨物時要考慮

19、車輛的載重和容積，使車輛的載重和容積充分利用，還要考慮配送多個客戶的問題：配送線路的確定，配送線路合理與否對配送速度、成本、效益影響很大，特別是多用戶配送線路的確定更為復雜。采用科學的、合理的方法來確定配送線路是車輛優化調度的核心部分，是物流系統優化、物流科學化的關鍵一環。對車輛進行優化調度，即合理的進行配貨優化、貨物配裝優化，特別是配送路線優化，能夠提高里程利用率，降低行駛費用，大大減少車輛空駛里程，增加貨運量，節約燃料，降低大修費，提高營運收入，從而帶來巨大的經濟效益。另外，還可以產生良好的社會效益，體現在減少廢氣排放量，降低城市空氣污染水平。目前，在我國一些地區，公路貨物運輸一方面存在超

20、負荷運行：另一方面由于缺乏科學組織，造成貨運車輛使用效率低下，浪費嚴重。運輸經營管理落后是一個重要問題，表現為先進的管理手段采用較少，管理方法落后，一般仍憑經驗調度，調度質量差、優化程度低，空駛率高、嚴重浪費，不能充分發揮運輸工具的效能。而在國外一些發達國家，貨運車輛優化調度己廣泛地運用于生產、生活的各個方面，如報紙投遞線路的優化、牛奶送達線路優化、電話預定貨物的車輛線路設計、垃圾車的線路優化及垃圾站選址優化、連鎖商店的送貨線路優化等等為了改善貨物運輸的質量狀況，充分發揮運輸車輛的效能，除了進一步擴大和改善城市道路系統和交通設施之外，加強運輸的科學組織管理也是極其重要的一個方面而且從所需投資和

21、見效迅速等方面考慮，后者往往更為現實，從而意義更大經濟的發展要求協調的綜合運輸體系支持，即整個運輸形成網絡，這樣對相應的組織管理也提出了更高的要求。因此，加強貨運組織的科學管理，對貨運車輛進行優化調度，配送線路進行優化管理，有著極為重要的意義。可以說對貨運車輛調度，配送線路優化理論與方法進行系統研究是建立現代調度指揮系統、發展智能交通運輸系統的基礎。1.2國內外研究現狀及分析由于車輛線路的優化是車輛優化調度的核心，目前國內外對車輛優化調度的研究基本是針對于車輛配送線路優化的研究。車輛路徑問題是由Dantzig和Ramser于1959年首次提出的。一般認為，當不考慮時間要求，僅根據空間位置安排線

22、路的稱為VRP（Vehicle Routing Problem，簡稱VRP）問題，根據時間要求安排線路的稱為VSP（Vehicle Scheduling Problem，簡稱VSP）問題，同時考慮空間位置和時問要求的稱為Routing和Scheduling混合問題。此問題一提出，很快引起運籌學、應用數學、組合數學、圖論與網絡分析、物流科學、計算機應用等學科的專家與運輸計劃制定者和管理者的極大重視，成為運籌學與組合優化領域的前沿與研究熱點問題。各學科專家對該問題進行了大量的理論研究及實驗分析，取得了很大進展。所謂配送優化，就是在配送的諸環節，如流通加工、整理、揀選、分類，配貨、末端運輸中，從物流

23、系統的總體目標出發，運用系統理論和系統工程原理和方法，充分利用各種運輸方式優點，以運籌學等數量方法建立模型與圖表選擇和規劃合理的配送線路和配送工具，以最短的路徑、最少的環節、最快的速度和最少的費用，組織好物品的配送活動，避免不合理配送情況和次優化的出現。車輛優化調度問題一般定義為：對一系列裝貨點和(或)卸貨點，組織適當的行車線路，使車輛有序地通過他們，在滿足一定的約束條件(如貨物需求量、發送量、交發貨時間、車輛容量限制、行駛里程限制、時間限制等)下，達到一定的目標(如路程最短、費用最少、時間盡量小、利潤最大、使用車輛數盡量少等)。國外對VRP和VSP作了大量而深入的研究，目前，問題的形式已有很

24、大發展，該問題己不僅僅局限于公路交通運輸領域，在水運、航空、通訊、電力、工業管理、計算機應用等領域也有一定的應用，其算法已用于航空乘務員輪班安排、生產系統中的計劃與控制等多種組合優化問題。目前國內外在遺傳算法用于物流調配的問題上的研究主要方向是遺傳算法與啟發式算法相結合。例如，將遺傳算法與掃描法相結合。先用掃描法對數據做預處理，用極坐標來表示各個需求點的區位，再取一點為起始點，定其角度為零度，以順時鐘或逆時鐘方向，以車容量為限制條件進行服務區域之分割，把數據進行歸類，然后再使用遺傳算法進行計算。采用這種方式在對數據進行遺傳計算前使用啟發式算法將數據進行預處理將會大大提高計算的效率。因為在遺傳算

25、法在進行染色體的交叉變異時計算量相對較大如果將一些不可行數據提前去除或將雜亂的數據歸類不僅節約計算時間也提高了計算結果的精確性、可靠性。其次將遺傳算法與C-W節約算法相結合、與改進算法相結合都是研究的熱點。1.3本文的研究方法 本文主要通過本文主要通過對遺傳算法運用學習，以及對物流配送問題的究分析，建立了一個物流配送模型。再對該物流配送模型的配送路線運用遺傳算法進行運算優化，得到一個最優化路線。從而體現出遺傳算法在此類問題上運用的可行性和優點。第一步，確立染色體編碼和初始基因群。第二步，確定適應度函數。第三步，確立遺傳算子復制、交叉、變異的方法。第四步，計算得出優化解。第五步，對結果進行分析。

26、第2章 物流配送車輛調度問題的綜述2.1物流配送車輛調度問題的概述物流的概念最早在美國形成，起初被稱為Physical Distribution(PD)，即實體分配或配送。1963年，物流的概念被引入日本，進一步理解為“在連接生產和消費間對物資履行保管、運輸、裝卸、包裝、加工等功能，以及作為控制這類功能后援的信息功能，在物資銷售中起橋梁作用”。我國在19世紀80年代初開始接觸“物流”的概念。此時物流一般被稱為Logistics，而不再是過去PD的概念。Logistics的原意為“后勤”，后來轉用于物資流通領域。這時，物流就不單純考慮從生產者到消費者的貨物配送問題，而且還要考慮從供應商到生產者對

27、原材料的采購，以及生產者在產品制造過程中的運輸、保管和信息等各個方面，如何全面地、綜合性地提高經濟效益和效率的問題。因此，現代物流是以滿足消費者的需求為目標，把制造、運輸、銷售等市場情況統一起來考慮的一種戰略措施，在原材料、產成品及相關信息從起點至終點有效流動的全過程，它將運輸、倉儲、裝卸、加工、整理、配送、信息等方面有機結合，形成完整的供應鏈，為用戶提供多功能、一體化的綜合性服務。與傳統物流作為“后勤保障系統”和“銷售活動中的橋梁”相比，它在深度和廣度上都有了進一步的含義。 一般認為，物流有以下六大功能:(1) 運輸。運輸是物流作業中最直觀的功能要素。它是通過運輸手段使貨物在物流據點之間流動

28、，產生地點或場所功效。(2) 保管。保管通過堆存、管理、保養、維護等活動，創造物品的時間功效。(3) 包裝。包裝是為在流通過程中保護商品、方便貯運、促進銷售，按一定的技術方法而采取的容器、材料及輔助物等的總稱。一般來說。包裝是生產的終點，也是物流的起點。(4) 搬運。搬運是指在物流過程中，對貨物進行裝卸、搬運、堆垛、取貨、理貨分類等，或與之相關的作業。(5) 流通加工。流通加工是在流通領域為了提高物流運轉效率而進行的加工活動。(6) 物流信息。物流信息是指能使物流暢通、定量化而需要及時收集和傳輸的有關信息。隨著物流配送集約化、一體化的發展，常將配送的各個環節綜合起來，核心部分為配送車輛的集貨、

29、貨物配裝及送貨過程。進行配貨系統優化，主要就是配送車輛優化調度，包括集貨線路優化、貨物配裝及送貨線路優化，以及集貨、貨物配裝和送貨一體化優化。 物流配送車輛優化調度問題一般定義為：對一系列發貨點和收貨點，組織適當的行車路線。使車輛有序的通過它們，在滿足一定的約束條件(如貨物需求量、發送量、交發貨時間、車輛容量限制、行駛里程限制、時問限制等)下，達到一定的目標(如路程最短、費用最小、時間盡量少、使用車輛數盡量少等)。雖然物流配送具有多種類型和形式，但大部分物流配送形式中運輸的特點是基本相同的，即將商品從配送中心按一定的要求送到多個需求點。由于運輸任務的性質和特點不同，道路條件及車輛類型不同，即使

30、在相同收發貨點間完成同樣任務時，采用的行駛路線方案也可能不同。而車輛按不同運行線路完成同樣的運輸工作時，其利用效果是不一樣的，有時甚至會有很大的差別。因此，在滿足貨運任務要求的前提下，如何選擇最經濟的運行路線，是一項重要的工作。所謂最經濟的運行路線，就是在保證貨物需求的前提下，運輸時間或運輸費用最省的路線。如何按時按量、經濟高效地配送商品，在很大程度上取決于有效的車輛調度安排，調度方案的優化與否，對提高配送效率、減少物流費用和提高服務水平具有重要的意義。 2.2物流配送車輛調度問題的分析車輛優化調度問題主要優化目標有：1.配送總里程最短。配送里程與配送車輛的耗油量、磨損程度以及司機疲勞程度等直

31、接相關，它直接決定運輸的成本，對配送業務的經濟效益有很大影響。由于配送路程計算簡便，它是確定配送路線時用得最多的指標。2.配送車輛的噸位公里數最少。該目標將配送距離與車輛的載重量結合起來考慮，即以所有配送車輛的噸位數(最大載重噸)與其行駛距離的乘積的總和最少為目標。3.勞動消耗最低。即以司機人數最少、司機工作時間最短為目標。4.準時性最高。由于客戶對交貨時間有較嚴格的要求，為提高配送服務質量，有時需要將準時性最高作為確定配送路線的目標。5.運力利用最合理。該目標要求使用的較少的車輛完成配送任務，并使車輛的滿載率最高，以充分利用車輛的裝載能力。6.綜合費用最低。降低綜合費用是實現配送業務經濟效益

32、的基本要求。在配送中，與取送貨有關的費用包括：車輛維護和行駛費用、車隊管理費用、貨物裝卸費用、有關人員工資費用等。物流配送車輛優化調度問題可以分為：(1)滿載和非滿載的車輛優化調度問題當每個客戶需求貨物量小于車輛容量時，用一輛車執行一項任務就存在不滿載運行情況，調度時可安排一輛車執行多項任務，即在一輛車上裝載不同貨主的貨物。這類問題稱為非滿載VRP，當然，這類問題有一個前提條件，即不同貨主的貨物允許混裝。當每個客戶需求貨物量大于車輛容量時，用一輛車執行一項任務就不能滿足客戶的需求，此時需要一輛以上的車對其進行送貨，車輛能夠滿載，該問題稱為滿載VRP。(2)集貨或送貨和集送一體化的車輛優化調度問

33、題所有任務全是集貨點(裝貨點)或全是送貨點(卸貨點)，空車從配送中心出發，去各貨主處裝滿貨后返回配送中心，或是車輛裝滿貨物去各貨主處卸貨后返回配送中心，這種情況稱為集貨或送貨的車輛調度問題。每一項貨運任務都有自己的集貨點和送貨點，車輛從配送中心出發，某一任務的集貨地點裝貨后運至其送貨地點卸貨，完成所有任務后返回配送中心，這種情況稱為集貨和送貨一體化的車輛調度問題。(3)有時間窗和無時間窗的車輛優化調度問題如果到達任務點的時間是事先規定的，則稱該問題是帶時間窗要求的車輛優化調度問題：若到達和離開時間沒有規定，則稱該問題就是一個直接的路線安排的問題。帶時問窗的VRP又可分為硬時問窗VRP和軟時問窗

34、VRP。硬時問窗VRP指每項任務必須在要求的時間內完成，軟時問窗VRP指如果某項任務不能在要求的時問范圍內完成，則給予一定的懲罰。(4)單車場和多車場的車輛優化調度問題單車場車輛優化調度問題是指所有的車輛均從一個配送中心發出，完成各自的任務后都返回該配送中心。多車場車輛優化調度問題是指，存在著多個配送中心，車輛可以從任何一個配送中心派出，完成任務后，車輛也可以返回其中的任何一個配送中心，隨著供應鏈的集成一體化，多車場的車輛優化調度將越來越多，越來越重要。對于這類問題可以通過一定的方法將其轉化為單源點的車輛優化調度問題。可以考慮的條件可由下表表1表示。表2.1 車輛調度問題約束條件歸類表車輛與物

35、流中心的所屬關系車輛開放問題車輛封閉問題車輛類型單車型問題多車型問題車場數目單車場問題多車場問題任務特性純裝載問題純卸載問題裝卸混合問題車輛載貨情況滿載情況非滿載情況時間限制有時間限制問題無時間限制問題出發原點多原點問題單原點問題 由于作者初識遺傳算法，個人能力有限，對復雜度較高的問題難以解決，本文主要考慮的問題為，車輛封閉、單車型、單車場、純裝載、非滿載、無時間窗的單原點問題。第3章 遺傳算法的概述與應用3.1 遺傳算法理論概述遺傳算法的起源于發展遺傳算法的概念最早是由Bagley JD在1967年提出的，而遺傳算法理論和方法的系統性研究是1975年開始的，這一開創性工作是由Michigan

36、大學的JHHolland實行的。當時其主要目的是說明自然和人工系統的自適應過程。遺傳算法簡稱GA(Genetic Algorithm)，在本質上是一種不依賴具體問題的直接搜索方法。它對優化對象既不要求連續，也不要求可微，并具有極強的魯棒性和內在的并行計算機制。1975年是遺傳算法發展史中至關重要的一年，兩大里程碑的豎立使遺傳算法的研究和應用更加活躍。這兩大里程碑一是Holland總結了他研究遺傳算法的精髓，出版了Adaptation in Nature and Artificial System一書，詳細闡述了遺傳算法的工作機理，并發展了一整套模擬生物自適應系統的原理；二是De Jong完成了

37、他的博士論文。An Analysis of the Behavior of a Class of Genetic Adaptive System”，他結合模式理論建立了著名的De Jong五函數測試平臺，定義了性能評價標準，并對六種遺傳算法方案的性能和機制進行了實驗和分析，得出一個結論：對于規模在50到100的群體，經過10到20代的演化，遺傳算法能以很大的概率找到最優解或近似最優解。進入90年代，遺傳算法迎來了興盛發展時期，無論是理論研究還是應用研究都成了十分熱門的課題。尤其是遺傳算法的應用研究顯得格外活躍，不但它的應用領域擴大，而且利用遺傳算法進行優化和規則學習的能力也顯著提高，同時產業應

38、用方面的研究也在摸索之中。此外一些新的理論和方法在應用研究中亦得到了迅速的發展，這些無疑均給遺傳算法增添了新的活力。遺傳算法的應用研究已從初期的組合優化求解擴展到了許多更新、更工程化的應用方面。 隨著應用領域的擴展，遺傳算法的研究出現了幾個引人注目的新動向：一是基于遺傳算法的機器學習，這一新的研究課題把遺傳算法從歷來離散的搜索空間的優化搜索算法擴展到具有獨特的規則生成功能的嶄新的機器學習算法。這一新的學習機制對于解決人工智能中知識獲取和知識優化精煉的瓶頸難題帶來了希望。二是遺傳算法與神經網絡、模糊推理以及混沌理論等其它智能計算方法相互滲透和結合，這對開拓21世紀中新的智能計算技術將具有重要的意

39、義。三是并行處理的遺傳算法的研究十分活躍。這一研究不僅對遺傳算法本身的發展，而且對于新一代智能計算機體系結構的研究都是十分重要的。四是遺傳算法和另一個稱為人工生命的嶄新研究領域正不斷滲透。所謂人工生命即是用計算機模擬自然界豐富多彩的生命現象，其中生物的自適應、進化和免疫等現象是人工生命的重要研究對象，而遺傳算法在這方面將會發揮一定的作用，五是遺傳算法和進化規劃（Evolution Programming .EP）以及進化策略（Evolution Strategy .ES）等進化計算理論日益結合。EP和ES幾乎是和遺傳算法同時獨立發展起來的，同遺傳算法一樣，它們也是模擬自然界生物進化機制的智能計

40、算方法，即同遺傳算法具有相同之處，也有各自的特點。目前，這三者之間彼此結合的研究正形成熱點。遺傳算法的工作特點 遺傳算法是從達爾文進化論中得到靈感和啟迪，借鑒自然選擇和自然進化的原理，模擬生物在自然界中的進化過程所形成的一種優化求解方法。盡管這種自適應尋優技術可用來處理復雜的線性、非線性問題，但它的工作機理十分簡單標準遺傳算法(Canonical Genetic Algorithms)的步驟如下；1.構造滿足約束條件的染色體。由于遺傳算法不能直接處理解空間中的解，所以必須通過編碼將解表示成適當的染色體。實際問題的染色體有多種編碼方式，染色體編碼方式的選取應盡可能地符合問題約束，否則將影響計算效

41、果2.隨機產生初始群體。初始群體是搜索開始時的一組染色體，其數量應適當選擇。3.計算每個染色體的適應度適應度是反映染色體優劣的唯一指標，遺傳算法就是要尋得適應度最大的染色體。4.使用復制、交叉和變異算子產生子群體。這三個算子是遺傳算法的基本算子，其中復制體現了優勝劣汰的自然規律，交叉體現了有性繁殖的思想，變異體現了進化過程中的基因突變。5.重復步驟3、4直到滿足終止條件為止同傳統的尋優算法相比較，遺傳算法具有以下特點：1.遺傳算法對問題參數的代碼集起作用，而不是對參數本身起作用。遺傳算法處理的對象是染色體，因而要求把所要優化問題的基本參數轉化成定長的有限符號的染色體。2.遺傳算法是從初始群體開

42、始搜索的，而不是從單點開始搜索的。許多傳統優化方法都是從搜索空間的單點出發，通過某些轉換規則確定下一點。這種點到點的搜索方法在多峰值優化問題中，首先找到的可能不是最優峰值；而遺傳算法是以點集開始的尋優過程，初始群體是隨機地在搜索空間中選取的，這樣在搜索過程中達到最優峰值的概率遠大于點到點方法的概率。3.遺傳算法在搜索過程中只使用適應度函數信息，而不用導數及其他輔助信息。對于不同類型的優化問題，傳統方法需要不同形式的輔助信息，沒有一種優化方法能適應各類問題的要求遺傳算法在優化過程中，放棄使用這些輔助信息，具有廣泛適應性。4.遺傳算法使用概率轉換規則而不用確定性規則。遺傳算法使用概率轉。換規則來調

43、整其搜索方向，各代群體問沒有統一的聯系規律。但使用概率轉換規則并不意味著這種方法屬于隨機算法范疇，它只是使用隨機轉換作為工具來調整搜索過程趨向于目標函數不斷改進的區域。對于傳統方法相比，遺傳算法的優越性主要表現在；首先，在遺傳算子的作用下，遺傳算法具有很強的搜索能力，能以很大概率找到問題的全局最優解：其次，由于它固有的并行性，能有效地處理大規模地優化問題。5.具有自組織、自適應和自學習性。遺傳算法利用進化過程獲得的信息自行組織搜索，時硬度大的個體具有較高的生存概率，并獲得更適應環境的基因結構。3.2遺傳算法的運用遺傳算法的步驟(1)初始種群的產生初始群體中的個體一般是隨機產生的，在問題解空間均

44、勻采樣，隨機生成數目為種群大小的個體，也可以隨機生成數目為種群大小2倍的個體，然后從中挑出較好的個體構成初始群體。(2)編碼方法由于遺傳算法計算過程的魯棒性，它對編碼的要求并不苛刻，大多數問題都可以采用基因呈一維排列的定長染色體表現形式。由于編碼形式決定了交叉算子的操作方式，因此，作為遺傳算法流程中第一步的編碼是遺傳算法中需要認真研究的問題，很多專家提出了多種編碼方法。目前常用的編碼方法有以下幾種：二進制編碼、順序編碼、實數編碼、樹編碼等。針對不同問題，算法設計者也可以設計適合該問題的編碼方法。 (3)適值函數遺傳算法將問題空間表示為染色體串空間，為了執行適者生存的原則，必須對個體位串的適應性

45、進行評價。因此，適值函數就構成了個體的生存環境。根據個體的適值，就可以決定它在此環境下的生存能力。一般來說，好的染色體位串結構具有比較高的適值，即可以獲得較高的評價，具有較強的生存能力。適值函數根據目標函數的類型來設計，用適值函數F(x)來標定目標函數f（x)。(4)遺傳運算交叉是遺傳算法中最主要的操作，一般分兩步進行，一是對群體中的個體進行隨機配對；二是在配對個體中，隨機設定交叉處，使配對個體彼此交換部分信息。變異是指按一定的概率改變個體的基因鏈。變異操作也是隨機進行的，其目的是挖掘群體中個體的多樣性，克服遺傳操作可能限于局部最優解的弊端。(5)選擇策略選擇即從當前群體中選擇適值高的個體以生

46、成交配池(mating pool)的過程。目前，主要有適值比例選擇(即輪盤賭選擇策略)、排序選擇、聯賽選擇等形式。交叉操作是遺傳算法中產生新個體的主要方法，若取值過小，產生新個體的速度會較慢，所以交叉概率一般應取較大值；但若取值過大的話，它又可能破壞群體中的優良模式，對進化運算產生不良影響。一般建議的取值范圍是0.4到0.99。 (6)停止準則遺傳算法迭代的終止，一般采用設定最大代數的方法。該方法簡單易行，但不準確。其次，可以根據群體的收斂程度來判斷，通過計算種群中的基因多樣性測度，即所有基因為的相似性程度來進行控制。第三，可根據算法的離線性能和在線性能的變化判定是否終止迭代。遺傳算法的數學模

47、型不同的編碼方法和不同的遺傳算子可以構成不同的遺傳算法，它們有一個共同的特點，即對生物進化過程中的選擇、交叉、變異的模仿，以此完成對問題最優解的自適應搜索。基本遺傳算法的構成要素主要包括：染色體的編碼方法、個體適應度的評價、遺傳算子、運行參數(包括群體大小、算法終止進化代數、交叉概率、變異概率)。 遺傳算法的數學模型可以表示為： SKIPIF 1 0 （ SKIPIF 1 0 ）式中： SKIPIF 1 0 ，個體的編碼方法，一般采用自然數編碼法。 SKIPIF 1 0 ，個體適應度，評價函數對種群中的每個個體，計算其適應值， QUOTE SKIPIF 1 0 , SKIPIF 1 0 SKI

48、PIF 1 0 ，初始種群，隨機選擇 SKIPIF 1 0 個初始點（稱為一個群體，每個點稱為一個個體） SKIPIF 1 0 SKIPIF 1 0 SKIPIF 1 0 ，種群大小，一般種群設立在20-100個之間。 SKIPIF 1 0 ，選擇算子，計算每個染色體選擇概率 SKIPIF 1 0 ，如用輪盤賭法，則從 SKIPIF 1 0 SKIPIF 1 0 ,中選擇 SKIPIF 1 0 SKIPIF 1 0 ,且每個 SKIPIF 1 0 SKIPIF 1 0 被選中的概率為 QUOTE SKIPIF 1 0 。 SKIPIF 1 0 交叉算子,從 SKIPIF 1 0 SKIPIF

49、1 0 中以相同的概率選出兩個個體，這兩個個體之間以事先給定的概率 QUOTE 執行重組運算，產生兩個新個體，重復這一過程，直至形成新群體 SKIPIF 1 0 SKIPIF 1 0 SKIPIF 1 0 變異算子,變異運算是根據一定的變異概率Pm隨機地對每個個體的每一位改變它的值，形成新一代群體 QUOTE SKIPIF 1 0 SKIPIF 1 0 SKIPIF 1 0 遺傳運行終止條件,檢驗終止準則是否滿足，如果滿足則停止運算，否則可令k=k+l，轉第二步繼續運算。算法流程圖如圖一。遺傳編碼方式以及群體大小隨機生成初始種群生成新一代群體評價群體滿足停止要求結束運算遺傳算法運算NY圖3.1

50、 遺傳算法流程圖第4章 基于遺傳算法的車輛調度模型4.1模型的建立 動態車輛調度問題是屬于一種信息不確定的問題類型。信息變化考慮的內容可以很多，例如道路屬性的不確定（收費路段與不收費路段等）、客戶(需求量、送貨時間、送貨地點)的不確定、車輛和司機的突發情況的不確定性、路段交通情況的變化等。考慮的變化越多，使車輛優化調度問題的求解越復雜，但當信息一旦明確已知，可以把動態車輛調度問題轉化為靜態車輛調度問題來求解。在這里我們考慮的主要有以下問題：車輛只負責送貨，即純卸載問題；每一車輛的都有一定的裝載量，裝載時不能超過其裝載量；所有車輛的裝載量相同，而且車輛參數相同。即所有的車輛可視為同一輛車，在運行

51、成本上只需計算路程的長短即可；每輛車只有一條行駛路線，從物流中心出發，配送完貨物后必須返回物流中心。即車輛是封閉的；客戶的需求量為一定值；貨物允許混裝；每個客戶需求量不超過車輛載重量，即每個客戶所需要貨物只需由一輛車提供即可；客戶對配送時間要求沒有嚴格要求。即沒有時間窗約束；設一個物流中心在該物流中心管轄范圍內目前有19個客戶需要配送貨物。客戶的需求量已知，物流中心有5輛車輛型號相同，最大運載量為3噸的配送貨車。為了更直觀的體現遺傳算法的群體搜索特性我們使用函數隨機生成客戶坐標與客戶需求量。使用C語言函數隨機產生20個二維坐標 SKIPIF 1 0 為整數。在這里我們將物流中心也視作一個客戶，

52、得到一個客戶坐標表，選取其中1個為物流中心坐標，剩余19個為客戶坐標。在選取物流中心坐標時我們選擇靠近中心點（50,50）的點。選取物流中心后將隨機得到的客戶需求量依次對應每一個客戶。得到坐標后，由于15號客戶距離中心點最近，我們選取15號客戶作為物流中心，并將物流中心設為0,16-20號客戶依次降1，變為15-19號客戶。再用隨機函數生成19個客戶需求量，客戶需求量為Q,Q(0-1)，Q保留兩位小數。得到表2。表4.1 客戶坐標及貨物需求表客戶1234坐標（41,91）（67,4）（34,2）（0,53）需求量0.310.830.790.44客戶5678坐標（69,92）（24，82）（78

53、，,21）（58,16）需求量0.220.570.290.32客戶9101112坐標（62,18）（64,95）（5,47）（45,26）需求量0.460.830.220.34客戶1314015坐標（81，71）（27,38）（61,69）（91,12）需求量0.960.510.930.48客戶16171819坐標（95,67）（42,99）（27,35）（36,94）需求量0.910.230.720.18根據公式 QUOTE SKIPIF 1 0 求出客戶群與物流中心彼此間的距離，得到的結果取整。得到表3表4.2 客戶距離表1234567891011121314015161718191090

54、895528197976752356654454299359857529003383888920151491753168526525689850953893306196804727329753268336725789973392455836107937846871767528230639996623254528889679046717674578702468248236277033619898037460817474423959584439967224471677920478471810201675773350535015498552848761527687674200479611659385

55、333638436819751432717474164077631856405129598338801023919776542757977076712967268741227028續表4.2：123456789101112131401516171819115675537783977616376045792360929263255612653126527059331618714505721454864732068134468838224585059297979570632059144864501454523630684453384067232163046697362356029657263243

56、9505351266045204606434354835159325579982961533298792485969640559968981659688996367249635941926414733455061756417898976227248584832263734862359961065718575033327047523638702520643486875650591959592543316848180285668505635986475904.2模型的求解. 確定染色體的編碼和初始群體編碼是應用遺傳算法時要解決的首要問題，是設計遺傳算法時的一個關鍵步驟，因此必須精心設計遺傳算法的染

57、色體結構，使算法能以較大的概率獲得全局最優解。由于每一輛配送車輛都形成一條配送路徑， 5輛車可構成5條配送路徑。這5條路徑即為一個配送方案，而一個解決方案做適當變換可以構成一條染色體。路徑1: 物流中心客戶1客戶2客戶3客戶4物流中心。 012340路徑2： 物流中心客戶5客戶6客戶7客戶8物流中心。 056780路徑3： 物流中心客戶9客戶10客戶11客戶12物流中心。 091011120路徑4： 物流中心客戶13客戶14客戶15客戶16物流中心。 0131415160路徑5： 物流中心客戶17客戶18客戶19物流中心。 01718190將5條路徑結合在一起：0123400567800910

58、11120013141516001718190在兩個路徑結合的地方有兩個0，這兩個0排在一起在計算上并沒有實際意義，反而在對其進行交叉和變異的計算中會增大計算量，在這里我們稍做改動。如果我們把5輛行駛的路徑用1輛車來完成，即走完一條路徑后，回到物流中心，再物流中心出發執行下一條路徑直到走完5條路徑，這樣可以將結合處的0省略一個，得到：01234056780910111201314151601718190，由于我們的模型車輛是封閉的，所有車輛從物流中心出發，配送完畢后要都要返回物流中心，無論車輛怎樣行駛路徑必定一頭一位都是0。我們要力圖使構造的染色體的長度最短，這樣做的目的不僅能節省計算時間，也

59、能提高計算精確度，所以這里我們把一頭一尾的0也省略，得到：123405678091011120131415160171819則我們把染色體編為（1,2,3,4,0,5,6,7,8,0,9,10,11,12,0,13,14,15,16,0,17,18,19）這種染色體結構，子路徑內部是有序的，如果子路徑中客戶順序改變會使目標函數改變。而子路徑是沒有序的，子路徑之間順序發生改變，目標函數不會發生改變。初始群體的產生可采用隨機方法，隨機產生50個 1到19,的全排列，在其內部隨機插入4個0。得到一個初始染色體群V。 . 適應性函數由于運輸車輛的相同，運營成本則只和運行路徑長短有關，在這里我們只考慮運

60、輸道路最短。設 QUOTE SKIPIF 1 0 是車輛 SKIPIF 1 0 從客戶 SKIPIF 1 0 到 SKIPIF 1 0 的路徑( SKIPIF 1 0 , SKIPIF 1 0 =0,119, SKIPIF 1 0 表示路徑， SKIPIF 1 0 =1-5)。 SKIPIF 1 0 是客戶之間的距離已知。 QUOTE SKIPIF 1 0 是每一個客戶的需求量， SKIPIF 1 0 =119。則有 SKIPIF 1 0 表示當車輛 SKIPIF 1 0 從客戶i到客戶j的時候 QUOTE SKIPIF 1 0 ，若車輛 SKIPIF 1 0 從 SKIPIF 1 0 沒有到