摘 要：

針對現(xiàn)存動(dòng)態(tài)上車點(diǎn)配置模型在大規(guī)模算例的全局最優(yōu)和求解效率方面存在瓶頸的問題，基于乘客步行距離、乘客步行時(shí)間、上車點(diǎn)路況指標(biāo)以及至乘客目的地所需成本四個(gè)關(guān)鍵影響因子進(jìn)行建模，并提出了基于多模深度森林的動(dòng)態(tài)上車點(diǎn)預(yù)測算法和一種迭代Kuhn-Munkres上車點(diǎn)配置算法。預(yù)測算法融合了多模態(tài)決策樹結(jié)構(gòu)和深度學(xué)習(xí)技術(shù)以提升模型預(yù)測準(zhǔn)確性；配置算法通過多場景自適應(yīng)機(jī)制自動(dòng)調(diào)整邊權(quán)重并選擇最優(yōu)邊進(jìn)行增廣，以得到所有乘客和上車點(diǎn)的最優(yōu)配置。實(shí)驗(yàn)結(jié)果表明，相較于其他主流預(yù)測模型，該預(yù)測算法平均絕對誤差降低2.705，均方誤差降低5.915，可決系數(shù)提升0.214，解釋方差提升0.195；配置算法在乘客數(shù)量占優(yōu)條件下的平均調(diào)度效果相較于實(shí)驗(yàn)中其他方案提高了2.04%。這表明預(yù)測算法和配置算法具有較高的實(shí)用性，且配置算法在處理大規(guī)模實(shí)例上具有明顯優(yōu)勢。

關(guān)鍵詞：上車點(diǎn)推薦；多模深度森林；迭代Kuhn-Munkres算法；網(wǎng)約車；城市交通

