機器人室內(nèi)自主載人自適應(yīng)性匈牙利派單算法

高慶吉，粟 鵬，佘亮亮，邢志偉

(中國民航大學 中國民航大學機器人研究所，天津 300300)

0 引言

航站樓等大型公共室內(nèi)環(huán)境中，經(jīng)常采用載客小車運送客人到達目的地，是目前已經(jīng)存在的便捷旅客乘離的服務(wù)模式。但是，所用車輛一般都是人工駕駛，旅客的可選擇性和自主性受其制約，故航空出行的體驗沒有得到很好提升[1]。受共享出行理念的啟發(fā)[2]，提出“室內(nèi)網(wǎng)約車”的概念。采用自主載人機器人作為“室內(nèi)網(wǎng)約車”，搭載旅客和行李，將旅客自主運送到登機口等目的地，不僅可以壓縮旅客在樓內(nèi)的行走時間，而且將大大提升出行體驗，具有重要的價值和意義。同時，考慮投入載人機器人為旅客解決航站樓“最后一公里”的出行問題，需考慮旅客的動態(tài)接載需求，建立自適應(yīng)性的調(diào)度策略，以提高旅客滿意度是非常有必要的[3]。

但是基于航站樓載人機器人應(yīng)用場景的派單特殊性，實現(xiàn)載人機器人的派單模式還需進一步探索。Lee[4]等通過分析基于最近坐標法的司乘直線距離最短的派單方式，提出了基于實時交通狀況的派單新方案，并建立了以司機到達載客點的時間最短為派單規(guī)則；Hanna[5]等學者的同類問題研究中，對無人駕駛共享汽車中的訂單分配問題進行了研究，在乘客和車輛數(shù)量不斷發(fā)生變化的動態(tài)場景中，把乘客和車輛的匹配問題轉(zhuǎn)化為二分圖匹配問題，研究了基于候車時間最短的匈牙利算法，并根據(jù)全域最優(yōu)策略，對算法進行改進，提出了集中式貪心算法和匈牙利算法的組合優(yōu)化算法；YE[6]等將網(wǎng)約車大規(guī)模訂單調(diào)度定義為NP問題，使用組合優(yōu)化等算法予以解決；張進[7]等對比分析傳統(tǒng)匈牙利算法與智能優(yōu)化算法的耗時性與穩(wěn)定性，展現(xiàn)了匈牙利算法的優(yōu)勢，并提出統(tǒng)一效率矩陣，所改進的匈牙利算法可適用于各類型的目標分配；Maciejewski[8]等根據(jù)連環(huán)派單的思想，遵循先到先服務(wù)的原則，對空車與非空車進行綜合考慮，把訂單分配給接駕時間最短的車輛，從而縮減了司機的接駕距離和乘客的候車時間。

上述研究主要為不斷優(yōu)化網(wǎng)約車派單調(diào)度[9-10]和多機器人調(diào)度[11-13]等內(nèi)容，而共享出行的理念對本文涉及問題有借鑒價值。對于大型公共室內(nèi)環(huán)境自主載人，需考慮空間范圍、人流密度、航班時刻分布及機器人載運能力等條件的約束，以及最短候載時間和機器人群體最低能耗的目標要求，從而建立相應(yīng)的載人機器人派單算法。

1 航站樓派單業(yè)務(wù)場景建立

對于航站樓載人機器人派單空間，將以安檢口到各登機口區(qū)域作為載人機器人的可行域，為旅客提供便捷乘機服務(wù)。其中“室內(nèi)網(wǎng)約車”模式相比于城市網(wǎng)約車異同點如下：

1)采用調(diào)度時間窗口，并延時集中批量處理訂單匹配，實現(xiàn)了略微更“全局”的優(yōu)化。

2)二分圖匹配問題，一邊為需求側(cè)，一邊為供給側(cè)，派單算法快速解決雙方的匹配關(guān)系。

其中兩者區(qū)別主要體現(xiàn)以下方面：

1)應(yīng)用場景不同。航站樓載人機器人應(yīng)用于動態(tài)高密度人流的室內(nèi)環(huán)境[14]，受其固定可行區(qū)域中障礙物環(huán)境的約束，且單個載人機器人只可載運單個旅客。而網(wǎng)約車應(yīng)用于動態(tài)高密度車流的城市路網(wǎng)，受其交通管制約束，并將城市地圖劃分為無數(shù)個六角形的網(wǎng)格圖，每個網(wǎng)格圖代表一個派單單元區(qū)域，且單個司機車輛只可搭乘單個或多個乘客。

