容爾健，易桂軒，魏金占，蔡素影

(1.廣東中冶地理信息股份有限公司，廣東 東莞 523000； 2.武漢市測繪研究院，湖北 武漢 430022；3.北部灣大學(xué)，廣西 欽州 535000)

1 引 言

排隊等號系統(tǒng)在社會領(lǐng)域扮演非常重要的角色，對于社會穩(wěn)定，人民素質(zhì)的提升意義重大。但傳統(tǒng)的廣播模式排隊等號系統(tǒng)不能及時與客戶溝通，很容易造成客戶時間的浪費，同時因為各類原因造成排號機(jī)會錯失需要再次排號，給客戶造成巨大浪費，極易造成服務(wù)方和客戶的矛盾，增加社會不穩(wěn)定因素。

近年來隨著物聯(lián)網(wǎng)技術(shù)快速發(fā)展，排隊等候業(yè)務(wù)逐漸與個人多媒體終端如手機(jī)、平板等融合，客戶可以在多媒體終端實現(xiàn)電子排號申請。這些手段在一定程度上方便了客戶，節(jié)約了一定時間，但本質(zhì)上與紙質(zhì)申請或排隊等候模式差異不大，都是以時間序列為基準(zhǔn)的單向模式，仍有巨大的提升空間。

對于排隊問題的本質(zhì)，實際上是服務(wù)資源的單一串行服務(wù)于突發(fā)的并行服務(wù)需求的矛盾?；诖死斫?，對于串行單向服務(wù)，一是增加服務(wù)資源，二是將服務(wù)對象合理分組串行化，即通過排隊候服以實現(xiàn)兩者的匹配，達(dá)到服務(wù)數(shù)量與服務(wù)對象的合理匹配。

從空間信息學(xué)的角度分析，可以做如下分析：一是服務(wù)點的位置不變；二是服務(wù)對象的空間分散與動態(tài)化；三是服務(wù)對象運動軌跡沿著道路行進(jìn)?；诖巳齻€基本特點，可以通過基于服務(wù)點的范圍分析，對服務(wù)對象進(jìn)行分組，協(xié)助兩者實現(xiàn)合理匹配。

結(jié)合以上分析，可以認(rèn)為該問題將涉及范圍分析、最短路徑分析和時空互動，基于此筆者提出一種交互式的排隊等號方法，其主要依托空間位置關(guān)系，充分考慮客戶的時間安排，做到等號效率與客戶時間利用率的最佳組合。

2 問題解決

服務(wù)點不動服務(wù)對象從多方位靠近，因此就涉及兩個核心技術(shù)：點點之間的最短路徑問題和服務(wù)范圍問題。

對于點點之間的最短路徑問題，這是一個經(jīng)典空間問題。對于最短路徑技術(shù)，當(dāng)前常見技術(shù)多以數(shù)學(xué)方法和生物學(xué)思維實現(xiàn)問題求解。前者以Dijkstra算法為主，后者以蟻群算法、遺傳算法為主[1～6]。

對于前者，該算法具有可以求得精確解的特性，而且對于樣本空間的所有結(jié)點都可以求得最短路徑，因此在面向點對點服務(wù)時，當(dāng)數(shù)據(jù)量較大則該算法適用性和效率欠佳[5]。

對于生物學(xué)思維，其采用進(jìn)化思維，該類方法的特點是可以并行計算，但難于給出最優(yōu)解，因此適用于并發(fā)、高效率路徑最短搜索[6]。

本問題最短路徑具有服務(wù)點不動特性，路網(wǎng)不會輕易變更的特性，基于此對于前者，可以采用傳統(tǒng)Dijkstra算法，將每個樣本空間的節(jié)點間的最短路徑求解，過濾出基于服務(wù)點的所有最短路徑[5]。待客戶發(fā)出需求服務(wù)時，臨近節(jié)點迅速被選中并調(diào)出該結(jié)點到最近服務(wù)點的最短路徑。其特點是也決定了對樣本量的要求不能過大，可以前期進(jìn)行預(yù)運算，適用于一般規(guī)模城市的該類問題解決。

