基于遺傳算法的多輛灑水車最優(yōu)路徑求解（其中包含MATLAB的一些關(guān)鍵語句說明和FloydDijkstraEuler算法

1、摘要車輛路徑問題可以分為以點(diǎn)為服務(wù)和以邊為服務(wù)兩種，灑水車問題是以邊為服務(wù)的一個(gè)子問題。作為容量限制弦路徑車輛行駛問題(CARP)的一種實(shí)際應(yīng)用，灑水車路線規(guī)劃涉及帶有一定容量限制的總行程最小，以及多輛灑水車工作的合理分配問題，屬于復(fù)雜的N-P難車輛路徑優(yōu)化問題。因此，在容量限制下實(shí)現(xiàn)作業(yè)車的總行駛路徑最小，節(jié)約成本，提高效率，成為我們研究的中心環(huán)節(jié)。本文采用了遺傳算法，對(duì)多輛灑水車線路優(yōu)化問題進(jìn)行了容量均衡性方面的研究。首先在矩陣計(jì)算過程中采用了Floyd和Dijkstra算法求解了作業(yè)區(qū)域上任意兩點(diǎn)之間的距離，以及指定兩點(diǎn)之間的具體路徑，為車輛的部分路段行駛獲得了指向。接著對(duì)灑水車作業(yè)圖的

2、奇數(shù)度點(diǎn)進(jìn)行隨機(jī)匹配，從而把灑水車的作業(yè)圖補(bǔ)成了每個(gè)頂點(diǎn)都是偶數(shù)，這樣就可以獲得一條Euler回路，即對(duì)應(yīng)一個(gè)花費(fèi)數(shù)值。然后通過遺傳算法，初始化，編碼，解碼，適應(yīng)度函數(shù)的計(jì)算以及選擇，交叉，變異等一系列操作，最終獲得一條花費(fèi)最小的Euler回路。最后對(duì)這條回路進(jìn)行分割，從而實(shí)現(xiàn)多輛車之間的作業(yè)分配。本文通過引用柳州市區(qū)的一部分區(qū)域地圖進(jìn)行實(shí)驗(yàn)，獲得了比較理想的結(jié)果，并服合一定的現(xiàn)實(shí)意義。關(guān)鍵詞:路線優(yōu)化 遺傳算法 匹配 Euler算法AbstractVehicle routing problem can be divided into the service for points and th

3、e service for sides， while sprinkler service is a subset of the side problem. As a practical application of CARP(Capacitated ARC Routing Problem) ，the sprinkler route planning demanks the total trip Minimum with a certain capacity and shares alike the work .So it is the complexity of VRP(Vehicle rou

4、ting problem).In order to achieve the total trip minimum， to increase the least cost and increase the efficiency that becomes the central link of our research.In this paper， we use the genetic algorithm to research how to finishes the sprinklers work equal. First of all， we apply the the Floyd and D

5、ijkstra to achieve the distance between any two points and the specific path between two cettain points， which provide a method for the car to some setions road.Then the point of odd-degree random match in the routing graph，in this way， we can change the degree of every vertex into even.This can be

6、an Euler circuit， which corresponds to a cost value.Whats more， through the genetic algorithm， initialization， encoding， decoding， the calculation of fitness function， as well as selection， crossover， mutation， such as a series of operations, eventually we get the answer.In the paper,we use Part of

7、the liuzhou mapto experiment,and obtain a more satisfactory results,in the same time show the algorithm has practical significance. Key words: path optimization ， Genetic Algorithm，matching; Euler Algorithm目 錄Abstract21緒論41.1 研究的目的和意義41.2 車輛路徑問題的國內(nèi)外研究現(xiàn)狀41.3 主要研究內(nèi)容52灑水車路線優(yōu)化問題72.1 路徑優(yōu)化問題72.2圖論的相關(guān)知識(shí)和算法

8、72.2.1Floyd與warshall算法92.2.2Dijkstra算法92.2.3Euler算法102.2.4奇數(shù)度路口的匹配112.2.5遺傳算法113單輛灑水車的路線優(yōu)化143.1問題及模型描述143.2 路徑優(yōu)化設(shè)計(jì)思路143.3 實(shí)例分析154多輛灑水車路線優(yōu)化184.1多輛灑水車路線優(yōu)化的描述184.2 多輛灑水車路線優(yōu)化的設(shè)計(jì)思想194.3 實(shí)例的設(shè)計(jì)與實(shí)現(xiàn)204.3.1灑水車路線優(yōu)化問題的編碼214.3.2奇數(shù)度點(diǎn)的初始化214.3.3解碼及灑水車行進(jìn)路線的獲取224.3.4計(jì)算目標(biāo)函數(shù)254.3.5選擇算子264.3.6交叉算子274.3.7變異算子284.3.8參數(shù)設(shè)計(jì)

9、294.3.9多輛灑水車行進(jìn)路線的分配29結(jié)束語32參考文獻(xiàn)33致謝341緒論1.1 研究的目的和意義在經(jīng)濟(jì)高速發(fā)達(dá)時(shí)代，人們絞盡腦汁地節(jié)約投入的成本，人們費(fèi)盡心血地研制出更加高效的生產(chǎn)工具，人們不斷完善人力資源的調(diào)度理論，其目的就是為了獲得高效的工作效率，合理地人力資源配置。人們生活方式的自動(dòng)化水平是一個(gè)反映時(shí)代的發(fā)展的標(biāo)志，隨著人們生活水平的提高，人們也更加地關(guān)注著他們所生存和發(fā)展的環(huán)境，人們所生活的環(huán)境，空氣的清凈度對(duì)人們的健康有著重要的意義。為了能夠更地完成城市的除塵工作，實(shí)現(xiàn)最低的成本花費(fèi)，高效的工作效率，合理的人力資源配置這一目標(biāo)。如何合理地對(duì)灑水車的作業(yè)線路進(jìn)行優(yōu)化將成為本課題的

10、核心。由于灑水車的作業(yè)是一個(gè)N-P難問題。如何合理地規(guī)劃灑水車的作業(yè)路線，從而減少不必要的行駛路程，不但可以更好地提高工作效率，而且可以可以有效地節(jié)約燃油的成本，對(duì)本課題的研究具有重要的現(xiàn)實(shí)意義。同時(shí)當(dāng)我們?yōu)榱颂岣邽⑺噷?duì)城市除塵工作的效率，而使用了多輛灑水車同時(shí)工作時(shí)，如何地分配好各輛車之間的作業(yè)路線，在保證高效的同時(shí)做到燃油的花費(fèi)最小，將比單輛灑水車的除塵應(yīng)用更加具有現(xiàn)實(shí)意義。1.2 車輛路徑問題的國內(nèi)外研究現(xiàn)狀灑水車問題是以邊為服務(wù)的問題。類似的還有冬季除冰車，城市垃圾回收，以及最古老的中國郵遞員問題都屬于ARP問題，由于它們都存在有一個(gè)共同的特點(diǎn)，即容量限制的問題，因此灑水車的問題又稱

