馮惠英 林宇洪 紀(jì)自家

1. 福建林業(yè)職業(yè)技術(shù)學(xué)院，福建，南平353000

2. 福建農(nóng)林大學(xué)，交通學(xué)院，福州350002

3. 廈門易維信息技術(shù)有限公司，福建，廈門361008

0 引 言

在中國(guó)，產(chǎn)業(yè)關(guān)聯(lián)、人文相似的相鄰城市已出現(xiàn)同城化趨勢(shì)。同城化將促進(jìn)區(qū)域一體化，提升區(qū)域整體競(jìng)爭(zhēng)力，形成輻射力與競(jìng)爭(zhēng)力越來(lái)越強(qiáng)的板塊經(jīng)濟(jì)。同城化能夠增進(jìn)多個(gè)城市的相互交流，消除經(jīng)濟(jì)壁壘，增加就業(yè)機(jī)會(huì)，調(diào)節(jié)農(nóng)產(chǎn)品價(jià)格，充分利用資源，提高市民生活水平[1]。

在同城化的背景下，原本分散于不同城市的市民在工作、生活中將會(huì)發(fā)生緊密的聯(lián)系。市民需要頻繁地來(lái)往于周邊城市，環(huán)保、經(jīng)濟(jì)的公交車將是市民的首選出行方式，原有的各自為政的城市公交信息查詢系統(tǒng)已不能滿足群眾需求[2]。

《廈漳泉大都市區(qū)同城化總體規(guī)劃》提出將實(shí)現(xiàn)廈漳泉海陸空交通的無(wú)縫對(duì)接，力爭(zhēng)2020年實(shí)現(xiàn)全城化[3]。在廈漳泉同城化進(jìn)程中，研發(fā)智能公交同城化信息查詢系統(tǒng)成為了迫切需求。

1 系統(tǒng)開發(fā)背景

在廈漳泉同城化進(jìn)程中，三地均意識(shí)到公交同城化必須先行，2012年6月29日，投資2800萬(wàn)元的漳州角美公交樞紐站建成投入使用。該樞紐站匯集了3條同城化公交車線路：廈門853路（廈門輪渡—漳州角美）、廈門709路（漳州角美火車站—廈門海滄房產(chǎn)）、廈門830路（廈門旭日海灣—漳州角美鎮(zhèn)）。三條線路受到了市民的歡迎，在調(diào)查中，市民認(rèn)為常態(tài)化、密集化跨城公交線路的客運(yùn)形式，比城際客運(yùn)、出租車更加便利和便宜。可以預(yù)見，隨著同城化進(jìn)程的發(fā)展，承擔(dān)同城化任務(wù)的公交線路將越來(lái)越多。

通過(guò)問(wèn)卷調(diào)查了解到，因?yàn)榻煌ㄐ畔⒌牟粚?duì)稱，許多市民感到同城化線路距離遠(yuǎn)，不確定因素較多，擔(dān)心誤選了停運(yùn)線路，導(dǎo)致出行失敗。還有一些市民抱怨到了另一個(gè)城市后，不熟悉當(dāng)?shù)氐墓痪€路，無(wú)法利用公交資源。因此公交優(yōu)先的發(fā)展戰(zhàn)略，不僅僅需要加強(qiáng)硬件設(shè)施的建設(shè)，還需要重視公交乘客的消費(fèi)心理，只有公交乘客獲得了良好的消費(fèi)體驗(yàn)后，才會(huì)從內(nèi)心真正支持并優(yōu)先選擇公交資源。因此建設(shè)一個(gè)透明的公交同城化信息查詢平臺(tái)，能夠向市民提供更多的公交資源信息，鼓勵(lì)并引導(dǎo)出行者優(yōu)先使用公交。

2 系統(tǒng)架構(gòu)的設(shè)計(jì)