2)處理RP(route planning)路線規(guī)劃不同。航站樓載人機器人的路徑規(guī)劃算法是每個空閑載人機器人訪問目標旅客，實時規(guī)劃出一條適合機器人在航站樓環(huán)境中行走的路徑。而網(wǎng)約車平臺計算路線規(guī)劃是基于城市路徑拓撲圖，其接駕的路線規(guī)劃代價是基于城市路網(wǎng)導(dǎo)航距離，而并非基于坐標的歐式距離。

3)派單軟件平臺組成不同。“室內(nèi)網(wǎng)約車”則是分為載人機器人端、旅客端和派單服務(wù)端。網(wǎng)約車平臺主體分為司機端、乘客移動端和派單云平臺。

故研究載人機器人的可行域時，主體考慮安檢通道至各登機口區(qū)域，由航站樓各指廊等部分組成。如圖1所示，如果以安檢口為起點，各登機口為終點，其主體載人機器人在隔離區(qū)(安檢口—登機口區(qū)域)內(nèi)服務(wù)，并在隔離區(qū)設(shè)置其類似城市路網(wǎng)及調(diào)頭地標等服務(wù)信息，主體以安檢口和登機口之間的旅客運送和返回為主要形成，時而有中間接載旅客的服務(wù)。

圖1 派單主體區(qū)域示意圖

其旅客搭乘起點主體以安檢出口為主，即載運等候區(qū)。其他起點可遍布于隔離區(qū)各處，而載運抵達的目標主體以遍布隔離區(qū)各處的登機口為主，當然也可以按照需求旅客指定確認的目的地點位，如購物餐飲等。由此在隔離區(qū)空間中存在用車需求的情況時，可考慮實行平臺派單模式，為全域需求旅客提供其載運服務(wù)。此時接載起點不僅僅為安檢通道的起點，也可以是隔離區(qū)域中的任意一點作為起點，抵達隔離區(qū)的目的地，構(gòu)建起終點(OD，orignation-destination，起點-終點)間的交通出行量[15-16]。

2 接載派單規(guī)劃原理

2.1 二分圖派單思想

探索航站樓載人機器人平臺派單算法，是對載人機器人和旅客接載任務(wù)的高效匹配。如圖2所示，對于航站樓載人機器人系統(tǒng)將充分共享服務(wù)端平臺[17]，滿足需求旅客高效位移的需求，各載人機器人在派單平臺上為特定的IP點(internet protocol)，系統(tǒng)將進行實時采集機器人狀態(tài)信息，以獲取可調(diào)度載人機器人在室內(nèi)環(huán)境中的坐標信息，并將呈現(xiàn)為在空間中的供給點，當載人機器人接到云端指令時，將前往某個位置接載旅客，或路上遇到旅客招手后將停車接載。而需求旅客作為移動端，發(fā)起使用需求時，將呈現(xiàn)為在空間中的需求點，當旅客看到機器人后做手勢搭乘，同時載人機器人移動到旅客身邊提醒旅客搭乘。

圖2 平臺派單系統(tǒng)架構(gòu)示意圖

由此建立了航站樓空間派單平臺，如圖3所示，其載人機器人概念如圖4所示。菱形點為需求旅客，構(gòu)造出載人機器人與需求旅客兩個集合，其中集合分別為Ci={c1、c2、…、ci}、Pj={p1、p2、…、pj}，形成了具有互不相交的兩個子集，構(gòu)建兩個集合后，將定義一個邊對兩個集合中的點與點實時匹配連接，并賦予一個權(quán)重代價值f，構(gòu)建一個二分圖數(shù)學模型，故載人機器人和需求旅客匹配為二分圖匹配問題(bipartite graph mathing)[18-21]。

圖3 空間派單二分圖示意圖

圖4 載人機器人樣機圖

2.2 接載OD矩陣

針對以上二分圖關(guān)系，將基于室內(nèi)柵格化地圖，計算各載人機器人訪問全域需求旅客的路徑代價。且航站樓載人機器人的路徑規(guī)劃需滿足高效計算，故利用JAVA軟件將A*路徑規(guī)劃算法構(gòu)建為RP(route planning)服務(wù)器。將全域柵格地圖利用0～1表示(0為自由區(qū)域，1為障礙區(qū)域)，構(gòu)造為柵格地圖的0～1矩陣，保存至RP(route planning)服務(wù)器。由此利用A*路徑規(guī)劃算法從起點逐步計算至終點，并形成多線程訪問路徑規(guī)劃，得出全域多載人機器人到目標需求旅客的預(yù)估接載路徑代價。因為空間中的載人機器人將基于A*算法同時進行大量的路徑訪問需求，所以假設(shè)在2 s時刻，空閑載人機器人的數(shù)量為M(滲透率計算)，需求旅客人數(shù)為N(旅客抵達航站樓服從泊松規(guī)律)，則在2 s時刻時路徑訪問次數(shù)為Y=M*N，呈線性增長關(guān)系。