11、為CARP問題的一個(gè)擴(kuò)展問題。而CARP問題屬于N-P難問題。對(duì)于小數(shù)量的(20條邊或弧以內(nèi)) 還可以用精確算法來來解決(分為整數(shù)規(guī)則和分枝定界)，但是實(shí)際問題往往規(guī)模較大，如果仍采用精確算法，在運(yùn)行時(shí)間和計(jì)算的復(fù)雜度將出現(xiàn)瓶頸。到目前為至，雖然國外對(duì)邊服務(wù)的論文仍比較少，但較于去年的研究情況。關(guān)于灑水車方面的論文開始有一些了，如鄧欣等人在2007年，針對(duì)單車場灑水車線路優(yōu)化問題，將路徑優(yōu)化問題轉(zhuǎn)化CARP的擴(kuò)展，提出了改進(jìn)遺傳算法OX交叉和局部搜索(local search)的方法，通過實(shí)際生活的例子驗(yàn)證了算法的可靠性和適用性，從而保證算法在解決一定規(guī)模的CARP具有一定的實(shí)用價(jià)值1。李小花

12、等人在2008年針對(duì)多車場灑水車路線優(yōu)化的問題，將傳統(tǒng)遺傳算法的種群結(jié)構(gòu)進(jìn)行改進(jìn)，提出了車輛的時(shí)間約束來保證各輛車工作時(shí)間的均衡性，即使效果并不理想，但仍有一定的參考價(jià)值2。劉建輝等人在2008年，針對(duì)多車場路線優(yōu)化的問題，提出了一種雙層遺傳算法，處理了車場與路徑的分配，以及每條路徑的服務(wù)弧之間的優(yōu)化問題，對(duì)人力資源的優(yōu)化和減少車輛總行程，取得了很好的效果3。朱征宇等到人在2008年針對(duì)復(fù)雜CARP問題中的多車型，多路型等因素，以傳統(tǒng)的遺傳算法為基礎(chǔ)，提出了一種高性能遺傳算法(HEGA)，使得染色體代表的含意截然不同，同時(shí)加入了重優(yōu)化措施的收入，防止了隨著迭代次數(shù)的不斷增加，優(yōu)化曲線逐漸平緩，

13、算法將會(huì)收斂，而此時(shí)可能并沒有達(dá)到全局最優(yōu)，這些算法和設(shè)計(jì)思想均對(duì)現(xiàn)實(shí)問題的考慮提供了很有價(jià)值的參考4。但正剛等人在2006年針對(duì)CARP的求解問題，研究了CARP與CVRP的轉(zhuǎn)化，提出了小環(huán)路方法(實(shí)質(zhì)為禁忌)來求解CARP，驗(yàn)證了算法的準(zhǔn)確性和效率，為實(shí)際應(yīng)用奠定了基礎(chǔ)5。 同時(shí)針對(duì)車輛線路優(yōu)化的均衡性問題，認(rèn)識(shí)到了LU算法在時(shí)間對(duì)車輛的均衡性的約束不夠，從而提出了一種新的算法，主要的思想為犧牲了車輛路徑的飽和來實(shí)現(xiàn)車輛路徑的均衡性6。賈立雙等人在2008年針對(duì)，單車場車輛調(diào)度問題，提出了一種綜合運(yùn)用最鄰近算法和遺傳算法的相關(guān)原理組合實(shí)現(xiàn)了單車場多車型的調(diào)度7。李松等人在2007年針對(duì)大規(guī)

14、模車輛路徑中存在的缺陷，提出了Sweep分區(qū)技術(shù)和分區(qū)的禁忌搜索算法與相鄰區(qū)域的優(yōu)化技術(shù)相結(jié)合，有效解決了大規(guī)模車輛路徑的優(yōu)化問題8。付彤等人在2006年針對(duì)一般網(wǎng)絡(luò)上單車型車輛配送問題，借鑒Floyd算法與節(jié)約路徑法，構(gòu)造出一種在所用車輛數(shù)最少的條件下，使總配送里程最短9。張濤等人在2002年針對(duì)車輛數(shù)目不確定的車輛路徑優(yōu)化問題，提出了遺傳算法GA和禁忌搜索算法TSA相結(jié)合，主要以GA為主，把TSA用在GA的變異操作中，從而獲得了最小化距離和最小化車輛的雙目標(biāo)優(yōu)化10。陳文蘭在2007年討論了VRP問題的分類，以及介紹了近年來的相關(guān)算法的主要成果11.。相對(duì)于(容量限制弧的邊路徑問題)CAR

15、P，國外的應(yīng)用相對(duì)國內(nèi)而言，就多一點(diǎn)。Maria Candida Mourao在2004年針對(duì)垃圾回收問題的求解，提出了一種新穎的HM啟發(fā)式算法12。Anita Amberg等人針對(duì)M-CARP問題提出了一種禁忌搜索算法，不過對(duì)于M-CARP的問題的研究還處于初步探索階段，能查到的相關(guān)文獻(xiàn)不多13。Dino Ahr在06年針對(duì)中國郵遞員問題利用了一種禁忌搜索算法，但是中國郵遞員的最大最小解屬于N-P難問題，因此，在論文中主要依賴啟發(fā)式算法產(chǎn)生近似解。同時(shí)，在許多情況下人們所能得到的解也是近似或更優(yōu)的解14。Jose Brandao在2006年針對(duì)CARP問題提出一種基于禁忌搜索的啟發(fā)式算法，在

16、應(yīng)用到標(biāo)準(zhǔn)例子的各種情況下，得到結(jié)果，說明了算法處理的過程可以在合理的計(jì)算時(shí)間內(nèi)得到較高的準(zhǔn)確性15。 灑水車的路徑優(yōu)化的問題，要考慮的問題還是有很多的。就單一的目標(biāo):要求路徑最短而言。當(dāng)?shù)缆返那闆r多種時(shí)，如單行道(要求只能從某個(gè)方向行駛)，雙邊道路(中間有綠化帶)，道路中有上下坡的(要求下坡時(shí)灑水)，還有在某個(gè)十字路口只能左轉(zhuǎn)或右轉(zhuǎn)的限制是時(shí)，都需要對(duì)算法作出一定的修改。當(dāng)在城市的道路中加入了一定數(shù)量的加水點(diǎn)(水樁)時(shí)，就要對(duì)灑水車加水點(diǎn)選擇的優(yōu)先性進(jìn)行考慮。當(dāng)為了提高灑水車除塵的效率，引入多車輛同時(shí)工作時(shí)，就要對(duì)灑水車間的路徑分配的均衡性問題進(jìn)行考慮。還有當(dāng)有多個(gè)車場時(shí)，道路與車場的分配問