設(shè)計(jì)系統(tǒng)架構(gòu)如圖1所示。三市公交總公司聯(lián)合架設(shè)云服務(wù)中心，委托信息公司管理，設(shè)置通訊服務(wù)器，建立短信平臺(tái)或Mobile Web手機(jī)網(wǎng)站，集中管理基礎(chǔ)數(shù)據(jù)，并響應(yīng)乘客發(fā)出的查詢請(qǐng)求[4]。同時(shí)通訊服務(wù)器接收公交車車載 GPS通過(guò)GPRS方式發(fā)出的位置信息，判斷公交線路是否擁堵停滯。接收接駁樞紐通過(guò)GPRS發(fā)出的運(yùn)營(yíng)狀態(tài)信息，判斷同城化線路、接駁線路是否停運(yùn)，確保出行者獲得的換乘方案均可執(zhí)行[5]。在公交車運(yùn)營(yíng)狀態(tài)改變、線路擁堵斷班次時(shí)，及時(shí)通知路途上的乘客最新交通信息，幫助乘客調(diào)整換乘方案，改善公交乘客的乘車體驗(yàn)。使用短信平臺(tái)或手機(jī)網(wǎng)站查詢的方式，無(wú)需隨身攜帶電腦，只需在手機(jī)上安裝特定查詢軟件，方便了用戶在出行移動(dòng)中查詢。無(wú)論手機(jī)硬件好壞，都能得到質(zhì)量大致相當(dāng)?shù)男畔⒎?wù)，體現(xiàn)了云服務(wù)資源分享的公平性。

圖1 系統(tǒng)架構(gòu)Fig.1 The system architecture

3 短信平臺(tái)的開發(fā)

問(wèn)卷調(diào)查了解到，當(dāng)?shù)毓怀丝拖矏凼謾C(jī)短信查詢換乘方案，因此在通訊服務(wù)器上架設(shè)短信平臺(tái)，用于接收乘客發(fā)出的查詢短信。把查詢請(qǐng)求存入 SQL Server數(shù)據(jù)庫(kù)，計(jì)算服務(wù)器隨機(jī)選取一條查詢請(qǐng)求，計(jì)算最優(yōu)的換乘方案后，存回?cái)?shù)據(jù)庫(kù)。通訊服務(wù)器從數(shù)據(jù)庫(kù)中檢索已計(jì)算好的查詢?nèi)蝿?wù)，把換乘方案以長(zhǎng)短信的形式發(fā)送給乘客。

3.1 架構(gòu)設(shè)計(jì)

以通訊服務(wù)器架設(shè)為短信平臺(tái)為例，平臺(tái)架構(gòu)見圖2，采用Microsoft Visual FoxPro 9.0開發(fā)。

（1）工作層?？紤]客戶的手機(jī)號(hào)可能分屬于不同的運(yùn)營(yíng)商，因此申請(qǐng)移動(dòng)、聯(lián)通或電信的短信網(wǎng)關(guān)（ISMG，Internet Short Message Gateway），用于接收和發(fā)送短信。

（2）控制層。控制層將實(shí)現(xiàn)對(duì)工作層的控制，使用CMPP（China Mobile Peer to Peer）協(xié)議實(shí)現(xiàn)對(duì)移動(dòng)公司短信網(wǎng)關(guān)的控制，使用 SCIP（Short Message Gateway Interface Protocol）協(xié)議實(shí)現(xiàn)對(duì)聯(lián)通公司短信網(wǎng)關(guān)的控制，使用 SMGP（Short Message Gateway Protoco）協(xié)議實(shí)現(xiàn)對(duì)電信公司短信網(wǎng)關(guān)的控制。

（3）緩存層。建立緩存層，短信平臺(tái)在工作中會(huì)接收到大量垃圾短信，將收到短信暫存于緩存層，簡(jiǎn)單判斷其格式是否符合系統(tǒng)定義的約定格式“（起點(diǎn)）#（終點(diǎn)）”，直接在緩存層刪除垃圾短信，避免把垃圾短信送入后臺(tái)數(shù)據(jù)層。另外，緩存層有助于緩沖并暫存收發(fā)短信，平衡工作層和邏輯層之間的速度差異。

（4）邏輯層。從已收短信表中獲取查詢短信，采用識(shí)別算法解析查詢短信，把查詢短信按約定格式轉(zhuǎn)換成帶起點(diǎn)、終點(diǎn)的查詢請(qǐng)求，將查詢請(qǐng)求存入 SQL Server數(shù)據(jù)庫(kù)，并設(shè)置為“等待計(jì)算”的標(biāo)識(shí)。隨后，從數(shù)據(jù)庫(kù)中檢索具有“計(jì)算成功”標(biāo)志的查詢請(qǐng)求，提取換乘方案，把換乘方案形成短信內(nèi)容，存入待發(fā)短信表，隨即把“計(jì)算成功”標(biāo)識(shí)改為“發(fā)送成功”標(biāo)識(shí)。

