席禹　唐健

摘要：本文研究的是噴灑車的最短噴灑時(shí)間問(wèn)題，主要采用基于Floyd算法的GA模型。在任務(wù)一中，我們計(jì)算出每輛噴灑車完成一個(gè)作業(yè)點(diǎn)所需要的最短時(shí)間。首先，對(duì)D1一直到F60的節(jié)點(diǎn)進(jìn)行編號(hào)，利用附件一計(jì)算出各個(gè)節(jié)點(diǎn)之間的距離，并利用MATLAB得出地圖。接著，利用各個(gè)節(jié)點(diǎn)的連接關(guān)系得出連接矩陣。由于A、B兩類車在不同類型的路徑的速度不同，因而對(duì)距離進(jìn)行加權(quán)，統(tǒng)一處理。以A車通過(guò)普通道路的速度作為權(quán)重1，計(jì)算出A在主干道;B在普通道路、主干道上對(duì)應(yīng)的權(quán)重分別為3/4;9/10;3/2"最后，通過(guò)Floyd算法，尋找各自10條最短路徑，并得出其中的最長(zhǎng)作業(yè)完成時(shí)間，即為最終的完成任務(wù)最短用時(shí)。通過(guò)計(jì)算，得出最短時(shí)長(zhǎng)為2.83h。在任務(wù)二中，我們計(jì)算出每輛車完成兩個(gè)作業(yè)點(diǎn)所需要的最短時(shí)間。首先，通過(guò)分析所有點(diǎn)的排列情況，發(fā)現(xiàn)數(shù)據(jù)過(guò)于龐大，不能進(jìn)行遍歷處理，因而只能選用局部最優(yōu)解。接著，把噴灑車的全部路程分）為三個(gè)階段，從七點(diǎn)到第一個(gè)作業(yè)點(diǎn)，第一個(gè)作業(yè)點(diǎn)到給水點(diǎn)，給水點(diǎn)到第二個(gè)作業(yè)點(diǎn)。最后，通過(guò)建立目標(biāo)函數(shù)：完成兩個(gè)作業(yè)點(diǎn)所需要的最短時(shí)間，和相應(yīng)的約束條件：（1）每輛噴灑車在第一次噴灑作業(yè)完成后一定要到補(bǔ)水站;（2）起點(diǎn)的噴灑車的數(shù)量、型號(hào)一定。最后，通過(guò)GA算法，交叉變異等一系列的操作，計(jì)算出噴灑車完成兩個(gè)作業(yè)點(diǎn)所需的最短時(shí)長(zhǎng)7.25h"在任務(wù)三中，我們計(jì)算完成所有作業(yè)點(diǎn)所需要的最短時(shí)間"首先，我們判斷只有當(dāng)每輛噴灑車都執(zhí)行三次作業(yè)任務(wù)時(shí)，所達(dá)到的利用率和效率是最高的。之后，把噴灑車的全部路程分成6個(gè)階段。最后，以求完成最遠(yuǎn)路程距離點(diǎn)的最小值為目標(biāo)函數(shù)，同時(shí)確定相應(yīng)的約束條件：補(bǔ)水站最多只能給車輛補(bǔ)水8次，其他與任務(wù)二一樣"最后，通過(guò)GA算法，計(jì)算出噴灑車完成作業(yè)所需的最短時(shí)長(zhǎng)：13.54h"在任務(wù)四中，在道路節(jié)點(diǎn)J中增設(shè)2個(gè)給水站，重新完成第三問(wèn)的噴灑任務(wù)，并計(jì)算所需時(shí)間。由于噴灑任務(wù)的最終目標(biāo)是用最短的時(shí)間不重復(fù)的完成作業(yè)任務(wù)，因而給水站選點(diǎn)的影響因素為F節(jié)點(diǎn)的位置"首先列出均勻度函數(shù)，通過(guò)F點(diǎn)的位置，利用方差最小計(jì)算出理想情況下最優(yōu)的一個(gè)J點(diǎn)。并通過(guò)選取隨機(jī)的兩個(gè)Z點(diǎn)，使得各個(gè)Z點(diǎn)到節(jié)點(diǎn)F的距離方差最小。確定給水點(diǎn)后，利用任務(wù)三的模型，即可得出噴灑車完成作業(yè)的時(shí)間。最短時(shí)長(zhǎng)為12.15h。