17、題，對(duì)道路除塵時(shí)，對(duì)車型容量的選擇(多車型)等等都會(huì)限制算法的適用性1.3 主要研究內(nèi)容在原來單輛灑水車的基礎(chǔ)上，實(shí)現(xiàn)多輛灑水車的線路優(yōu)化問題。由于原來做的是單輛灑水車在無限容量下的情況，這樣一來，只要形成一條最短回路就可以了。現(xiàn)在要做的是，把這種無限容量下的路線優(yōu)化變得現(xiàn)實(shí)一點(diǎn)，即把無限容量的的情況考慮成有容量限制的情況，這樣不但增加了課題的復(fù)雜性，而且實(shí)現(xiàn)了課題的現(xiàn)實(shí)性，在單輛灑水車現(xiàn)實(shí)性的前提下，為了可以更好地提高灑水車的作業(yè)效率，實(shí)現(xiàn)多輛灑水車同時(shí)進(jìn)行城市的除塵工作。本文的研究內(nèi)容主要有以下幾個(gè)方面首先從線路優(yōu)化問題出發(fā)，介紹了常見的兩類線路優(yōu)化問題VRP和CARP，分析了兩者的應(yīng)用區(qū)

18、別，明確灑水車線路優(yōu)化問題的數(shù)學(xué)模型，并說明了灑水車在線路優(yōu)化的具體設(shè)計(jì)時(shí)用到的一些算法，其中遺傳算法是整個(gè)尋優(yōu)求解的中心環(huán)節(jié)，而warshall，Dijkstra，Euler算法只是作為遺傳算法解碼計(jì)算的輔助算法。其次介紹了單輛灑水車線路優(yōu)化的總體設(shè)計(jì)思路結(jié)果。最后對(duì)多輛灑水車線路優(yōu)化問題以多輛車作業(yè)分配和總行程最小為目標(biāo)，提出了容量分割的方法并進(jìn)行了詳細(xì)的設(shè)計(jì)，包括路線優(yōu)化的模型描述，設(shè)計(jì)原理，編碼的方式與確定，種群的初始化，如何對(duì)染色體進(jìn)行解碼，轉(zhuǎn)換到問題的現(xiàn)實(shí)解(難點(diǎn))，計(jì)算目標(biāo)函數(shù)及適應(yīng)度函數(shù)和各種操作算子進(jìn)化方式的確定(重點(diǎn))。本文用MATLAB7.0在Window XP下進(jìn)行編程

19、并調(diào)試，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行了比較和分析。2灑水車路線優(yōu)化問題2.1 路徑優(yōu)化問題說到路徑優(yōu)化問題，我們會(huì)很自然地就想起車輛路徑問題(Vehicle Routing Problem，VRP)，因?yàn)榕渌蛦栴}在商業(yè)領(lǐng)域的應(yīng)用十分廣泛。VRP的一般描述為:用于送貨的若干輛相同型號(hào)的車從配送中心出發(fā)，到不同的地理位置的客戶那里去送貨，然后返回配送中心，要求每輛車只能出發(fā)一次，任何一個(gè)客戶有且只有一輛車訪問，并且所配送的貨物不能超過車輛的載重量，求解一種配送方案使得配送總成本最少。VRP問題根據(jù)不同的標(biāo)準(zhǔn)可以分為不同的類別。根據(jù)車輛是否有容量約束，可分為有容量約束的VRP問題(貨擔(dān)郎問題)，和無容量約束的V

20、RP問題(TSP問題);根據(jù)貨運(yùn)任務(wù)的完成是否有時(shí)間要求，又可分為有時(shí)間約束和無時(shí)間約束兩種。對(duì)于有時(shí)間約束的VRP還可以進(jìn)一步分為帶軟時(shí)間窗的VRP和帶硬時(shí)間窗的VRP。從1959年的VRP問題的開始提出到現(xiàn)在的半世紀(jì)以來，國內(nèi)外對(duì)VRP的研究已經(jīng)相當(dāng)成熟，在各類VRP(如有時(shí)間窗、多車場等)的研究上都取得了豐富成果，采用的解決方法也多種多樣，可分為精確算法(如整數(shù)規(guī)劃、分枝定界等)和啟發(fā)式算法(禁忌搜索、遺傳算法、蟻群算法等)兩大類。還有另外一種路徑問題，也是本文的路徑優(yōu)化問題，那就是與VRP相類似的弧路徑規(guī)劃問題(Arc Routing Problem，ARP)這類問題在基礎(chǔ)設(shè)施中的應(yīng)用

21、就相對(duì)就要多一些。本文研究的灑水車的路徑優(yōu)化問題就屬于特殊的ARP問題，由于灑水車的城市除塵作業(yè)，車輛本身帶有容量限制，因而灑水車路徑優(yōu)化問題屬于“容量限制弦路徑車輛行駛問題”。有容量限制的ARP，在現(xiàn)實(shí)中擁有廣泛的應(yīng)用背景，如前面提到的灑水車作業(yè)路線安排，以及冬季除冰車作業(yè)路線安排，城市垃圾車作業(yè)路線安排，還有城市輸電線路的檢查等。這時(shí)，我們會(huì)提出這樣一個(gè)疑問:在前面的提到的兩種路線優(yōu)化問題中(VRP問題與CARP問題)，它們都可以有容量限制方面的約束條件，到底是怎樣的一種分類方式把它們分成了兩種不同的路線優(yōu)化問題。這個(gè)劃分的關(guān)鍵就在于它們?cè)诰€路優(yōu)化中的具體服務(wù)的對(duì)象是不一完全一樣的，對(duì)于V

22、RP問題而言，它主要是以點(diǎn)的服務(wù)主，而對(duì)于CARP問題，它主要是以邊的服務(wù)為主。如果說到了這里還是不大清楚，也許可以通過一個(gè)問題的對(duì)比來說明。例如VRP問題中的車輛的配送問題(不帶時(shí)間窗的)，因?yàn)檐囕v要裝載貨物，因此有一定的裝載容量。同樣的對(duì)于CARP問題中的灑水車路線優(yōu)化問題，車輛本身就有一定的裝水容量。這是相同的地方。然而不同的就是它們的服務(wù)對(duì)象是不同的。車輛的配送只要把貨物送到指定的點(diǎn)就可。配送的本質(zhì)在于遍歷所有的點(diǎn)，所以不用遍歷所有的邊。而灑水車的路線優(yōu)化則要遍歷完所有的邊。邊集往往包含了點(diǎn)集，而點(diǎn)集不一定可以包含邊集。也正是因?yàn)檫@點(diǎn)的不同這兩類問題在路線優(yōu)化時(shí)，即有相似點(diǎn)，但又不相同

23、。2.2圖論的相關(guān)知識(shí)和算法圖論中所討論的”圖”，不是微積分，解析幾何，幾何學(xué)中討論的圖形，而是客觀世界中某些具體事物間聯(lián)系的一個(gè)數(shù)學(xué)抽象。如二元關(guān)系圖，在關(guān)系圖，在關(guān)系圖中，我們不考慮點(diǎn)的位置及邊線的長短曲直，而只關(guān)心哪些點(diǎn)之間有線相連通。這種數(shù)學(xué)抽象就是”圖”的概念。圖論在灑水車路線優(yōu)化過程中起到的作用是:實(shí)現(xiàn)客觀道路網(wǎng)到數(shù)學(xué)模型上的抽象。圖是一個(gè)三元組，包括結(jié)點(diǎn)集合，邊集合以及關(guān)聯(lián)函數(shù)。無向圖:每條邊都是無向邊的圖稱為無向圖。有向圖:每一條邊都是有向邊的圖稱為有向圖。連通圖:如果無向圖G中每一對(duì)不同的頂點(diǎn)X和Y都有一條路，則稱G是連通圖。強(qiáng)連通圖:如果有向圖D任何一對(duì)結(jié)點(diǎn)之間都可以相互到

