席禹 唐健
摘要:本文研究的是噴灑車的最短噴灑時間問題,主要采用基于Floyd算法的GA模型。在任務(wù)一中,我們計算出每輛噴灑車完成一個作業(yè)點所需要的最短時間。首先,對D1一直到F60的節(jié)點進(jìn)行編號,利用附件一計算出各個節(jié)點之間的距離,并利用MATLAB得出地圖。接著,利用各個節(jié)點的連接關(guān)系得出連接矩陣。由于A、B兩類車在不同類型的路徑的速度不同,因而對距離進(jìn)行加權(quán),統(tǒng)一處理。以A車通過普通道路的速度作為權(quán)重1,計算出A在主干道;B在普通道路、主干道上對應(yīng)的權(quán)重分別為3/4;9/10;3/2"最后,通過Floyd算法,尋找各自10條最短路徑,并得出其中的最長作業(yè)完成時間,即為最終的完成任務(wù)最短用時。通過計算,得出最短時長為2.83h。在任務(wù)二中,我們計算出每輛車完成兩個作業(yè)點所需要的最短時間。首先,通過分析所有點的排列情況,發(fā)現(xiàn)數(shù)據(jù)過于龐大,不能進(jìn)行遍歷處理,因而只能選用局部最優(yōu)解。接著,把噴灑車的全部路程分)為三個階段,從七點到第一個作業(yè)點,第一個作業(yè)點到給水點,給水點到第二個作業(yè)點。最后,通過建立目標(biāo)函數(shù):完成兩個作業(yè)點所需要的最短時間,和相應(yīng)的約束條件:(1)每輛噴灑車在第一次噴灑作業(yè)完成后一定要到補水站;(2)起點的噴灑車的數(shù)量、型號一定。最后,通過GA算法,交叉變異等一系列的操作,計算出噴灑車完成兩個作業(yè)點所需的最短時長7.25h"在任務(wù)三中,我們計算完成所有作業(yè)點所需要的最短時間"首先,我們判斷只有當(dāng)每輛噴灑車都執(zhí)行三次作業(yè)任務(wù)時,所達(dá)到的利用率和效率是最高的。之后,把噴灑車的全部路程分成6個階段。最后,以求完成最遠(yuǎn)路程距離點的最小值為目標(biāo)函數(shù),同時確定相應(yīng)的約束條件:補水站最多只能給車輛補水8次,其他與任務(wù)二一樣"最后,通過GA算法,計算出噴灑車完成作業(yè)所需的最短時長:13.54h"在任務(wù)四中,在道路節(jié)點J中增設(shè)2個給水站,重新完成第三問的噴灑任務(wù),并計算所需時間。由于噴灑任務(wù)的最終目標(biāo)是用最短的時間不重復(fù)的完成作業(yè)任務(wù),因而給水站選點的影響因素為F節(jié)點的位置"首先列出均勻度函數(shù),通過F點的位置,利用方差最小計算出理想情況下最優(yōu)的一個J點。并通過選取隨機的兩個Z點,使得各個Z點到節(jié)點F的距離方差最小。確定給水點后,利用任務(wù)三的模型,即可得出噴灑車完成作業(yè)的時間。最短時長為12.15h。
關(guān)鍵詞:GA算法;Floyd模型;平均度
1問題重述
某城市共有綠化噴灑車20臺,分為A、B兩類。其中A、B類噴灑車分別有12輛、8輛,執(zhí)行噴灑任務(wù)前平均部署在2個??奎c(D1,D2)。所屬域內(nèi)有6個給水站(Z01Z06)、60個噴灑作業(yè)點(F01F60),每一個噴灑作業(yè)點只需一臺噴灑車進(jìn)行一次作業(yè)。各給水站最多可以給八臺噴灑車加水,不計加水時間。噴灑車裝滿水停,在停,點,接到噴灑任務(wù)后駛向噴灑作業(yè)點噴灑作業(yè)。一次噴灑作業(yè)A、B兩類噴灑車分別需要用時20分鐘、15分鐘。每輛噴灑車完成一次噴灑任務(wù)后,需要到給水站加水再進(jìn)行下次噴灑作業(yè)。
B兩類噴灑車在主干道路上的平均行駛速度分別是60公里/小時、50公里/小時,在其他道路上的平均行駛速度分別是45公里/小時、30公里/小時。噴灑車裝滿水停,在停,點,接到噴灑任務(wù)后駛向噴灑作業(yè)點噴灑作業(yè)。一次噴灑作業(yè)A、B兩類噴灑車分別需要用時20分鐘、15分鐘。每輛噴灑車完成一次噴灑任務(wù)后,需要到給水站加水再進(jìn)行下次噴灑作業(yè)。
1、任務(wù)一:每輛噴灑車只執(zhí)行一次噴灑作業(yè)。請給出完成任務(wù)一的最短時間及相應(yīng)的最優(yōu)噴灑作業(yè)方案。
2、任務(wù)二:每輛噴灑車執(zhí)行兩次次噴灑作業(yè)。請給出完成任務(wù)二的最短時間及相應(yīng)的最優(yōu)噴灑作業(yè)方案。
3、任務(wù)三:完成所有60個噴灑作業(yè)點(F01F60)的噴灑任務(wù)。請給出完成任務(wù)三的最短時間及相應(yīng)的最優(yōu)噴灑作業(yè)方案。
4、如果在道路節(jié)點J01J62中的某兩個節(jié)點?分別增建一個給水站,請重新考慮問題3。并給出增建給水站的最佳位置。
2問題分析
2.1問題1的分析
任務(wù)一要求找出每輛車只執(zhí)行一次噴灑任務(wù)時的最短時間和及其對應(yīng)的作業(yè)方案。
這道題的核心是最優(yōu)解問題。題目最終的目標(biāo)的求出完成噴灑任務(wù)所需的最短時間,而由于A、B兩類車的速度固定,則可以把問題轉(zhuǎn)換為路徑最短問題。首先,通過圖論的最短路問題的思想,篩選出十個最短的路徑,之后比較A、B輛車的速度,將四條最近的路徑分配給B車,其余分配給A車,計算十條線路完成的最長用時,得出的即為完成任務(wù)的最短時間。
2.2問題2的分析
任務(wù)二要求計算每輛噴灑車完成兩次噴灑任務(wù)時的最短時間。由題意得,每輛噴灑車在完成一次噴灑作業(yè)時,必須要到Z點給水站補水,之后才能向下一個灑水作業(yè)點前進(jìn)。同時,每個給水點只能完成8次補水,補水的時間忽略不計。題目的意思可以轉(zhuǎn)換為先找出10個最短路徑,分別分配給A、B車,并計算出其中的最長作業(yè)完成時間,即為完成任務(wù)的最短用時。其中,車輛在進(jìn)行兩個作業(yè)之間必須經(jīng)過一個Z點進(jìn)行補水。那么該題可以在第一問的基礎(chǔ)上改為三段路徑進(jìn)行分析。分別分成起點到第一個作業(yè)點,第一個作業(yè)點到給水點,給水點到第二個作業(yè)點。需要注意的是,當(dāng)三段路徑一起考慮后,由于組合的情況過于復(fù)雜,則不可能進(jìn)行遍歷,因而尋找局部最優(yōu)解是本題的關(guān)鍵。
2.3問題3的分析
任務(wù)三要求計算噴灑車完成所有噴灑任務(wù)時的最短時間。對于該題,思路和任務(wù)二基本一致。不同在于以下幾點:(1)每輛車都要保證自己的噴灑任務(wù)充分利用,即每輛噴灑車都完成三次噴灑任務(wù);(2)每個補水站只能為8輛噴灑車進(jìn)行補水,當(dāng)大于8輛噴灑車時,補水站就變?yōu)槠胀ǖ墓?jié)點。
2.4問題4的分析
任務(wù)四中找出平均度的定義是問題的關(guān)鍵。由于Z點的取點規(guī)則是與F點有著密切聯(lián)系的,當(dāng)Z點在圖上分布的越均勻,則最終用時越短。當(dāng)確定Z點的分布后,步驟和任務(wù)三基本一致。
3模型的優(yōu)缺點
優(yōu)點:
1、Floyd算法可以精確的計算出各點之間沿路線的最短距離;
2、用Ga算法進(jìn)行上千萬次的運算求出的解,可以較為準(zhǔn)確的接近最優(yōu)解;
3、引入均勻度函數(shù),可以衡量布置點的均勻性。
缺點:
1、GA算法得出結(jié)果存在誤差;
2、GA算法計算時間過長,效率較低;
3、均勻度算法結(jié)果較優(yōu),但不是最優(yōu)
改進(jìn):
1、GA算法求解復(fù)雜,效率低,可以在算法上進(jìn)行優(yōu)化,改進(jìn)算法,使算法更加簡答快速。
2、第四問可以降低求解次數(shù),先用聚類分析,分析聚類后的結(jié)果,可以降低求解次數(shù)。
參考文獻(xiàn):
[1]王殿超.一種改進(jìn)的遺傳算法在TSP問題中的應(yīng)用[J].遼寧工業(yè)大學(xué)學(xué)報(自然科學(xué)版),2019(04):235-239.
[2]李鳳坤.改進(jìn)AHP-GA算法的多目標(biāo)配送路徑優(yōu)化[J].計算機系統(tǒng)應(yīng)用,2019,28(02):152-157.
[3]潘立彥,張大成.改進(jìn)Floyd算法在城市交通網(wǎng)絡(luò)優(yōu)化中的應(yīng)用[J].物流技術(shù),2018,37(11):71-74+115.