鋪沙車最短路徑規(guī)劃的優(yōu)化算法

鋪沙車最短路徑規(guī)劃的優(yōu)化算法

1鋪設路徑及軌跡優(yōu)化問題在車輛路徑優(yōu)化中，車輛路徑優(yōu)化實際上存在兩個情況。其中之一是交通路徑優(yōu)化（rp），該模型以抽象為服務對象，物流中心對超市的商品銷售。其次，道路優(yōu)化（arcrobottal.a）包括城市照明路徑配置和鋪沙道路配置。為了從不同角度說明問題,分兩層模擬:第一層假定卡車的載沙量足夠大,即裝載一次就可以完成所有街道的鋪設任務;第二層加入鋪沙車運量的限制,即裝滿一車沙只能鋪設一定距離;對于第一層而言,就是讓一輛鋪沙車以最短的距離將圖中的每一條單行線按所指示的方向遍歷一遍。對于第二層,顯然是不能將所有的單行線鋪上沙的,需要安排若干輛車去完成鋪沙任務,在確定鋪沙車數(shù)量的情況下,對所有車的路徑進行整體的優(yōu)化。1節(jié)點選擇導致的算法針對此問題,筆者建立如下合理的假設:起點站的運沙車數(shù)量不受限制;鋪沙車在鋪完沙以后,最終要回到起點站;鋪沙車在對一條路進行鋪沙時,不會半途而返,即一旦駛?cè)肽骋粭l路,那么就一定要將該路鋪完;在第二問中,車行駛單位路徑的費用是恒定的。首先給出所要求的目標函數(shù):其中,eij表示第i個節(jié)點到第j個節(jié)點的街道的長度,如果第i個節(jié)點到第j個節(jié)點之間沒有直接的單行線連接,則令eij為∞,xij表示eij被走過的次數(shù)。對于xij進一步的說明為:接著,考慮約束條件,對于每一個節(jié)點,出度與入度要相等:上式左邊表示對所有從i發(fā)出的單行線條數(shù)求和,即出度之和,等式右邊表示對所有進入i的單行線條數(shù)求和,即入度之和。約束條件二,對于存在街道eij的節(jié)點i,j,則eij前的系數(shù)一定要大于等于1,于是得到最終的規(guī)劃模型為:緊接著,著手第二步,即按照歐拉回路的方法尋找出一條路徑作為鋪沙車的巡行路徑。定義圖G(V,E),V為節(jié)點集,E為邊集,對于任一節(jié)點v0∈V,deg(v0)≠0,deg(v0)表示節(jié)點v0的度,所以一定可以找到e1=〈v0,v1〉∈E,若v1=v0,則找到了G的一條回路。否則,又由于deg(v2)為偶數(shù),可以找到e3=〈v2,v3〉∈E,且e3≠e2,e3≠e1。若v3=v0,則找到G的一條回路。如此進行下去,每邊僅取一次,并且沒到一個節(jié)點就沿著該節(jié)點的關聯(lián)邊中沒有走過的一條邊走,只有當沒有其他選擇時才選未走過的邊所構(gòu)成子圖的割邊走。因為E是有限集,故一定存在e1e2Len,使en的終點為v0,從而構(gòu)成G的一條歐拉回路C:v0e1v1e2Lvkek+1Lvn-1env02車輛數(shù)和容量限制當加入了對鋪沙車運輸量的限制,也就是說,僅用一輛車是不能把它鋪完的,而如果一定要使用一輛車的話,那么這一輛車就要走若干趟,在此有必要首先弄清楚車的輛數(shù)與每一輛車需要走的趟數(shù)之間的關系。目標函數(shù)為使所有路徑的總花費值最小,即:其中,Ti表示第i輛車巡行所產(chǎn)生的圈;cost(Ti)表示第i輛車的花費;k表示車輛數(shù),在此經(jīng)過前面的分析確定為4。容量限制條件:針對一輛車完成一個圈這一任務,設每個路徑Ti中包含的鋪沙任務為Ti1,Ti2,LTijL,Tini(Tij表示圈Ti中的需要鋪沙的第j條單行線,ni表示圈Ti中要鋪沙的單行線的總數(shù)目),一條單行線被某一輛車鋪了以后就不能被其它的車鋪。q(Tij)表示Ti中的需要鋪沙的第j條單行線的長度。Wi表示第i輛車的裝載量。則即某一輛車完成其鋪設任務所鋪下的沙量要小于等于它的裝載量?；ㄙM函數(shù):圈Ti的花費為:從道路養(yǎng)車站出來,到第一個任務街道的最短距離,加上第二條街道的長度,加上第二條街道到第三條街道的最短距離,累加到最后一條街道,然后加上最后一條街道長度和最后一條街道到道路養(yǎng)車站的最短距離。即:其中,q(Tij)表示Tij的長度,d表示最短路。每個服務邊都被服務:表示要鋪設街道總數(shù)目)定義了集合Rk,Rk中的元素由第k條路徑中的要鋪沙的街道組成。任意兩條路徑中不能有重復的服務邊,也就保證了每個單行線只能被一輛車服務一次:綜上所述,目標函數(shù)與約束條件,目標函數(shù)為:3遺傳算法編碼實質(zhì)上檢討的是一個容量約束的邊尋路問題(CapacitatedareRoutingProblem)。已經(jīng)證明出這個問題是一個NP難的問題,所以利用常規(guī)方法難于求解,現(xiàn)利用遺傳算法求得滿意解。算法可分為以下幾個部分:(1)輸入預處理。首先,要輸入圖的鄰接矩陣。其次采用Floyd算法得到任意兩點之間的最短距離矩陣D,以及前驅(qū)矩陣P(用以記錄路徑)。第三對邊按照一個順序進行編號,構(gòu)造一個矩陣,矩陣的第一列表示了邊的序號,第二列表示了邊的起始節(jié)點的編號,第三列表示了邊的終止節(jié)點的編號。(2)遺傳算法的編碼方式。首先,染色體數(shù)據(jù)結(jié)構(gòu)為一維數(shù)組,長度為m(弧的總條數(shù)),由m個不同的整數(shù)組成(取值范圍是1-m)。其中每一個整數(shù)就代表了一條服務弧,例如整數(shù)i(i∈1,…,m)就代表了弧i。初始化染色體就是生成CNum條染色體,對每條染色體進行隨機賦值從而生成初始種群。假設有5條邊需要鋪設沙子,初始種群需要生成3條染色體,則初始后的種群可能為(Chrom1=2,1,4,3,5;Chrom2=5,2,3,1,4;Chrom3=1,5,3,2,4)。其次,由于上面的編碼方式要求每個染色體的元素不等,不方便于實際問題的處理,將原自然數(shù)編碼轉(zhuǎn)變成為grefenstette碼。grefenstette碼的優(yōu)點在于對于變異函數(shù)的要求低,對于編碼元素沒有互異的要求。(3)遺傳算法的解碼方式。利用congrefenstette解碼方法將grefenstte碼轉(zhuǎn)變成為自然數(shù)編碼;再將自然數(shù)編碼對應成為相應的的路徑。4雙向街道鋪沙優(yōu)化模型現(xiàn)給出南方某一城市某一街區(qū)的示意圖,弧表示街道,數(shù)據(jù)表示街道的長度,單位:m;結(jié)點表示街道的交匯處,一共有12個結(jié)點。假設街道養(yǎng)路站位于交匯點1處,鋪沙的任務由養(yǎng)路站負責,所需要的沙和所使用的卡車都在該養(yǎng)路站內(nèi)。箭頭表示單車道方向,對于雙向街道,必須按方向要求為每個方向的車道分別鋪沙;對于某條單行線,允許因鋪沙需要而多次通過(見圖1)?，F(xiàn)需解答如下的問題:(1)假設卡車的載沙量足夠大,即裝載一次就可以完成所有街道的鋪設任務,在此情況下為鋪沙車選擇一條路線,使得完成所有路面鋪沙任務所需的路程最短。(2)現(xiàn)在加入鋪沙車運量的限制,如裝滿一車沙僅能鋪設1500m,此種情況下又該如何完成鋪沙任務。(3)進一步加入限制條件,每輛車不僅裝載量有限,而且空車與載重車所需要的運輸費用也有差別,又該如何完成任務。根據(jù)建立的模型,第一問結(jié)果如下:這兩條路徑的總長為6059m。其中,數(shù)字1到9分別表示圖1中的前9個節(jié)點,字母ABC分別表示節(jié)點10、11、12。第二問結(jié)果:共需要4輛卡車,4輛卡車的路線如下:四條路徑的總長6943m5啟發(fā)式算法的優(yōu)缺點建立的模型具有推廣性,可適用于鋪沙車、灑水車等多種針對路徑服務的公共問題。其中3個模型步步加強,越發(fā)的貼近實際,可分別從3個方面、3個層次指導實際中的鋪路問題。其中,小規(guī)模、簡單的約束問題就可直接用lingo規(guī)劃求解。約束復雜時,就采用啟發(fā)式算法,而且問題的規(guī)模越大時,越可以體現(xiàn)出啟發(fā)式算法的優(yōu)點。對結(jié)果的分析細致、到位,在短時間內(nèi)盡量多地考慮到了各方面的問題。如在解決問題一時,還考慮到了某一條街道不鋪的情況,在這種情況下對總的費用的影響,由此對于原問題就有了比較性和指導性,從而可以對有關的部門提出合理的建議。詳細地突出了各個問題及模型之間的主要區(qū)別,并妥善地處理了這些差別。但是,模型在問題中未能給出加入某一條街道后對總的費用所造成的影響,這主要是由于難以確定加入的路徑的具體長度,而這一長度對總費用又是有所影響的。同時,問題未能確定給出的是否是最優(yōu)解,而僅能確定給出的是滿意解,這是