GA在交巡警服務(wù)平臺調(diào)度模型的應(yīng)用

邱 靖，彭莞云，于學(xué)媛，吳瑞武

（1.云南農(nóng)業(yè)大學(xué) 教務(wù)處，云南 昆明 650201；2.云南農(nóng)業(yè)大學(xué) 植物保護(hù)學(xué)院，云南 昆明 650201；3.云南農(nóng)業(yè)大學(xué) 基礎(chǔ)與信息工程學(xué)院，云南 昆明 650201）

GA在交巡警服務(wù)平臺調(diào)度模型的應(yīng)用

邱 靖1，彭莞云2，于學(xué)媛1，吳瑞武3

（1.云南農(nóng)業(yè)大學(xué) 教務(wù)處，云南 昆明 650201；2.云南農(nóng)業(yè)大學(xué) 植物保護(hù)學(xué)院，云南 昆明 650201；3.云南農(nóng)業(yè)大學(xué) 基礎(chǔ)與信息工程學(xué)院，云南 昆明 650201）

為能更好地解決交巡警服務(wù)平臺的調(diào)度問題，利用圖論和遺傳算法的理論及方法，建立了交巡警服務(wù)平臺調(diào)度模型。根據(jù)具體實驗數(shù)據(jù)，利用該模型找到了交巡警管轄范圍分配方案及全封鎖的最佳調(diào)度方案。得出了服務(wù)平臺到進(jìn)出口最遠(yuǎn)節(jié)點的距離為8015.46米，最快需要用時480.93秒才能實現(xiàn)路口全封鎖。同時，根據(jù)均衡度原則和出警時間最少原則，認(rèn)為新增交巡警服務(wù)平臺4個，其具體位置在91，61，66，52 4個節(jié)點處。

遺傳算法；交巡警服務(wù)平臺；最短路徑；調(diào)度模型

1 模型假設(shè)

1）出警時道路恒暢通（無交通事故、交通堵塞、天氣原因等發(fā)生），警車行駛正常，速度恒定為60 km/h；

2）假設(shè)區(qū)域內(nèi)的每條道路都是雙向通行，不考慮轉(zhuǎn)彎對結(jié)果的影響；

3）路口節(jié)點即為網(wǎng)絡(luò)拓?fù)鋱D中的頂點。

2 最短路徑問題理論基礎(chǔ)

2.1 圖論描述

無向圖G（V，A，W）中，V為頂點集合，文獻(xiàn)8中A區(qū)總共有92條道路，因此V={v1，v2，…，v92}；

2.2 均衡度

國民黨在意識形態(tài)層面的劣勢固然有其先天的缺陷，但與其領(lǐng)袖蔣介石也脫不了關(guān)系。正如有論者指出的那樣，雖然蔣介石的自我角色定位是豪杰、圣賢、革命領(lǐng)袖，但卻缺乏足夠的現(xiàn)代色彩。蔣介石是一個缺乏浪漫、幻想和激情的人，其人性格偏向保守、中庸，其政治家個性遠(yuǎn)勝于革命家氣質(zhì)。上述特質(zhì)決定了蔣介石是一個缺乏意識形態(tài)魅力的領(lǐng)袖。

問題要求交巡警盡快趕到出事地點并且工作量盡量能均衡，說明交巡警到達(dá)出事地點的路程短，且每個交巡警平臺分配管轄的范圍合理。均衡度的定義[8]如式（3）：

式（3）中Ci為Vi的最佳路線，w（Ci）為Ci的權(quán)，α0為該巡警服務(wù)平臺的實際工作量均衡度，α為最大容許工作量均衡度。顯然0≤α0≤1，α0越小，說明分組的均衡性越好。

最佳調(diào)度方案即尋求一種較合理的最佳路線，使得每個交巡警平臺滿足均衡性條件。

在交巡警服務(wù)平臺分配和調(diào)度時應(yīng)遵循以下準(zhǔn)則：

1）同一干枝上及其分枝上的點分在同一個交巡警服務(wù)平臺；

