基于時空預測的多策略網約車調度算法

摘 要：準確預測網約車訂單需求與實施高效車輛調度策略，對于提升運營效率、降低成本和保證服務質量至關重要，是優化資源配置、增強乘客滿意度的關鍵途徑。然而，現存研究在模型構建上往往側重單一維度分析，調度算法的求解效率及解空間探索能力有待提升，限制了對復雜出行場景的適應性和解決方案的全面性。針對上述問題，構建了時空融合圖卷積預測模型，通過集成注意力機制，深度挖掘并利用時空維度綜合信息，準確捕捉影響訂單需求的隱含特征；同時設計了多策略解搜索算法，基于A*算法生成的代價矩陣選用多樣化解搜索策略進行求解，增強了算法在復雜情境下的收斂性與求解質量?；诖罅空鎸嵕W約車數據的實驗結果表明，相較于對比模型，所提預測模型MAE平均提升為1.87%，RMSE平均提升為1.92%。多策略解搜索算法較之對比算法，在最優解數量、解超體積以及解間距上平均優化提升率分別為13.88%、 32.48%、 17.61%，求解效率平均提升21.13%。

關鍵詞：需求預測；多目標優化；車輛調度；交通運輸；可行解搜索

中圖分類號：TP18;TP399"" 文獻標志碼：A""" 文章編號：1001-3695（2025）04-009-1034-10

doi： 10.19734/j.issn.1001-3695.2024.09.0339

Multi-strategy ride-hailing dispatching algorithm based on spatio-temporal prediction

Guo Yuhan， Qian Yiyang， Qian Yaguan

（School of Science， Zhejiang University of Science amp; Technology， Hangzhou 310012， China）

Abstract：Accurately predicting ride-hailing order demand and implementing efficient vehicle scheduling strategies are critical for improving operational efficiency， reducing costs， and ensuring service quality. Existing studies often focus on single-dimensional analysis in model construction， and scheduling algorithms exhibit limited efficiency and solution space exploration. To address these issues， this paper developed a spatiotemporal graph convolutional prediction model to integrate attention mechanisms， enabling deep exploration and utilization of spatiotemporal information to capture latent features affecting order demand. Additionally， it designed a multi-strategy solution search algorithm to employ diverse search strategies based on a cost matrix generated by the A* algorithm. This approach enhanced the algorithm’s convergence and solution quality in complex scenarios. Experimental results on large-scale real-world ride-hailing datasets demonstrate that the proposed prediction model achieves an average improvement of 1.87% in MAE and 1.92% in RMSE compared to baseline models. The multi-strategy solution search algorithm outperforms comparison algorithms， achieving average improvements of 13.88% in the number of feasible solutions， 32.48% in hypervolume， and 17.61% in spacing. Furthermore， the algorithm’s computational efficiency is enhanced by an average of 21.13%.

Key words：demand-forecasting; multi-objective optimization; vehicle-scheduling; transportation; solution search

0 引言

借助互聯網技術支持的服務平臺，網約車服務成功整合供需資源，打造出超越傳統出租車的高效司乘匹配模式，顯著提升了出行體驗。但現有體系中，信息分析的不全面性與全局調度策略的缺失已成為制約因素，導致車輛部署難以精準適配乘客的實際出行需求。這一失衡不僅延長了乘客等待時間、削弱了對平臺的滿意度，同時也加劇了車輛空駛情況，直接影響到司機收入水平。若網約車平臺能前瞻性地掌握并分析不同時域和區域內的需求分布趨勢并提升其車輛調度效率，則可在全局范圍內促成供需均衡，提升服務效率與質量，實現乘客、司機與平臺的共贏。為構建高效的網約車調度體系，精確的需求預測模型與高效的車輛調度方法需同時實現，其中需求預測本質上可視為一個回歸問題，解決此類問題通常通過統計回歸、機器學習、深度學習三類方法。在統計回歸方法中，Moreira-Matias等人［1］通過將信息聚合成直方圖時間序列，并結合三種不同的時間序列預測技術，成功實現了需求預測。在機器學習領域，Hao等人［2］提出了一種基于差分進化算法和徑向基函數的融合算法。Jiang等人［3］以網約車短期需求預測為目標，提出了一種基于最小二乘向量機的預測方法。雖然這些單一的機器學習模型在一定程度上提升了預測性能，但它們仍存在誤差和過擬合問題。通過集成學習方法，可有效提升模型的準確性和魯棒性。例如Zhang等人［4］ 設計了一種基于LGBM（light gradient boosting machine）的預測框架用于交通流量預測，而Lei等人［5］則采用了XGBoost方法預測快速變化的交通網絡演變。Khan等人［6］ 則提出了一種基于袋裝集成（bagging ensemble）的交通流量預測方案，顯著減少了預測誤差和提升模型穩健性。Zhao等人［7］通過采用混合方法，將XGBoost、CatBoost等多種模型集成，以減少目標問題的復雜性。盡管這些機器學習模型在處理預測任務時表現出良好的性能，并且具備較高的可解釋性，但它們仍需依賴繁雜的特征工程，并且在處理高維復雜數據時仍面臨挑戰。尤其是面對特征之間復雜的非線性隱含關系時，這些模型的表現往往受到限制。深度學習通過構建深層神經網絡，從原始數據中學習特征，近年來已被廣泛應用于問題建模與預測過程。例如高俊杰等人［8］從時間維度出發，綜合多種因素影響，應用LSTM模型對車輛需求進行預測。杜圣東等人［9］則指出經典的深度學習模型在捕獲交通流多通道、多變量序列數據中的時空依賴性特征時表現不佳，由此提出了一種結合LSTM的時空注意力機制的預測方法，可自適應地捕捉特征之間的依賴關系。Shu等人［10］提出了一種基于改進門遞歸單元（GRU）的神經網絡模型，用于短期交通的交通流預測。在空間特征處理中，Ma等人［11］通過將交通流量映射到二維地理空間，并利用卷積神經網絡進行空間特征提取，以預測未來的交通狀況。然而，復雜的交通模式、路網結構以及動態變化的交通流量等因素導致傳統卷積方法難以獲得較好的效果。為解決該問題，Zheng等人［12］提出了一種GMAN（graph multi-attention network）模型，采用編碼器-解碼器架構，結合空間和時間注意力機制來建模復雜的時空依賴關系，從而有效提升了長時間預測的準確性。此外，張興銳等人［13］提出了一種基于圖卷積神經網絡（GCN）和組合門控卷積（GLU）的模型用于提升預測客流量的準確性。

現有文獻表明，通過對數據中的時空特征進行解耦處理，對需求預測取得一定成效。然而時間與空間維度各自的隱含特征對預測結果的影響存在顯著差異，現有研究往往未能充分捕捉這兩者之間復雜的耦合關系。如果僅對時空維度進行獨立建模，而忽視它們之間的相互作用，則無法全面、準確地揭示時空特征在不同城市、不同規模下的動態變化和潛在依賴性。因此，為實現高精度的需求預測，需充分考慮時空耦合性，特別是在面對復雜的城市交通環境時，預測的準確性和魯棒性會受到顯著影響。車輛調度問題（vehicle dispatching problem， VDP）是智能交通系統中的重要研究方向，通常涉及調度模型和求解算法兩部分內容。調度模型通過建立優化目標，例如車輛利用率、運營成本、乘客服務質量等，而調度求解算法則旨在對調度模型進行高效求解或提高可行解質量。例如Long等人［14］通過注重減少總持有成本、旅行成本等因素，解決了生產調度和車輛路徑問題。段曉紅等人［15］設計了一種蝙蝠算法，以準確選取最短時間與最短路徑為目標。吳凡等人［16］以運輸成本最低、時間懲罰最少等因素為優化目標建立了一類多目標調度優化模型，并使用了一種改進的遺傳算法提升優化性能。李婷婷等人［17］以優化車輛調度路徑為目標提出了一種改進的蟻群算法。Sadrani等人［18］提出一種優先考慮最小化乘客等待時間的算法。Gkiotsalitis等人［19］提出了一種不僅考慮車輛運營成本還考慮乘客等待時間的調度算法。同時，針對模型的求解算法也十分重要，強化學習因其在動態和復雜環境中，可通過自適應學習策略優化調度效果，成為了解決車輛調度問題的重要手段。例如Holler等人［20］提出了一種基于深度強化學習的調度算法，以解決訂單調度和在線車隊管理的問題。Li等人［21］使用馬爾可夫決策過程（Markov decision process，MDP）制定車輛調度決策，并引入基于強化學習的調度方法。然而強化學習方法僅在處理小規模問題時表現出高效性，在處理大規模車輛調度問題時，特別是在復雜和多維的現實世界場景中，其求解效率易受到影響。為進一步提升調度策略，啟發式算法與元啟發式算法成為了另一種解決手段。例如Lunardi等人［22］提出了一種局部搜索策略和元啟發式方法，大幅提升了求解效率和結果。Zarouk等人［23］則提出了一種基于遺傳算法和模擬退火的混合元啟發式求解方法，優化了車輛調度的決策過程。Johnsen等人［24］提出了一種自適應可變鄰域搜索啟發式算法（adaptive variable neighborhood search， AVNS），以用于解決農村地區相關的車輛優化調度問題。

現有研究在車輛調度問題上雖已取得一定進展，但仍存在一些不足。首先，大部分文獻提出的數學模型集中于優化特定指標，如出行成本和乘客等待時間，但對司機收入以及全局供需平衡的關注相對較少，這限制了調度策略的全面性和實用性。其次由于算法復雜性和訓練周期長等因素，許多研究難以在有限的計算時間內提供有效的調度解決方案，特別是在面對大規模、動態的交通環境時。因此，針對這些不足，首先需構建更全面的數學模型，將司機收入、全局供需平衡等因素引入模型，以此提升模型的全面性和實用性。此外，車輛調度為實時任務，需在極短的時間內完成算法求解并提供結果反饋，因此對算法的求解效率與求解質量提出了更高的要求。

綜合需求預測與車輛調度相關文獻，目前網約車調度研究仍面臨以下幾方面的挑戰，這些問題在實際應用中限制了網約車調度體系的效率和可靠性，亟需進一步深入探討和改進：

a）需求預測。大量現有研究僅考慮時間或空間某一單一維度，未能充分挖掘時空數據中的隱含特征。這種局限性導致了預測模型難以準確捕獲需求在時間和空間上的復雜變化，尤其在面對動態、復雜的交通場景時表現不佳。預測偏差將顯著影響調度決策的準確性，從而降低整體調度效率。

b）數學模型。當前許多調度數學模型往往集中于優化某些特定目標，如乘客等待時間、司機收入以及車輛空駛距離等，常常以犧牲司機或乘客一方的利益為代價。此類數學模型缺乏多角度綜合考慮，易導致全局供需失衡，使得調度結果難以令多方滿意。

c）求解算法。在大規模、復雜的交通場景下，現有求解算法往往面臨學習周期過長、可行解較少等問題。特別在現實動態的交通應用場景中，調度方案需能夠快速響應需求變化，但由于現有算法的學習周期過長且可行解數量有限，難以實現快速優化，限制了其實用性。

針對上述問題，本文分別對應預測模型、數學模型和求解算法三個方面，針對性地進行探討與改進，主要貢獻如下：

a）設計了一種時空雙維度融合的預測模型，通過捕捉不同節點在不同時間上的隱含特征，不僅能揭示過去數據對未來數據的時序影響，還可有效建模不同節點之間的空間動態聯系。該方法通過綜合利用時空數據，克服了單一維度建模帶來的預測偏差，提升了預測結果在復雜交通場景中的準確性。

b）構建了一個更為全面的調度數學模型，以最大化司乘雙方的總收益為目標。該模型綜合考慮了多項關鍵因素，包括車輛行駛路程、司機收入、全局供需平衡以及乘客等待時間四項優化指標，從而實現了更均衡的調度結果。此數學模型克服了現有數學模型對于優化目標關注的局限性，確保了調度結果在實際應用中更具全面性和合理性。

c）提出了一種多策略解搜索算法，在求解過程中根據當前求解狀態動態使用不同的搜索算子。利用隨機策略和多階段策略對求解狀態進行優化，確保求解過程中求解效率與求解質量達到動態平衡。該方法克服了現有調度算法在大規模復雜場景下的求解效率低與可行解數量較少的限制，使求解更靈活高效。

1 問題定義與建模

1.1 相關定義

定義1 服務區域。設有給定地理區域空間S，其經度最大與最小值分別為lngmax與lngmin，緯度最大與最小值分別為latmax與latmin，將該空間分割為p×q個服務區域sij，如式（1）所示，其中每個服務區域長寬分別為lijlng=（lngmax－lngmin）/p與lijlat=（latmax－latmin）/q。

上述約束中，式（9）～（11）分別表示成本、收入與等待時間。式（9）中N（rvn－sij）表示在調度路徑rvn－sij上經過的服務區域數量。式（12）表示確保派往服務區域sij的車輛數量不多于該區域需求量，避免車輛派送多余而形成擁堵與供應浪費。式（13）表示確保所有車輛都能被派往一個區域并且確保只被派往這一區域，可避免造成資源空缺或冗余。式（14）表示確保調度過程中參與調度的每一輛車都處于空閑狀態，且優先考慮未參與調度的車輛，最大化利用車輛資源。

本文模型屬多目標混合整數規劃問題（multi-objective mixed integer programming problem，MOMIPP），包含四個優化目標，且不同目標之間存在相互制約關系，無法通過單一解同時達到最優。因此需探索帕累托最優解，以實現不同優化目標的最大化。此外，在最壞情況下，混合整數規劃計算的計算復雜性隨著問題規模的增加而顯著上升，使得在多項式時間內找到精確解變得困難。同時，車輛調度過程的實時性要求在匹配過程中實施快速決策，這對模型的求解效率提出了較高的要求。

2 基于預測的車輛調度算法

針對問題與模型特點，本章首先提出了一種集成注意力機制的圖神經網絡模型（圖1），旨在深度挖掘并利用時空維度隱含特征。其次，介紹了一種多策略驅動解搜索算法，利用A*算法生成車輛與區域匹配的代價矩陣。基于該代價矩陣，采用多策略靈活使用不同解搜索算子進行可行解搜索。

2.1 時空融合圖卷積模型

預測訂單需求量的過程伴隨著數據的不確定性和動態性，隨著空間與時間的變化，時空雙維度隱含特征往往會影響訂單需求量的波動。因此精確捕捉時空雙維度內在隱含特征對于提高預測準確率至關重要。

注意力機制通過動態學習輸入數據各時間窗或節點之間的關聯程度，可使模型選擇性地關注與當前預測任務最相關的信息，從而更有效地捕捉不同時刻和不同空間的需求變化規律。空間注意力用于捕捉不同節點之間的復雜空間相關性，而時間注意力則用于揭示不同時間窗之間的動態時間相關性。鑒于訂單需求分布的變化具有周期性和規律性，于模型中創建了三個具有相同結構的獨立通道，分別針對歷史數據中小時周期、日周期和周周期進行訓練。沿時間軸分別以小時、天、周三種不同頻率進行采樣，得到Th，Td，Tw三個類型時間片段，采樣示例如圖2所示，時間段定義如式（15）～（17）所示。

2.2 多策略解搜索算法

具有多個目標函數的數學模型求解帕累托最優需花費大量計算時間和資源，為解決此局限性，提出了一種多策略解搜索算法，以高效解決車輛與服務區域的匹配問題。該算法首先利用A*算法［28］計算各車輛與區域匹配的代價值，形成代價矩陣，該矩陣包括路程、司機收入及乘客等待時間三個因素?；诖鷥r矩陣，使用解搜索算法對車輛與區域的匹配進行求解，實現多目標最優調度方案。

2.2.1 車輛-區域代價矩陣獲取

為在車輛匹配中提供精確的路徑規劃和代價評估，通過采用A*算法計算每輛車前往各目標區域的最優路徑。該算法不僅可找到最短路徑，還可結合需求預測數據，綜合考慮多個因素生成用于調度決策的代價矩陣。具體而言，A*算法通過評估初始服務區域至目標服務區域sij的歐氏距離Gijtk、曼哈頓距離Hijtk、車流量ζijtk以及調度需求量θijtk，動態計算每個區域的優先級P，從而確定下一步的最優移動區域。優先級P計算過程如式（29）所示。

2.2.2 初始解生成

對車輛區域匹配問題求解時首先需要一組初始解，且該組解通常是隨機的。但由于初始解的設置對后續迭代求解速度以及可行解的質量有顯著影響，所以本文在生成初始解時基于代價矩陣Va，采用了一種價值優先策略來生成初始解，流程如下所示。

a）初始化維度為［n，（i×j）］的調度矩陣DM，其中n表示待調度車輛數量，i×j表示調度區域的數量，同時初始化所有元素DMij為0。

b）按行遍歷價值矩陣Va，獲取當前行所有數值Varow，并對其進行排序，選取當前最大值max（Varow），將調度矩陣DM對應位置元素設置為1。接著根據式（13）（14）判斷此時調度矩陣DM是否滿足約束，若滿足則對下一行進行重復操作；否則將該元素重置為0，并選擇下一價值最大值再次進行判斷。

c）重復上述過程，直至調度矩陣DM中所有行或列滿足約束。此時，生成的初始解已具備較好的可行性，為后續的迭代優化提供了良好基礎。

算法1 初始解生成偽代碼

輸入：代價矩陣 Va。

輸出：調度矩陣 DM。

初始化調度矩陣 DM，維度與Va相同（假設為［m，n］，以下同假設），所有元素初始化為 0

對于i 從1到m：

獲取當前行Va［i］的所有元素值，并按從大到小排序

對于排序后的每個元素 j：

將DMij設為 1

若DM滿足約束條件：

跳出當前行循環，處理下一行 i+1

若不滿足約束條件：

將DMij重置為 0，繼續選擇下一個代價值

返回調度矩陣 DM

算法1時間復雜度可計算為O（m×n）

2.2.3 迭代解搜索

算法性能由解集的覆蓋性和收斂性進行評估。較高的覆蓋性意味著算法可在解空間內進行更廣泛的搜索，從而有效避免求解陷入局部最優，但廣泛的搜索會導致求解效率不可避免地降低。另一方面，較高的收斂性表明算法可在較短時間內快速收斂，但也可能增加陷入局部最優的風險。

針對上述特性，為平衡覆蓋性與收斂性，設計了三種不同的解搜索算子，并結合兩種迭代解搜索策略，確保在不同迭代階段既能保證求解速度又能維持可行解質量。

1）解搜索算子 對于解向量Sa，通過交換其中元素si與sj的值，將其轉換為一個新解Sb，將此定義為解交換操作（solution exchange operation，SEO）。

Sa（s0，s1，…，si，…，sj，…）SEO（i，j）Sb（s0，s1，…，sj，…，si，…）（32）

a）隨機交換算子（random solution exchange operation， RSEO）。

RSEO表示為在解空間中向隨機方向執行一次SEO操作。具體步驟為：首先隨機選取調度矩陣DM某一行DMrow，選定其中的一個匹配元素dij，然后隨機選定同一行另一元素dik進行數值互換。隨機交換算子關鍵在于隨機性，這確保搜索過程不會因搜索方向固定而陷入局部最優，從而在更廣泛的解空間中搜索最優解，但同時會不可避免導致收斂性較差。該算子的時間復雜度為O（n）。

Sa（s0，s1，…，si，…，sj，…）RSEO（i，j）random choose（i，j）

Sb（s0，s1，…，sj，…，si，…）

（33）

算法2 RSEO偽代碼

輸入： 調度矩陣DMold。

輸出：調度矩陣DMnew。

隨機選擇并遍歷調度矩陣DMold的某一行i：

在行 i 中，隨機選擇一個匹配元素DMoldij

在行 i 中，隨機選擇另一個不同的元素DMoldik

交換DMoldij和DMoldik的值

返回更新后的調度矩陣DMnew

算法2的時間復雜度為O（n）。

b）價值增益算子（value increase operation，VIO）。價值增益算子是一種在解空間中通過滿足特定約束條件方式進行的解交換操作 （SEO）。具體步驟如下：首先隨機選取調度矩陣DM某一行中的匹配元素DMij，然后在該行中隨機選定另一元素DMik，要求保證該元素在對應代價矩陣中的代價值大于DMij的代價值。接著，將元素DMij與DMik進行數值互換。若交換后矩陣的整體價值大于交換之前且滿足約束限制，則保留該交換結果；否則放棄當前操作，對下一元素進行相同操作。價值增益算子關鍵在于引入約束條件，確保搜索過程沿著滿足條件的方向前進，從而實現快速收斂。雖然這一方式加速了收斂，但由于引入了價值約束，解覆蓋性會有所下降。

Sa（s0，s1，…，si，…，sj，…）VIO（i，j）choose（valueilt;valuej）

Sb（s0，s1，…，sj，…，si，…）

（34）

算法3 VIO算子偽代碼

輸入：調度矩陣DMold，代價矩陣Va。

輸出：調度矩陣DMnew。

隨機選擇并遍歷調度矩陣DMold的一行 i：

在行 i 中，隨機選擇一個匹配元素 DMoldij

在行 i 中，隨機選擇另一個元素DMoldik，要求 Vaikgt;Vaij

交換DMoldij和DMoldik的值

計算交換后的整體價值，并檢查是否滿足約束條件

如果滿足條件，保留交換結果；否則，將DMoldij和DMoldik的值重置

返回更新后的調度矩陣DMnew

算法3復雜度為O（m+n）。

c）偏向性隨機算子（biased roulette operation，BRO）。偏向性隨機算子在SEO操作前引入了偏向性輪盤賭策略［29］，以平衡解搜索的收斂性和覆蓋性。具體操作為：首先基于代價矩陣Va，按行遍歷獲取當前行每個元素的價值vavn－sij，并計算每個元素的價值占比pvn－sij，按價值占比分配概率權重wvn－sij。通過加權后的價值占比，計算累計占比Cavn－sij。接著，生成［0，1］的隨機數Ra，判斷該隨機數Ra落入累計占比區域psum的位置，選擇對應元素dselcet。最后，選定該元素dselcet與初始選定元素doriginal進行一次SEO操作。該策略通過結合傾向性與隨機性，使解在保證收斂性的同時又具有一定解覆蓋性。

Sa（s0，s1，…，si，…，sj，…）BRO（i，j）choose（Ra∈psum）

Sb（s0，s1，…，sj，…，si，…）

（35）

算法4 BRO算子偽代碼

輸入：調度矩陣DMold，價值矩陣Va。

輸出：調度矩陣DMnew。

對于調度矩陣DMold的每一行 i：

獲取該行中所有元素對應的價值vaij

計算每個元素的價值占比

pvn－sij=vaij∑nj=0vaij

pvn－sij=pvn－sij（1+pvn－sij）

基于pvn－sij計算累計占比Cavn－sij，生成一個隨機數Ra，介于［0，1］

判斷隨機數Ra所落入的累計占比區間，選擇相應的元素DMoldij

將選定的DMoldij與初始選定的元素DMoldik進行解交換操作

返回更新后的調度矩陣DMnew

算法4的復雜度計算為O（m×n）。

2）解搜索策略 理想的解搜索策略應在不同求解階段利用不同算子的特性，以優化求解過程，使算法的覆蓋性與收斂性均能保持在較高水平。為此，設計了兩種解搜索策略，旨在提高求解效率與質量，實現覆蓋性與收斂性的動態平衡。

a）隨機策略。隨機策略（圖3）通過隨機交替使用三種解搜索算子實現求解迭代，其中隨機交換算子保證求解過程的解覆蓋性，價值增益算子則增強了求解過程的收斂性，偏向性隨機算子則在收斂性與解覆蓋性之間實現了良好的平衡。該策略的時間復雜度可表示為O（m×n）。

b）多階段策略。多階段策略（圖4）通過比較每次迭代產生的解，以此判斷當前所處求解階段。設定迭代窗口大小L、高低閾值δh與δl，當過去L次迭代結果的均值與最近一次迭代結果的差值大于δh，判定當前處于收斂期；當差值小于δl，則判定陷入局部最優期；其余情況則判定進入平穩期。當判定處于收斂期時，選擇使用價值增益算子加速解收斂；若陷入局部最優期時，則使用隨機交換算子來跳出局部最優；當判定位于平穩期時，則使用偏向性隨機算子，結合隨機性與傾向性進行進一步搜索。該策略時間復雜度取決于迭代次數IT以及迭代中計算量最大的算子的時間復雜度Max（O），因此時間復雜度可表示為O（IT×m×n）。

2.2.4 解排序與選擇

經迭代操作后，將得到若干解，記為解集Siter={S1，S2，…，Sn}，從解集中選取可行解并進行排序操作。定義不同解之間的支配關系為：若解Si在所有目標上的結果都至少與解Sj一樣優異，且在至少一個目標上比解Sj更優，則稱解Sj受解Si支配。

Si→fi（C，－I，D，T）≥fj（C，－I，D，T）←Sj" SidominateSj

（36）

基于支配關系，將Siter中每個解按被支配次數進行支配等級排序，定義解支配等級Dom為

Domn=num_count（Sn be dominanted ）

（37）

支配等級越低，意味著該解被支配的次數越少，因此該解的優先級越高。此外，為進一步衡量同一支配等級下不同解的優劣性，定義杰出度（outstanding-degree，OD）作為解評估指標，由式（39）表示：

ODn=∑f∈［f1，f2，f3，f4］ωif（i）

（38）

其中：f（i）表示解Si對應在四個優化目標函數上各自對應的值；ωi表示不同優化目標的權重。最后從所有可行解中優先選取支配等級較低的解，并對于同一支配等級下的解，選取OD值較小的解作為更優解，以此選取解，直至滿足需求。

3 實驗與分析

本章介紹不同模型在三個真實數據集上進行的對比實驗結果，以此評估預測模型的性能與調度策略的有效性。實驗中的數據集由滴滴出行提供，為成都、西安和?？谌齻€主要城市的真實在線網約車訂單。所有實驗均在環境為Python 3.10，配備有CPU 13th Gen Intel CoreTM i5-13400F 2.50 GHz 系統為Windows 10的計算機上實現。

3.1 預測模型的評價

3.1.1 效果評價

本節通過對比平均絕對誤差（MAE）、均方根誤差（RMSE）以此評估模型的性能優劣。將TS-AGCN與其他12種模型進行對比，包括統計回歸、機器學習和深度學習方法，其中統計回歸模型包括線性回歸（LR）、ARIMA，向量自回歸（VAR）；機器學習模型包括LGBM［5］、XGBoost和CatBoost；深度學習模型包括Conv-LSTM、CACRNN［30］、GRU［31］、MGSTGCN［32］、STGCN［33］、DSTGCN［34］。實驗對比結果具體如表1所示，圖5展示上述指標在三個數據集上的平均差異。由表1可知，TS-AGCN在所有指標上均優于其他模型，具體而言，在成都數據集中TS-AGCN MAE得分為3.25，RMSE得分為5.13；在西安數據集中MAE得分為2.39，RMSE得分為4.32；最后在?？跀祿蠺S-AGCN MAE得分為1.77，RMSE為6.51。較之其余對比模型，TS-AGCN在三個數據集上預測準確度均有所提升，其中MAE較之其余最優模型提升分別為122%、165%和275%；RMSE提升為248%、137%和182%。

通過分析同一時間窗下不同子區域需求量分布差異，可更直觀地驗證模型的有效性。圖6為兩個時間窗下區域真實訂單需求量與模型預測值熱力圖對比，圖中陰影顏色越深表示該地區需求量越大。此外，左側為真實數據，右側為模型預測值。通過熱力圖的比較可看出，預測值和真實值之間存在高度一致性，充分體現了模型的預測準確性。

3.1.2 敏感性分析

本節以西安數據集為例，針對預測模型的結構和參數進行了敏感性分析。首先通過調整不同時間分量（小時/日/周）的輸入比例，評估模型的預測性能。如圖7所示，當小時分量輸入增加時，模型MAE、RMSE得分都有所優化，顯示出更高的預測準確性；當天、周分量增加時，模型預測性能出現一定波動，預測精確度出現下降。這一結果表明，短時間維度（小時級別）的數據在需求預測中可更好地捕捉訂單需求的動態變化，而較長時間周期的數據可能會引入較大的不確定性，導致模型在這些時間尺度上的預測精度下降。

接著通過調整不同的鄰居節點階數來評估模型的表現。如圖8所示，當鄰居節點階數增加至4時，模型性能呈現逐步提升，表現出更高的預測精度。但當階數進一步增加時，模型性能開始出現波動。這一結果表明，適當的鄰居節點擴展有助于捕捉更廣泛的空間相關性，從而提升模型的預測性能。

最后對模型進行長短期預測性能評估。由圖9可見，不同模型對于未來時間窗客戶需求的預測整體存在波動，但整體可較好的擬合需求波動趨勢。相比之下，TS-AGCN雖然在多步預測中也存在波動，但預測性能仍優于其余對比模型，表明該方法仍可較好地適應長短期預測任務。

3.2 多策略解搜索算法的評價

本節介紹了為評估雙模式混合調度算法所做的實驗，選取不同實例進行驗證。在進行車輛調度時，所有服務車輛可被自由調度至任意一個地區，且只和該地區進行匹配，當車輛處于調度過程中不對其進行新的匹配操作。

首先，圖10分別可視化了兩個不同時間窗下，進行調度前后的車輛分布對比。圖中顏色較淺的點代表調度后的車輛分布，顏色較深的代表調度前的車輛分布。可以看出，在進行了車輛調度操作后，原本較為分散的車輛被合理地分配到了各個有需求的服務區。圖11展示了求解過程中優化目標的收斂以及可行解數量隨迭代次數的變化。從圖11中可看出，通過多階段策略進行求解，優化目標值在20次迭代左右就已可快速收斂至最優值。此外，在相對較少的迭代輪次內，該解搜索算法也可快速地得出足夠的可行解。

表2展示了兩種搜索策略在最終優化目標上的最佳結果，圖12、13分別展示了這兩種策略生成的可行解分布。

由圖可知，兩種策略均在解空間內較為全面地搜索到了不同的最優解分布，顯示出了良好的解空間覆蓋能力。根據解的分布情況，可發現帕累托最優解的明顯特征，例如隨著收入的增加，旅行距離和乘客等待時間等其余目標對應值均會相應增加。這表明當一個目標靠近其最優方向時，其他目標通常會不可避免地遠離其最優值。例如，當司機收入提高到80時，乘客等待時間相應增加至85，這反映了實際情況中，司機收入增加往往會因其主觀性，促使司機選擇高收入區域提供服務，導致車輛資源向特定區域集中，進而使其余地區的乘客等待時間不可避免地增加。同時，由于可服務車輛數量以及最優方案數量的有限性，導致全局供需差的值在最終的帕累托最優集群內保持不變。這也同時符合實際情況中，在有限的資源條件下，即使進行最優方案搜索，也難以完全平衡所有區域的供需。

接著將該解搜索算法與NSGA-Ⅲ［35］、迭代的Kuhn-Munkres（iterative Kuhn-Munkres，IKM［28］）以及AVNS［24］進行對比，主要通過最優解數量（number of feasible solutions， NFS）、超體積（hypervolume，HV）［36］以及間距（spacing，SP）［37］進行性能評估對比。其中：NS代表所得可行解數量，可有效衡量解空間覆蓋率;HV通過計算非支配解集與參考點圍成的目標空間體積來評估解的多樣性;SP通過計算每個解與其他解之間的最小距離的標準差來評估解的均勻性。

如表3所示，多策略解搜索算法相較于對比算法可獲取更多可行解，并且在解空間覆蓋率以及解均勻性上均表現出良好的性能。具體而言，多策略解搜索算法在實驗所提的8個實例中，NFS平均提升率分別為25.88%、8.24%以及7.51%； HV平均提升率分別為68.54%、7.92%以及20.97%； SP平均提升率分別為47.17%、1.77%以及3.82%。

此外，選擇8個不同數據規模的實例，基于求解時長對不同算法求解性能進行了對比。如表4所示，在對比實驗中解搜索算法在各個實例上的求解時間均優于其余對比算法。具體而言，實驗中解搜索算法較之其余算法，求解時長平均優化提升為12.65%、22.41%以及28.29%。

3.3 實際應用建議

本文TS-AGCN在不同城市的客戶需求預測任務中均表現出了良好的性能，具有較強的跨城市推廣潛力。同時多策略解搜索算法經實驗結果證實，其在處理實時車輛調度的大規模多目標優化問題中具有高效的求解能力。在選擇最終的可行調度方案時，平臺方可根據業務需求，在可行解選擇時靈活設置權重，以此挑選更加符合實際需求的調度方案。此外，多策略解搜索算法結構簡易，僅需人為簡單地設置參數即可對實際問題進行求解，易于平臺在實際業務中的部署。接下來為一些可參考的建議，以便于企業與平臺方在實際運營管理中作出應對：

a）在不同的時間窗下，車輛的分布與調度方案差距較大，應及時根據不同時間窗下的車輛分布波動調整調度計劃。

b）靈活選取最佳調度方案。當預測模型預測某服務區域為高需求時，應在選擇最佳調度方案時，傾向于考慮全局車輛供需平衡和客戶等待時間的優先級，而在低需求時期，則傾向于考慮其余優化目標優先級。

c）平臺可以在實際應用中靈活更改算法中的不同參數與權重，以進一步提高算法在各種規模以及不同實例下的有效性與可行性。

4 結束語

本文首先提出了一種融合時空雙維度隱含特征的預測模型，并提出了一種多策略驅動的解搜索算法，利用不同解搜索策略靈活調用不同解搜索算子組合求解獲取帕累托最優解。實驗結果表明，本文使用的預測模型效果顯著優于前沿對比模型，可準確預測未來用戶訂單需求變化。此外，多策略驅動解搜索算法相較于對比算法，可為車輛調度問題提供更高質量的解，并在不同大小的實例上均可進行高效求解。

此外，對于需求預測，本文目前僅考慮單一訂單需求變化量，在未來的研究中擬考慮將更多數據引入模型，利用多模態模型進行求解，融合這些數據將有助于構建更加準確的預測模型，提高調度的精確度和可靠性。對于車輛調度，本文目前僅考慮傳統網約車的車輛區域匹配問題，而隨著電動車、自動駕駛汽車等多種類型網約車的普及，在未來研究中擬考慮構建協同調度模型，并引入更多優化目標，以擴展至更廣泛的匹配問題，增強車輛調度算法的泛化能力。

參考文獻：

［1］Moreira-Matias L， Gama J， Ferreira M，et al. Predicting taxi-passenger demand using streaming data ［J］. IEEE Trans on Intelligent Transportation Systems， 2013， 14（3）： 1393-1402.

［2］Hao Shurong， Zhang Mingming， Hou Anping. Short-term traffic flow forecast based on DE-RBF fusion model ［J］. Journal of Physics： Conference Series， 2021， 1910（1）： 012035.

［3］Jiang Peng， Huang Yibin， Liu Xiao. Intermittent demand forecasting for spare parts in the heavy-duty vehicle industry： a support vector machine model ［J］. International Journal of Production Research， 2021， 59（24）： 7423-7440.

［4］Zhang Yunchao， Chen Yanyan， Gu Xin， et al. A proactive crash risk prediction framework for lane-changing behavior incorporating indivi-dual driving styles［J］. Accident Analysis amp; Prevention， 2023， 188： 107072.

［5］Lei Weihua， Alves L G A， Amaral L A N. Forecasting the evolution of fast-changing transportation networks using machine learning ［J］. Nature Communications， 2022， 13： 4252.

［6］Khan N U， Ali S M， Maple C， et al. Traffic flow prediction： an intelligent scheme for forecasting traffic flow using air pollution data in smart cities with bagging ensemble ［J］. Sustainability， 2022， 14（7）： 4164.

［7］Zhao Yuexu， Deng Wei. Prediction in traffic accident duration based on heterogeneous ensemble learning ［J］. Applied Artificial Intelligence， 2022， 36（1）： 2018643.

［8］高俊杰， 崔曉敏， 趙鵬， 等. 基于需求預測的單向共享電動汽車車輛調度方法 ［J］. 大連理工大學學報， 2019， 59（6）： 648-655. （Gao Junjie， Cui Xiaomin， Zhao Peng， et al. Scheduling method for one-way electric car-sharing based on demand forecasting ［J］. Journal of Dalian University of Technology， 2019， 59（6）： 648-655.）

［9］杜圣東， 李天瑞， 楊燕， 等. 一種基于序列到序列時空注意力學習的交通流預測模型 ［J］. 計算機研究與發展， 2020， 57（8）： 1715-1728. （Du Shengdong， Li Tianrui， Yang Yan， et al. A sequence-to-sequence spatial-temporal attention learning model for urban traffic flow prediction ［J］. Journal of Computer Research and Development， 2020， 57（8）： 1715-1728.）

［10］Shu Wanneng， Cai Ken， Xiong N N. A short-term traffic flow prediction model based on an improved gate recurrent unit neural network ［J］. IEEE Trans on Intelligent Transportation Systems， 2022， 23（9）： 16654-16665.

［11］Ma Xiaolei， Dai Zhuang， He Zhengbing， et al. Learning traffic as images： a deep convolutional neural network for large-scale transportation network speed prediction ［J］. Sensors， 2017， 17（4）： 818.

［12］Zheng Chuanpan， Fan Xiaoliang， Wang Cheng， et al. GMAN： a graph multi-attention network for traffic prediction ［C］// Proc of AAAI Conference on Artificial Intelligence. Palo Alto， CA：AAAI Press， 2020： 1234-1241.

［13］張興銳， 劉暢， 陳哲， 等. 基于時空圖卷積網絡的機場地鐵短時客流預測 ［J］. 計算機工程與應用， 2023， 59（8）： 322-330. （Zhang Xingrui， Liu Chang， Chen Zhe， et al. Short-term passenger flow prediction of airport subway based on spatio-temporal graph convolutional network ［J］. Computer Engineering and Applications， 2023， 59（8）： 322-330.）

［14］Long Jianyu， Pardalos P M， Li Chuan. Level-based multi-objective particle swarm optimizer for integrated production scheduling and vehicle routing decision with inventory holding， delivery， and tardiness costs ［J］. International Journal of Production Research， 2022， 60（11）： 3319-3338.

［15］段曉紅， 吳家新， 周芷晴. 基于層次蝙蝠算法的應急車輛調度與交通疏散協同決策 ［J］. 交通運輸系統工程與信息， 2020， 20（2）： 157-165. （Duan Xiaohong， Wu Jiaxin， Zhou Zhiqing. Colla-borative decision-making of emergency vehicle scheduling and traffic evacuation based on bi-level bat algorithm ［J］. Journal of Transportation Systems Engineering and Information Technology， 2020， 20（2）： 157-165.）

［16］吳凡， 楊冰， 洪思. 基于變長基因型遺傳算法的多供應點應急物資調度優化 ［J］. 計算機應用研究， 2022， 39（4）： 1148-1154. （Wu Fan， Yang Bing， Hong Si. Scheduling optimization of emergency supplies with multi-supply points based on variable length genotype genetic algorithm ［J］. Application Research of Computers， 2022， 39（4）： 1148-1154.）

［17］李婷婷， 鄧社軍， 陸曹燁， 等. 一種基于改進蟻群算法的垃圾車輛低碳收運路徑優化方法 ［J］. 公路交通科技， 2023， 40（5）： 221-227， 246. （Li Tingting， Deng Shejun， Lu Caoye， et al. An improved ant colony algorithm based low-carbon collection path optimization method for waste vehicles ［J］. Journal of Highway and Transportation Research and Development， 2023， 40（5）： 221-227， 246.）

［18］Sadrani M， Tirachini A， Antoniou C. Vehicle dispatching plan for minimizing passenger waiting time in a corridor with buses of different sizes：model formulation and solution approaches ［J］. European Journal of Operational Research， 2022， 299（1）： 263-282.

［19］Gkiotsalitis K， Iliopoulou C， Kepaptsoglou K. An exact approach for the multi-depot electric bus scheduling problem with time windows ［J］. European Journal of Operational Research， 2023， 306（1）： 189-206.

［20］Holler J， Vuorio R， QinZhiwei， et al. Deep reinforcement learning for multi-driver vehicle dispatching and repositioning problem［C］// Proc of IEEE International Conference on Data Mining.Piscataway， NJ： IEEE Press， 2019： 1090-1095.

［21］Li Mengqi， Geng Ziyao， Wang Yi. Research on vehicle dispatch problem based on Kuhn-Munkres and reinforcement learning algorithm［C］// Proc of IEEE International Conference on Power Electronics， Computer Applications.Piscataway， NJ： IEEE Press， 2021： 986-992.

［22］Lunardi W T， Birgin E G， Ronconi D P，et al. Metaheuristics for the online printing shop scheduling problem ［J］. European Journal of Operational Research， 2021， 293（2）： 419-441.

［23］Zarouk Y， Mahdavi I， Rezaeian J，et al. A novel multi-objective green vehicle routing and scheduling model with stochastic demand， supply， and variable travel times ［J］. Computers amp; Operations Research， 2022， 141： 105698.

［24］Johnsen L C， Meisel F. Interrelated trips in the rural dial-a-ride problem with autonomous vehicles ［J］. European Journal of Operational Research， 2022， 303（1）： 201-219.

［25］郭羽含， 李文華， 錢亞冠. 融合時空流差的網約車雙模式混合調度算法 ［J］. 計算機工程， 2024， 50（6）： 377-393. （Guo Yuhan， Li Wenhua， Qian Yaguan. Dual-mode hybrid scheduling algorithm for online car-hailing fusion spatiotemporal flow difference ［J］. Computer Engineering， 2024， 50（6）： 377-393.）

［26］梁秀霞， 夏曼曼， 何月陽， 等. 基于時空多頭圖注意力網絡的交通流預測 ［J］. 電子學報， 2024， 52（2）： 500-509. （Liang Xiu-xia， Xia Manman， He Yueyang， et al. Traffic flow prediction based on spatio-temporal multi-head graph attention network ［J］. Acta Electronica Sinica， 2024， 52（2）： 500-509.）

［27］徐冰冰， 岑科廷， 黃俊杰， 等. 圖卷積神經網絡綜述 ［J］. 計算機學報， 2020， 43（5）： 755-780. （Xu Bingbing， Cen Keting， Huang Junjie， et al. A survey on graph convolutional neural network ［J］. Chinese Journal of Computers， 2020， 43（5）： 755-780.）

［28］Guo Yuhan， Li Wenhua， Xiao Linfan， et al. A prediction-based iterative Kuhn-Munkres approach for service vehicle reallocation in ride-hailing ［J］. International Journal of Production Research， 2024， 62（10）： 3690-3715.

［29］于海波， 朱秦娜， 康麗， 等. 帶偏向性輪盤賭的多算子協同粒子群優化算法 ［J］. 控制與決策， 2024， 39（4）： 1167-1176. （Yu Haibo， Zhu Qinna， Kang Li， et al. A multi-operator collaborative particle swarm optimization algorithm with biased roulette ［J］. Control and Decision， 2024， 39（4）： 1167-1176.）

［30］樊云閣， 呂玉輝， 韓紅旗. 基于情境感知注意機制的出租車需求深度學習預測模型 ［J］. 計算機應用與軟件， 2023， 40（7）： 41-49， 96. （Fan Yunge， Lyu Yuhui， Han Hongqi. Deep learning prediction model of taxi demand based on context aware attention mechanism ［J］. Computer Applications and Software， 2023， 40（7）： 41-49， 96.）

［31］李林波， 李楊. 面向精細化管理的停車需求短時預測 ［J］. 同濟大學學報： 自然科學版， 2021， 49（9）： 1301-1306. （Li Linbo， Li Yang. Short-term prediction of parking demand for parking delicacy management ［J］. Journal of Tongji University： Natural Science， 2021， 49（9）： 1301-1306.）

［32］周云彤， 熊衛華， 姜明. 基于多圖時空圖卷積神經網絡的網約車需求預測 ［J］. 計算機系統應用， 2021， 30（5）： 214-218. （Zhou Yuntong， Xiong Weihua， Jiang Ming. Prediction of ride-hailing demand based on multi-graph spatial-temporal graph CNN ［J］. Computer Systems amp; Applications， 2021， 30（5）： 214-218.）

［33］Yu Bing， Yin Haoteng， Zhu Zhanxing.Spatio-temporal graph convolutional networks： a deep learning framework for traffic forecasting［C］// Pro of the 27th International Joint Conference on Artificial Intelligence. Palo Alto， CA：AAAI Press， 2018： 3634-3640.

［34］Liu Mingzhi， Liu Guanfeng， Sun Lijun. Spatial-temporal dependence and similarity aware traffic flow forecasting ［J］. Information Sciences， 2023， 625： 81-96.

［35］張燕， 劉佶禎， 秦佳良， 等. 鐵路施工多目標均衡優化模型與改進NSGA-Ⅲ算法 ［J］. 交通運輸工程學報， 2024， 24（4）： 171-183. （Zhang Yan， Liu Jizhen， Qin Jialiang， et al. Multi-objective equilibrium optimization model and improved NSGA-Ⅲ algorithm of railway construction ［J］. Journal of Traffic and Transportation Engineering， 2024， 24（4）： 171-183.）

［36］Zitzler E， Thiele L. Multiobjective evolutionary algorithms： a compara-tive case study and the strength Pareto approach ［J］. IEEE Trans on Evolutionary Computation， 1999， 3（4）： 257-271.

［37］Schott J R. Fault tolerant design using single and multicriteria genetic algorithm optimization［D］. Cambridge， MA： Massachusetts Institute of Technology， 1995.