假設(shè)需求旅客p1，p2，…，pj，其中位置信息為(xj，yj)，載人機器人c1，c2，…，ci其中ci(i=1，2，…，i，i∈M)，位置信息為(xi，yi)。利用路徑規(guī)劃算法計算載人機器人到每位需求旅客pj(j=1，2，…，j，j∈N)的路徑代價為rij。故以載人機器人自身為源點，以需求旅客為終點，構(gòu)建接載OD矩陣M所示：

因此，構(gòu)建載人機器人計算當前訪問需求旅客狀態(tài)時，若只考慮接載任務(wù)距離，其預(yù)估個體需求旅客大致平均等待時間為：

(1)

其中：vij表示載人機器人移動的平均速度。若引入城市網(wǎng)約車道路交通狀態(tài)分析，將利用機器人平均行駛速度來描述航站樓通行的擁擠程度。故載人機器人在執(zhí)行接載任務(wù)期間的行駛時間不僅取決于任務(wù)節(jié)點之間的距離，還取決于周圍人流密度的影響。故引入環(huán)境路況因子δ(route)ij表述旅客密度ρ對載人機器人行駛速度的影響，并根據(jù)格林希爾茲模型[22-23]，得到旅客密度與航站樓載人機器人速率的影響及預(yù)計到達時間，并建立相關(guān)公式如下：

(2)

(3)

(4)

(5)

2.3 接載派單數(shù)學模型

針對調(diào)度時段范圍內(nèi)，研究其需求旅客與載人機器人存在動態(tài)供需不平衡等情況時，以全域最優(yōu)派單算法解決派單匹配問題。假設(shè)在Δt=2 s時，航站樓空閑載人機器人數(shù)量為m，需求旅客數(shù)量為n，并且每次接載任務(wù)為一對一達成合乘的接載服務(wù)。令其Pn={p1，p2，…，pn}代表全域的需求旅客，集合Cm={c1，c2，…，cm}代表全域編號的載人機器人。若載人機器人ci與需求旅客pj關(guān)聯(lián)，則載人機器人訪問到需求旅客得出的路徑代價為rij，建立其訪問路徑矩陣M的基礎(chǔ)上，將考慮個體載人機器人所處的環(huán)境因素，其中包括接載路徑、旅客等待時間和機器人能耗，即路徑-時間-能量的調(diào)度模型，并將3個指標分別考慮融入權(quán)重w1，w2，w3，得到適應(yīng)度函數(shù)值fij作為匹配的權(quán)重值，由此整理構(gòu)建為二分圖接載任務(wù)OD矩陣ODij，可以表達為：

同時，在建立航站樓全域載人機器人訪問接載任務(wù)適應(yīng)度值最小為原則，以獲取全域載人機器人接載派單矩陣。因此在獲取需求旅客與載人機器人的派單關(guān)聯(lián)策略時，即求解關(guān)聯(lián)策略的狀態(tài)變量矩陣C，其為i×j的矩陣，各元素為{0，1}，即cij={0，1}。故對載人機器人—需求旅客的派單關(guān)聯(lián)過程進行建模，其目標函數(shù)以fij為自變量，fij與cij有關(guān)。故利用組合優(yōu)化算法以約束原則求出其派單關(guān)聯(lián)矩陣，進而對全域載人機器人進行派單。此時得出對應(yīng)的狀態(tài)變量矩陣C=[cij]i×j為派單關(guān)聯(lián)矩陣，令其派單關(guān)聯(lián)矩陣為M，此時M=C。

目標適應(yīng)度函數(shù)：

(6)

M=C=[cij]i×j

(7)

約束條件：

(8)

(9)

2.4 接載派單原理分析

將載人機器人考慮動態(tài)供需不平衡的派單問題時，主體考慮平衡目標分配和不平衡目標分配[24]，假設(shè)空閑載人機器人數(shù)量為m，需求旅客數(shù)量為n。當兩者人數(shù)不相等時，將添加附近快到達目標點的載人機器人和虛擬需求旅客，以增加二分圖接載任務(wù)OD矩陣中派單的可行解，以解決不平衡目標分配等情況：