關(guān)鍵詞：GA算法;Floyd模型;平均度

1問(wèn)題重述

某城市共有綠化噴灑車20臺(tái)，分為A、B兩類。其中A、B類噴灑車分別有12輛、8輛，執(zhí)行噴灑任務(wù)前平均部署在2個(gè)?？奎c(diǎn)（D1，D2）。所屬域內(nèi)有6個(gè)給水站（Z01Z06）、60個(gè)噴灑作業(yè)點(diǎn)（F01F60），每一個(gè)噴灑作業(yè)點(diǎn)只需一臺(tái)噴灑車進(jìn)行一次作業(yè)。各給水站最多可以給八臺(tái)噴灑車加水，不計(jì)加水時(shí)間。噴灑車裝滿水停，在停，點(diǎn)，接到噴灑任務(wù)后駛向噴灑作業(yè)點(diǎn)噴灑作業(yè)。一次噴灑作業(yè)A、B兩類噴灑車分別需要用時(shí)20分鐘、15分鐘。每輛噴灑車完成一次噴灑任務(wù)后，需要到給水站加水再進(jìn)行下次噴灑作業(yè)。

B兩類噴灑車在主干道路上的平均行駛速度分別是60公里/小時(shí)、50公里/小時(shí)，在其他道路上的平均行駛速度分別是45公里/小時(shí)、30公里/小時(shí)。噴灑車裝滿水停，在停，點(diǎn)，接到噴灑任務(wù)后駛向噴灑作業(yè)點(diǎn)噴灑作業(yè)。一次噴灑作業(yè)A、B兩類噴灑車分別需要用時(shí)20分鐘、15分鐘。每輛噴灑車完成一次噴灑任務(wù)后，需要到給水站加水再進(jìn)行下次噴灑作業(yè)。

1、任務(wù)一：每輛噴灑車只執(zhí)行一次噴灑作業(yè)。請(qǐng)給出完成任務(wù)一的最短時(shí)間及相應(yīng)的最優(yōu)噴灑作業(yè)方案。

2、任務(wù)二：每輛噴灑車執(zhí)行兩次次噴灑作業(yè)。請(qǐng)給出完成任務(wù)二的最短時(shí)間及相應(yīng)的最優(yōu)噴灑作業(yè)方案。

3、任務(wù)三：完成所有60個(gè)噴灑作業(yè)點(diǎn)（F01F60）的噴灑任務(wù)。請(qǐng)給出完成任務(wù)三的最短時(shí)間及相應(yīng)的最優(yōu)噴灑作業(yè)方案。

4、如果在道路節(jié)點(diǎn)J01J62中的某兩個(gè)節(jié)點(diǎn)？分別增建一個(gè)給水站，請(qǐng)重新考慮問(wèn)題3。并給出增建給水站的最佳位置。

2問(wèn)題分析

2.1問(wèn)題1的分析

任務(wù)一要求找出每輛車只執(zhí)行一次噴灑任務(wù)時(shí)的最短時(shí)間和及其對(duì)應(yīng)的作業(yè)方案。

這道題的核心是最優(yōu)解問(wèn)題。題目最終的目標(biāo)的求出完成噴灑任務(wù)所需的最短時(shí)間，而由于A、B兩類車的速度固定，則可以把問(wèn)題轉(zhuǎn)換為路徑最短問(wèn)題。首先，通過(guò)圖論的最短路問(wèn)題的思想，篩選出十個(gè)最短的路徑，之后比較A、B輛車的速度，將四條最近的路徑分配給B車，其余分配給A車，計(jì)算十條線路完成的最長(zhǎng)用時(shí)，得出的即為完成任務(wù)的最短時(shí)間。