中圖分類號：TP301.6"" 文獻(xiàn)標(biāo)志碼：A""" 文章編號：1001-3695（2024）12-015-3634-11

doi： 10.19734/j.issn.1001-3695.2024.04.0123

Dynamic pick-up point recommendation based on multi-modal deep forest and iterative Kuhn-Munkres algorithm

Guo Yuhan， Zhu Rushi

（School of Science/School of Big Data Science， Zhejiang University of Science amp; Technology， Hangzhou 310023， China）

Abstract：

To address the bottleneck issues of global optimality and computational efficiency in existing dynamic pick-up point allocation models for large-scale scenarios， this paper developed a model based on four key influencing factors： passenger walking distance， passenger walking time， pick-up point road conditions， and the cost to the passenger’s destination. This paper proposed a multi-modal deep forest-based dynamic pick-up point prediction algorithm and an iterative Kuhn-Munkres pick-up point allocation algorithm. The prediction algorithm integrated a multi-modal decision tree structure with deep learning techniques to enhance prediction accuracy. The allocation algorithm utilized a multi-scenario adaptive mechanism to automatically adjust edge weights and selected the optimal edges for augmentation to achieve the optimal allocation for all passengers and pick-up points. Experimental results demonstrate that the proposed prediction algorithm reduces the mean absolute error by 2.705， the mean squared error by 5.915， increases the coefficient of determination by 0.214， and improves the explained variance by 0.195 compared to other mainstream prediction models. Under conditions where passenger quantity advantage， the allocation algorithm improves average scheduling effectiveness by 2.04% compared to other schemes tested in the experiments. These results indicate that the proposed algorithms are highly practical， with the allocation algorithm shows significant advantages in handling large-scale instances.

Key words：pick-up point recommendation; multi-modal deep forest; iterative Kuhn-Munkres algorithm; online ride-hailing; urban transportation

0 引言

近年來，智能通信終端的普及為乘客和網(wǎng)約車司機(jī)間的信息交流提供了便捷性和即時(shí)性，消除了以往由于空間差異而存在的信息壁壘［1］。在乘客通過智能軟件發(fā)起訂單并與司機(jī)匹配后，雙方均需前往指定的上車點(diǎn)，合理的上車點(diǎn)配置可有效提升接駕效率、降低服務(wù)的經(jīng)濟(jì)和時(shí)間成本且有助于緩解交通擁堵。

目前國內(nèi)外對于網(wǎng)約車的研究主要集中在需求預(yù)測［2，3］、匹配調(diào)度［4］以及路徑規(guī)劃［5，6］等方面，對于上車點(diǎn)推薦的研究較為有限。文獻(xiàn)［7，8］對上車點(diǎn)推薦問題進(jìn)行了綜述，將其研究方向主要?dú)w納為減少乘客的步行距離和步行時(shí)間［9～15］，優(yōu)化上車點(diǎn)路況［1，16～20］和降低出行成本［21～24］等方面。

a）在減少乘客的步行距離和步行時(shí)間方面， Xia等人［9］設(shè)計(jì)了基于Spark的并行SP-DBSCAN算法，以滿足乘客在特定位置沒有成功搭車而隨機(jī)轉(zhuǎn)向下一個(gè)地點(diǎn)時(shí)仍能在熱點(diǎn)區(qū)域乘車的要求。Mann等人［10］基于劃分聚類法和層次聚類法提出了改進(jìn)的混合聚類算法，向乘客推薦距離當(dāng)前位置最近的上車點(diǎn)?？弟姷热耍?1］對各個(gè)上車點(diǎn)出租車空載率進(jìn)行預(yù)測，并推薦乘客去往空載率最高且最近的上車點(diǎn)候車。Olakanmi等人［12］基于司機(jī)與乘客曾訪問過的歷史位置提出了一種考慮司機(jī)和乘客間信任與評價(jià)相似度的模型，為乘客推薦最短步行距離的上車點(diǎn)；Gu等人［13］設(shè)計(jì)了一個(gè)可視化分析系統(tǒng)，旨在可視化探索乘客在不同區(qū)域選擇對自身有利的上車點(diǎn)；You等人［14］基于粒度網(wǎng)格和時(shí)空神經(jīng)網(wǎng)絡(luò)可有效預(yù)測和優(yōu)化乘客步行時(shí)間和等待時(shí)間；Dieter等人［15］根據(jù)將乘客分配至上車點(diǎn)問題建模為一個(gè)順序決策過程，以最小化乘客的步行距離。

b）在優(yōu)化上車點(diǎn)路況方面，Zhu等人［1］綜合各種交通影響因素，在保證上車點(diǎn)設(shè)置與實(shí)際交通情況相適應(yīng)的情況下為乘客推薦上車點(diǎn)。Chang等人［16］基于上車點(diǎn)路況指標(biāo)進(jìn)行上車點(diǎn)推薦，并設(shè)計(jì)了宏觀路徑推薦方法，旨在提升交通領(lǐng)域低碳管理水平。Aliari等人［17］以乘客步行距離為指標(biāo)，利用混合整數(shù)線性規(guī)劃為乘客推薦上車點(diǎn)，以此緩解上車點(diǎn)擁堵問題。Zhang等人［18］根據(jù)歷史上下車數(shù)據(jù)進(jìn)行建模，利用時(shí)空有向圖卷積網(wǎng)絡(luò)算法為乘客推薦路況良好的上車點(diǎn)。郭羽含等人［19］建立上車點(diǎn)的復(fù)合收益評價(jià)體系，構(gòu)建了上車點(diǎn)的動(dòng)態(tài)推薦模型；在此基礎(chǔ)上，他們設(shè)計(jì)了多目標(biāo)整數(shù)規(guī)劃模型，并提出了松弛分割迭代算法，從不同角度對上車點(diǎn)進(jìn)行有效推薦［20］。

c）在降低出行成本方面，文獻(xiàn)［21］利用空間聚類方法在空間和時(shí)間尺度上合并出租車行程簇，生成使乘客和出租車公司出行成本最小的上車點(diǎn)；文獻(xiàn)［22］設(shè)計(jì)了一種基于用戶激勵(lì)機(jī)制的上車點(diǎn)推薦系統(tǒng)，鼓勵(lì)乘客在一定距離內(nèi)步行至合適的上車點(diǎn)，以最大限度降低出行成本；文獻(xiàn)［23］發(fā)現(xiàn)出行成本與乘客使用乘車服務(wù)軟件具有明顯的非線性關(guān)系；文獻(xiàn)［24］提出了網(wǎng)約車與乘客最佳乘車匹配的禁忌搜索，使乘客可節(jié)約更多成本，最大限度地提高乘客和司機(jī)的利益。

表1對現(xiàn)存代表性研究進(jìn)行了總結(jié)，分析了各研究對步行距離、步行時(shí)間、上車點(diǎn)路況、預(yù)估訂單金額等主要指標(biāo)的考慮情況。

綜合來看，現(xiàn)存模型與方法考慮的影響因素較為單一，滴滴出行在統(tǒng)計(jì)并分析網(wǎng)約車數(shù)據(jù)后發(fā)現(xiàn)，乘客出行行為與成本、時(shí)間、路況、便利度等多種因素相關(guān)。Vega-Gonzalo等人［25］通過問卷調(diào)查及廣義結(jié)構(gòu)方程模型得出乘客打車頻率不僅受出行成本影響，還受行車安全、步行距離等因素的影響。Hou等人［26］認(rèn)為空間可達(dá)性及路況是影響乘客出行的關(guān)鍵因素。Naumov等人［27］通過對乘客的出行習(xí)慣進(jìn)行仿真分析，發(fā)現(xiàn)減少步行距離可提升約25%的乘客滿意度。由此可見，綜合分析乘客出行影響因素對于準(zhǔn)確合理推薦上車點(diǎn)具有重要意義。此外，現(xiàn)存研究還存在以下問題需進(jìn)一步解決：a）現(xiàn)存研究主要基于GPS數(shù)據(jù)進(jìn)行分析，但由于GPS數(shù)據(jù)所跟蹤的坐標(biāo)點(diǎn)與實(shí)際可行的上車位置間存在差異，準(zhǔn)確提取潛在上車點(diǎn)仍具挑戰(zhàn)性；b）匹配算法僅獨(dú)立考慮單次推薦，未將全局最優(yōu)作為優(yōu)化目標(biāo)，導(dǎo)致同時(shí)段內(nèi)單一上車點(diǎn)訂單積壓，從而引發(fā)訂單取消或交通擁堵等問題。

針對上述問題，本文建立了考慮多影響因子的上車點(diǎn)推薦模型，提出了基于多模深度森林的動(dòng)態(tài)上車點(diǎn)預(yù)測算法，并基于其預(yù)測結(jié)果設(shè)計(jì)了一種迭代Kuhn-Munkres上車點(diǎn)配置算法，實(shí)現(xiàn)了多角度多策略的上車點(diǎn)動(dòng)態(tài)配置。本文主要貢獻(xiàn)包括四個(gè)方面：

a）提出了基于路網(wǎng)匹配的潛在上車點(diǎn)提取方法，通過綜合考量道路條件、實(shí)時(shí)交通信息等因素充分整合路網(wǎng)信息，使得所提取的潛在上車點(diǎn)更具實(shí)時(shí)性和準(zhǔn)確性。

b）基于乘客步行距離、步行時(shí)間、上車點(diǎn)路況指標(biāo)和預(yù)估訂單金額四個(gè)關(guān)鍵影響因子建立上車點(diǎn)推薦模型，構(gòu)建了全面考慮乘客便利性、運(yùn)營效率及經(jīng)濟(jì)可行性的模型。

c）提出了基于多模深度森林的動(dòng)態(tài)上車點(diǎn)預(yù)測算法，融合了不同結(jié)構(gòu)的決策樹，利用多模隨機(jī)森林和復(fù)合隨機(jī)森林替代原始隨機(jī)森林和完全隨機(jī)森林，對經(jīng)過滑動(dòng)窗口掃描后的子樣本進(jìn)行多模態(tài)特征采樣，并通過級聯(lián)結(jié)構(gòu)將采樣后的特征逐層組織和整合，有效降低了過擬合風(fēng)險(xiǎn)，提高了模型的泛化能力。

d）設(shè)計(jì)了一種高效的迭代Kuhn-Munkres上車點(diǎn)全局最優(yōu)配置算法，在每輪迭代中通過多場景自適應(yīng)機(jī)制自動(dòng)調(diào)整乘客與上車點(diǎn)之間的邊權(quán)重，并選擇最優(yōu)邊進(jìn)行增廣以持續(xù)優(yōu)化配置結(jié)果，從而顯著提升配置算法的平均調(diào)度效果，并在大規(guī)模算例上具有較高的求解效率。

1 問題定義與建模

1.1 問題定義

1.2 數(shù)學(xué)模型

本文基于乘客步行距離、步行時(shí)間、上車點(diǎn)路況指標(biāo)和預(yù)估訂單金額四個(gè)關(guān)鍵影響因子建立上車點(diǎn)推薦模型。首先，乘客步行距離和時(shí)間直接關(guān)聯(lián)乘客體驗(yàn)及出行效率，合理的步行距離和時(shí)間既可鼓勵(lì)乘客接受一定程度的步行以達(dá)到更高效的車輛分配（如減少空駛、縮短等待時(shí)間），又避免造成乘客不便，從而提高整體服務(wù)滿意度。在城市密集區(qū)域，限制過長的步行距離對于促進(jìn)公共交通與網(wǎng)約車的無縫銜接尤為重要。其次，考慮到城市交通擁堵狀況的普遍性，上車點(diǎn)路況直接影響接駕效率和行程時(shí)間預(yù)測的準(zhǔn)確性。將路況納入模型，可避免在交通繁忙或道路施工區(qū)域安排上車點(diǎn)，減少延誤，同時(shí)優(yōu)化司機(jī)的行駛路徑以提高整體運(yùn)營效率并降低碳排放。最后，成本因素不僅關(guān)乎乘客支付意愿，也是平臺(tái)和司機(jī)收益考量的關(guān)鍵，合理優(yōu)化成本有助于平衡供需雙方利益，促進(jìn)資源的高效配置，避免因成本過高導(dǎo)致的服務(wù)不可持續(xù)問題。

針對上述指標(biāo)，本文建立了線性整數(shù)規(guī)劃模型，將多個(gè)指標(biāo)通過線性加權(quán)組合為單目標(biāo)函數(shù)，從而將多指標(biāo)優(yōu)化問題轉(zhuǎn)換為該目標(biāo)函數(shù)最大化問題。乘客與上車點(diǎn)配置階段以多指標(biāo)線性加權(quán)和作為評價(jià)乘客與上車點(diǎn)的匹配價(jià)值，再將其轉(zhuǎn)換為一個(gè)帶約束的二分圖匹配問題。問題目標(biāo)即為求得一種配置方案，使得所有乘客上車點(diǎn)匹配對的價(jià)值總和最大，因此可將該問題的目標(biāo)函數(shù)定義為式（8）。

其中：coij表示乘客pj是否在上車點(diǎn)bi上車。式（8）中α、δ、γ、φ分別為TRCIbi、WDISbipj、TIMEpj、COSTbipj在目標(biāo)函數(shù)中的權(quán)重參數(shù)。式（9）表示對分配至上車點(diǎn)bi的乘客數(shù)進(jìn)行限制，確保其不超過設(shè)定的閾值bi。式（10）表示一個(gè)乘客只可被分配至一個(gè)特定的上車點(diǎn)上車。式（11）限定了coij的取值范圍，其中1表示上車，0表示不上車。

根據(jù)上述定義構(gòu)造了適用于動(dòng)態(tài)上車點(diǎn)預(yù)測的數(shù)據(jù)集U4×m={（xj，yj）}mj=1，其中xj=（TRCIbi、WDISbipj、TIMEpj、COSTbipj）T為上述定義的4維特征向量，yj∈{0，1}表示經(jīng)過歸一化處理后的動(dòng)態(tài)上車點(diǎn)得分，得分越高代表該上車點(diǎn)更具推薦價(jià)值。

本文模型屬NP-hard問題，當(dāng)解空間巨大時(shí)，整數(shù)約束使問題的求解難度顯著提升，在最壞情況下求解時(shí)間隨問題規(guī)模呈指數(shù)增長。二分圖匹配問題盡管存在多項(xiàng)式時(shí)間算法來解決完美匹配問題，但在大規(guī)模數(shù)據(jù)集上，算法計(jì)算復(fù)雜度依然較高。尤其當(dāng)二分圖的節(jié)點(diǎn)數(shù)量巨大時(shí)，模型求解的復(fù)雜度和資源需求急劇上升。此外，上車點(diǎn)推薦過程具有實(shí)時(shí)性，需在匹配過程中實(shí)施快速?zèng)Q策，對模型求解效率提出了較高要求。

2 求解算法

針對模型特點(diǎn)，本文提出了多模深度森林動(dòng)態(tài)上車點(diǎn)預(yù)測算法與迭代Kuhn-Munkres上車點(diǎn)配置算法，其總體架構(gòu)如圖1所示。a）通過潛在上車點(diǎn)提取算法，在預(yù)測前對上車點(diǎn)集合進(jìn)行數(shù)據(jù)處理并篩選出潛在上車點(diǎn)，保障后續(xù)預(yù)測和配置過程中數(shù)據(jù)的準(zhǔn)確性和真實(shí)性；b）通過點(diǎn)到線匹配算法將經(jīng)過篩選的潛在上車點(diǎn)與真實(shí)路網(wǎng)中的路段匹配，解決GPS數(shù)據(jù)所跟蹤的坐標(biāo)點(diǎn)與實(shí)際可行上車位置間存在差異的問題；c）通過多模深度森林預(yù)測算法，利用1.2節(jié)中建立的特征向量與上車點(diǎn)得分，構(gòu)建用于模型訓(xùn)練的訓(xùn)練集和用于校驗(yàn)的測試集，并輸出可用于上車點(diǎn)推薦的預(yù)測結(jié)果；d）針對動(dòng)態(tài)上車點(diǎn)的全局最優(yōu)化問題，設(shè)計(jì)了迭代Kuhn-Munkres上車點(diǎn)配置算法，利用預(yù)測結(jié)果進(jìn)行決策，通過多場景自適應(yīng)機(jī)制持續(xù)優(yōu)化權(quán)重參數(shù)和配置結(jié)果，使其更好地適應(yīng)不同策略下的配置需求，從而實(shí)現(xiàn)乘客與上車點(diǎn)的全局供需平衡。

2.1 潛在上車點(diǎn)提取

在GPS數(shù)據(jù)中，軌跡點(diǎn)載客狀態(tài)可定義

stk=1 "網(wǎng)約車處于載客狀態(tài)0 "網(wǎng)約車處于空載狀態(tài)（12）

通過觀察圖2上車事件圖中載客事件1，可確定當(dāng)軌跡點(diǎn)載客狀態(tài)由0轉(zhuǎn)換為1時(shí)，即發(fā)生了一次上車事件，此時(shí)將載客狀態(tài)為1的數(shù)據(jù)點(diǎn)視為一個(gè)上車點(diǎn)。

根據(jù)GPS數(shù)據(jù)中網(wǎng)約車在相鄰兩個(gè)時(shí)刻軌跡點(diǎn)載客狀態(tài)的變化，可提取出網(wǎng)約車的候選上車點(diǎn)集Htk，再對所有車輛的候選上車點(diǎn)進(jìn)行合并得集合D，如式（13）（14）所示。

Htk=［tidk，stk|tidkk，t（stk）=1 amp; tidkk，t－1（stk）=0］（13）

D={Ht1∪Ht2∪…∪Htk∪…∪Hts}（14）

最后，利用基于密度的噪聲應(yīng)用空間聚類算法將集合D以半徑為Eps、密度閾值為MinPts進(jìn)行聚類，得到潛在上車點(diǎn)集B。算法示意如圖3所示。

2.2 路網(wǎng)匹配

由于GPS傳感器的讀數(shù)具有定位誤差和采樣誤差，導(dǎo)致GPS數(shù)據(jù)與實(shí)際可使用上車點(diǎn)存在偏差［30］。所以需對GPS數(shù)據(jù)進(jìn)行路網(wǎng)匹配，以保證數(shù)據(jù)的準(zhǔn)確性和可靠性。

本文采用點(diǎn)到線的匹配方法將路網(wǎng)中所有路段視為候選路段，并以兩點(diǎn)間幾何距離以及點(diǎn)與周圍路段的幾何形態(tài)特征［31］作為約束條件。圖4展示了點(diǎn)到線匹配，其中實(shí)線表示提取的潛在上車點(diǎn)的實(shí)際路網(wǎng)數(shù)據(jù)；虛線表示候選路段。首先以待匹配點(diǎn)q1、q2、q3為圓心，以誤差閾值r為半徑進(jìn)行圓心匹配搜索，并計(jì)算待匹配點(diǎn)q1、q2、q3至每個(gè)候選路段的垂直距離和夾角所構(gòu)成的投影距離，較短的投影距離表示路網(wǎng)匹配度較高，因此可將該路段視為最佳匹配路段。投影距離Ω在本文中可定義為

Ω=μL+ωθ（15）

其中：L表示待匹配點(diǎn)至候選路段的垂直距離；θ表示待匹配點(diǎn)移動(dòng)方向與候選路段行駛方向的夾角；μ和ω分別為權(quán)重參數(shù)，用于調(diào)節(jié)距離和夾角對投影距離的影響。

2.3 多模深度森林預(yù)測算法

預(yù)測動(dòng)態(tài)上車點(diǎn)的過程面臨數(shù)據(jù)不確定性和動(dòng)態(tài)性挑戰(zhàn)，使得上車點(diǎn)的分布和特征可能隨時(shí)間、地點(diǎn)和其他外部因素的變化而動(dòng)態(tài)變化，從而增加了預(yù)測難度。此外，動(dòng)態(tài)上車點(diǎn)預(yù)測問題涉及非線性關(guān)系，采用多模深度森林回歸算法（multi-modal deep forest regression，MDFR）可較好捕捉數(shù)據(jù)中的非線性特征和復(fù)雜關(guān)系，提高預(yù)測準(zhǔn)確度。同時(shí)，通過MDFR進(jìn)行動(dòng)態(tài)上車點(diǎn)預(yù)測可充分利用集成學(xué)習(xí)的優(yōu)勢，提高預(yù)測的魯棒性。MDFR由多粒度掃描（multi-grained scanning，MGS）和級聯(lián)森林（cascade forest，CF）階段組成。其中MGS通過滑動(dòng)窗口對原始特征進(jìn)行掃描，提取樣本中各個(gè)特征之間的關(guān)系，旨在增強(qiáng)CF的性能并實(shí)現(xiàn)特征復(fù)用；CF則模擬了深度神經(jīng)網(wǎng)絡(luò)的級聯(lián)森林框架，增強(qiáng)了算法的表征學(xué)習(xí)能力。本文MGS模型可定義為

MGS=（eτ，c，ζ，ε）（16）

其中：eτ為原始輸入τ維的樣本；c表示滑動(dòng)窗口大小；ζ表示掃描步長；ε表示子樣本數(shù)。經(jīng)掃描可得子樣本數(shù)量如下：

ε=τ－cζ+1（17）

經(jīng)隨機(jī)掃描過后的時(shí)間復(fù)雜度為TI1=O（c×ο），其中ο表示掃描次數(shù)。將子樣本分別輸入多模隨機(jī)森林（multi-modal random forest，MRF）和復(fù)合隨機(jī)森林（composite random forest，CRF）中進(jìn)行訓(xùn)練。

針對數(shù)據(jù)動(dòng)態(tài)性和預(yù)測精確度較低的問題，MRF將隨機(jī)森林作為基礎(chǔ)模型，然后使用梯度提升樹擬合殘差，以提高模型的預(yù)測性能、泛化能力和穩(wěn)定性。假設(shè)已將輸入空間劃分為U個(gè)單元，且在每個(gè)單元上有固定輸出值，則決策樹模型可定義為

f（xl）=∑Ul=1ulI（xl∈Ul）（18）

利用多棵決策樹集成隨機(jī)森林，計(jì)算初始預(yù)測值與真實(shí)標(biāo)簽之間的殘差，如式（20）所示。

f^（xl）=∑Ul=1f（xl）U（19）

υl=f（xl）－f^（xl）（20）

將殘差作為新的目標(biāo)值，利用梯度提升樹擬合殘差，梯度提升樹在本文可定義為

MRF（xl）=∑Ul=1ηlf（xl）（21）

其中：ηl表示第l棵決策樹的權(quán)重。梯度提升樹采用梯度下降法來求解最優(yōu)模型，對于第ι輪迭代，MRF可定義為

MRFι（xl）=MRFι－1－ηι∑Ul=1ΔFL（yl，MRFι－1（xl）+υl）（22）

最后，重復(fù)上述步驟多次，直到達(dá)到最小殘差為止。

整個(gè)過程中需要對殘差進(jìn)行循環(huán)擬合以達(dá)到最小，時(shí)間復(fù)雜度為TI2=O（4m×log m×U+4m×ι）。

針對動(dòng)態(tài)上車點(diǎn)預(yù)測的非線性特征和復(fù)雜關(guān)系問題，CRF將多項(xiàng)式特征變換嵌入到?jīng)Q策樹算法中以增強(qiáng)決策樹的非線性建模能力。在節(jié)點(diǎn)分裂過程中對輸入的子樣本進(jìn)行多項(xiàng)式特征變換，形成新的特征集合如式（24）所示。

xj=（1，xj1，…，xj4，x2j1，…，x2j4，…，xκj1，…，xκj4）（23）

Xj=（x1，x2，…，xj，…，xm）（24）

式（23）中，xκj4表示第j個(gè)數(shù)據(jù)第4維特征的第κ階多項(xiàng)式。將特征集合利用平方誤差最小化準(zhǔn)則作為劃分節(jié)點(diǎn)的條件［32］，則CRF可以定義為

CRF（Xj）=minj（∑Xj∈U（yj－f（Xj））2）（25）

此過程中無循環(huán)，僅為決策樹節(jié)點(diǎn)的分裂，時(shí)間復(fù)雜度為TI3=O（4κm×log m）。

圖5中多粒度掃描階段展示了MGS生成CF輸入特征向量的過程。首先將4 dim的xj=（TRCIbi，WDISbipj，TIMEpj，COSTbipj）T作為輸入層，滑動(dòng)窗口c大小分別取1 dim、2 dim和3 dim，對輸入樣本進(jìn)行滑動(dòng)取樣；掃描步長ζ默認(rèn)為1，分別得子樣本數(shù)ε為4、3和2。然后采用MRF和CRF對所得子樣本進(jìn)行訓(xùn)練，每個(gè)樣本輸出1個(gè)2 dim的概率特征向量，即分別生成16 dim，12 dim和8 dim的特征向量。最后，將所有向量合并作為CF輸入特征向量。

在CF中，MGS的輸出結(jié)果MGSo作為第一層輸入CFx1，特征向量FV作為第一層輸出CFy1，前層輸入和輸出結(jié)果合并作為下一層的輸入［33］，第一層輸出和第二層輸入可分別定義為

CFy1=g（1）（MGSo，F(xiàn)V）（26）

CFx2={MGSo∪FV∪CFy1}（27）

式（26）中g(shù)（1）表示第一層CF中的特征處理函數(shù)。每層輸入均來自于上層的特征處理，并將經(jīng)過處理的特征傳遞給下層，因此第M層輸出和第M+1層輸入可分別定義為

CFyM=g（I）（CFxM）（28）

CFxM+1={MGSo∪FV∪CFy1∪CFyM}（29）

式（28）中g(shù)（I）表示第I層CF中的特征處理函數(shù)。在CF中，每個(gè)森林預(yù)測樣本xJ的輸出類向量和輸出結(jié)果，可分別定義為

G（xJ）=∑VJ=1（MRF（xJ）+CRF（xJ）+CFxJ）V（30）

W（xJ）=G11（xJ）G12（xJ）…G1N（xJ）

G21（xJ）G22（xJ）…G2N（xJ）

GK1（xJ）GK2（xJ）…GKN（xJ）（31）

其中：V表示森林中決策樹個(gè)數(shù)；GKN（xJ）表示CF中第N層第K個(gè)森林所輸出的預(yù)測向量。根據(jù)預(yù)測向量對樣本進(jìn)行最終預(yù)測，如式（32）所示。

CF（xJ）=max（avg（W（xJ）））（32）

CF過程中每層為上一層的結(jié)果處理，無循環(huán)，時(shí)間復(fù)雜度為TI4=O（m×K×U×N/）+O（4m+），其中表示每個(gè)森林可以劃分為個(gè)子森林。綜上所述，多模深度森林的時(shí)間復(fù)雜度為TI=TI1+TI2+TI3+TI4。

圖5中級聯(lián)森林階段展示了CF的完整流程，經(jīng)過MGS后，共提取了36 dim特征向量作為CF的第一層輸入；第一層經(jīng)過MRF和CRF訓(xùn)練后產(chǎn)生8 dim的增加特征向量，加之原始36 dim特征向量，形成44 dim變換特征向量作為第二層輸入。依此類推，經(jīng)過N層處理后輸出為每個(gè)MRF或CRF對動(dòng)態(tài)上車點(diǎn)的預(yù)測評分。最后，對該結(jié)果的平均取最大值，即可得最終上車點(diǎn)評分。

2.4 迭代Kuhn-Munkres上車點(diǎn)配置算法

在乘客和上車點(diǎn)的動(dòng)態(tài)配置問題中，首先需構(gòu)建帶權(quán)二分圖，利用乘客對上車點(diǎn)的評分作為邊權(quán)重；然后采用二分圖最大權(quán)匹配算法求出最優(yōu)匹配方案，并計(jì)算匹配后子圖中所有邊權(quán)重的和［34］。由于實(shí)際路網(wǎng)數(shù)量龐大，傳統(tǒng)二分圖最大權(quán)匹配算法（Kuhn-Munkres， KM）在處理大型算例時(shí)表現(xiàn)出較高的時(shí)間復(fù)雜度，且其運(yùn)行時(shí)間呈現(xiàn)出超線性趨勢增長［35］，因此，同時(shí)規(guī)劃出乘客和任一上車點(diǎn)之間配置策略的難度較高，無法保證算法的實(shí)時(shí)性；此外，KM算法只能解決一對一的匹配問題，無法有效處理一對多的匹配問題?；谏鲜隹紤]，本文提出了迭代Kuhn-Munkres上車點(diǎn)配置算法（iterative Kuhn-Munkres， IKM），其能在較短時(shí)間內(nèi)搜索到較優(yōu)的配置結(jié)果，并可結(jié)合實(shí)際情況靈活調(diào)整路徑、切換配置頂點(diǎn)，以實(shí)現(xiàn)乘客與上車點(diǎn)的全局供需平衡。在每輪迭代中針對局部增廣路徑進(jìn)行更新，且在無法找到更多增廣路徑時(shí)提前停止迭代，從而減少了計(jì)算時(shí)間，提高了算法的效率。IKM算法偽代碼如算法1所示。

算法1 IKM算法

輸入：OBP=（B，P，（i， j）），bi，yj。

輸出：最優(yōu)匹配結(jié)果。

mate= {}；

bi=max{yj}， pj=0，mai=0，Oau={}; /*初始化節(jié)點(diǎn)和上車點(diǎn)節(jié)點(diǎn)人數(shù)*/

for pj in P

max（（i， j））=－∞;

bei=;

/*初始化賦權(quán)值和最佳上車點(diǎn)*/

for bi in B

if bi+pj=（i， j）

if bi not in Oau

"Oau［bi］=［］;

Oau［bi］.append（pj）;

/*對于每個(gè)乘客節(jié)點(diǎn)j，都能在輔助二分圖中找到對應(yīng)的可行上車點(diǎn)節(jié)點(diǎn)集合*/

end if

Qi={};

for bi in Oau

if len（Oau［bi］）gt;0

Qi［i］=Oau［bi］［i］;

Qi.append（Qi［i］）;

/*任取輔助二分圖中的任一匹配*/

end if

if len（Qi）==len（OBP）

mate［j］=bpj;

elseif mai≤bi

（i， j）=yj;

if （i， j）gt;max（（i， j））

max（（i， j））=（i， j）;

bei=i;

/*找到與乘客節(jié)點(diǎn)j權(quán)值最高的上車點(diǎn)節(jié)點(diǎn)i*/

end if

end if

if bei≠

"將乘客節(jié)點(diǎn)j分配給最佳上車點(diǎn);

mai+=1

/*最佳上車點(diǎn)的容納人數(shù)增加*/

end if

if maigt;bi

將該上車點(diǎn)從集合B中移除;

end if

end for

end if

end for

mate［j］= 分配給乘客節(jié)點(diǎn)j的上車點(diǎn);

mate. append（mate［j］）;

return mate;

end for

令B=∪ni=1bi，P=∪mj=1pj，可將乘客與上車點(diǎn)的配置問題定義為有向帶權(quán)二分圖OBP=（B，P，（i， j）），其中（i， j）表示將集合P中乘客節(jié)點(diǎn)j配對至集合B中上車點(diǎn)的權(quán)值。在此基礎(chǔ)上利用IKM通過多場景自適應(yīng)機(jī)制進(jìn)行配置，其具體步驟如下。

首先輸入二分圖OBP=（B，P，（i， j）），根據(jù)式（8）設(shè)置初始節(jié)點(diǎn)標(biāo)號bi=max{yj}，pj=0，mai=0。

從OBP中選擇滿足條件bi+pj=（i， j）的邊構(gòu)造輔助二分圖Oau，并任取Oau的一個(gè)匹配Qi。若Qi飽和了OBP的所有節(jié)點(diǎn)，那么Qi即為所求最優(yōu)匹配，計(jì)算停止并返回匹配結(jié)果，即mate［j］=bpj，其中bpj表示分配給乘客節(jié)點(diǎn)j的上車點(diǎn)；否則，根據(jù)式（1）可分別得式（33）（34）。

（i， j）=yj" mai≤bi0其他 （33）

bei=i，max（（i， j））=（i， j） （i， j）gt;max（（i， j））其他（34）

若此時(shí)bei≠，則將pj分配至bei，最佳上車點(diǎn)的容納人數(shù)相應(yīng)增加。當(dāng)最佳上車點(diǎn)人數(shù)大于該上車點(diǎn)人數(shù)容量閾值bi時(shí)，將該最佳上車點(diǎn)bei從上車點(diǎn)集合B中移除。

最后，尋找一條由集合P到集合B的增廣路徑ρ，令Qi+1=Qi⊕ρ，i=i+1。重復(fù)以上步驟，直至Qi飽和了OBP的所有節(jié)點(diǎn)。

設(shè)配置圖中的節(jié)點(diǎn)數(shù)量為mnode，邊數(shù)量為medge，乘客數(shù)量為m，上車點(diǎn)數(shù)量為n。對于原算法，單次KM算法進(jìn)行乘客與上車點(diǎn)配置的時(shí)間復(fù)雜度為O（mnode×medge），需要執(zhí)行mnode次，故總體時(shí)間復(fù)雜度為O（m2node×medge）。而經(jīng)過IKM算法迭代縮減循環(huán)，實(shí)際總體執(zhí)行IKM算法的次數(shù)為min（m，n），故時(shí)間復(fù)雜度為O（mnode×medge×min（m，n））。需要強(qiáng)調(diào)的是，以上處理并未增加空間開銷。

3 實(shí)驗(yàn)與分析

實(shí)驗(yàn)采用Python語言，相關(guān)數(shù)據(jù)來源于上海市出租車GPS數(shù)據(jù)集以及滴滴出行中上海市網(wǎng)約車訂單數(shù)據(jù)，實(shí)驗(yàn)參數(shù)設(shè)置如表2所示。由于本文所使用的數(shù)據(jù)集基于上海市出租車數(shù)據(jù)集，所以按照上海市的交通標(biāo)準(zhǔn)設(shè)定定價(jià)方案。

本文權(quán)重參數(shù)基于層次分析法，并綜合考慮真實(shí)應(yīng)用場景與大量實(shí)驗(yàn)的最優(yōu)輸出值進(jìn)行設(shè)定［36］。首先根據(jù)影響因子構(gòu)造判斷矩陣A，然后由判斷矩陣A計(jì)算出被比較的影響因子對于該準(zhǔn)則的相對權(quán)重并進(jìn)行一致性檢驗(yàn)。利用一致性指標(biāo)CI和一致性比例CR判斷一致性檢驗(yàn)是否通過，一致性指標(biāo)CI和一致性比例CR可分別定義為

CI=λmax（A）－－1（35）

CR=CIRI（36）

其中：λmax（A）表示判斷矩陣A的最大特征值；表示判斷矩陣A的維數(shù)；RI表示判斷矩陣A的一致性標(biāo)準(zhǔn)。當(dāng)CR≤0.1時(shí)，表明判斷矩陣A的一致性程度在容許范圍內(nèi)，此時(shí)可對判斷矩陣A采用算術(shù)平均法、幾何平均法、特征值法三種方法所得的權(quán)重計(jì)算平均值，避免單一方法所產(chǎn)生的偏差。

3.1 預(yù)測算法評估

本文采用平均絕對誤差（MAE）、均方根誤差（RMSE）、可決系數(shù)（R2）和可解釋方差（EV）對MDFR進(jìn)行評估，計(jì)算公式如下：

MAE=∑ni=1|yi－i|n（37）

RMSE=∑ni=1（yi－i）2n（38）

R2=1－∑ni=1（yi－i）2∑ni=1（yi－i）2（39）

EV=1－∑ni=1［（yi－i）－（yi－i）］2∑ni=1（yi－）2（40）

=∑ni=1yin（41）

其中：yi和i分別為觀測值和預(yù)測值；（yi－i）是（yi－i）的均值；n為觀測樣本的大小。

對比模型選取了：a）集成模型，梯度提升樹回歸模型（GBDTR）和隨機(jī)森林回歸模型（RFR）；b）機(jī)器學(xué)習(xí)模型，線性回歸模型（LR）、支持向量機(jī)回歸模型（SVR）和K近鄰回歸模型（KNNR）；c）代表性深度學(xué)習(xí)模型，包括循環(huán)神經(jīng)網(wǎng)絡(luò)（RNN）和長短時(shí)記憶神經(jīng)網(wǎng)絡(luò)（LSTM）；d）其他，多頭注意力時(shí)空卷積圖網(wǎng)絡(luò)模型（MASCGN）［37］、LightGBM混合模型（HLGBM）［38］和多元交互注意力機(jī)制模型（SDT-ATT）［39］。預(yù)測模型對比實(shí)驗(yàn)結(jié)果如表3所示。

由表3可知，對于MDFR，其MAE、RMSE、R2和EV值平均分別為2.375、30.935、0.909以及0.911。與其他模型相比，MDFR的平均絕對誤差降低了2.705，均方誤差降低了5.915，可決系數(shù)提升了0.214，解釋方差提升了0.195，說明MDFR在預(yù)測最佳上車點(diǎn)方面表現(xiàn)良好。此外，不同模型在不同尺寸數(shù)據(jù)集上的表現(xiàn)存在差異，隨著數(shù)據(jù)集尺寸的增加，模型的擬合程度有所提升。但在所有模型中LR表現(xiàn)最差，說明線性模型無法準(zhǔn)確預(yù)測最佳上車點(diǎn)，與實(shí)際情況相符。

下面對MDFR進(jìn)行敏感性分析，實(shí)驗(yàn)中分別修改了MDFR的四個(gè)參數(shù)，即葉子節(jié)點(diǎn)中含有的最小樣本、最大樹深度、每個(gè)森林模型中樹的數(shù)量以及每層森林模型的個(gè)數(shù)。由圖6可知，隨著葉子節(jié)點(diǎn)中含有的最小樣本的增加，MAE持續(xù)上升，而R2和EV值先上升后持續(xù)下降；當(dāng)最大樹深度增加時(shí)，MAE先大幅減少后趨于平穩(wěn)，而R2和EV值則先減少后增大再減少；隨著每個(gè)森林模型中樹的數(shù)量增加，MAE先大幅下降后緩慢增加，而R2和EV則相反；隨著每層森林模型的個(gè)數(shù)增加，MAE、R2和EV均先增加后下降。在葉子節(jié)點(diǎn)含有的最小樣本小于3、最大樹深度為40、每個(gè)森林模型中樹的數(shù)量為100以及每層森林模型的個(gè)數(shù)在6～10時(shí)，MDFR表現(xiàn)最佳。

為了驗(yàn)證MDFR算法中MRF和CRF的高效性和有效性，本文使用深度森林預(yù)測模型（DFR）作為基礎(chǔ)模型在原數(shù)據(jù)集上進(jìn)行消融實(shí)驗(yàn)。為了保證結(jié)果的可靠性，在隨機(jī)選擇不同尺寸的數(shù)據(jù)集上各運(yùn)行10次，取10次的平均值作為最終結(jié)果。實(shí)驗(yàn)結(jié)果如表4所示。

由表4可知，MDFR算法中MRF和CRF對算法MAE、RMSE、R2和EV的影響有所不同，但均比基礎(chǔ)模型有所提升。當(dāng)處理不同尺寸大小的數(shù)據(jù)集時(shí)，MDFR、僅含MRF和僅含CRF算法比不使用這些算法的DFR， MAE分別降低了0.514、0.255和0.265；RMSE分別降低了0.568、0.272和0.302； R2分別提升了0.034、0.014和0.019，EV分別提升了0.042、0.019和0.022。產(chǎn)生這樣結(jié)果的原因是，MRF結(jié)合了隨機(jī)森林和梯度提升樹的優(yōu)點(diǎn)，在每輪迭代中都會(huì)捕捉前一輪模型無法解釋的數(shù)據(jù)動(dòng)態(tài)性，能夠逐步減少預(yù)測誤差，持續(xù)優(yōu)化模型性能，提高模型的預(yù)測準(zhǔn)確性；CRF則是通過在決策樹中引入多項(xiàng)式特征變換生成新的特征，使得模型可在更細(xì)致的層次上進(jìn)行數(shù)據(jù)劃分。由于特征空間變得更復(fù)雜，決策樹可在多維空間中找到更合適的劃分點(diǎn)，更好地適應(yīng)數(shù)據(jù)中的非線性關(guān)系和復(fù)雜性。

綜上所述，MDFR算法在大數(shù)據(jù)環(huán)境下具有良好的可行性和有效性。

3.2 配置算法評估

3.2.1 配置算法實(shí)驗(yàn)結(jié)果

本節(jié)從乘客數(shù)量和上車點(diǎn)數(shù)量兩個(gè)角度，對比分析在乘客數(shù)量占優(yōu)（passenger quantity advantage，PQA）和上車點(diǎn)數(shù)量占優(yōu)（pick-up point quantity advantage，PPQA）的條件下，上車點(diǎn)優(yōu)先策略（pick-up point priority strategy，PPPS）［1］、乘客優(yōu)先策略（passenger priority strategy，PPS）［19］和本文策略（comprehensive strategy，CS）的優(yōu)劣以及對動(dòng)態(tài)上車點(diǎn)推薦的影響。PPPS［1］、PPS［19］及CS策略的參數(shù)權(quán)重設(shè)置分別如表5所示。

本節(jié)模擬了6個(gè)實(shí)例，3個(gè)不同數(shù)量乘客和3個(gè)不同數(shù)量上車點(diǎn)，實(shí)例參數(shù)如表6所示。對6個(gè)實(shí)例分別用IKM和KM算法各執(zhí)行10次，將IKM的平均解、平均時(shí)間與KM算法的最優(yōu)解、平均時(shí)間作比較，得到質(zhì)量比和時(shí)間比，對比結(jié)果如表7所示。

由表7可知，對于較大規(guī)模的實(shí)例，時(shí)間比隨著數(shù)據(jù)集尺寸的增加逐漸下降，且質(zhì)量比均在98%以上，說明與KM算法最優(yōu)解相比較，IKM算法可在較短時(shí)間內(nèi)得到高質(zhì)量的解。IKM算法的平均運(yùn)行時(shí)間緩慢增長，而KM算法的平均運(yùn)行時(shí)間呈非線性增長且增長迅速，說明IKM算法的時(shí)間效率優(yōu)于KM算法。

IKM和KM算法在處理PQA條件下不同規(guī)模算例數(shù)據(jù)集時(shí)的平均運(yùn)行時(shí)間分別為69.24 s和238.26 s，前者僅為后者的29.06%；IKM和KM算法在處理PPQA條件下不同規(guī)模算例數(shù)據(jù)集時(shí)的平均運(yùn)行時(shí)間分別為66.95 s和200.78 s，前者僅為后者的33.34%。在本實(shí)驗(yàn)規(guī)模算例下，改進(jìn)后的Kuhn-Munkres算法在解決乘客與上車點(diǎn)配置問題時(shí)表現(xiàn)出較好的結(jié)果，各種方案中IKM算法的求解效率是傳統(tǒng)KM算法的64.97%。

3.2.2 PQA條件

在某些特定時(shí)間段、特殊事件期間或交通管制時(shí)，會(huì)出現(xiàn)在同一時(shí)刻內(nèi)乘客叫車數(shù)量大于上車點(diǎn)數(shù)量的情況。本條件下限定乘客數(shù)量分別為100人、500人和1 000人，而上車點(diǎn)數(shù)量則分別在小于100個(gè)、500個(gè)和1 000個(gè)數(shù)據(jù)集中隨機(jī)選擇不同數(shù)量的上車點(diǎn)進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表8所示。

1）PPPS實(shí)驗(yàn)分析

圖7中三角形圖標(biāo)表示乘客，圓形圖標(biāo)表示上車點(diǎn)，相同顏色表示該乘客被分配至該上車點(diǎn)（參見電子版）。盡管PPPS算法能確保每位乘客被成功配置到上車點(diǎn)，但應(yīng)用上車點(diǎn)優(yōu)先策略后，圖7顯示多數(shù)乘客步行距離和步行時(shí)間均有所增加。與CS和PPS相比，PPPS的平均得分分別降低了2.04%和1.08%，如表8所示。這一差異表明，在乘客與上車點(diǎn)的配置過程中，PPPS策略以犧牲乘客便利性為代價(jià)，追求其他目標(biāo)的實(shí)現(xiàn)。因此，在特定PQA條件下PPPS不是最優(yōu)選擇。

2）PPS實(shí)驗(yàn)分析

圖8采用了與圖7相同的表達(dá)方法展示乘客與上車點(diǎn)的對應(yīng)關(guān)系。PPS算法基于自適應(yīng)機(jī)制，綜合考慮了乘客步行距離和步行時(shí)間，旨在為每位乘客分配一個(gè)具有相對優(yōu)勢的上車點(diǎn)。然而，此方法在特定區(qū)域（如景點(diǎn)和醫(yī)院周邊）的高峰時(shí)段易引發(fā)上車點(diǎn)附近路況惡化現(xiàn)象。此外，由于司機(jī)前往乘客指定的上車點(diǎn)過程中發(fā)生了行程偏移，導(dǎo)致乘客抵達(dá)目的地的訂單金額超出預(yù)期。這些因素的共同作用使PPS的平均得分相較CS偏低，如表8所示。

3）CS實(shí)驗(yàn)分析

圖9中乘客與上車點(diǎn)的對應(yīng)關(guān)系延續(xù)了圖7相同的表達(dá)方式。由圖9可知，CS算法通過多場景自適應(yīng)機(jī)制，綜合考量了上車點(diǎn)路況指標(biāo)、預(yù)估訂單金額、乘客步行距離及步行時(shí)間，將乘客分配至相應(yīng)的上車點(diǎn)。盡管部分乘客被分配至距離稍遠(yuǎn)的上車點(diǎn)，但并未對整體評分產(chǎn)生顯著影響。相反，由于所分配上車點(diǎn)位于交通狀況較佳的區(qū)域，且減少了不必要的路線偏離。所以，乘客到達(dá)目的地的預(yù)估金額相對較低，反映了IKM算法在綜合考量多因素后得出的優(yōu)化結(jié)果。

3.2.3 PPQA條件

一般情況下，上車點(diǎn)數(shù)量通常會(huì)超過同時(shí)叫車的乘客數(shù)量。隨著可供選擇的上車點(diǎn)數(shù)量增加，乘客更易按照個(gè)人偏好選擇上車點(diǎn)，這也與實(shí)驗(yàn)結(jié)果保持一致。通過對比分析表8和9可知，在PPQA條件下，乘客對各上車點(diǎn)的評分普遍高于PQA條件下的評分。本實(shí)驗(yàn)設(shè)定了不同數(shù)量上車點(diǎn)（100個(gè)、500個(gè)和1 000個(gè)）和乘客（小于100人、500人和1 000人），并在處理好的數(shù)據(jù)集中隨機(jī)選擇各種數(shù)量的乘客經(jīng)緯度以及目的地經(jīng)緯度，實(shí)驗(yàn)結(jié)果如表9所示。

1）PPPS實(shí)驗(yàn)分析

圖10中三角形圖標(biāo)表示乘客，正方形圖標(biāo)表示上車點(diǎn)，圓形圖標(biāo)表示候選上車點(diǎn)，相同顏色表示該乘客被分配至該上車點(diǎn)（參見電子版）。PPPS算法將上車點(diǎn)作為首要考慮因素，旨在為每位乘客分配一個(gè)基于算法邏輯計(jì)算得出的最佳上車點(diǎn)。以深黃色乘客為例，由于步行距離最近的上車點(diǎn)靠近景點(diǎn)，基于交通情況考量，通常不被視為推薦的上車點(diǎn)；對于藍(lán)灰色乘客而言，盡管存在更近的上車點(diǎn)，但鑒于道路設(shè)計(jì)或交通規(guī)則限制，司機(jī)在此處執(zhí)行車輛轉(zhuǎn)向操作存在困難，導(dǎo)致預(yù)估的訂單金額增加。因此，PPPS算法將該乘客分配至一個(gè)路況較好且預(yù)估訂單金額適宜的上車點(diǎn)，如圖10所示。

2）PPS實(shí)驗(yàn)分析

圖11沿用了圖10中的表達(dá)方法展示乘客與上車點(diǎn)的對應(yīng)關(guān)系。在該圖中，乘客與上車點(diǎn)的匹配結(jié)果均基于最小化乘客步行距離和步行時(shí)間的優(yōu)化目標(biāo)進(jìn)行決策，此策略顯著凸顯了對乘客利益的優(yōu)先考量，并將乘客的步行優(yōu)化條件置于決策過程的核心地位。相較于其他兩種策略，乘客對該策略匹配結(jié)果的評分普遍較高，進(jìn)一步驗(yàn)證了該策略在提高乘客滿意度方面的有效性，如表9所示。

3）CS實(shí)驗(yàn)分析

圖12沿用了圖10中的表達(dá)方法展示乘客與上車點(diǎn)的對應(yīng)關(guān)系。在PPQA條件下，盡管乘客傾向于選擇最為便利的上車點(diǎn)，但從CS角度來看，乘客的選擇并不僅限于個(gè)人利益最大化。以上下班高峰期等特殊時(shí)間段為例，為減少交通擁堵帶來的等待時(shí)間，乘客會(huì)選擇增加步行距離，從而提高整體出行效率。然而從全局視角分析，CS策略下的平均得分指數(shù)略低于PPS［19］策略下的表現(xiàn)，如表9所示。

3.2.4 各影響因子真實(shí)占比分析

本節(jié)旨在通過調(diào)整權(quán)重參數(shù)來比較分析各影響因子真實(shí)占比之間的相關(guān)性，以及這些因素如何影響上車點(diǎn)平均得分指數(shù)的變化。圖13中，（a）和（b）權(quán)重參數(shù)根據(jù)PPPS［1］策略設(shè)置，（c）和（d）權(quán)重參數(shù)根據(jù)PPS［19］策略設(shè)置。

由圖13（a）可知，隨著上車點(diǎn)路況指標(biāo)占比的增加，上車點(diǎn)平均得分指數(shù)呈現(xiàn)正相關(guān)性，且在上車點(diǎn)路況指標(biāo)占比介于［0.3， 0.4］時(shí)，上車點(diǎn)平均得分增長幅度最為顯著。與此同時(shí)，預(yù)估訂單金額、乘客步行距離和步行時(shí)間真實(shí)占比均有所下降，表明當(dāng)上車點(diǎn)路況較差時(shí)，IKM算法更加重視路況因素，以優(yōu)化乘客的出行體驗(yàn)。

由圖13（b）可知，預(yù)估訂單金額占比與上車點(diǎn)平均得分指數(shù)之間呈現(xiàn)出負(fù)相關(guān)性，隨著預(yù)估訂單金額占比的增加，上車點(diǎn)平均得分指數(shù)呈逐漸下降趨勢。此外，上車點(diǎn)路況指標(biāo)真實(shí)占比隨著預(yù)估訂單金額占比的增加而降低，表明在高價(jià)值訂單情況下，路況因素對上車點(diǎn)配置的影響減弱。同時(shí)，乘客步行距離和乘客步行時(shí)間真實(shí)占比雖變化不大，但也呈現(xiàn)出緩慢增加的趨勢，表明在訂單金額較高時(shí)，乘客對步行距離和步行時(shí)間的敏感度有所增加，但此變化相對較小。

由圖13（c）可知，隨著乘客步行距離占比的增加，上車點(diǎn)平均得分指數(shù)呈現(xiàn)先下降后趨于穩(wěn)定的趨勢，表明在乘客步行距離達(dá)到一定閾值后對上車點(diǎn)配置的影響減弱。同時(shí)，上車點(diǎn)路況指標(biāo)真實(shí)占比隨著乘客步行距離占比的增加而持續(xù)下降，表明在短步行距離情況下，IKM算法更傾向于優(yōu)先考慮步行距離而非上車點(diǎn)路況指標(biāo)，以優(yōu)化乘客的上車點(diǎn)配置。另一方面，預(yù)估訂單金額真實(shí)占比呈現(xiàn)緩慢增加的趨勢，表明隨著步行距離的增加，預(yù)估訂單金額在決策過程中的重要性逐漸上升。乘客步行時(shí)間真實(shí)占比隨著步行距離占比的增加而呈現(xiàn)出先上升后下降的趨勢，這一現(xiàn)象與多種因素有關(guān)，如乘客步行速度的變化、等待時(shí)間的長短、路況和環(huán)境因素等。

由圖13（d）可知，隨著乘客步行時(shí)間占比的增加，上車點(diǎn)平均得分指數(shù)呈現(xiàn)出緩慢下降后趨于穩(wěn)定的趨勢，這與乘客對步行時(shí)間的敏感度有關(guān)，即在步行時(shí)間較長時(shí)，乘客更傾向于選擇得分較高的上車點(diǎn)以減少步行時(shí)間。同時(shí)，上車點(diǎn)路況指標(biāo)真實(shí)占比呈現(xiàn)出先快速下降后趨于穩(wěn)定的趨勢，反映了在步行時(shí)間較長時(shí)上車點(diǎn)路況指標(biāo)對決策的影響減弱。預(yù)估訂單金額真實(shí)占比平緩增加且乘客步行距離真實(shí)占比先上升后下降，表明在乘客需求較低且乘客步行時(shí)間較長時(shí)，IKM算法更傾向于考慮減少乘客步行時(shí)間的上車點(diǎn)。

3.3 綜合分析

3.3.1 平均得分分析

由表8可知，當(dāng)處于PQA條件下時(shí)，CS策略具有一定優(yōu)勢，而PPPS策略的平均得分較低，與CS策略平均相差2.04%。由表9可知，當(dāng)處于PPQA條件下時(shí)，PPS策略優(yōu)于其他兩種方案，且PPPS 策略平均得分仍為最低，與PPS策略平均相差4.14%。

綜上所述，當(dāng)處于PQA條件下時(shí)，乘車軟件應(yīng)根據(jù)CS策略為乘客推薦最佳上車點(diǎn)；當(dāng)處于PPQA條件下時(shí)，則應(yīng)根據(jù)PPS策略為乘客進(jìn)行推薦。在實(shí)際生活中，需根據(jù)不同的現(xiàn)實(shí)情況進(jìn)行討論和動(dòng)態(tài)推薦。

3.3.2 行程時(shí)間對比

本文設(shè)定行人步行的平均速度為60 m/min，網(wǎng)約車的平均行駛速度為600 m/min。表10給出了不同條件下行程時(shí)間的對比結(jié)果。

由表10可知，KM算法在處理不同規(guī)模數(shù)據(jù)時(shí)耗時(shí)明顯高于IKM算法，無法滿足乘客與上車點(diǎn)配置的實(shí)時(shí)性要求。由于KM算法只考慮局部最優(yōu)，導(dǎo)致乘客平均步行時(shí)間、行程平均總時(shí)間均高于IKM算法考慮全局最優(yōu)后所得出的配置結(jié)果。

4 結(jié)束語

本文提出了一種基于多模深度森林和迭代Kuhn-Munkres的動(dòng)態(tài)上車點(diǎn)推薦算法。首先，對時(shí)空軌跡大數(shù)據(jù)進(jìn)行約束處理，以提取出基于路網(wǎng)匹配的潛在上車點(diǎn)集；其次，基于乘客步行距離、步行時(shí)間、上車點(diǎn)路況指標(biāo)以及上車點(diǎn)至乘客目的地的預(yù)估訂單金額等關(guān)鍵影響因子，利用多模深度森林預(yù)測算法進(jìn)行最佳上車點(diǎn)預(yù)測；最后，通過迭代Kuhn-Munkres算法引導(dǎo)乘客前往最佳上車點(diǎn)上車，旨在減少運(yùn)算資源消耗，并通過設(shè)置上車點(diǎn)的最大容納人數(shù)閾值來解決同一上車點(diǎn)多乘客導(dǎo)致的交通擁堵問題。實(shí)驗(yàn)研究表明，本文提出的多模深度森林預(yù)測算法和迭代Kuhn-Munkres配置算法具有較高的實(shí)用性，且配置算法不僅能有效提升平均調(diào)度效果，同時(shí)在處理大規(guī)模數(shù)據(jù)集上有較高的求解效率。

本文目前僅從乘客和上車點(diǎn)的角度考慮上車點(diǎn)推薦問題，且提出的算法中的一些參數(shù)（如決策樹數(shù)量、深度、決策權(quán)重等）需事先設(shè)定，并可能對最終的預(yù)測結(jié)果和配置結(jié)果產(chǎn)生影響。在未來的研究中，擬考慮將司機(jī)角度納入模型范圍以進(jìn)一步提升交通效率、司機(jī)接單率以及乘客滿意度；同時(shí)，將探索利用自動(dòng)化參數(shù)調(diào)優(yōu)技術(shù)來自動(dòng)搜索最佳參數(shù)組合，以提高算法的性能和參數(shù)調(diào)節(jié)效率。

參考文獻(xiàn)：

［1］Zhu Wanqiu， Lu Jian， Li Yunxuan， et al. A pick-up points recommendation system for ridesourcing service ［J］. Sustainability， 2019， 11（4）： 1097.

［2］路民超， 李建波， 逄俊杰， 等. 面向出租車需求預(yù)測的多因素時(shí)空圖卷積網(wǎng)絡(luò) ［J］. 計(jì)算機(jī)工程與應(yīng)用， 2020， 56（24）： 266-273. （Lu Minchao， Li Jianbo， Pang Junjie， et al. Multi-factor spatio-temporal graph convolution network for taxi demand prediction ［J］. Computer Engineering and Applications， 2020， 56（24）： 266-273.）

［3］熊亭， 戚湧， 張偉斌， 等. 基于時(shí)空相關(guān)性的短時(shí)交通流預(yù)測模型 ［J］. 計(jì)算機(jī)工程與設(shè)計(jì)， 2019， 40（2）： 501-507. （Xiong Ting， Qi Yong， Zhang Weibin， et al. Short term traffic flow forecasting model based on temporal-spatial correlation ［J］. Computer Engineering and Design， 2019， 40（2）： 501-507.）

［4］陳瑞， 沈鑫， 萬得勝， 等. 面向綠色節(jié)能的智能網(wǎng)聯(lián)電動(dòng)車調(diào)度方法 ［J］. 計(jì)算機(jī)科學(xué)， 2023， 50（12）： 285-293. （Chen Rui， Shen Xin， Wan Desheng， et al. Intelligent networked electric vehicles scheduling method for green energy saving ［J］. Computer Science， 2023， 50（12）： 285-293.）

［5］鄭渤龍， 明嶺峰， 胡琦， 等. 基于深度強(qiáng)化學(xué)習(xí)的網(wǎng)約車動(dòng)態(tài)路徑規(guī)劃［J］. 計(jì)算機(jī)研究與發(fā)展， 2022， 59（2）： 329-341. （Zheng Bolong， Ming Lingfeng， Hu Qi， et al. Dynamic ride-hailing route planning based on deep reinforcement learning ［J］. Journal of Computer Research and Development， 2022， 59（2）： 329-341.）

［6］陳立軍， 張屹， 陳孝如， 等. 網(wǎng)約車任務(wù)分配系統(tǒng)優(yōu)化 ［J］. 計(jì)算機(jī)系統(tǒng)應(yīng)用， 2022， 31（6）： 19-28. （Chen Lijun， Zhang Yi， Chen Xiaoru， et al. Optimization of task allocation system for online car-hailing ［J］. Computer Systems Applications， 2022， 31（6）： 19-28.）

［7］Wang Sai， Wang Jianjun， Li Weijia， et al. Revealing the influence mechanism of urban built environment on online car-hailing travel considering orientation entropy of street network ［J］. Discrete Dynamics in Nature and Society， 2022（1）： 3888800.

［8］Agarwal S， Charoenwong B， Cheng S F， et al. The impact of ride-hail surge factors on taxi bookings ［J］. Transportation Research Part C： Emerging Technologies， 2022， 136（3）： 103508.

［9］Xia Dawen， Bai Yu， Zheng Yongling， et al. A parallel SP-DBSCAN algorithm on spark for waiting spot recommendation ［J］. Multimedia Tools and Applications， 2022，81（1）： 4015-4038.

［10］Mann S K， Chawla S. A proposed hybrid clustering algorithm using K-means and BIRCH for cluster based cab recommender system （CBCRS） ［J］. International Journal of Information Technology， 2023， 15（1）： 219-227.

［11］康軍， 張凡， 段宗濤， 等. 基于LightGBM的乘客候車路段推薦方法 ［J］. 測控技術(shù)， 2020， 39（2）： 56-62. （Kang Jun， Zhang Fan， Duan Zongtao， et al. Recommendation method of passengers’ boar-ding sections based on LightGBM ［J］. Measurement amp; Control Technology， 2020， 39（2）： 56-62.）

［12］Olakanmi O O， Odeyemi K O. A collaborative 1-to-n on-demand ride sharing scheme using locations of interest for recommending shortest routes and pick-up points ［J］. International Journal of Intelligent Transportation Systems Research， 2021， 19（6）： 285-298.

［13］Gu Shuxian， Dai Yemo， Feng Zezheng， et al. T-PickSeer： visual analysis of taxi pick-up point selection behavior ［J］. Journal of Visualization， 2024， 27（6）： 451-468.

［14］You Lan， Guan Zhengyi， Li Na， et al. A spatio-temporal schedule-based neural network for urban taxi waiting time prediction ［J］. ISPRS International Journal of Geo-Information， 2021， 10（10）： 703.

［15］Dieter P， Stumpe M， Ulmer M W， et al. Anticipatory assignment of passengers to meeting points for taxi-ridesharing ［J］. Transportation Research Part D： Transport and Environment， 2023， 121（8）： 103832.

［16］Chang Mengmeng， Chi Yuanying， Ding Zhiming， et al. A continuous taxi pickup path recommendation under the carbon neutrality context ［J］. ISPRS International Journal of Geo-Information， 2021， 10（12）： 821.

［17］Aliari S， Haghani A. Alternative pickup locations in taxi-sharing： a feasibility study ［J］. Transportation Research Record， 2023， 2677（1）： 1391-1403.

［18］Zhang Yan， Shen Guojiang， Han Xiao， et al. Spatio-temporal digraph convolutional network-based taxi pickup location recommendation ［J］. IEEE Trans on Industrial Informatics， 2023， 19（1）： 394-403.

［19］郭羽含， 劉秋月. 時(shí)空軌跡和復(fù)合收益的動(dòng)態(tài)上車點(diǎn)推薦［J］. 計(jì)算機(jī)科學(xué)與探索， 2022， 16（7）： 1611-1622. （Guo Yuhan， Liu Qiuyue. Dynamic pickup-point recommendation based on spatiotemporal trajectory and hybrid gain evaluation ［J］. Journal of Frontiers of Computer Science and Technology， 2022， 16（7）： 1611-1622.）

［20］郭羽含， 劉雨希， 劉秋月. 動(dòng)態(tài)約束與松弛分割的多目標(biāo)上車點(diǎn)推薦 ［J］. 計(jì)算機(jī)工程與應(yīng)用， 2023， 59（11）： 320-328. （Guo Yuhan， Liu Yuxi， Liu Qiuyue. Multi-objective pick-up point recommendation with dynamic constraint and relaxed segmentation ［J］. Computer Engineering and Applications， 2023， 59（11）： 320-328.）

［21］Zhang Wenbo， Ukkusuri S V. Share-a-Cab： scalable clustering taxi group ride stand from huge geolocation data ［J］. IEEE Access， 2021， 9： 9771-9776.

［22］Zhang Jing， Li Biao， Ye Xiucai， et al. Pick-up point recommendation strategy based on user incentive mechanism ［J］. PeerJ Computer Science， 2023，9（11）：e1692.

［23］Zhang Xiaojian， Zhou Zhengze， Xu Yiming， et al. Analyzing spatial heterogeneity of ridesourcing usage determinants using explainable machine learning ［J］. Journal of Transport Geography， 2024， 114（1）：103782.

［24］Nickkar A， Lee Y J， Meskar M. Developing an optimal peer-to-peer ride-matching problem algorithm with ride transfers ［J］. Transportation Research Record， 2022， 2676（11）： 124-136.

［25］Vega-Gonzalo M， Aguilera-García á， Gomez J， et al. Traditional taxi， e-hailing or ride-hailing？ A GSEM approach to exploring service adoption patterns ［J］. Transportation， 2024，51（8）： 1239-1278.

［26］Hou Yi， Garikapati V， Weigl D， et al. Factors influencing willingness to pool in ride-hailing trips ［J］. Transportation Research Record， 2020， 2674（5）： 419-429.

［27］Naumov S， Keith D. Optimizing the economic and environmental bene-fits of ride-hailing and pooling ［J］. Production and Operations Management， 2022， 32（3）： 904-929.

［28］Wang Wensi， Yu Bin， Fang Ke， et al. Causal effect of metro operation on regional resident mobility considering zone-based trip time relia-bility ［J］. Tunnelling and Underground Space Technology， 2023， 135（5）： 105041.

［29］潘志宏， 萬智萍， 謝海明. 跨平臺(tái)框架下基于移動(dòng)感知的智慧公交應(yīng)用研究 ［J］. 計(jì)算機(jī)工程與應(yīng)用， 2018， 54（19）： 243-247， 260. （Pan Zhihong， Wan Zhiping， Xie Haiming. Research on intelligent public transport application based on mobile sensing in cross platform framework ［J］. Computer Engineering and Applications， 2018， 54（19）： 243-247， 260.）

［30］高文超， 李國良， 塔娜. 路網(wǎng)匹配算法綜述 ［J］. 軟件學(xué)報(bào)， 2018， 29（2）： 225-250. （Gao Wenchao， Li Guoliang， Ta Na. Survey of map matching algorithms ［J］. Journal of Software， 2018， 29（2）： 225-250.）

［31］李志超， 王艷東， 賈若霖. 基于多因子幾何匹配的AI提取路網(wǎng)屬性信息重建方法 ［J］. 計(jì)算機(jī)應(yīng)用研究， 2021， 38（12）： 3688-3691， 3696. （Li Zhichao， Wang Yandong， Jia Ruolin. Attribute information reconstruction method of road network extracted by AI based on multi-factor geometric matching ［J］. Application Research of Computers， 2021， 38（12）： 3688-3691， 3696.）

［32］周杰英， 賀鵬飛， 邱榮發(fā)， 等. 融合隨機(jī)森林和梯度提升樹的入侵檢測研究 ［J］. 軟件學(xué)報(bào)， 2021， 32（10）： 3254-3265. （Zhou Jieying， He Pengfei， Qiu Rongfa， et al. Research on intrusion detection based on random forest and gradient boosting tree ［J］. Journal of Software， 2021， 32（10）： 3254-3265.）

［33］崔展齊， 謝瑞麟， 陳翔， 等. DeepRanger： 覆蓋制導(dǎo)的深度森林測試方法 ［J］. 軟件學(xué)報(bào)， 2023， 34（5）： 2251-2267. （Cui Zhanqi， Xie Ruilin， Chen Xiang， et al. DeepRanger： coverage-guided deep forest testing approach ［J］. Journal of Software， 2023， 34（5）： 2251-2267.）

［34］Liu Jiahao， Jin Hanxin， Qiang Lei， et al. Hybrid two-phase task allocation for mobile crowd sensing ［J］. Computer Engineering， 2022， 48（3）： 139-145.

［35］李曉會(huì)， 董紅斌. 基于E-CARGO模型的共乘出行匹配建模與優(yōu)化方法［J］. 計(jì)算機(jī)應(yīng)用， 2022， 42（3）： 778-782. （Li Xiaohui， Dong Hongbin. Modeling and optimization method of ride-sharing matching based on E-CARGO model ［J］. Journal of Computer Applications， 2022， 42（3）： 778-782.）

［36］王子慧， 任寧寧， 周毅， 等. 優(yōu)化多層次分析法的影響因素績效評價(jià)模型 ［J］. 計(jì)算機(jī)工程與設(shè)計(jì)， 2023， 44（7）： 2039-2046. （Wang Zihui， Ren Ningning， Zhou Yi， et al. Optimizing perfor-mance evaluation model of influencing factors of AHP ［J］. Computer Engineering and Design， 2023， 44（7）： 2039-2046.）

［37］夏英， 石梔琦. 面向交通流量預(yù)測的多頭注意力時(shí)空卷積圖網(wǎng)絡(luò)模型 ［J］. 計(jì)算機(jī)應(yīng)用研究， 2023， 40（3）： 766-770. （Xia Ying， Shi Zhiqi. Multi-head attention spatio-temporal convolutional graph network for traffic flow prediction ［J］. Application Research of Computers， 2023， 40（3）： 766-770.）

［38］Gallo F， Sacco N， Corman F. Network-wide public transport occupancy prediction framework with multiple line interactions ［J］. IEEE Open Journal of Intelligent Transportation Systems， 2023， 4： 815-832.

［39］Sun Dongxian， Guo Hongwei， Wang Wuhong. Vehicle trajectory prediction based on multivariate interaction modeling［J］. IEEE Access， 2023， 11： 131639-131650.