謝 婷

（安徽省馬鞍山市委黨校，安徽馬鞍山243011）

RA 網(wǎng)絡(luò)多協(xié)同排序算法模型及算法研究

謝 婷

（安徽省馬鞍山市委黨校，安徽馬鞍山243011）

針對當下約車平臺迅猛發(fā)展的態(tài)勢，就其中廣泛關(guān)注的問題——RA網(wǎng)絡(luò)多協(xié)同排序問題進行了探究。針對滴滴出行的實際數(shù)據(jù)，將RA網(wǎng)絡(luò)多協(xié)同排序問題轉(zhuǎn)化為求解數(shù)學(xué)模型兩個評價指標最優(yōu)解的問題，基于傳統(tǒng)的免疫算法（generate and test）的相關(guān)概念，融合半解析解的相關(guān)思想，構(gòu)建一種優(yōu)化算法GBFA（Generate Bacterial Foraging Algorithm），進而提出了基于GBFA算法的RA網(wǎng)絡(luò)多協(xié)同排序算法，并據(jù)此開發(fā)RA網(wǎng)絡(luò)多協(xié)同排序軟件”RA－LC”。以滴滴出行北京市2015年5月—2016年4月的數(shù)據(jù)為對比對象，利用RA－LC對相關(guān)實例進行仿真，結(jié)果顯示該算法對于時間預(yù)測具有較高的準確度，對于RA網(wǎng)絡(luò)多協(xié)同排序問題具有極佳的適用性和精確度。

多協(xié)同排序；Mathematica；GBFA；滴滴出行；時間預(yù)測

0 引言

網(wǎng)絡(luò)約車平臺的迅猛發(fā)展已悄然改變了人們的生產(chǎn)、生活方式［1］?？蛻舭l(fā)單（request）與司機的應(yīng)答（answer）涉及到復(fù)雜的排序問題，在同一片區(qū)往往存在著多名司機，司機彼此之間的線路相互影響，使得request－answer網(wǎng)絡(luò)（RA網(wǎng)絡(luò)）極其復(fù)雜，應(yīng)加強RA網(wǎng)絡(luò)的關(guān)聯(lián)性，進而凸顯出多協(xié)同排序算法研究的重要性和必要性［2－3］。

鑒于此，國內(nèi)外學(xué)者對RA網(wǎng)絡(luò)的多協(xié)同排序算法進行了大量研究。Cui J X、Shen H［4－5］等人利用GPS定位對司機位置進行的計算，通過對司機當前行進數(shù)據(jù)進行擬合，計算出司機達到客戶發(fā)單（request）位置的時間，依照到達時間的長短由低到高排序，但文獻［4］和文獻［5］僅僅考慮了當前數(shù)據(jù)的效用，沒有將堵車、遲緩度加入?yún)f(xié)同決策方案中。Petrovic′M［6］基于改進后的粒子群算法，將行進過程中的堵車問題以概率的形式加入到?jīng)Q策函數(shù)中，排序的結(jié)果更加有效，但是文獻［6］依舊沒有利用歷史數(shù)據(jù)，導(dǎo)致排序仿真的結(jié)果與實驗結(jié)果有較大的出入。Huang X［7］、Jianxun Cui［8］等人基于優(yōu)步約車平臺的運行數(shù)據(jù)，對于RA網(wǎng)絡(luò)進行多變量的數(shù)據(jù)擬合，從而為排序提供支持，但是文獻［7］和文獻［8］所使用的擬合模型僅僅是多項式擬合，導(dǎo)致了誤差較大，量綱不統(tǒng)一。SAVCHENKO［9］基于量綱分析法，依照的司機行車歷史數(shù)據(jù)進行數(shù)據(jù)擬合，但擬合模型僅僅是多項式擬合，導(dǎo)致了擬合結(jié)果與真實情況相差較大。

