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

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

1 模型假設(shè)

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

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

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

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

2.1 圖論描述

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

2.2 均衡度

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

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

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

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

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

1）同一干枝上及其分枝上的點(diǎn)分在同一個(gè)交巡警服務(wù)平臺(tái)；

2）離交巡警服務(wù)平臺(tái)最近的點(diǎn)分在一組；

3）一個(gè)交巡警服務(wù)平臺(tái)不能太多的點(diǎn)，也即服從均衡度原則。

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

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

3.1 初始化種群

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

3.2 選擇算子

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

3.3 交叉操作

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

3.4 變異操作

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

4 模型求解

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

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

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

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

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

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

表3 增加不同交巡警平臺(tái)數(shù)均衡度和最長(zhǎng)出警時(shí)間比較

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

5 結(jié)束語(yǔ)

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

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

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

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

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

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

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

[7]2011高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽題目[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項(xiàng)目調(diào)度研究[J].西安工業(yè)大學(xué)學(xué)報(bào)，2014（9）：755-759.

[10]江濤.基于動(dòng)態(tài)規(guī)劃框架下的水電系統(tǒng)優(yōu)化調(diào)度[J].西安工程大學(xué)學(xué)報(bào)，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 稿件編號(hào)：201507165

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