2）離交巡警服務(wù)平臺最近的點分在一組；

3）一個交巡警服務(wù)平臺不能太多的點，也即服從均衡度原則。

3 基于遺傳算法的交巡警服務(wù)平臺分配調(diào)度模型

遺傳算法借助生物進(jìn)化理論，體現(xiàn)了優(yōu)勝劣汰思想，通過交叉及變異操作保證了種群的多樣性，具有較強(qiáng)的全局搜索能力和并行處理能力[9-10]。而粒子群的編碼方式和適應(yīng)度函數(shù)的選擇決定了算法的時間和空間復(fù)雜度以及搜索性能的好壞。本研究編碼方式采用長度可變的實數(shù)編碼方式，粒子編碼由路徑經(jīng)過的節(jié)點號決定，染色體的長度為最短路徑的節(jié)點數(shù)，但長度最大為所有節(jié)點數(shù)，且粒子群中個體不存在重復(fù)基因。適應(yīng)度函數(shù)的選擇，起點到終點距離最短，適應(yīng)度函數(shù)如式（4）所示：

3.1 初始化種群

隨機(jī)產(chǎn)生一組粒子群，設(shè)置交叉和變異概率以及粒子群的局部和全局最優(yōu)位置。為保持種群的多樣性，產(chǎn)生初始種群采用隨機(jī)算法。以20個交巡警服務(wù)平臺（起點）到各個節(jié)點（終點）的最短距離。其思路是：以其中一個交巡警服務(wù)平臺出發(fā)，隨機(jī)選取與該服務(wù)平臺相連的節(jié)點作為下一次搜索的起點，如此循環(huán)，直到找到該終點。為避免環(huán)路，在算法中設(shè)計了一個標(biāo)記，看這個節(jié)點是否被選中，如已選，就搜索另外的節(jié)點。

3.2 選擇算子

選擇算子采用家族內(nèi)選擇和順序選擇方式結(jié)合，家族內(nèi)選擇是將適應(yīng)度最小的兩個個體直接進(jìn)入下一代，不再進(jìn)行交叉和變異操作，而將適應(yīng)度值最大的兩個個體淘汰。其余的個體進(jìn)行交叉和變異操作。

3.3 交叉操作

根據(jù)交叉概率的值判定粒子是否進(jìn)行交叉操作，由于最短路徑中不存在短路和回路現(xiàn)象，因此采用單點交叉。將兩父代個體相同節(jié)點后或前的基因組進(jìn)行交叉，形成新的個體，從而保證了粒子群的多樣性。如交叉過程出現(xiàn)回路或短路，則不執(zhí)行交叉操作。

3.4 變異操作

根據(jù)變異概率判定是否對粒子進(jìn)行變異操作，隨機(jī)生成i j兩個節(jié)點（不包括起點和終點）的變異位置，重新搜索一條連接兩節(jié)點的路徑執(zhí)行變異操作，如變異過程出現(xiàn)回路或短路，則不執(zhí)行變異操作。

4 模型求解

問題1：根據(jù)文獻(xiàn)中的數(shù)據(jù)以及利用遺傳算法建立的模型，利用mat lab實現(xiàn)了該算法模型，得到了該A區(qū)20個交巡警服務(wù)平臺的有效管轄分配方案，其分配方案見表1。

表1 20個巡警服務(wù)平臺管轄范圍分配結(jié)果表

問題2：主要解決以最快的速度完成對13條交通要道全封鎖，問題可以轉(zhuǎn)換為求離交巡警服務(wù)平臺路程最遠(yuǎn)的路口路程最短，即時間最少。其最佳調(diào)度方案見如表2

表2 交巡警服務(wù)平臺最佳調(diào)度方案

由表2可知，其最長總路程為8015.46米，因此最快需要480.93秒才能實現(xiàn)路口全封鎖。

問題3：根據(jù)第一問題的分析來看，該區(qū)現(xiàn)有的交巡警服務(wù)平臺的工作量明顯不均衡且有些地方出警時間過長等情況，根據(jù)服務(wù)均衡度的原則及出警時間最少的原則，建立的模型同模型一，得到如下增加平臺的具體方案，如表3所示。