24、達(dá)，則稱這個(gè)有向圖是強(qiáng)連通的。弱連通圖:若在有向圖D的基礎(chǔ)圖是連通的，則稱有向圖D是弱連通的。簡單圖:無環(huán)并且無平行邊的圖稱為簡單圖。環(huán):兩端點(diǎn)相同的邊稱為環(huán)或稱為自回路。平行邊:兩個(gè)結(jié)點(diǎn)間方向相同的若干條邊稱為平行邊或重邊。NP問題:至今既沒有找到多項(xiàng)式算法，又不能證明它不存在多項(xiàng)式算法一類問題稱為NP問題。度數(shù):設(shè)G是任意圖，X為G的任意結(jié)點(diǎn)，與結(jié)點(diǎn)X關(guān)聯(lián)的邊數(shù)(一條環(huán)要計(jì)算兩次)稱為X的度數(shù)(degree)。入度與出度:設(shè)D是任意有向圖，X為D的任意一結(jié)點(diǎn)，射入X的邊數(shù)稱為X的入度(in-degree) ，射入X的邊數(shù)稱為X的入度(in-degree)。最短路徑:給定一個(gè)起始點(diǎn)S和一個(gè)結(jié)

25、束頂點(diǎn)T，在圖中找出從S到T的一條最短路徑。我們將起始點(diǎn)稱為”源點(diǎn)”，結(jié)束點(diǎn)T稱為”匯點(diǎn)”。單源最短路徑:給定一個(gè)起始點(diǎn)S找出從S到圖中其他各頂點(diǎn)的最短路徑。最短路徑的操作實(shí)質(zhì)稱為”淞弛”。開始進(jìn)行最短路徑算法時(shí)，只知道網(wǎng)的邊和權(quán)值，隨著要遍歷中間點(diǎn)的加入，可以獲得一條新的路徑距離，如果在這一過程中出現(xiàn)這個(gè)新獲得的路徑距離比保存的記錄值小，則把這個(gè)新得到的最小值傳送給保存的最小記錄中。這樣的一個(gè)不斷比較并更新最小值的遍歷過程?？梢孕蜗蟮剡@樣來描述，在兩個(gè)頂點(diǎn)之間用一根橡皮筋系起來，后把它拉緊繞過另一個(gè)頂點(diǎn)，然后在這三個(gè)點(diǎn)的內(nèi)部找到一個(gè)新的點(diǎn)，(相當(dāng)于找到了新的當(dāng)前最小值)，然后把被繞過的那個(gè)頂

26、點(diǎn)拔掉，這樣就在橡皮筋的張力作用下，而收縮，直到橡皮筋打在了那個(gè)新的頂點(diǎn)上。這樣的一個(gè)過程就好像一張拉滿的弓，慢慢松開的過程。 在灑水車的線路優(yōu)化過程中，為了得到線路的最小值，在求解一條回路的過程中，首先要把實(shí)際的作業(yè)圖轉(zhuǎn)化到圖的模型下，其次通過Floyd求解任意兩點(diǎn)間的距離值，但又因?yàn)閳D中存在奇數(shù)度頂點(diǎn)而無法實(shí)現(xiàn)回路，所以要消除奇數(shù)度頂點(diǎn)。再次通過Dijkstra獲得在遺傳算法隨機(jī)編碼下對(duì)應(yīng)奇數(shù)度點(diǎn)間的具體路徑，接著用Euler求得對(duì)應(yīng)編碼下的一條回路，最后通過遺傳算法的尋優(yōu)思想獲得所有回路中線路值最小的一條。2.2.1Floyd與warshall算法為了在灑水車線路優(yōu)化中求得求得轉(zhuǎn)換模式下

27、的任意兩點(diǎn)間距離，使用了Floyd算法已知矩陣A=(aij)m*l，B=(bjk)l*n， C=A*B=(Cij)m*n， 其中 Cij =min(ai1+b1j，ai2+b2j，ail+blj)已知矩陣A=(aij)m*n， B=(bij)m*n， 規(guī)定其中dij=min(aij，bij) 可以利用上面定義的運(yùn)算求任意兩點(diǎn)間的最短矩離。已知N階加權(quán)簡單圖G，設(shè)D=(dij)n*n是圖G的邊權(quán)矩陣，即dij=w(i，j)(若G是有向圖，則dij=w)，若結(jié)點(diǎn)i到結(jié)點(diǎn)j無邊相連時(shí)，則取dij=。 然后依次計(jì)算出矩陣D2，D3，Dn及S其中D2=D*D=(d2ij)n*nD3=D2*D=(d3ij

28、)n*nDn=Dn-1*D=(dnij)n*n由定義可知，dkij表示從結(jié)點(diǎn)i到j(luò) 經(jīng)k邊的路(在有同圖中即為有向路)中的長度最短者，而Sij為結(jié)點(diǎn)i到j(luò)的所有路(若是有向圖，即為有向路)中的長度最短者。 不難看出，F(xiàn)loyd算法的時(shí)間復(fù)雜性是O(n4)，下面看介紹求任意兩點(diǎn)間最短路的Warshall算法。已知n階加權(quán)簡單G，設(shè)D=(dij)n*n是圖G的邊權(quán)矩陣。(1) 輸入D;(2) k:=1;(3) i:=1;(4) dij:=min(dij，dik+dkj)，j=1，2，n;(5) i:=i+1，若，轉(zhuǎn)(4);(6) k:=k+1，若，轉(zhuǎn)(3);否則停止。該算法是對(duì)i，j，k進(jìn)進(jìn)行行循

