一種基于最短路徑分析的雙向交互模式排隊(duì)系統(tǒng)構(gòu)建

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

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

1 引 言

排隊(duì)等號(hào)系統(tǒng)在社會(huì)領(lǐng)域扮演非常重要的角色，對(duì)于社會(huì)穩(wěn)定，人民素質(zhì)的提升意義重大。但傳統(tǒng)的廣播模式排隊(duì)等號(hào)系統(tǒng)不能及時(shí)與客戶溝通，很容易造成客戶時(shí)間的浪費(fèi)，同時(shí)因?yàn)楦黝愒蛟斐膳盘?hào)機(jī)會(huì)錯(cuò)失需要再次排號(hào)，給客戶造成巨大浪費(fèi)，極易造成服務(wù)方和客戶的矛盾，增加社會(huì)不穩(wěn)定因素。

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

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

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

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

2 問題解決

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

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

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

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

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

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

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

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

對(duì)于覆蓋問題，通常可以采用簡單緩沖區(qū)分析思維來實(shí)現(xiàn)。但由于行人多基于道路行動(dòng)，因此簡單緩沖區(qū)思維將造成實(shí)際點(diǎn)位到服務(wù)點(diǎn)的道路距離大于直線距離。基于此弊端，結(jié)合如上提及的距離升維方法，將對(duì)樣本區(qū)間進(jìn)行如下操作：

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

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

3 案例分析

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

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

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

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

1為服務(wù)點(diǎn)，2為客戶位置點(diǎn)，3為當(dāng)次叫號(hào)時(shí)間差對(duì)應(yīng)范圍，4為下班前時(shí)差對(duì)應(yīng)活動(dòng)范圍。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 小 結(jié)

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