表3 增加不同交巡警平臺數(shù)均衡度和最長出警時間比較

從表3分析來看，增加的服務(wù)平臺點數(shù)為4個更合理，其具體位置為91，61，66，52這4個位置。

5 結(jié)束語

研究對交巡警服務(wù)平臺的分配問題進(jìn)行了分析，利用遺傳算法建立了相應(yīng)的模型，并得到了較好的分配方案和全封鎖方案以及服務(wù)平臺點數(shù)，從分析研究看，該方法對解決最短距離問題具有較強(qiáng)的合理性和實用性。

[1]李妍妍.Dijkstra最短路徑分析算法的優(yōu)化實現(xiàn)[J].測繪與空間地理信息，2014，37（5）:172-173，190.

[2]張慧檔，賀昱曜，張奇志.基于混沌神經(jīng)網(wǎng)絡(luò)的最短路徑路由算法[J].計算機(jī)工程，2006，32（17）:12-14.

[3]黎忠文，覃志東，王全宇，等.游戲引擎最短路徑搜索優(yōu)化遺傳算法設(shè)計[J].計算機(jī)應(yīng)用研究，2014，31（1）:76-79.

[4]夏正冬，卜天明，張居陽.SPFA算法的分析及改進(jìn)[J].計算機(jī)科學(xué)，2014，41（6）:180-183，213.

[5]陳香，李璞，劉嘯澤.交巡警服務(wù)平臺的設(shè)置與調(diào)度[J].Electronic Test，2014（4）:155-157.

[6]張成堂.城市交巡警平臺的設(shè)置與調(diào)度優(yōu)化模型[J].重慶理工大學(xué)學(xué)報（自然科學(xué)），2012，26（11）:63-69.

[7]2011高教社杯全國大學(xué)生數(shù)學(xué)建模競賽題目[EB/OL］.[2011-09-09]．http://www.mcm.edu.cn/html_cn/node/a1ffc4c 5587c8a6f96eacefb8dbcc34e.html.

[8]谷云東，趙峰.均衡度公理化定義的改進(jìn) [J].模糊系統(tǒng)與數(shù)學(xué)，2008，22（3）:130-135.

[9]韓丹丹，袁媛.基于銀行承兌匯票的Max-NPV項目調(diào)度研究[J].西安工業(yè)大學(xué)學(xué)報，2014（9）：755-759.

[10]江濤.基于動態(tài)規(guī)劃框架下的水電系統(tǒng)優(yōu)化調(diào)度[J].西安工程大學(xué)學(xué)報，2015（4）:420-425.

Application of GA in traffic and patrol police service platform of dispatching model

QIU Jing1，PENG Wan-yun2，YU Xue-yuan1，WU Rui-wu3
（1.Teaching Affairs Office，Yunnan Agriculture University，Kunming 650201，China；2.College of Plant Protection，Yunnan Agriculture University，Kunming 650201，China；3.College of Foundation and Information Engineering，Yunnan Agriculture University，Kunming 650201，China）

In order to better solve the scheduling problem of traffic and patrol police service platform，using the theory and method of graph theory and genetic algorithm，established a patrol service platform scheduling model.According to the specific experimental data，the use of the model had been jurisdiction assignment scheme of traffic and patrol police，and the optimal scheduling scheme of full blockade.It obtained that the farthest node distance of servicing platform to import and export is 8015.46 meters，and it realized the full blockade that the fastest need 480.93.At the same time，according to the principle of balance degree and the least time the police，it consider that traffic and patrol police service platform should be added four platforms，its location in the 91，61，66，52 nodes.

genetic algorithm（GA）；traffic and patrol police service platform；shortest route；scheduling model

TN02

A

1674－6236（2016）15-0032-03

2015-07-24 稿件編號：201507165

邱 靖（1979—），女，四川達(dá)州人，碩士，講師。研究方向：人工智能和計算機(jī)應(yīng)用。