29、環(huán)，故它的復(fù)雜性是O(n3)，即對(duì)矩D進(jìn)行k次修改。2.2.2Dijkstra算法在灑水車線路優(yōu)化中，一條Euler回路的獲得要求圖中沒有奇數(shù)度頂點(diǎn)，而圖中必定存在奇數(shù)度頂點(diǎn)。為了消除圖中奇數(shù)度頂點(diǎn)，主要通過Dijkstra的指定點(diǎn)路徑實(shí)現(xiàn)來完成。迪克斯屈拉算法求出一個(gè)連通加權(quán)加權(quán)簡單圖中從指定結(jié)點(diǎn)(如a)到指定終點(diǎn)(如z)的最短路。邊i，j的權(quán)w(i，j)0，且結(jié)點(diǎn)x的標(biāo)號(hào)為L(x)。L(z)是從指定結(jié)點(diǎn)a到z的最短路的長度。Dijkstra的算法描述:對(duì)于一個(gè)所有權(quán)都為正數(shù)的加權(quán)連通簡單圖G，G中有頂點(diǎn)a=v0，v1，vn=z和權(quán)w(vi，vj)，若vi，vj不是G中的邊，則w(vi，vj

30、)=，(1)初始化標(biāo)志，令L（a）=0，其余結(jié)點(diǎn)為無窮大，并定義一個(gè)記錄現(xiàn)實(shí)路徑的集合如S為空集。（2）第一次時(shí)把起點(diǎn)a存入S中，并逐個(gè)比較當(dāng)前記錄的結(jié)點(diǎn)L（a）+w(a，u)與L（u）的大小，u為不屬于S的頂點(diǎn)，如果L（a）+w(a，u)L（u），則L（a）+w(a，u)= L（u），記下這一輪中結(jié)點(diǎn)標(biāo)號(hào)的最小值，并把這一標(biāo)號(hào)送入S中，這樣就給S中添加帶最小標(biāo)記的頂點(diǎn)并且更新不在S的頂點(diǎn)，當(dāng)遍歷完所有的頂點(diǎn)時(shí)，也就相應(yīng)地得到了這個(gè)指定起點(diǎn)和終點(diǎn)的現(xiàn)實(shí)路徑了。當(dāng)然是一種合理的描述，但是考慮到在前面已經(jīng)用到了Floyd算法實(shí)現(xiàn)任意兩點(diǎn)之間的距離值（邊權(quán)），因此在實(shí)現(xiàn)Dijkstra時(shí)，可以充分地

31、利用前面得到的任意兩點(diǎn)間的邊權(quán)結(jié)果。這樣一來就可以大大提高求解結(jié)果的快速性，而沒有必要再重新地由已知的頂點(diǎn)維數(shù)以及邊權(quán)初始化開始一一遍歷。2.2.3Euler算法 在完成了Dijdstra算法以后，灑水車的作業(yè)圖就不存在奇數(shù)度頂點(diǎn)，從而可以形成一條Euler回路。這對(duì)應(yīng)于灑水車的一種作業(yè)方案。歐拉路:對(duì)于給定無孤立結(jié)點(diǎn)的無向圖G，經(jīng)過圖G每邊一次且一次的跡稱為歐拉路。歐拉回路:對(duì)于給定無孤立結(jié)點(diǎn)的無向圖G，經(jīng)過圖G每邊一次且一次的回路稱為歐拉回路。歐拉圖:含有歐拉回路和無向連通圖與含有向歐拉回路的弱連通有向圖，統(tǒng)稱歐拉圖。 歐拉回路的充分必要條件:連通圖G具有歐拉回路當(dāng)且僅當(dāng)它的每點(diǎn)都有偶數(shù)度

32、。Euler回路的遍歷算法可以用Fleury算法出實(shí)現(xiàn)。其思想是:(1) 任意選取一個(gè)頂點(diǎn)V0，置W0=V0(2) 假定跡(若是有向圖，則是有向圖)Wi=v0e1v1eivi已經(jīng)選出，那么用下列方法從E(G)e1，e2，ei中選取ei+1(a) ei+1與vi關(guān)聯(lián)(若是有向圖，ei+1以vi為起點(diǎn)(b) 除非沒有別的邊可以選擇，ei+1不是Gi=Ge1，e2，ei的割邊。(3) 當(dāng)(2)不能執(zhí)行時(shí)，停止。否則讓i+1i，轉(zhuǎn)(2)顯然，F(xiàn)leury算法作出了G的一條跡。2.2.4奇數(shù)度路口的匹配因?yàn)椴煌钠ヅ浣Y(jié)果對(duì)應(yīng)不同的Euler回路，一條Euler回路對(duì)應(yīng)灑水車作業(yè)的一種方案，奇數(shù)度路口的匹

33、配就是要盡可能地找出所有的灑水車作業(yè)方案。同時(shí)它也是實(shí)現(xiàn)Dijkstra指定點(diǎn)的數(shù)據(jù)準(zhǔn)備。對(duì)于一個(gè)任意的圖，它有沒有一條歐拉回路，就看連通圖G中的每一個(gè)點(diǎn)的度數(shù)是不是都為偶數(shù)。如果說是偶數(shù)，那么毫無疑問，可以從連通圖中獲得一條歐拉回路。但是在實(shí)際的應(yīng)用中我們對(duì)實(shí)際情況所轉(zhuǎn)化的圖往往是帶有奇數(shù)度的點(diǎn)。這種情況下是不滿足形成歐拉回路的充要條件。如果我們又很想用這種方法，那么只能對(duì)不滿足歐拉充要條件的進(jìn)行修改。就是對(duì)對(duì)些是奇數(shù)度的點(diǎn)進(jìn)行兩兩組合，從而讓奇數(shù)度的點(diǎn)變?yōu)榕紨?shù)。這種方法在圖論中稱為最優(yōu)球游的奇偶點(diǎn)圖上作業(yè)法。其實(shí)這樣的設(shè)計(jì)思想還有別外一個(gè)好處，因?yàn)镋uler本身就是為了要獲得一條路徑最小的

34、回路，然而這條回路的最終選擇是通過遺傳算法來實(shí)現(xiàn)的，即由遺傳算法的適應(yīng)度函數(shù)來決定。 遺傳算法的應(yīng)用或要達(dá)到它的一種較好的實(shí)驗(yàn)效果，那就不得不考慮遺傳算法的尋優(yōu)能力。粗略地講要求遺傳算法設(shè)計(jì)的染色體長度或染色體的基因位數(shù)(在遺傳算法一章中會(huì)有詳細(xì)的說明)在20位左右。因此奇偶點(diǎn)圖上作業(yè)法的奇數(shù)度點(diǎn)之間的組合，它是考慮了遺傳算法的編碼問題對(duì)尋優(yōu)效果的響影。雖然這樣的思想不僅考慮了遺傳算法的編碼的尋優(yōu)能力而且實(shí)現(xiàn)了在奇數(shù)度點(diǎn)下的Euler回路。給我們帶來了很大的欣慰。但是在原來的圖中用編程去實(shí)現(xiàn)的時(shí)候會(huì)產(chǎn)生錯(cuò)誤。即那次是本來走的通路，那次是因?yàn)槠鏀?shù)點(diǎn)的原因而使奇數(shù)度點(diǎn)間的通路要重復(fù)行走，在計(jì)算機(jī)中

35、并沒有可以自動(dòng)識(shí)別。所以我們又要加入虛擬點(diǎn)以區(qū)分要重復(fù)行走的那一次或幾次。所謂虛擬就是實(shí)際上不存在，只是作為一種標(biāo)志罷了，確切的說，在實(shí)際上這些路線仍然是要走的。說它是虛的是針對(duì)于優(yōu)化問題中的現(xiàn)實(shí)意義而言，那些重復(fù)要走的邊針對(duì)于優(yōu)化過程不作為要考慮的過程，只能是標(biāo)記用于區(qū)分:那一次是要進(jìn)行除塵作業(yè)，那一次只是作為一種輔助Euler回路的形成，而并沒有把它作為要進(jìn)行除塵作業(yè)的路線。因?yàn)橹貜?fù)邊是不作為為除塵計(jì)算考慮。所以要加入虛擬點(diǎn)來進(jìn)行除塵計(jì)算的區(qū)分。2.2.5遺傳算法在人工智能領(lǐng)域中，有不少問題需要在復(fù)雜而龐大的搜索空間中尋找最優(yōu)或準(zhǔn)最優(yōu)解。像VRP問題和規(guī)劃問題等組合優(yōu)化問題就是典型的的例子