1)假設(shè)添加虛擬需求旅客，將實行加邊補零法，零則表示添加訪問虛擬需求旅客適應(yīng)度函數(shù)值fij=0，使其派單矩陣形成方陣，再采用派單規(guī)劃算法進行計算。

2.5 自適應(yīng)接載派單算法

為此設(shè)計各種載運供需場景的派單求解算法的流程，具體自適應(yīng)性匈牙利算法流程步驟如圖5所示。

圖5 自適應(yīng)性匈牙利算法流程圖

3 仿真實驗與結(jié)果分析

3.1 小規(guī)模環(huán)境派單實驗

在MATLAB軟件中進行小規(guī)模派單仿真實驗：在處理派單匹配時刻，給定其6個載人機器人和6個需求旅客的信息如表1所示。

表1 當前狀態(tài)信息表

其中，Nt=2 343人，S0=25 000 m2，vf=4 m/s，ρs=0.204 28，i=6，j=6，w1=0.3，w2=0.3，w3=0.3，U0=24 V，I0=8 A。根據(jù)航站樓實際路況，其列出路況因子信息，并求得各載人機器人訪問目標需求旅客路徑代價值。得到結(jié)果如表2所示。

表2 訪問目標需求旅客路徑代價rij信息表

由此計算得出二分圖接載任務(wù)矩陣，即載人機器人訪問各需求旅客的目標適應(yīng)度函數(shù)值，如下矩陣ODij所示：

根據(jù)二分圖接載任務(wù)ODij矩陣可知，載人機器人分配不同需求旅客會獲得不同目標的適應(yīng)度函數(shù)值fij，并通過自適應(yīng)性匈牙利派單算法以分配接載目標。

由此針對各類動態(tài)供需場景的派單問題時，將以載人機器人與需求旅客數(shù)量關(guān)系研究派單求解實驗。如下將主體分為供需平衡和供需不平衡條件的派單實驗。

1)載人機器人供需平衡條件的實驗：

如圖6所示，圖中對比出自適應(yīng)性匈牙利派單算法能滿足其就近派單，并以此約束全域需求旅客接載時間最短，反之模擬退火算法得出派單結(jié)果較差。其中對于自適應(yīng)性匈牙利算法得出其全域接載適應(yīng)值和比模擬退火算法小20%。同時，在具體接載任務(wù)分配上面，模擬退火算法將C6分配給了P3，C4分配給了P4，這樣會導(dǎo)致P3旅客等待時間較長。而自適應(yīng)性匈牙利算法得出的派單規(guī)劃，將C6分配給了P4，C4分配給了P3，使其P3和P4旅客等待時間都能接受，也充分滿足了將就近的載人機器人派給需求旅客。

圖6 兩種算法的分配結(jié)果示意圖

2)載人機器人供需不平衡條件的實驗：

(1)機器人多時，即m>n。如圖7所示，在全域載人機器人數(shù)量多于需求旅客時。兩者都是添加虛擬需求旅客，將二分圖接載任務(wù)ODij矩陣計算，最終得出了派單結(jié)果均滿足就近原則和結(jié)果的一致性。

圖7 兩種算法的分配結(jié)果示意圖

(2)旅客多時，即m

圖8 兩種算法的分配結(jié)果示意圖

綜上對小規(guī)模動態(tài)供需不平衡派單匹配的計算，既基于旅客密度-時長-能耗模型設(shè)計了載人機器人的二分圖接載任務(wù)ODij矩陣，同時涵蓋了三類供需不平衡場景時，對該派單矩陣處理的策略。故將統(tǒng)一建立基于微小調(diào)度時窗內(nèi)(Δt=2 s)批量派單處理，以得到全域的最優(yōu)指派規(guī)劃，并充分滿足全域需求旅客的就近派單，提高需求旅客的滿意度。

3.2 大規(guī)模派單實驗

以上利用軟件構(gòu)建了航站樓載人機器人的自適應(yīng)性匈牙利派單算法，并對小規(guī)模動態(tài)供需不平衡派單匹配進行計算分析。故針對大規(guī)模模擬航站樓派單場景的仿真實驗時，將利用Anylogic軟件進行場景搭建及實驗，其中整理了相關(guān)模擬航站樓的實驗參數(shù)數(shù)據(jù)，包括實驗統(tǒng)計日期為2018-01-31。其詳細采集數(shù)據(jù)如表3所示。

表3 航站樓的實驗參數(shù)數(shù)據(jù)表

同時建立了航站樓便捷乘機規(guī)劃，在模型中的邏輯乘機服務(wù)模塊參數(shù)如表4所示。

表4 航站樓的便捷乘機規(guī)劃服務(wù)模塊參數(shù)表