本文在前人的研究基礎(chǔ)上，選用細菌覓食算法（簡稱BFA，下同），同時基于免疫算法（generate and test）的相關(guān)概念，融合半解析解的相關(guān)思想［10］，針對BFA算法的3個操作環(huán)節(jié)（復(fù)制操作環(huán)節(jié)、趨向性操作環(huán)節(jié)和遷移操作環(huán)節(jié)），提出BFA的一種優(yōu)化算法GBFA（Generate Bacterial Foraging Algorithm）：將趨向性操作環(huán)節(jié)中的步長變?yōu)榉枪潭ú介L，可以隨著計算的進行而改變，建立趨向性操作步長的動態(tài)更新機制；此后，利用免疫算法（generate and test）替換BFA的復(fù)制操作環(huán)節(jié)，針對細菌群落進行篩選，將其中適應(yīng)度較高的細菌復(fù)制并替換適應(yīng)度較低的細菌；最后，在遷移操作環(huán)節(jié)中，適應(yīng)度最高的個體被驅(qū)散的概率為0，適應(yīng)度其他的個體被驅(qū)散的概率為Ped。利用GBFA算法，針對RA網(wǎng)絡(luò)建立了以最短接車時間為目標函數(shù)的數(shù)學(xué)模型，并注重考慮了堵車、司機遲緩、司機到達后客戶尋車等因素，構(gòu)建完整的RA網(wǎng)絡(luò)多協(xié)同排序模型。并利用滴滴出行的歷史數(shù)據(jù)進行仿真驗算，驗證本文所提出的RA網(wǎng)絡(luò)多協(xié)同排序模型的適用性和算法的優(yōu)越性，以期為當下約車平臺提供更加合理的排序模型。

1 模型構(gòu)建

1．1 問題定義

客戶打開滴滴出行APP，滴滴出行APP自動定位客戶的位置，客戶輸入目的地后進行“呼叫”操作，這便是發(fā)單（request）；滴滴出行APP將request命令導(dǎo)入云處理器并傳送給某位司機，該司機接單后便完成了一次應(yīng)答（answer）。

自司機應(yīng)答（answer）并送客戶至目的地為一次MISSION，整個事件耗時為TIME。

滴滴出行APP將某個城市劃分成為n個區(qū)域，該城市區(qū)域的集合為D，被劃分的區(qū)域為d，則有

將一天的時間劃分為144個時間片｛t1，t2，t3，…，t144｝，每個時間片的長度為10min。對于區(qū)域di，在時間片tj，有rij個客戶request，同時有aij個司機成功進行了aij次answer；對于區(qū)域di，在時間片tj，需求demandij，供給supplyij＝aij，供需缺口gapij可以表示為

1．2 評價指標

對n個區(qū)域和q個時間片，對于區(qū)域di，在時間片tj，供需缺口為gapij，算法計算出缺口為sij，以MAPE作為排序計算精度的評價指標

以TIME的最優(yōu)解作為排序計算效用的評價指標。

2 算法簡介

將RA網(wǎng)絡(luò)多協(xié)同排序模型問題轉(zhuǎn)化為求解兩個評價指標最優(yōu)值的問題，以下利用GBFA算法進行解答。

2．1 GBFA算法的基本思想

BFA中第i次的步長為

式中：Ns為BFA虛擬的細菌群落中細菌游動的最大次數(shù)；Led為細菌游動的初始步長。

細菌移動的每一次步長均小于初始步長Led。并且，計算開始之時（i值較?。?，第i次的步長Ci很大，可以提高搜索的速度，使得計算可以更快進行；隨著計算過程的進行（i值的增大），第i次的步長Ci會越來越小，這是為了在計算的后期，保證足夠的收斂精度。

在趨向性操作步長的動態(tài)更新機制建立之后，將群落中所有細菌的適應(yīng)度進行累加，并按從大到小的順序進行排列，形成細菌序列。將細菌序列前m（m為百分比）部分的細菌進行n次復(fù)制，將細菌序列中的其余細菌進行剔除，m和n的關(guān)系為

如此一來，細菌群落中m部分的細菌代表了原有的細菌菌落，可以提高細菌群落的整體覓食能力。此后，依照如下步驟對細菌菌落進行變異、繁殖：

