基于WOT的珠海綠道自行車(chē)調(diào)度算法的研究

周毅強(qiáng)++王德昌++李炳煉++楊裕

摘 要：本文介紹一種基于WOT的綠道自行車(chē)調(diào)度的實(shí)現(xiàn)方法，通過(guò)真實(shí)環(huán)境的實(shí)驗(yàn)，證明這種算法是可行性。

關(guān)鍵詞：WOT 調(diào)度算法 ANN算法

中圖分類(lèi)號(hào)：TP3 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2014）09（b）-0012-02

綠道（Greenway）是一種線形綠色開(kāi)敞空間，通常沿著河濱、山脊、風(fēng)景道路等自然和人工廊道建立，內(nèi)設(shè)可供行人和騎車(chē)者進(jìn)入的景觀游憩線路。本文提出一種基于WOT的綠道自行車(chē)調(diào)度算法，盡量使用最少的自行車(chē)數(shù)量服務(wù)盡可能多的綠道出游市民。

1 程序設(shè)計(jì)

我們將程序分為三個(gè)子程序。一、設(shè)計(jì)收集相關(guān)信息的JavaScript程序；二、預(yù)測(cè)前對(duì)源數(shù)據(jù)的分析處理程序；三、預(yù)測(cè)的BP算法。具體實(shí)現(xiàn)如下。

1.1 收集相關(guān)信息的JavaScript程序

由于國(guó)內(nèi)沒(méi)有相關(guān)的實(shí)時(shí)自行車(chē)網(wǎng)上租賃數(shù)據(jù)。因此我們選擇抓取西班牙巴塞羅那的“Bicing”自助自行車(chē)服務(wù)網(wǎng)站（https：//www.bicing.cat/）的數(shù)據(jù)并進(jìn)行分析。Bicing網(wǎng)站的單車(chē)租憑狀況是使用谷歌地圖來(lái)顯示，同時(shí)使用AJAX技術(shù)異步拿數(shù)據(jù)，并且無(wú)刷新更新數(shù)據(jù)。這樣給我們抓數(shù)據(jù)帶來(lái)一些麻煩。我們不能直接請(qǐng)求一個(gè)HTML頁(yè)面來(lái)達(dá)到抓取數(shù)據(jù)的目的。另外，AJAX內(nèi)部其實(shí)也是通過(guò)HTTP協(xié)議來(lái)發(fā)送請(qǐng)求，由于瀏覽器不能看到AJAX發(fā)送的請(qǐng)求和參數(shù)，我們則使用抓包工具分析請(qǐng)求的HTTP包結(jié)構(gòu)（URL以及參數(shù)），并模仿該格式向Bicing服務(wù)器發(fā)送欺騙包，其功能就是模仿用戶(hù)在它的頁(yè)面上點(diǎn)擊查詢(xún)功能。

由于數(shù)據(jù)從傳感器進(jìn)入Bicing的系統(tǒng)，處理后可以在其網(wǎng)站上獲取。我們獲得的直接數(shù)據(jù)是一段包含若干站點(diǎn)數(shù)據(jù)的HTML報(bào)文，需要對(duì)其進(jìn)一步處理，提取有用數(shù)據(jù)，把這些包含多個(gè)站點(diǎn)在某個(gè)時(shí)間的信息保存入單獨(dú)日志文件。

我們使用AJAX異步捕捉數(shù)據(jù)。因?yàn)锳JAX使用HTTP協(xié)議發(fā)送請(qǐng)求，所以AJAX的請(qǐng)求與參數(shù)就不會(huì)顯示在瀏覽器。具體步驟如下。首先，我們?cè)O(shè)置一個(gè)時(shí)間器。當(dāng)時(shí)間到了，重發(fā)一個(gè)請(qǐng)求并重啟時(shí)間器。如果請(qǐng)求并沒(méi)有返回，新建一個(gè)XMLHttpRequest對(duì)象發(fā)送查詢(xún)請(qǐng)求。注意：在時(shí)間器結(jié)束前，我們需要不斷應(yīng)答數(shù)據(jù)，然后抽取其中最有用的信息保存到文件中，如果數(shù)據(jù)應(yīng)答正確的話，否則拋棄該部分?jǐn)?shù)據(jù)。

1.2 預(yù)測(cè)前對(duì)源數(shù)據(jù)的分析處理程序

在物聯(lián)網(wǎng)中，最大的特點(diǎn)就在于終端設(shè)備多樣性。在本系統(tǒng)中，除了在租賃現(xiàn)場(chǎng)使用傳感器收集數(shù)據(jù)外，相關(guān)的的重要數(shù)量，如驛站名稱(chēng)、自行車(chē)剩余數(shù)量等應(yīng)該通過(guò)網(wǎng)站、手機(jī)等其它方式顯示給市民。因此需要對(duì)不同來(lái)源的數(shù)據(jù)統(tǒng)一處理。另一方面，JS腳本產(chǎn)生的日志文件是針對(duì)多個(gè)站點(diǎn)的，而每個(gè)站點(diǎn)數(shù)分鐘即產(chǎn)生一個(gè)日志文件，這樣每天都會(huì)產(chǎn)生數(shù)百個(gè)文件，單靠人工來(lái)整理是不可能的。