（5）數(shù)據(jù)層。數(shù)據(jù)層建立在數(shù)據(jù)庫(kù)服務(wù)器上，用于存儲(chǔ)用戶的查詢請(qǐng)求。周邊的計(jì)算服務(wù)器從數(shù)據(jù)庫(kù)中隨機(jī)提取標(biāo)識(shí)為“等待計(jì)算”的查詢請(qǐng)求，計(jì)算出換乘方案后，再回存于數(shù)據(jù)庫(kù)中，并在該記錄上設(shè)置“計(jì)算成功”的標(biāo)志。在短信平臺(tái)外，還有一些協(xié)同系統(tǒng)參與工作，例如公交GIS管理系統(tǒng)、同城化線路調(diào)度系統(tǒng)[6]。

圖2 短信平臺(tái)架構(gòu)Fig.2 The SMS platform architecture

3.2 長(zhǎng)短信技術(shù)開發(fā)

公交同城化換乘方案內(nèi)容會(huì)比較復(fù)雜，因此普通70字的短信無(wú)法承載，必須開發(fā)長(zhǎng)短信技術(shù)，長(zhǎng)短信技術(shù)可以攜帶 70～2000字的信息內(nèi)容。長(zhǎng)短信PDU(Protocol Data Unit)數(shù)據(jù)包的編碼規(guī)則必須遵循GSM 03.40規(guī)范[7]，本課題設(shè)計(jì)的編碼見表1。首先制作長(zhǎng)短信的短信頭，按要發(fā)送的內(nèi)容字?jǐn)?shù)，建立分拆短信的數(shù)組，向分拆短信數(shù)組中存入每條短信的協(xié)議頭。例如，要發(fā)送180個(gè)漢字的內(nèi)容，將拆成三條分拆短信，取一隨機(jī)數(shù)作為本次長(zhǎng)短信唯一標(biāo)識(shí) ID，如 ID為“28”，三條分拆短信的協(xié)議頭分別為，“050003280301”、“050003280302”、“050003280303”。將180個(gè)漢字的內(nèi)容分解為三段分拆正文，字?jǐn)?shù)分別為 67、67、46。把長(zhǎng)短信的短信頭、分拆短信的協(xié)議頭與分拆正文組成一條分拆短信，把三條分拆短信分別存入數(shù)組。從數(shù)組中提取分拆短信，逐條送至短信網(wǎng)關(guān)發(fā)送。在用戶手機(jī)上能顯示成一條長(zhǎng)短信，方便用戶閱讀。

表1 長(zhǎng)短信編碼表Tab.1 CSMS transmitting codes

4 同城化換乘算法的研究

同城化公交換乘算法與普通的單城市換乘算法不同，在收到查詢短信時(shí)，首先判定起點(diǎn)、終點(diǎn)是否在同一城市：如果在同一個(gè)城市，使用單城市換乘算法即可；如果不處于同一個(gè)城市，則要：（1）先計(jì)算兩城市中最便利的同城化線路的換乘方案，選優(yōu)標(biāo)準(zhǔn)采用費(fèi)用最低優(yōu)先。選中同城化線路，則確定了一批匹配的接駁樞紐。（2）接著用單城市換乘算法計(jì)算起點(diǎn)至始發(fā)城市選中的接駁樞紐的換乘方案、計(jì)算目標(biāo)城市選中的接駁樞紐至終點(diǎn)的換乘方案。（3）將“始發(fā)城市的換乘方案”+“同城化線路”+“目標(biāo)城市的換乘方案”拼接成出行方案。為了保證乘客獲得的出行方案可行，還必須利用車輛的位置信息、樞紐的運(yùn)營(yíng)信息判定所需線路是否處于正常通行狀態(tài)。

4.1 搜索樹算法