36、。在求解此類問題時(shí)，若不肥利用問題的固有知識(shí)來縮小搜索空間則會(huì)產(chǎn)生搜索的組合爆炸。因此，研究能在搜索過程中自動(dòng)獲得和積累有關(guān)搜索過程，從而得到最優(yōu)解或準(zhǔn)最優(yōu)解的通用搜索算法一直是令人矚目的課題。遺傳算法就是這樣一種特別有效的算法。它的主要特點(diǎn)是簡單，通用，具有全局搜索性，搜索時(shí)只使用適應(yīng)度函數(shù)，不用其他輔助信息，魯棒性強(qiáng)，遺傳算法的基本思想是優(yōu)勝劣汰，適者生存。解的性能越優(yōu)，越容易進(jìn)入一下代進(jìn)化，將其優(yōu)良基因承下去，直至搜索到滿意解或近似最優(yōu)解。模擬進(jìn)化的方法主要是用于求解組合優(yōu)化問題以及存在不可微的目標(biāo)函數(shù)或約束條件的復(fù)雜的非線性優(yōu)化問題。常規(guī)的數(shù)學(xué)優(yōu)化技術(shù)是基于梯度尋優(yōu)技術(shù)，計(jì)算速度快，但

37、要求優(yōu)化問題具有可微性，且通常只能求得局部最優(yōu)解，而模擬進(jìn)化方法無可微性要求，適用于任意優(yōu)化問題，而且由于它們采用隨機(jī)優(yōu)化技術(shù)，保證了有較大的概率求得全局最優(yōu)解。從前面的說明我們已經(jīng)知道，一種匹配對(duì)應(yīng)一條回路，一條回路對(duì)應(yīng)一種灑水車的作業(yè)方案.在灑水車的作業(yè)圖中共有22個(gè)奇數(shù)度頂點(diǎn)，這22位的排列組合是一個(gè)非常大的數(shù)目，如果說要精確地求解，那么花費(fèi)的計(jì)算時(shí)間是十分驚人的，因此，我們想通過GA的隨機(jī)優(yōu)化技術(shù)來實(shí)現(xiàn)解的獲得.編碼:這是應(yīng)用GA時(shí)要解決的首要問題，也是設(shè)計(jì)GA的一個(gè)關(guān)鍵。編碼方法除了個(gè)體的染色體排列形式之外，它還決定了個(gè)體從搜索空間的基因型變換到解空間的表現(xiàn)型時(shí)的解碼方法。一個(gè)好的編

38、編碼方法，有可能會(huì)使得交叉運(yùn)算，變異運(yùn)算等GA操作可以簡單地實(shí)現(xiàn)和執(zhí)行。編碼原則:1.(有意義積木塊編碼原則):就使用能易于產(chǎn)生與所求問題相關(guān)的且有低階，短定義長度模式的編碼方案。2.(最小字符編碼原則):就使用能使得問題得到自然表示或描述的具有最小編碼字符集的編碼方案。編碼方法:大體上可以分為三類，二進(jìn)制編碼，浮點(diǎn)數(shù)編碼，符號(hào)編碼。 二進(jìn)制編碼是GA中最常用的一種編碼方法，是由0 和1所組成的二進(jìn)制符號(hào)串。符號(hào)編碼;是指個(gè)體染色體編碼串中的基因值取自一個(gè)無數(shù)值含義，而只有代碼含義的符號(hào)集。如A，B，C，D或1，2，3，4，這種編碼的主要優(yōu)點(diǎn):1.符合有意義積木塊編碼原則2.便于在GA中利用所

39、求解問題的專門知識(shí)3.便于GA與相關(guān)近似得法的混合使用。 評(píng)價(jià)個(gè)體適應(yīng)度的一般過程是:1.對(duì)個(gè)體編碼串進(jìn)行解碼處理后，可得到個(gè)體的表現(xiàn)型。2.由個(gè)休的表現(xiàn)型可計(jì)算出對(duì)應(yīng) 個(gè)體勞動(dòng)的目標(biāo)函數(shù)值。3.根據(jù)最優(yōu)化問題的類型，設(shè)計(jì)目標(biāo)函數(shù)值與適應(yīng)度間的轉(zhuǎn)換規(guī)則(一般目標(biāo)函數(shù)值越好其對(duì)應(yīng)的適應(yīng)度值越大)。在計(jì)算適應(yīng)度函數(shù)的過程中，需要對(duì)編碼形式下的染色體進(jìn)行解碼，才可以計(jì)算其目標(biāo)函數(shù)，進(jìn)而得到其對(duì)應(yīng)轉(zhuǎn)換法則下的適應(yīng)度函數(shù)值。適應(yīng)度值的尺度變換:主要有線性變換，乘冪尺度變換和指數(shù)尺度變換。這變換思想是針對(duì)選擇過程中，存在初期易于發(fā)生早熟現(xiàn)象。而在后期個(gè)體的適應(yīng)度差異不大，從而無法對(duì)重點(diǎn)區(qū)域的重點(diǎn)搜索。需要

40、對(duì)個(gè)體的適應(yīng)度適當(dāng)?shù)胤糯?，提高個(gè)體間差異和競爭。選擇操作建立在對(duì)個(gè)體的適應(yīng)度進(jìn)行評(píng)價(jià)的基礎(chǔ)之上。選擇操作的主要目的是為了避免基因缺失，提高全局收斂性和計(jì)算效率。常用的方法有比例選擇算子(賭盤法)。其基本思想是，各個(gè)個(gè)體被選中的概率與其適應(yīng)度大小成正比。即適應(yīng)度越高的個(gè)體被選中的概率也越大，反之越小。由于是隨機(jī)操作的原因 ，有時(shí)甚至連適應(yīng)度較高的個(gè)體也選擇不上。從多樣性分析，這恰恰是一個(gè)優(yōu)點(diǎn)。交叉算子的設(shè)計(jì)和實(shí)現(xiàn)與所研究的問題密切相關(guān)，一般要求它不要太多地破壞個(gè)體編碼串中表示優(yōu)良性狀的優(yōu)良模式，又要能夠有效地產(chǎn)生出一些較好的新個(gè)體模式。另外交叉算子的設(shè)計(jì)要和個(gè)體編碼設(shè)計(jì)統(tǒng)一考慮。交叉一般有單點(diǎn)交