我們使用C++編寫(xiě)整理上述收集的日志，把每個(gè)日志里的每個(gè)站點(diǎn)信息單獨(dú)歸為一個(gè)日志文件。在儲(chǔ)存采集到的數(shù)據(jù)文件中，主要有三組重要的數(shù)據(jù)：出租點(diǎn)的號(hào)碼，某出租點(diǎn)自行車(chē)出租和空閑的數(shù)量。所有的信息抽取后生成為新的文件，以出租點(diǎn)的號(hào)碼來(lái)進(jìn)行分組。

1.2 設(shè)計(jì)預(yù)測(cè)的BP算法

為了更準(zhǔn)確的預(yù)測(cè)，本系統(tǒng)使用成熟的BP算法。BP神經(jīng)網(wǎng)絡(luò)是一種神經(jīng)網(wǎng)絡(luò)，一般由三層構(gòu)成，如輸入層，中間層（即隱藏層）和輸出層。在每?jī)蓪又g的聯(lián)系，而沒(méi)有在每一層中的神經(jīng)元之間的聯(lián)系。BP算法的主要思想是將學(xué)習(xí)過(guò)程分為兩個(gè)階段：第一，解決每個(gè)單元的實(shí)際輸出值根據(jù)輸入的信息通過(guò)輸入層，隱藏層處理的；第二，找出誤差之間的實(shí)際和預(yù)期的輸出，如果期望輸出值不在輸出得到的層，它是用來(lái)調(diào)整權(quán)重。

2 實(shí)驗(yàn)

“Bicing”自助自行車(chē)服務(wù)中心在全市共有多個(gè)自行車(chē)租車(chē)點(diǎn)，提供約200輛自行車(chē)，有包含385個(gè)傳感器實(shí)時(shí)測(cè)量出在不同的出租站可用自行車(chē)的數(shù)量及空位。

圖一列出其中三個(gè)出租點(diǎn)收集的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，圖中的三條曲線分別是使用ANN算法進(jìn)行觀測(cè)的結(jié)果，真實(shí)數(shù)值和平均值方法預(yù)測(cè)。

可以看出，該算法與實(shí)際情況相吻合。同時(shí)，可以從圖1得出三個(gè)結(jié)論。首先，在某個(gè)出租點(diǎn)自行車(chē)的出租數(shù)量在某些時(shí)間是飛速變化而某些時(shí)間卻維持不變，而這些時(shí)間與生活作息時(shí)間高度吻合。第二，與平均預(yù)測(cè)算法相比，ANN算法在自行車(chē)的出租數(shù)量變化不大的時(shí)間里，表現(xiàn)相對(duì)差些，但在出租數(shù)量變化頻繁的時(shí)間里表現(xiàn)良好，而這剛好才是我們關(guān)心的上下班高峰時(shí)間段。第三，該算法的預(yù)測(cè)結(jié)果與真實(shí)值有一定的距離，尤其在圖1（c）中表現(xiàn)明顯，這種現(xiàn)象主要是因?yàn)樵撍惴ㄐ枰紤]泛化能力而引起的正常誤差。圖2給出某天預(yù)測(cè)數(shù)據(jù)與原始數(shù)據(jù)的對(duì)比圖。

最后我們給出選擇捕捉數(shù)據(jù)的時(shí)間窗口大小對(duì)預(yù)測(cè)準(zhǔn)確性的影響。我們選擇從5分鐘到25分鐘不同大小的時(shí)間窗口，列出對(duì)應(yīng)的預(yù)測(cè)錯(cuò)誤率，如圖2。

3 結(jié)論

本文提出了一種基于人工神經(jīng)網(wǎng)絡(luò)的自行車(chē)調(diào)度預(yù)測(cè)算法。由于預(yù)測(cè)目標(biāo)，即出租自行車(chē)的數(shù)量是與以前的出租情況及生活作息高度相關(guān)，因此我們采用三層人工神經(jīng)網(wǎng)絡(luò)算法作為預(yù)測(cè)的主要算法。通過(guò)實(shí)驗(yàn)對(duì)比，這種算法在實(shí)際應(yīng)用中是可行的。

參考文獻(xiàn)

[1] Rob van Kranenburg.The Internet of Things：A critique of ambient technology and the all-seeing network of RFID[J].Network Notebooks，2007，2（1A）：22-50.

[2] Trieschmann，Jammes S.and George E.Pinches，A Multivariate Model for Predicting Financially Distressed P-L Insures，Journal of Risk and Insurance， 1973，40：327-338.endprint