2.2問(wèn)題2的分析

任務(wù)二要求計(jì)算每輛噴灑車完成兩次噴灑任務(wù)時(shí)的最短時(shí)間。由題意得，每輛噴灑車在完成一次噴灑作業(yè)時(shí)，必須要到Z點(diǎn)給水站補(bǔ)水，之后才能向下一個(gè)灑水作業(yè)點(diǎn)前進(jìn)。同時(shí)，每個(gè)給水點(diǎn)只能完成8次補(bǔ)水，補(bǔ)水的時(shí)間忽略不計(jì)。題目的意思可以轉(zhuǎn)換為先找出10個(gè)最短路徑，分別分配給A、B車，并計(jì)算出其中的最長(zhǎng)作業(yè)完成時(shí)間，即為完成任務(wù)的最短用時(shí)。其中，車輛在進(jìn)行兩個(gè)作業(yè)之間必須經(jīng)過(guò)一個(gè)Z點(diǎn)進(jìn)行補(bǔ)水。那么該題可以在第一問(wèn)的基礎(chǔ)上改為三段路徑進(jìn)行分析。分別分成起點(diǎn)到第一個(gè)作業(yè)點(diǎn)，第一個(gè)作業(yè)點(diǎn)到給水點(diǎn)，給水點(diǎn)到第二個(gè)作業(yè)點(diǎn)。需要注意的是，當(dāng)三段路徑一起考慮后，由于組合的情況過(guò)于復(fù)雜，則不可能進(jìn)行遍歷，因而尋找局部最優(yōu)解是本題的關(guān)鍵。

2.3問(wèn)題3的分析

任務(wù)三要求計(jì)算噴灑車完成所有噴灑任務(wù)時(shí)的最短時(shí)間。對(duì)于該題，思路和任務(wù)二基本一致。不同在于以下幾點(diǎn)：（1）每輛車都要保證自己的噴灑任務(wù)充分利用，即每輛噴灑車都完成三次噴灑任務(wù);（2）每個(gè)補(bǔ)水站只能為8輛噴灑車進(jìn)行補(bǔ)水，當(dāng)大于8輛噴灑車時(shí)，補(bǔ)水站就變?yōu)槠胀ǖ墓?jié)點(diǎn)。

2.4問(wèn)題4的分析

任務(wù)四中找出平均度的定義是問(wèn)題的關(guān)鍵。由于Z點(diǎn)的取點(diǎn)規(guī)則是與F點(diǎn)有著密切聯(lián)系的，當(dāng)Z點(diǎn)在圖上分布的越均勻，則最終用時(shí)越短。當(dāng)確定Z點(diǎn)的分布后，步驟和任務(wù)三基本一致。

3模型的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

1、Floyd算法可以精確的計(jì)算出各點(diǎn)之間沿路線的最短距離;

2、用Ga算法進(jìn)行上千萬(wàn)次的運(yùn)算求出的解，可以較為準(zhǔn)確的接近最優(yōu)解;

3、引入均勻度函數(shù)，可以衡量布置點(diǎn)的均勻性。

缺點(diǎn)：

1、GA算法得出結(jié)果存在誤差;

2、GA算法計(jì)算時(shí)間過(guò)長(zhǎng)，效率較低;

3、均勻度算法結(jié)果較優(yōu)，但不是最優(yōu)

改進(jìn)：

1、GA算法求解復(fù)雜，效率低，可以在算法上進(jìn)行優(yōu)化，改進(jìn)算法，使算法更加簡(jiǎn)答快速。

2、第四問(wèn)可以降低求解次數(shù)，先用聚類分析，分析聚類后的結(jié)果，可以降低求解次數(shù)。

參考文獻(xiàn)：

[1]王殿超.一種改進(jìn)的遺傳算法在TSP問(wèn)題中的應(yīng)用[J].遼寧工業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版），2019（04）：235-239.

[2]李鳳坤.改進(jìn)AHP-GA算法的多目標(biāo)配送路徑優(yōu)化[J].計(jì)算機(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.