1）挑選出細菌群落中適應(yīng)度較高的細菌，標記為克隆群體A；

2）克隆群體A繁殖成為群體B：

式中max為取最大值函數(shù)。

3）對群體B進行變異操作，生產(chǎn)群體C：

式中：random為隨機函數(shù)；B（i）為計算的克隆群體的個數(shù)；β為變異概率β，計算方法為

根據(jù)式（6）可知，適應(yīng)度越高的個體，變異概率β越大。

因為交叉方法

式（7）中，x1、x2、x3、x4為克隆群體中4個不同的細菌。將群體C融合進入群體B中，形成群體D：

4）對群體中，將其中前m（m為百分比）部分的細菌進行n次復(fù)制，將其余細菌進行剔除。

在傳統(tǒng)的BFA算法之中，需要設(shè)定一個遷移概率Ped，如果隨機數(shù)小于遷移概率Ped，就會對細菌進行遷移操作。這樣做的目的是希望細菌可以躍出局部最優(yōu)解的陷阱。但是，這種做法同樣具有極大的弊端，因為遷移概率Ped對于所有的細菌都有效，無論細菌的適應(yīng)度如何，都可能被遷移。GBFA算法在遷移操作環(huán)節(jié)中，適應(yīng)度最高的個體被驅(qū)散的概率為

式中：Round為四舍五入函數(shù)；S為細菌群落的整體個數(shù)；A（i）為計算的克隆群體A的個數(shù)；i為第i次計算；α為克隆的系數(shù)。

為了方便計算，將適應(yīng)度F進行標準化0，適應(yīng)度最高的個體被驅(qū)散的概率為Ped，以提高搜索的速度。

根據(jù)以上思想，繪制GBFA算法流程圖，如圖1所示。

圖1 GBFA算法流程圖

化簡得到

2．2 GBFA算法的斂散性

DASGUPTA對BFA算法的斂散性進行了研究［11－12］，但是DASGUPTA沒有考慮BFA算法模擬菌群內(nèi)部各個細菌個體之間的影響。筆者提出的GBFA雖然沒有觸及到傳統(tǒng)BFA算法的定義基礎(chǔ)，但是由于免疫算法的加入，需要重新證明GBFA的斂散性。

根據(jù)李濤［13］的研究：對于抗體種群A0，抗體空間幾何為I＊，v（A（k））為計算所得最優(yōu)解的個數(shù)，B為最優(yōu)解的個數(shù)，

便可以稱之為該算法收斂到最優(yōu)解集的概率為1。故而，當算法迭代數(shù)量達到一定程度時，便一定會收斂。

GBFA引入了免疫算法，對于抗體種群A0，有

式中Ai（k）表示細菌i在第k次操作的時候所在的位置，而Ai（k）是由Ai（k－1）經(jīng)過克隆、變異而得。

為了方便表述，標記

則有

則有

所以

故而

因為

所以

所以

綜上所述，GBFA以概率1收斂。

2．3 擬合方案

針對歷史數(shù)據(jù)而對未來做出預(yù)測，其數(shù)學(xué)原理為函數(shù)的擬合，對于擬合函數(shù)模型的優(yōu)化，基于智能算法［14］。本文利用Mathematica來進行擬合模型的優(yōu)化，利用GBFA算法對優(yōu)化結(jié)果進行排序。Mathematica是Stephen Wolfram開發(fā)的一套計算機代數(shù)系統(tǒng)，可以對數(shù)據(jù)的擬合函數(shù)模型進行自動優(yōu)化。

選取實驗函數(shù)

其中，RandomVariate［NormalDistribution［0，0．2］］的作用是加上一個均值為0、標準差為2的正態(tài)分布隨機噪聲，x∈［－10，10］。計算結(jié)果為

通過GBFA算法對上述10個擬合模擬進行誤差計算，選取誤差最小的擬合模型：1．134 935 310 743 823 1＋cosx＋1．964 926 975 541 333 4sin（x）cos（x），擬合結(jié)果如圖2所示。

圖2 5擬合模型的自動優(yōu)化

