機器人室內自主載人自適應性匈牙利派單算法

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

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

0 引言

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

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

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

1 航站樓派單業務場景建立

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

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

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

其中兩者區別主要體現以下方面：

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

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

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

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

圖1 派單主體區域示意圖

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

2 接載派單規劃原理

2.1 二分圖派單思想

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

圖2 平臺派單系統架構示意圖

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

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

圖4 載人機器人樣機圖

2.2 接載OD矩陣

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

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

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

(1)

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

(2)

(3)

(4)

(5)

2.3 接載派單數學模型

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

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

目標適應度函數：

(6)

M=C=[cij]i×j

(7)

約束條件：

(8)

(9)

2.4 接載派單原理分析

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

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

2.5 自適應接載派單算法

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

圖5 自適應性匈牙利算法流程圖

3 仿真實驗與結果分析

3.1 小規模環境派單實驗

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

表1 當前狀態信息表

其中，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。根據航站樓實際路況，其列出路況因子信息，并求得各載人機器人訪問目標需求旅客路徑代價值。得到結果如表2所示。

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

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

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

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

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

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

圖6 兩種算法的分配結果示意圖

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

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

圖7 兩種算法的分配結果示意圖

(2)旅客多時，即m

圖8 兩種算法的分配結果示意圖

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

3.2 大規模派單實驗

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

表3 航站樓的實驗參數數據表

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

表4 航站樓的便捷乘機規劃服務模塊參數表

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

圖9 航站樓各時段隔離區旅客數量分布圖

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

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

由此結合圖9和圖10可得載人機器人速率變化規律：

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

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

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

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

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

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

圖13 航站樓24 h派單接載耗時統計圖

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

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

4 結束語

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