41、叉和雙點(diǎn)交叉。GA中的所謂變異運(yùn)算，是指將個(gè)體染色體編碼串中的某些基因座上的基因值用相應(yīng)基因座上的基因值來相互替換，從而形成一個(gè)新的個(gè)體。從遺傳運(yùn)算過程中產(chǎn)生新個(gè)體的方面來說。交叉運(yùn)算是產(chǎn)生新個(gè)體的主要方法，決定了GA的全局搜索能力，而變異只是產(chǎn)生新個(gè)體的輔助方法，但它是必不可少的步驟。因?yàn)樗鼪Q定了GA的局部搜索能力。3單輛灑水車的路線優(yōu)化3.1問題及模型描述灑水車路徑優(yōu)化優(yōu)化問題是以道路為服務(wù)對(duì)象的車輛路徑問題，并帶有容量限制，則問題可以看成是一個(gè)CARP的子問題。令作業(yè)圖G由無向邊組成。G=(V，E)。其中V表示圖G的頂點(diǎn)集合，在這這些頂點(diǎn)中有一點(diǎn)代表車場，可以任意給定。E表示圖G邊集合。

42、假設(shè)車場有一輛灑水車，讓它從出發(fā)，對(duì)所有的邊進(jìn)行有且僅有一次的除塵工作，并且有一個(gè)重要的前提:要求進(jìn)行完所有邊的除塵的需水量q小于這輛灑水車的總裝水容量W。在這個(gè)前提下實(shí)現(xiàn)該灑水車的行駛距離最小的目的。因此目標(biāo)函數(shù)為灑水車的總花費(fèi)最小。即MinZ=Cost(T) (3.1)相應(yīng)的約束條件為: (3.2) (3.3)t=m,其中m表示邊的條數(shù) (3.4) (3.5)公式(3.4)和(3.5)共同保證每個(gè)服務(wù)邊都有且僅被服務(wù)一次。3.2 路徑優(yōu)化設(shè)計(jì)思路根據(jù)單輛灑水車的問題描述，我們可以把握兩個(gè)重要的信息點(diǎn)，就是1。要對(duì)圖中所有的邊都要進(jìn)行有且僅有一次的除塵工作(即圖中所有邊都有走一次)，這是一個(gè)

43、固定的值，無論你如何優(yōu)化這一個(gè)距離是必需的。但這又不是實(shí)際行駛距離的最小值，因?yàn)槿我庖黄鞘械牡缆肪W(wǎng)，很難保證每一個(gè)路口的度數(shù)都是偶數(shù)，也就是說必定存在路口的度數(shù)是奇數(shù)的情況，那么由歐拉回路形成的充分必要條件可知，在圖中是無法得到一條歐拉回路，如果說要遍歷圖中每條邊有且僅一次，那么就要對(duì)某些邊進(jìn)重復(fù)地行駛。因此我們可以得到這樣一個(gè)結(jié)論:總的花費(fèi)=所有邊的花費(fèi)+重復(fù)行駛邊的花費(fèi)。如果要總的花費(fèi)最小，那么在所有邊的花費(fèi)是一個(gè)固定值的條件下，只要重復(fù)邊的花費(fèi)最小，則有總的花費(fèi)最小。單輛灑水車的路徑優(yōu)化思想用了四個(gè)算法把路徑優(yōu)化分為了四個(gè)相對(duì)獨(dú)立的部分。每一部分完成不同的工作，最終實(shí)現(xiàn)一條總的花費(fèi)最小

44、的除塵路徑。步驟如下:1. 用Floyd算法算出各奇數(shù)度點(diǎn)之間的距離，這樣就得到了任意奇數(shù)度點(diǎn)之間的距離矩陣。這一個(gè)數(shù)值矩陣將成為GA實(shí)現(xiàn)最優(yōu)的奇數(shù)度路口的匹配提供了一張選擇，比較的數(shù)據(jù)表。2. 通過利用遺傳算法的隨機(jī)優(yōu)化技術(shù)，保證以較大的概率求得全局的最優(yōu)解的優(yōu)點(diǎn)，實(shí)現(xiàn)了各個(gè)奇數(shù)度路口之間的最優(yōu)匹配。3. 接著再對(duì)GA獲得的最優(yōu)匹配結(jié)果用Dijkstra求得對(duì)應(yīng)匹配的現(xiàn)實(shí)路徑，這樣就對(duì)原來的作業(yè)圖補(bǔ)成了一個(gè)各各路口都是偶數(shù)度的路口。從而滿足了Euler形成的條件。4. 最后通過Euler回路算法實(shí)現(xiàn)單輛灑水車的具體優(yōu)化路徑。也是總花費(fèi)最小的結(jié)果。3.3 實(shí)例分析實(shí)驗(yàn)設(shè)計(jì)使用的是柳州某區(qū)域部分

45、路段見下圖所示圖1 柳州市某區(qū)域地圖圖2 圖1的加權(quán)圖圖中線條表示各條需要的道路，帶有數(shù)字的圓圈和方框表示路口，且圓圈表示偶數(shù)度路口，方框表示奇數(shù)度路口，數(shù)字表示路口的標(biāo)號(hào)。經(jīng)過調(diào)查知道，該區(qū)域地圖的道路對(duì)于灑水車來說都是單行道路即灑水車只需要行走一遍就可以了。用遺傳算法實(shí)現(xiàn)奇數(shù)度路口的匹配，得到的最優(yōu)匹配結(jié)果為:Value=2037 3-4 17-18 21-20 19-13 15-16 7-8 12-14 11-6 5- 22 10-9 2-1 用Dijkstra算法求出固定路口到距離及路徑，要求得出兩個(gè)匹配好的奇數(shù)度路口的匹配路線，得到的結(jié)果如下:347900

46、17-182021310.00 20-211913 651.0019-24-26-27-131516110.0015-1678 1240012-32-31-14116 297.0011-43-652258.005-22910 299.00 9-101271.001-2生成Euler閉跡回路。由Euler可知Euler回路里不允許有重復(fù)邊的存在，但是在灑水車線路優(yōu)化中對(duì)奇數(shù)點(diǎn)進(jìn)行了匹配的同時(shí)，用Dijkstra實(shí)現(xiàn)匹配奇數(shù)度點(diǎn)間的具體路徑的同時(shí)引入了重復(fù)邊，這會(huì)使得Euler回路無法完成。因此要加入虛擬點(diǎn)，這樣重復(fù)的那條道路就被劃分為兩條道路，從而可以得到一條Eule

47、r閉跡回路。虛擬點(diǎn)的手工安排如下:奇數(shù)度路呂匹配實(shí)現(xiàn)路徑虛擬點(diǎn)343-59-459171817-1873202120-74-2174191319-71-24-70-26-69-27-68-1371 70 69 68151615-72-1672787-63-863121412-65-32-66-31-67-1465 66 67116 11-62-43-61-662 615225-60-22609109-64-1064121-58-258通過以上幾步，設(shè)點(diǎn)43為停車場，即回路的始終點(diǎn)，在這里只研究有一個(gè)停車場的情況，并且不考慮加水地點(diǎn)和時(shí)間。最后得到的車輛行駛路線為:43-6-49-5-48-46

48、-44-45-46-47-48-49-22-60-5-22-47-43-39-34-33-40-39-36-51-6-61-43-40-41-42-44-11-62-43-51-52-4-59-3-38-2-58-1-2-25-9-8-7-53-10-9-64-10-55-53-50-49-52-37-38-8-63-7-3-4-50-45-42-12-30-18-17-24-19-54-18-73-17-28-26-16-15-25-23-16-72-15-35-1-37-36-35-24-13-14-31-29-27-13-68-27-26-24-23-21-20-57-21-74-20-