根據(jù)圖2，發(fā)現(xiàn)擬合效果頗佳。

3 排序?qū)崿F(xiàn)方法

根據(jù)問題模型和GBFA算法，開發(fā)RA網(wǎng)絡(luò)多協(xié)同排序軟件”RA－LC”，現(xiàn)就其中的計算流程進行簡要說明。

步驟1：以客戶當前位置為目的地，以附近i名滴滴出行司機的位置為出發(fā)點，尋找出i名滴滴出行司機的位置和客戶當前位置之間所有可行的路徑，按照路徑長度基于GBFA算法進行排序，各自選中序列前j種路徑方案，共ij種路徑方案。

步驟2：調(diào)取該i名滴滴出行司機在時間片tk接單之后，選用第j條路徑方案前往客戶當前位置的時間的歷史數(shù)據(jù)，利用GBFA算法進行排序并選擇最優(yōu)擬合模型，計算得出該次該i名滴滴出行司機在時間片tk接單之后，選用第j條路徑方案前往客戶當前位置的時間為tijk，0。

步驟3：調(diào)取該i名滴滴出行司機在時間片tk發(fā)車前往客戶當前位置之后，選用第j條路徑方案至客戶當前位置的平均速度的歷史數(shù)據(jù)，利用GBFA算法進行排序并選擇最優(yōu)擬合模型，計算得出該次該i名滴滴出行司機在時間片tk發(fā)車前往客戶當前位置之后，選用第j條路徑方案至客戶當前位置的平均速度為vtjk，0。

步驟4：調(diào)取第j條路徑方案在時間片tk突發(fā)堵車的頻率以及時間的歷史數(shù)據(jù)，利用GBFA算法進行排序并選擇最優(yōu)擬合模型，計算得出該次選用第j條路徑方案在時間片tk突發(fā)堵車的概率Pjk，0以及時間tjk，0。

步驟5：計算該i名滴滴出行司機選用第j條路徑方案到達客戶當前位置的時間Tij，0

式中Lj為第j條路徑解決方案的長度。

步驟6：在第i名司機到達客戶當前位置且客戶上車之后，以客戶當前位置為出發(fā)點，尋找出客戶出發(fā)點和目的地之間所有可行的路徑，按照路徑長度基于GBFA算法進行排序，選中序列前J種路徑方案。

步驟7：調(diào)取該i名滴滴出行司機在時間片tk＋Tij0接客戶之后，選用第J條路徑方案前往客戶目的地的時間的歷史數(shù)據(jù)，利用GBFA算法進行排序并選擇最優(yōu)擬合模型，計算得出該次該i名滴滴出行司機在時間片tk＋Tij，0接客戶之后，選用第J條路徑方案前往客戶目的地的時間為tijk，1。

步驟8：調(diào)取該i名滴滴出行司機在時間片tk＋Tij，0發(fā)車前往客戶目的地之后，選用第J條路徑方案至客戶目的地的平均速度的歷史數(shù)據(jù)，利用GBFA算法進行排序并選擇最優(yōu)擬合模型，計算得出該次該i名滴滴出行司機在時間片tk＋TiJ，0發(fā)車前往客戶目的地之后，選用第J條路徑方案至客戶目的地的平均速度為viJk，1。

步驟9：調(diào)取第J條路徑方案在時間片tk＋TiJ，0突發(fā)堵車的頻率以及時間的歷史數(shù)據(jù)，利用GBFA算法進行排序并選擇最優(yōu)擬合模型，計算得出該次選用第J條路徑方案在時間片tk＋TiJ，0突發(fā)堵車的概率PJk，1以及時間tJk，1。

步驟10：計算該i名滴滴出行司機選用第J條路徑方案到達客戶目的地的時間TiJ，1

式中LJ為第J條路徑解決方案的長度。

步驟11：i名滴滴出行司機選用第j條路徑方案到達客戶當前位置，并選用第J條路徑方案到達客戶目的地，整個MISSION的耗時TIMEijJ