若采用生物學(xué)類的相關(guān)技術(shù)，因其具有并發(fā)高效的特點，適用于大范圍、高效率的路徑分析，因此不需要進(jìn)行預(yù)運算即可實現(xiàn)問題求解[6]。該類技術(shù)原理簡單易于實現(xiàn)，特別適合于云時代并行計算，因此對于建設(shè)各類城市大腦模式服務(wù)的資源調(diào)度具有普適性。

以上技術(shù)雖然具有最優(yōu)和最快的特點，各有優(yōu)劣，但是經(jīng)過分析可知，前者最怕的是樣本空間的擴(kuò)大化，后者最怕的是快的同時缺失精準(zhǔn)度。因此可以將后者的搜索結(jié)果，作為前者的樣本空間，進(jìn)而實現(xiàn)兩種技術(shù)優(yōu)劣互補(bǔ)。

筆者選用由魏金占等人提出的基于空間分析技術(shù)的最短路徑搜索技術(shù)。其特點在于通過將樣本區(qū)間通過升維進(jìn)行拓展，將長度區(qū)間升維到橢圓空間，通過面空間約束搜索范圍，進(jìn)而實現(xiàn)了最短路徑搜索。與前兩者相比，其特點是可以實現(xiàn)實時、動態(tài)、海量樣本的最優(yōu)搜索，是將以上兩種思維進(jìn)行融合的新產(chǎn)物[7～11]。特別是其利用的是空間分析相關(guān)技術(shù)，與本問題求解的覆蓋分析部分，技術(shù)同源，因此對于該問題的求解，本文優(yōu)選采用空間思維的新技術(shù)。

對于覆蓋問題，通?？梢圆捎煤唵尉彌_區(qū)分析思維來實現(xiàn)。但由于行人多基于道路行動，因此簡單緩沖區(qū)思維將造成實際點位到服務(wù)點的道路距離大于直線距離?；诖吮锥耍Y(jié)合如上提及的距離升維方法，將對樣本區(qū)間進(jìn)行如下操作：

首先確定客戶行進(jìn)的速度和距離，得到其返回的最理想時間。把距離減半，以服務(wù)點為中心，將所有減半后的范圍內(nèi)路口節(jié)點都作為滿足條件的節(jié)點。對于處于一半距離以上但在該距離之內(nèi)的，通過空間分析過濾后，將各個節(jié)點到服務(wù)點的最短距離求解出來，滿足條件標(biāo)識出來。最后將所有處于該環(huán)內(nèi)的滿足條件的節(jié)點依次相連，范圍內(nèi)部即為該客戶的自由活動范圍。

該步驟的優(yōu)勢在于通過一半距離的過濾，減少計算機(jī)的運算量。后期通過距離分析，過濾出最終范圍，類似于雙層過濾，結(jié)合自然思維“設(shè)置的約束條件越多”求解速度越快，實現(xiàn)了問題求解快與準(zhǔn)的協(xié)調(diào)統(tǒng)一[12]。

3 案例分析

基于以上思維，本文旨在提供一種雙向互動模式的排號呼叫方法，該方法克服現(xiàn)有排號系統(tǒng)單向廣播模式的缺陷，實現(xiàn)了客戶與服務(wù)點的雙向互動，具有原理簡單，易于實現(xiàn)、適用性強(qiáng)的特點[12]。

為了簡化問題，對于活動區(qū)域的定義，暫時只采用緩沖區(qū)分析模式，通過距離判定實現(xiàn)問題分析，實際實現(xiàn)時必須結(jié)合路網(wǎng)實際進(jìn)行細(xì)化，確保問題求解的精確可靠[12]。

圖1為本文實施例的服務(wù)點與客戶位置點示意圖，圖中各部分名稱及序號如下：

圖1 服務(wù)點、客戶位置及范圍類別示意圖

1為服務(wù)點，2為客戶位置點，3為當(dāng)次叫號時間差對應(yīng)范圍，4為下班前時差對應(yīng)活動范圍。

下面結(jié)合圖2和實施例具體說明本發(fā)明的實施過程：

圖2 客戶及時返回范圍示意和保留資格范圍示意

A、計算當(dāng)前號碼與客戶號碼的差值n=10；

B、根據(jù)差值及平均服務(wù)時間t=5 min，預(yù)估排隊時間T=n×t=10×5=50；