49、54-56-19-71-24-70-26-69-27-28-29-30-31-32-12-65-32-33-14-67-31-66-32-41-11-434多輛灑水車路線優(yōu)化4.1多輛灑水車路線優(yōu)化的描述多輛灑水車同量進(jìn)行城市的除塵作業(yè)時(shí)，車輛均從車場(加水點(diǎn))出發(fā)，依某條路徑行駛并對(duì)需噴灑的道路服務(wù)，水用盡后返回加水繼續(xù)噴灑，重復(fù)此過程直至所有需求道路均得到服務(wù)，問題是要獲得所有車輛的行駛路徑，且盡量保證整個(gè)總花費(fèi)Cost(即行駛總距離)最小。這樣就可以有目標(biāo)函數(shù)為: MinZ表示總花費(fèi)最小的標(biāo)志，Ti表示第i條路徑，Cost(Ti)表示第i條路徑的花費(fèi)，而一個(gè)可行解包含了k條路徑，MinZ

50、就等于這k條路徑花費(fèi)的加權(quán)。由于灑水車自身有容量限制的問題，故存在裝水容量的約束:要求每條服務(wù)路徑的需水量q(Ti)小于灑水車的裝載容量Q，故有，其中Tij表示第i條路徑中的第j條服務(wù)弧，第i條路徑Ti中包含了第i條路徑的容量計(jì)算為:qi=Li*pi其中Li道路i的長度，pi為相應(yīng)道路的噴灑系數(shù)。 第i條路徑的花費(fèi)計(jì)算公式為:其中第Ti條路徑的花費(fèi)為:從車場出發(fā)到第一條服務(wù)邊的最小距離，接著對(duì)第一條服務(wù)邊到倒數(shù)第二條服務(wù)邊進(jìn)行加權(quán)，每一次加權(quán)的內(nèi)容為:對(duì)應(yīng)的服務(wù)邊長度加上有重復(fù)行駛的最小距離(也稱非服務(wù)邊或可以認(rèn)為是對(duì)奇數(shù)度頂點(diǎn)匹配的距離)，然后加上最后一條服務(wù)邊的長度，最后加上回到車場的最小

51、距離。同時(shí)也有一個(gè)服務(wù)邊的條件約束:即要保證每一條服務(wù)邊都要被服務(wù)到，并且任意兩條服務(wù)邊之間不能被重復(fù)。還有綜上所述，多輛灑水車的CARP數(shù)學(xué)模型如下: (4.1) (4.2) (4.3)qi=Li*pi (4.4) (4.5) (4.6)4.2 多輛灑水車路線優(yōu)化的設(shè)計(jì)思想多輛灑水車的線路優(yōu)化是單輛灑水車線路優(yōu)化的延伸，由前面單輛灑水車線路優(yōu)化的設(shè)計(jì)思想可以知道:它主要的側(cè)重點(diǎn)在于用遺傳算法得到奇數(shù)度點(diǎn)之間的最優(yōu)匹配(因?yàn)樗袃蓚€(gè)很重要的前提就是，所有邊都是服務(wù)邊，并且不用考慮灑水的容量不足的問題)，就可以對(duì)應(yīng)到優(yōu)化的結(jié)果上來。但是在現(xiàn)實(shí)設(shè)計(jì)中，不考慮灑水車的容量問題是不現(xiàn)實(shí)的，灑水車在城市

52、的除塵作業(yè)中必定會(huì)存在加水的問題，這樣灑水車在線路優(yōu)化的過程中必定要考慮一個(gè)問題，那就是灑水車沒有水以后要回到車場(加水點(diǎn))，并重新回到?jīng)]有服務(wù)完的除塵路徑，接著進(jìn)行除塵作業(yè)?；剀噲龊椭匦禄氐?jīng)]有完成的服務(wù)邊的路徑的引入，如果仍用單輛灑水車的設(shè)計(jì)思想去做得到的結(jié)果就不一定是一個(gè)較優(yōu)的解。因?yàn)檫@時(shí)總的最小花費(fèi)問題分成了兩個(gè)部分，其一是要遍歷完所有的服務(wù)邊，其二是還加上每次加水時(shí)回車場以及去到服務(wù)邊時(shí)的距離。在其一中由于城市的道路網(wǎng)的每個(gè)路口的度數(shù)全為偶數(shù)的概率幾乎為零。這樣在其一中要遍歷完所有的服務(wù)邊，這里又可以分為兩部分。即所有服務(wù)邊的距離(是一個(gè)定值)，以及因?yàn)榈缆肪W(wǎng)中存在奇數(shù)度路口的原因，

53、而不得不重復(fù)行駛的一部分路線(是一個(gè)不定值，隨著奇數(shù)度路口的匹配的不同而不同)。這樣總的最小花費(fèi)=所有服務(wù)邊距離+重復(fù)行駛距離+回車場及到服務(wù)邊的距離。又因?yàn)樗蟹?wù)邊的距離是一個(gè)定值，而重復(fù)行駛距離(是一個(gè)不定值)+回車場及到服務(wù)邊的距離(也是一個(gè)不定值)，則總的最小花費(fèi)可以等效為重復(fù)行駛距離+回車場及到服務(wù)邊的距離。因此遺傳算法的重點(diǎn)不再是奇數(shù)路口的匹配最小就可以實(shí)現(xiàn)灑水車的路線優(yōu)化，而是要考慮加入每次加水時(shí)回車場以及去到服務(wù)邊時(shí)的距離以后得到總的距離最小的一條Euler回路。這才是多輛灑水車路線優(yōu)化的中心環(huán)節(jié)。又由于本課題的研究只考慮一個(gè)車場的優(yōu)化問題。灑水車在城市的除塵過程中存在回到車場以后再重新去到下一條服務(wù)邊的現(xiàn)象。這就為多輛灑水車的同時(shí)除塵作業(yè)的分配提供了一種方法。也恰恰得到了同時(shí)考慮灑水車的容量限制和多輛車的分配的設(shè)計(jì)思想，在這個(gè)設(shè)計(jì)的過程中是不相互沖突的。因此多輛灑水車的線路優(yōu)化過程是如何得到一條加入了因每次加水而要回到車場以及去到服務(wù)邊最終遍歷完所有服務(wù)邊的總的距離最小的Euler回路。所以遺傳算法的側(cè)重點(diǎn)在于求得這一條總的距離最小的回路。4.3 實(shí)例的設(shè)計(jì)與實(shí)現(xiàn)本文的實(shí)驗(yàn)設(shè)計(jì)以柳州某區(qū)域部分路段為實(shí)例，也是單輛灑水車實(shí)驗(yàn)設(shè)計(jì)時(shí)的地圖。首先從多輛灑水車優(yōu)化中心算法(遺傳算法)開始出分析設(shè)計(jì)。其流程圖如下Floyd求解圖上的距離