步驟12：利用GBFA算法對序列TIMEijJ進行排序，尋找出最優(yōu)方案TIMEmin

4 仿真實驗

以滴滴出行北京市2015年5月—2016年4月的數(shù)據(jù)為對比對象。快車是滴滴出行推出的一種較為快捷的出行方式，司機以單注冊客戶（但注冊客戶可能一人乘車，也可能多人乘車）為服務(wù)對象的服務(wù)方式。2015年9月16日21點37分有單注冊客戶以快車形式request，客戶的當前位置為天壇南門，目的地為北京市昌平區(qū)潢京客棧主題賓館（圖3）。

利用RA－LC軟件計算7位司機在本次MISSION的TIME（圖4）。

2015年9月16日21點37分4號滴滴出行司機answer，選用的路徑與GBFA算法計算路徑相同，2015年9月16日22點41分4號滴滴出行司機完成此次MISSION，耗時64min。由此可見，GBFA算法的計算精度極高，對于TIME的預(yù)測極為精確。

為了進一步驗證GBFA算法對更為廣泛的時間片的適應(yīng)性，選取2015年9月15日、2015年10月15日、2015年11月15日、2015年12月15日、2016年1月15日共5日的數(shù)據(jù)作為研究范圍，每個時間片（10min）選取10個answer，共7 200單出行數(shù)據(jù)，利用RA－LC軟件計算每次MISSION的TIME（圖5），與實際的TIME相比較，分析其誤差N。

式中：N為每個時間片10組數(shù)據(jù)的誤差的平均值；TIMEi，1為時間片內(nèi)實際的i單MISSION的TIME，TIMEi，2為時間片內(nèi)利用RA－LC軟件計算的i單MISSION的TIME。

圖3 GBFA算法計算路線與客戶當前位置的車輛

圖4 利用RA－LC計算而得的7位司機的TIME

通過圖5可以看出，RA－LC軟件計算的MISSION的TIME與實際的誤差較小，均在－0．06～0．06。說明RA－LC軟件對于寬時間跨度的滴滴出行排序模型具有較高的精度。此外，無論是哪個月份，RA－LC軟件計算的MISSION的TIME與實際的誤差值隨時間片的變化是不規(guī)則的，說明RA－LC軟件不受時間的約束，具有極高的適用性。

圖5 N的分布情況

5 結(jié)語

本文改進傳統(tǒng)的細菌覓食算法提出GBFA算法，將GBFA算法應(yīng)用到RA網(wǎng)絡(luò)多協(xié)同排序模型中，并開發(fā)計算程序RA－LC，對滴滴出行2015年 5月—2016年4月的數(shù)據(jù)進行對比，結(jié)論顯示：

1）利用Mathematica軟件對于擬合模型進行優(yōu)化，并利用GBFA算法對優(yōu)化模型進行排序，選取其中最優(yōu)擬合模型，對于預(yù)測司機選用第j條路徑方案前往客戶當前位置的時間為tijk，0、選用第j條路徑方案至客戶當前位置的平均速度為vijk，0、選用第j條路徑方案在時間片tk突發(fā)堵車的概率Pjk，0以及時間tjk，0具有頗佳的準確度。

2）通過單次MISSION，利用RA－LC計算其TIME，并與實際的TIME進行對比，兩者相差近1 min，說明RA－LC對于單次MISSION具有極高的精確度。

3）選取更加寬的時間范圍，利用RA－LC計算其TIME，繪制的分布圖，顯示基于GBFA算法RA網(wǎng)絡(luò)多協(xié)同排序模型對于解答RA網(wǎng)絡(luò)多協(xié)同排序問題具有極佳的適用性，而且N與時間并無明顯的比例關(guān)系，說明基于GBFA算法RA網(wǎng)絡(luò)多協(xié)同排序算法并不受時間的影響。

［1］劉亞秋，吳雙滿，韓大明，等．基于云計算的手機智能出租車呼叫系統(tǒng)［J］．計算機工程，2014，40（4）：14－18．