C、以預(yù)估排隊時間為準(zhǔn)，根據(jù)交通方式的參考速度v=5 km/h，分析出活動范圍R=n×t×v=10×5×5÷60=4.16 km，取整為4 km；

D、以如圖2中第一個4 km范圍小圓為界，若在該范圍內(nèi)呼叫客戶并給出返回時間建議，若超出范圍，下一位客戶進(jìn)入步驟A，當(dāng)前客戶進(jìn)入步驟E；

E、以下班時間為準(zhǔn)得到當(dāng)前時間差Tt，當(dāng)前時間為9點，下班時間12點，時間差3個小時，計算出對應(yīng)活動范圍區(qū)Rt=Tt×v=3×5=15 km；

F、以如圖2中第二個15 km范圍大圓為界。若該范圍內(nèi)通知客戶是否愿意返回，若同意則保號保留排隊資格，若不同意則進(jìn)入步驟G；

G、取消排隊資格，下一位客戶進(jìn)入步驟A。

2、步驟D中包括以下步驟：

D1、以步驟C所生成的如圖2中第一個4 km范圍小圓為例，分析客戶當(dāng)前位置是否在緩沖區(qū)內(nèi)；

D2、若在緩沖區(qū)內(nèi)如圖2中1號客戶位置，則根據(jù)當(dāng)前客戶位置及參考速度計算到達(dá)服務(wù)點的時間并通知客戶在該時間內(nèi)返回服務(wù)點；

D3、若在緩沖區(qū)外，則通知當(dāng)前客戶超出排隊距離，下一客戶自動進(jìn)入步驟A，當(dāng)前客戶進(jìn)入步驟E；

所述的步驟D2優(yōu)選基于空間分析技術(shù)的最短路徑搜索算法[8]，若求得最短路徑長度為S=3 km，則返回路程時間為36 min，排隊時間為50 min，則客戶必須在14 min內(nèi)返回；

4、步驟E中包括以下步驟：

以下班時間12點，當(dāng)前時間9點為例，時間差Tt=3 h，交通方式的參考速度v=5 km/h，測算出下班前返回范圍半徑Rt=Tt×v=3×5=15 km，以服務(wù)點生成如圖2中第二個15 km范圍大圓為界的緩沖區(qū)。

5、步驟F中包括以下步驟：

F1、以步驟E所生成的15 km范圍緩沖區(qū)為例，分析客戶當(dāng)前位置是否在緩沖區(qū)內(nèi)；

F2、若在15 km范圍緩沖區(qū)內(nèi)如圖2中2號客戶位置，則根據(jù)當(dāng)前客戶位置及參考速度計算到達(dá)服務(wù)點的時間并通知客戶在該時間內(nèi)返回服務(wù)點，若當(dāng)前客戶不同意則進(jìn)入步驟G；

F3、若在15 km范圍緩沖區(qū)外，則通知當(dāng)前客戶超出排隊距離，當(dāng)前客戶進(jìn)入步驟G；

所述的步驟F2優(yōu)選基于空間分析技術(shù)的最短路徑搜索算法[8]，若求得最短路徑長度為10公里，則返回路程時間為10÷5×60=120 min，預(yù)留排號時間為180 min，則客戶必須在180-120=60 min內(nèi)返回[12]。

4 小 結(jié)

本排號方法通過客戶和服務(wù)點位置，計算出服務(wù)時間差，為客戶進(jìn)行其他社會活動提供參考。其特點在于將時空因素和人機(jī)交互綜合運用，變更了傳統(tǒng)排號系統(tǒng)廣播模式，同時對于首次排號機(jī)會錯失的客戶，在不影響他人服務(wù)質(zhì)量同時，人性化考慮個性需求[12]。此外該發(fā)明也間接地存在加急排號而不影響他人服務(wù)質(zhì)量的可能，對提升客戶體驗、節(jié)約社會資源、減少社會不穩(wěn)定因素都具有重要意義。本發(fā)明技術(shù)原理簡單成熟，是將串行服務(wù)與并行服務(wù)矛盾解決的新思路，可以在社會各個行業(yè)進(jìn)行推廣，應(yīng)用潛力巨大。