基于公交乘客最少換乘次數(shù)、最少站點(diǎn)的消費(fèi)心理，設(shè)計(jì)用于單城市換乘查詢的搜索樹算法，見圖3。以從站點(diǎn)A至站點(diǎn)B為例，算法過(guò)程如下：（1）查詢直達(dá)方案：從起點(diǎn)A出發(fā)，途經(jīng)A的所有公交線路均為主干，查詢主干所有節(jié)點(diǎn)(公交站點(diǎn))中是否出現(xiàn)B，如果出現(xiàn)多個(gè)B，則存在多種直達(dá)方案。如果未出現(xiàn)B，說(shuō)明不存在直達(dá)方案，執(zhí)行步驟2。（2）查詢一次換乘方案：在主干上的所有節(jié)點(diǎn)繪制新的公交線路，成為第一層枝。查詢第一層枝節(jié)點(diǎn)中是否存在B，如果未出現(xiàn)B，說(shuō)明不存在一次換乘方案，執(zhí)行步驟3。（3）查詢二次換乘方案，在第一層枝上的所有節(jié)點(diǎn)上繪制新的公交線路，形成第二層枝，在第二層枝上查詢是否出現(xiàn)B，如果未出現(xiàn)B，說(shuō)明不存在二次換乘方案，搜索中止。廈漳泉的實(shí)驗(yàn)證明，二次換乘已能實(shí)現(xiàn)市內(nèi)任意兩個(gè)站點(diǎn)通達(dá)。如果未來(lái)出現(xiàn)兩點(diǎn)之間二次換乘不能通達(dá)，說(shuō)明當(dāng)?shù)毓痪W(wǎng)絡(luò)有缺陷，應(yīng)當(dāng)對(duì)公交網(wǎng)絡(luò)進(jìn)行優(yōu)化。為了避免出現(xiàn)死循環(huán)，一個(gè)公交線路號(hào)僅能在搜索樹中出現(xiàn)一次。

圖3 公交換乘搜索樹Fig.3 The bus transfer searching tree

搜索樹建立在數(shù)據(jù)庫(kù)中，每個(gè)節(jié)點(diǎn)由五字段表達(dá)：prestat(前節(jié)點(diǎn)站點(diǎn)編號(hào))、preline (前節(jié)點(diǎn)線路編號(hào))、selfstat(本節(jié)點(diǎn)站點(diǎn)編號(hào))、selfline(本節(jié)點(diǎn)線路編號(hào))、selfleve(本節(jié)點(diǎn)枝的層級(jí))。以查詢二次換乘方案為例，在以A為起點(diǎn)的搜索樹“A_tree”中，采用SQL查詢指令“SELECT * INTO AtoB_2 FROM A_tree WHERE selfstat=B AND selflevel=2”，數(shù)據(jù)集“AtoB_2”的記錄數(shù)即為從A二次換乘可達(dá) B的方案數(shù)。使用SQL查詢指令“SELECT * FROM A_treec WHERE selfstat =B1.prestat AND selfline=B1.preline”，能夠逆推節(jié)點(diǎn) B1的父節(jié)點(diǎn)信息，從而追溯獲得從A至B的換乘方案。

4.2 折半查找算法

搜索樹算法首先考慮換乘次數(shù)最少方案，接著考慮站點(diǎn)數(shù)最少方案，吻合了公交乘客的消費(fèi)心理，是很理想的換乘算法。但在壓力測(cè)試中也發(fā)現(xiàn)，臨時(shí)構(gòu)建搜索樹，消耗了較多的計(jì)算資源，在公交高峰期，查詢壓力很大，系統(tǒng)響應(yīng)會(huì)有明顯的滯后現(xiàn)象。通過(guò)觀察，早上七點(diǎn)半，下午五點(diǎn)半兩個(gè)公交高峰期均為白天班線，而白天班線運(yùn)營(yíng)狀態(tài)穩(wěn)定，因此可以建立一個(gè)靜態(tài)的“通聯(lián)表”，記錄任意兩站點(diǎn)之間的換乘方案。