并且在航站樓的便捷乘機規(guī)劃中，包括了安檢口至登機口的隔離區(qū)作為派單可行區(qū)域，也是考慮載運的便捷通行區(qū)域。由此對于派單區(qū)域的需求旅客，主體考慮其隔離區(qū)人流的用車需求，不僅來源于隔離區(qū)旅客的用車需求，同時服務(wù)快速離港乘機通道的旅客。因此，統(tǒng)計了該航站樓模型在隔離區(qū)各時段旅客人數(shù)，如圖9所示。

圖9 航站樓各時段隔離區(qū)旅客數(shù)量分布圖

由圖9看出，其密集人流主要集中在早高峰和下午16點左右。利用其航站樓便捷乘機規(guī)劃Anylogic的模型，當離港人流分布流速為ni時，即設(shè)置每小時抵達人數(shù)的速率。由此統(tǒng)計其對應(yīng)全域載人機器人整體平均耗時t，并作出t關(guān)于ρ的變化曲線，如圖10所示。

圖10 平均接載耗時隨密集人流變化圖

由此結(jié)合圖9和圖10可得載人機器人速率變化規(guī)律：

由此在Anylogic模型中設(shè)計出主體需求旅客的離港流程并搭建航站樓整體三維模型，并特別將航站樓模型運行當日高峰小時流量場景，得到全流程航站樓整體模型的人流密度，如圖11所示。

圖11 航站樓人流密度分布圖

同時對于航站樓模型將考慮全域載人機器人服務(wù)需求旅客的滲透率，其中整體服務(wù)人流來自于傳統(tǒng)乘機模式與便捷乘機模式，即研究載運區(qū)占比主體服務(wù)人流的滲透率大小。在不同滲透率大小時，對比需求旅客使用載人機器人與傳統(tǒng)步行的耗時對比，進而得出投入航站樓載人機器人的必要性。由此在隔離區(qū)(安檢口—登機口)區(qū)域，得出全域載運需求旅客的耗時與傳統(tǒng)步行模式時間對比變化規(guī)律，如圖12所示。

圖12 全域平均接載耗時對比圖

橫坐標即投放載人機器人服務(wù)人流占比，即滲透率，由此得出其載人機器人與傳統(tǒng)步行的耗時分析，得出其載運耗時明顯低于傳統(tǒng)步行的模式，其平均節(jié)約4 min左右。

由此，將派單算法實時計算航站樓全域載人機器人接載路由(Δt=2 s)及全域旅客預(yù)估等待時間，處理延時集中派單請求，并統(tǒng)計其一天24 h的實驗結(jié)果，如圖13所示。

圖13 航站樓24 h派單接載耗時統(tǒng)計圖

最終，運行主體航站樓模型24 h派單統(tǒng)計實驗，得出整體便捷乘機規(guī)劃與傳統(tǒng)乘機流程耗時對比圖，旅客使用載人機器人比傳統(tǒng)步行耗時具有明顯優(yōu)勢，平均節(jié)約4 min左右，并且在高峰時段也能滿足需求旅客用車請求。

綜上所述，整體得出將航站樓載人機器人投放至安檢口-登機口區(qū)域服務(wù)時，突顯其便捷快速等優(yōu)點，同時引用共享出行模式建立載人機器人的派單算法，以提高離港需求旅客出行的滿意度。

4 結(jié)束語

針對類似航站樓大型公共室內(nèi)環(huán)境，研究載人機器人與需求旅客數(shù)量動態(tài)供需不平衡而引起的派單優(yōu)化問題，借鑒了網(wǎng)約車派單優(yōu)化策略，將航站樓載人機器人供需關(guān)系和連環(huán)派單情況加入考慮范疇，提出了自適應(yīng)性匈牙利派單算法。實驗驗證了在小規(guī)模派單實驗時，得出全域機器人整體接載適應(yīng)值，相比較模擬退火算法減少20%；并且相比經(jīng)典匈牙利派單算法，引入了連環(huán)派單能夠增加全域派單求解的可能性。同時在大規(guī)模航站樓場景派單統(tǒng)計實驗中，結(jié)合航站樓旅客時空分布規(guī)律，得出了在不同滲透率時，機器人接載耗時比傳統(tǒng)旅客步行耗時平均節(jié)約50%，而且整體形成的便捷乘機模式比傳統(tǒng)乘機模式節(jié)約了43%。故對于類似航站樓室內(nèi)動態(tài)的人機交互環(huán)境中，所研究的自適應(yīng)性匈牙利派單算法具有應(yīng)用參考價值。