席禹　唐健

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

關鍵詞：GA算法;Floyd模型;平均度

1問題重述

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

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

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

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

3、任務三：完成所有60個噴灑作業(yè)點（F01F60）的噴灑任務。請給出完成任務三的最短時間及相應的最優(yōu)噴灑作業(yè)方案。

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

2問題分析

2.1問題1的分析

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

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

2.2問題2的分析

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

2.3問題3的分析

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

2.4問題4的分析

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

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

優(yōu)點：

1、Floyd算法可以精確的計算出各點之間沿路線的最短距離;

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

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

缺點：

1、GA算法得出結果存在誤差;

2、GA算法計算時間過長，效率較低;

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

改進：

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

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

參考文獻：

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

[2]李鳳坤.改進AHP-GA算法的多目標配送路徑優(yōu)化[J].計算機系統(tǒng)應用，2019，28（02）：152-157.

[3]潘立彥，張大成.改進Floyd算法在城市交通網(wǎng)絡優(yōu)化中的應用[J].物流技術，2018，37（11）：71-74+115.