調(diào)用搜索樹算法計(jì)算任意兩點(diǎn)之間最優(yōu)秀的 5個(gè)換乘方案，存入“通聯(lián)表”，在“通聯(lián)表”中設(shè)置檢索編號(hào)，檢索編號(hào)=起點(diǎn)編號(hào)×10000+終點(diǎn)編號(hào)。“通聯(lián)表”建立好后，接到查詢請(qǐng)求時(shí)，無(wú)須動(dòng)態(tài)生成搜索樹，而是直接計(jì)算檢索編號(hào)，采用折半查找法從“通聯(lián)表”中取出檢索編號(hào)對(duì)應(yīng)的換乘方案。

設(shè)“通聯(lián)表” L = ( R1,R2,… ,Rn)，其中 Ri(1 ≤ i≤n)，用y表示檢索號(hào)，在L中尋找特定檢索號(hào)的過(guò)程可以表達(dá)為Ri·y=B，B指要查找的編號(hào)，當(dāng)R1·y、 R2·y、 … 、 Rn·y 為有序排列，則無(wú)須順序遍歷尋找，可采用折半查找法。當(dāng)表長(zhǎng)為n，查找B成功時(shí)的查找次數(shù)最多為h次，則 n ≈ 2h-1。設(shè)表長(zhǎng) n = 2h-1，所以有：

以上數(shù)學(xué)推導(dǎo)證明了“采用折半查找法能夠使查找長(zhǎng)度按1/2的指數(shù)級(jí)縮小”。以廈門為例，廈門目前有1 454個(gè)公交站點(diǎn)，考慮到大多數(shù)公交線路有上下行差異，從起點(diǎn)至終點(diǎn)的公交線路不一定可逆，因此兩兩站點(diǎn)相通聯(lián)組合為2 112 662個(gè)，采用折半查找算法平均僅用20.01次讀表即可找到換乘方案，查找時(shí)所需要的內(nèi)存空間為1個(gè)字段。采用順序查找法則平均需要1 056 331次讀表，查找時(shí)所需要的內(nèi)存空間為1個(gè)字段。廈門目前有107條線路，考慮上下行差異，計(jì)214條線路，每條線路平均28個(gè)站點(diǎn)，即需要5992×5次讀表獲得各線路的途經(jīng)站點(diǎn)信息，才能構(gòu)建完整的搜索樹，建樹時(shí)所需要的內(nèi)存空間為5992×5個(gè)字段。原本采用搜索樹算法需要6.38s的查詢?nèi)蝿?wù)，現(xiàn)采用折半查找算法僅需 0.01s，消耗的服務(wù)器資源微乎其微，因此在公交高峰期，可以承受巨大的并發(fā)查詢壓力，不會(huì)出現(xiàn)滯后的現(xiàn)象。

4.3 兩種換乘算法聯(lián)合使用

折半查找算法適合于運(yùn)營(yíng)狀態(tài)穩(wěn)定的白天班線，以承受海量查詢壓力。在夜間許多線路會(huì)陸續(xù)停運(yùn)，切換為搜索樹算法，利用運(yùn)營(yíng)狀態(tài)動(dòng)態(tài)地創(chuàng)建搜索樹，以確保出行方案可實(shí)現(xiàn)。

5 運(yùn)行實(shí)例

本次設(shè)計(jì)的查詢系統(tǒng)已投入試用，云服務(wù)系統(tǒng)架設(shè)在廈門某信息公司的機(jī)房，集中管理三地公交資源數(shù)據(jù)。目前通訊服務(wù)器采用短信平臺(tái)的形式，統(tǒng)一響應(yīng)三地市民發(fā)出的查詢請(qǐng)求。

跨城換乘查詢舉例如下：云服務(wù)系統(tǒng)收到市民發(fā)出的查詢短信“1#廈門大學(xué)#漳州教育學(xué)院”后，系統(tǒng)根據(jù)功能號(hào)“1”判定為查詢換乘方案，模糊查詢起點(diǎn)最近的公交站有“廈門大學(xué)站”，終點(diǎn)最近的公交站有漳州市的“教育學(xué)院站”，從而判斷起點(diǎn)、終點(diǎn)不在同一個(gè)城市。調(diào)用“同城化線路換乘算法”，獲得廈門至漳州費(fèi)用最低的同城化線路為“廈門853路”、接駁線路為“漳州23路”，從而確定接駁樞紐站為“角美樞紐站”。調(diào)用“搜索樹算法”或“折半查找法”計(jì)算從“廈門大學(xué)站”至“角美樞紐站”的最佳方案，再計(jì)算“角美樞紐站”至“漳州教育學(xué)院站”的最佳方案，將三段方案拼成完整的公交出行方案。根據(jù)車輛位置信息，估算起點(diǎn)站的公交車到站時(shí)間。最后系統(tǒng)回應(yīng)短信內(nèi)容為“廈門大學(xué)站乘廈門841路12站至海滄房產(chǎn)站，換乘廈門853路26站至角美樞紐站，換乘漳州23路37站至漳州教育學(xué)院站。廈門841路車約6分鐘后到達(dá)廈門大學(xué)站”。

