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

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

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