［2］王超學(xué)，田利波．一種改進的多目標合作型協(xié)同進化遺傳算法［J］．計算機工程與應(yīng)用，2016，52（2）：18－23．

［3］孟祥豪，羅景青，馬賢同．一種基于多站測向和多參數(shù)信息的聯(lián)合分選算法［J］．控制與決策，2016，31（1）：160－164．

［4］Cui J X，Liu F，Janssens D，et al．Detecting urban road network accessibility problems using taxi GPS data［J］．Journal of Transport Geography，2016，51：147－157．

［5］Shen H，Li Z，Qin J，et al．Changes in functional connectivity dynamics associated with vigilance network in taxi drivers［J］．Neuroimage，2016，124（Pt A）：367－378．

［6］Petrovic′M，Sadowski J T， iber A，et al．Wrinkles of graphene on Ir（1 1 1）：Macroscopic network ordering and internal multi－lobed structure［J］．Carbon，2015，94：856－863．

［7］Huang X，Zhao Y，Ma C，et al．TrajGraph：A Graph－Based Visual Analytics Approach to Studying Urban Network Centralities Using Taxi Trajectory Data．［J］．Visualization ＆Computer Graphics IEEE Transactions on，2016，22（1）：160－169．

［8］Jianxun Cui，F(xiàn)eng Liu，Davy Janssens，et al．City－Wide Examining Transport Network Accessibility Using Taxi GPS Data［C］／／Cota International Conference of Transportation Professionals．New York：American Society of Civil Engineers，2015．

［9］SAVCHENKO，VYACHESLAV．Future Developmentof E－Commerce in Russia and Germany［D］．Valencia：University of Applied Sciences Valencia，2015．

［10］王俊奇，李闖，董曄．Bishop法的半解析解及其廣義數(shù)學(xué)模型［J］．水利與建筑工程學(xué)報，2015（6）：123－128．

［11］Tang W J，Li M S，He S，et al．Optimal Power Flow With Dynamic Loads Using Bacterial Foraging Algorithm［C］／／Power System Technology，2006．PowerCon 2006．International Conference on．IEEE，2006：1－5．

［12］DAS S，BISWAS A，DASGUPTA S，et al．Bacterial Foraging Optimization Algorithm：the Oretical Foundations，Analysis，and Applications［C］∥Foundations of Computational Intelligence Volume 3．Berlin／Heidelberg：Springer，2009：23－55．

［13］李濤．計算機免疫學(xué)［M］．北京：電子工業(yè)出版社，2004．

［14］Li L，Zhang B，Li W，et al．Orthogonal polynomial function fitting for hyperspectral data representation and discrimination［J］．Pattern Recognition Letters，2016（1）：56－58．

The Model and Algorithm Research on RA Network More Collaborative Sorting Algorithm

XIE Ting
（Party School of Maanshan City Anhui Province，Maanshan Anhui 243011，China）

A issue got a wide range of concern in the research circle——RA more cooperative network scheduling based on the current rapid development car booking platform．As for the actual travel data bit， the RA network more collaborative problem solving scheduling problems have been changed into two optimal solutions to mathematical model evaluation．Based on the related concepts on traditional immune algorithm（generate and test），combined with semi－analytical solution，an optimization algorithm GBFA（Generate Bacterial foraging algorithm）has been established．Furthermore，an RA network more collaborative sorting algorithm based on GBFA algorithm has been proposed，and an“RA－LC”more collaborative sorting software has been developed．Taking Didi travel data in Beijing from May 2015to April 2016as the contrast object，the relevant examples has been simulated by using RA－LC software．The results show that the algorithm has higher temporal prediction accuracy，and has an excellent applicability and accuracy for the issue of RA more cooperative network sorting．

multi－coordinated sorting；MATHEMATICA；GBFA；Didi travel；time predict

TP391

A

1009－8984（2016）02－0119－07

10．3969／j．issn．1009－8984．2016．02．030

2016－03－25

謝婷（1975－），女（漢），安徽馬鞍山，碩士，講師主要研究計算機信息技術(shù)、網(wǎng)絡(luò)應(yīng)用。