公交信息查詢舉例如下：云服務(wù)系統(tǒng)收到市民發(fā)出的查詢短信“2#853”后，系統(tǒng)根據(jù)功能號(hào)“2”判定為查詢公交資源信息。系統(tǒng)則在三個(gè)城市的線路表、站點(diǎn)表中模糊檢索關(guān)鍵詞為“853”信息，猜測(cè)用戶擬查詢廈門853路公交車的詳情。隨后系統(tǒng)把廈門853路公交車上下行途經(jīng)站點(diǎn)、上下班時(shí)間以長(zhǎng)短信的形式發(fā)回給用戶。

6 總 結(jié)

同城化發(fā)展戰(zhàn)略將實(shí)現(xiàn)地區(qū)經(jīng)濟(jì)一體化，消除商業(yè)活動(dòng)的壁壘，讓生產(chǎn)要素自由流動(dòng)。在這一進(jìn)程中，公交同城化必須先行，拉近城市之間的生活距離。本系統(tǒng)為廈漳泉市民提供了統(tǒng)一的公交同城化查詢平臺(tái)，設(shè)計(jì)了搜索樹算法實(shí)現(xiàn)了最優(yōu)換乘方案的求解，并應(yīng)用折半查找算法對(duì)搜索樹算法進(jìn)行了改良，提高了計(jì)算能力[8]。在壓力測(cè)試時(shí)，4臺(tái)計(jì)算服務(wù)器可以應(yīng)對(duì) 24 000條/h的查詢壓力。本架構(gòu)計(jì)算能力具有優(yōu)秀的擴(kuò)展性，如果以后不能滿足實(shí)際需求，根據(jù)新增加的工作壓力大小，掛入適量的計(jì)算服務(wù)器即可。

[1] 余舒悅．廈漳泉大都市區(qū)同城化建設(shè)的條件分析與對(duì)策思考[J]．臺(tái)灣農(nóng)業(yè)探索，2012，(3)：40-43．

[2] 王明浩，龐革平，謝振華．廣西北部灣經(jīng)濟(jì)區(qū)開啟“同城化”[N]．人民日?qǐng)?bào)，2013-06-22 (1)．

[3] 李志清，王婷，吳繼貴．廈漳泉物流同城化發(fā)展研究[J]．物流工程與管理，2012，34(10)：29-32．

[4] Scanaill C. N., Ahearne B., Lyons G. M. Long-term telemonitoring of mobility trends of elderly people using SMS messaging[J]. IEEE Transactions on Information Technology in Biomedicine, 2006, 10(2):412-413．

[5] Swadesh Kumar Samanta, John Woods, Mohammed Ghanbari. A business model for mobile commerce applications using multimedia messaging service[J].International Journal of Business Information Systems, 2010, 5(4): 418-439．

[6] 林春水，林宇洪，郭建鋼．基于BPNN的高速公路風(fēng)雨天氣限速系統(tǒng)的設(shè)計(jì)[J]．交通運(yùn)輸工程與信息學(xué)報(bào)，2013，11(3)：35-39，57．

[7] Samanta S.K., Woods et al. Special delivery: an increase in MMS adoption[J]． IEEE Potentials,2009, 28(1): 12-16.

[8] 林宇洪，沈嶸楓，邱榮祖．南方林區(qū)林產(chǎn)品運(yùn)輸監(jiān)管系統(tǒng)的研究[J]．北京林業(yè)大學(xué)學(xué)報(bào)，2011，33(5)：130-135．