考慮實時訂單更新的拼車調度雙層規劃模型

摘 要：針對訂單實時更新的實際情況，為仍有待完成訂單的司機持續分配任務，在保證司機收益增加的同時，提升拼車平臺的派單效率。在考慮拼車系統服務質量與運行成本的基礎上，基于平臺角度構建了以司機總收益最大化為目標的雙層規劃模型，并給出求解該模型的雙層算法：底層模型對拼車路徑進行規劃，設計改進的遺傳算法求解；上層模型決定訂單分配的順序，通過貪心算法調用底層模型，比較收益變化后得到最終的調度結果。通過具體算例對模型進行驗證，結果表明模型能夠較快求解出訂單匹配結果及行駛路線，說明了模型的可行性及算法的有效性，且計算結果能夠反映實際場景。對比實驗結果表明，模型在滿足提升司機收益的基礎上，能有效減少延誤時間及降低行駛距離，對于實時訂單更新場景下拼車調度問題的相關研究具有積極的參考意義。

關鍵詞：網約拼車； 匹配策略； 路徑優化； 雙層算法

中圖分類號：TP18; U491 文獻標志碼：A

文章編號：1001-3695（2024）06-016-1714-08

doi：10.19734/j.issn.1001-3695.2023.09.0438

Double-layer scheduling model for carpooling serviceconsidering dynamic order-updating

Abstract：To effectively address the real-time updates of passenger demand orders on online carpooling platforms， this paper proposed an algorithm for continuously assigning orders to drivers with unfinished orders. The proposed algorithm ensured an increase in driver earnings while enhancing the dispatch efficiency of the carpooling platform. Specifically，this paper developed a double-layer scheduling model which maximized the total driver revenue on the basis of the service quality and operational costs of the carpooling system， and proposed a double-layer algorithm for this model. The bottom layer involved the construction of a model for the carpooling routing problem， which was solved by using an improved genetic algorithm. The upper layer determined the order of task assignments， which adopted the greedy algorithm to call the model in the botton layer and compared revenue changes to obtain the final scheduling result. The model demonstrated its effectiveness and feasibility through a specific example， validating the prompt determination of order matching results and travel routes. The calculated results faithfully reflect real-world scenarios. Comparative experiments shows that the model not only achieves the goal of increasing driver earnings， but also effectively reduces delay time and travel distances. This has positive reference significance for related studies on carpooling scheduling problems in the context of real-time order updates.

Key words：ridesplitting; matching strategy; routing optimization; double-layer algorithm

0 引言

當前我國交通需求類型多樣、數量日漸增多，在移動互聯網技術的迅猛發展下，以網約車服務為代表的新興出行系統取得了顯著成功，成為人們日常出行的重要組成部分［1，2］。網約車平臺采用多種策略，為不同類型的乘客群體提供多種服務模式，例如快車、尊享和拼車等，從而為乘客提供更精細化的服務和更好的乘坐體驗［3］。

拼車模式可以在有限的車輛資源下，提供更多的出行服務，從而提高車輛的利用率［4］。拼車服務根據乘客的需求，實時動態地調整行駛路線，其收費也通常低于常規的網約車［5］。在進行訂單匹配時，平臺需要綜合考慮乘客的出行請求和司機的狀態，而司機與乘客的狀態也隨著調度方案的調整而不斷變化。拼車調度問題受到搭乘地點、時間窗口、搭乘路線、車輛乘客容量以及行駛速度等多種變量的約束，相對比較復雜［6］。

許多學者對拼車問題進行了研究，關注于為特定狀態下的司機和乘客進行匹配及調度。這種靜態的訂單分配要求司機完成服務后才能接受新的訂單，導致司機等待接單時間較長。此外，平臺在訂單分配時并未考慮司機的收益變化，導致司機為更多乘客提供服務但收益不增反降。因此，針對訂單實時更新的實際情況，如何為仍有待完成訂單的司機持續分配任務，以減少其等待接單時間，同時確保插單后司機收益增加，成為本文研究的核心問題。

1 相關研究

拼車匹配優化主要是指將有拼車需求的乘客與運營車輛進行合理配置，從而提高拼車成功率和服務效率［7］。當前拼車優化調度主要有匹配優化、路徑優化，還有匹配和路徑組合優化三個方向［8］。

拼車服務中，乘客向平臺發出合乘請求，平臺整合車輛與乘客雙方信息，對多車多乘客進行匹配，給出匹配方案并規劃每輛車的行駛路徑，圖1展示了拼車訂單分配的流程。近年來，訂單分配問題受到了許多專家學者的廣泛研究，主要涉及最小化乘客等待時間、最大化匹配率和最大化整體收益等。Qian等人［9］將出行起點和目的地相似的乘客進行分類，并優化出一個最佳的碰面點，以該碰面點作為基點與等待派單的司機進行匹配。Vazifeh等人［10］將精確的最小車隊規模優化問題轉換為最小路徑覆蓋問題，提出解決最小車隊問題的最優化計算方案。滴滴出行［11］提出了一個基于深度強化學習與半馬爾可夫決策過程的智能派單系統，利用深度神經網絡進行價值評估。吳玥琳等人［12］針對綜合客運樞紐出租車停靠點乘客滯留問題，設計兩階段算法求解合乘匹配方案及路徑問題。Kucharski等人［13］提出了基于需求的合乘出行匹配算法，利用效用函數替代時間窗口，以節省費用為目標對共享網絡進行優化。De Palma等人［14］模擬了動態的拼車行為，并計算每位乘客的出發時間與路線選擇。

在拼車出行服務的優化中，拼車路徑規劃算法直接影響著司機的工作效率、乘客的出行體驗以及平臺的盈利情況。將司機與拼車訂單匹配后，對拼車的路徑進行優化，這將拼車問題轉換為多個特殊的開放式的車輛路徑優化問題，每個問題都只包含一輛車及多個服務節點［15］。Masoud等人［16］提出一種解決實時拼車匹配問題的優化算法，引入動態交換機制，避免“先到先服務”規則的不利影響。郭羽含等人［17］針對長期車輛合乘問題，將具有相同目的地的用戶進行合乘匹配，設計了復合變鄰域搜索算法。Xu等人［18］提出了一種基于馬爾可夫決策過程的大規模訂單分配算法，旨在整體提高司機的收入。Hou等人［19］也提出了一種拼車優化模型，先根據乘客的出行需求與車輛進行最優匹配，然后對匹配后的車輛路徑進行優化。Braverman等人［20］提出一種封閉排隊網絡模型，通過控制網絡中的車輛流動來優化整個系統，證明了優化后的網絡路徑分布具有穩定性。Chen等人［21］提出封閉社區內通勤者共享出行問題，考慮返程限制、會面位置以及司乘間的互相選擇，提出整數線性規劃模型，并給出了對應的啟發式算法。

拼車調度問題類似于接乘問題PDP（pickup and delivery problem），屬于NP問題（non-deterministic polynomial）的范疇。拼車調度研究領域，國內外許多學者致力于改進創新匹配和路徑規劃模型及求解算法。Simonetto等人［22］提出兩種拼車方式：車輛主動的方式是將乘客請求進行組合后，和車輛進行匹配；乘客主動的方式中，乘客提交拼車請求后，平臺為乘客分配車輛。Xu等人［23］提出使用動態規劃的方法，將查詢最優乘客插入位置的問題轉換為查詢時間間隔最小值的問題。Birx等人［24］研究了動態場景下多乘客和多車輛的拼車問題，提出了重新規劃框架和遺忘框架，并給出解決匹配問題的啟發式算法。Xu等人［25］提出了一種基于橢圓約束的方法以提高插隊的效率，若乘客請求的起點和終點位置在橢圓內，則可以插入至車輛路線。Ferreira等人［26］將乘客上車和下車位置固定在某一特定的集合，從而提高乘客與車輛之間路線的相似度，過濾掉路線與乘客上下車位置不重疊的車輛。Yang等人［27］在拼車匹配優化模型中引入了匹配范圍和等待時間間隔的概念，構建了一種能夠顯著提高匹配成功率的優化模型。陳玲娟等人［28］研究帶時間窗約束的靜態拼車問題，從三個方面建立乘客車輛匹配及路徑優化的目標函數，采用演化策略算法求解問題。孫芮等人［29］提出了基于訂單匹配數量、司機旅行時間、乘客等待時間和乘客延誤時間的合乘匹配模型，并設計了對應匹配與路徑規劃算法。王志建等人［30］以車輛的總行駛距離最短以及總信任度值最高為目標，引入信任度權重和用戶偏好來衡量合乘的信任水平，對合乘軌跡線路進行優化。考慮到拼車的實際應用場景，Sun等人［31］基于拼車平臺的現實情況，提出平臺派單和司機搶單的混合匹配系統，并計算出了系統的最大匹配半徑。針對機場拼車，晏鵬宇等人［32］提出前瞻式動態拼車匹配策略，將未來隨機到達的乘客信息納入拼車匹配決策中，建立了乘客匹配與車輛路徑聯合優化兩階段隨機規劃模型。在考慮社會效益和服務質量的基礎上，袁鵬程等人［33］提出了基于風險分級的多目標拼車模型。

國內外關于訂單分配與路徑優化的先前研究為本文的研究提供了理論基礎。在典型的PDP問題研究中，已經提出了各種各樣的拼車模型，但實際拼車服務仍存在一些尚未解決的問題。首先，大多數學者仍然將拼車問題研究限定在靜態層面，即為特定狀態下的司機和乘客進行匹配和調度，司機只能機械地執行平臺分配的訂單，在其服務過程中無法接受新的訂單。司機完成服務后，平臺為其重新派單，這會導致司機等待接單時間延長，降低了系統的派單效率。其次，學者們在動態拼車研究中專注于提高拼車匹配成功率，忽略了插單后司機收益的變化，這可能導致插單后司機服務更多乘客，但其收益比為較少乘客服務時更低，降低了司機的服務熱情。因此，與以往的研究不同，本文研究的是一個新的動態插單問題，即在乘客拼車請求實時更新的實際場景下，平臺如何綜合考慮車輛位置、新的乘客訂單以及待服務訂單等信息，在服務過程中為司機持續分配一個或多個訂單，在保證司機收益提升的基礎上，提升整個系統的派單效率。

2 模型構建

2.1 問題描述

本文研究的是拼車訂單匹配與路徑優化的實際場景，即如何為仍有未完成訂單的拼車服務司機分配一個或多個訂單，以最大化司機收益。具體而言，系統中有m位司機，司機k當前已接受了hk個訂單待完成，訂單池里有n個訂單待分配，拼車平臺的任務是為每位司機分配一個或多個訂單，并重新規劃路徑，以最大化司機總收益。使用圖2展示的二分圖來表示這個問題，其中點集K表示提供拼車服務的司機，點集O表示待分配拼車訂單，K與O互不相交，且圖中的每條邊（k，i）所關聯的兩個頂點k和i分別屬于K和O（k in K，i in O）。

在本文研究的問題中，司機具有靈活性，可以在任意空閑時間開始或停止接單。因此，司機的行駛路線不是閉環，而是從當前位置出發，不斷接單繼續完成任務，如圖3所示。拼車問題具有以下特點：a）每個訂單需上車再下車；b）乘客上下車有時間窗，乘客需在上車時間窗內上車，并且若乘客下車時間超出最晚下車窗，對司機有懲罰；c）網約車容量有限，存在乘客數量限制。

2.2 雙層規劃模型

對拼車司機來說，所得收益不僅是每個訂單預計收益的簡單相加，還需扣除行駛成本，以及因延遲到達終點導致的懲罰成本。因此，在訂單分配時還需考慮司機是否能在最晚預計時間內將乘客送達終點、是否會產生懲罰等情況。拼車路徑規劃本身是NP-hard問題，而訂單分配則是基于路徑規劃的更高層次的決策問題。

本文提出了一個雙層模型，如圖4所示。其上層模型通過設定的評分機制對待分配訂單進行評分，根據評分順序為司機進行訂單分配，以司機總收益最高為目標；下層模型則以每位司機收益最大為目標，考慮時間窗、延遲送達懲罰，以及乘客數量約束等因素。下層模型在得到上層模型給出方案后，按照下層模型的最優目標作出反應，從而對上層模型的目標作進一步的優化。可見，上層模型的目標是雙層規劃的最終優化目標。

2.2.1 訂單評價分配模型

在上層模型中，為司機加入推薦訂單的順序將直接影響最終訂單分配的結果。對平臺而言，將K個司機與n個訂單所有可能的順序組合，有KAnn種，為了減小求解規模，同時增加較優的訂單被分配的可能性，本文先建立訂單評分模型。

訂單評分模型考慮了訂單對司機收入影響的主要因素，包括訂單預計收益、訂單上車時間、訂單需求行駛速度和訂單上車點位置。針對這四個主要因素構建評分模型：s（UP）i為訂單i的預計收益得分，收益高的訂單得分更高；s（TP）i為訂單的上車時間得分，訂單最早上車時間越早，得分越高；s（VP）i表示訂單的預期行駛速度，將上下車點的距離作為司機的預計行駛距離，最早上車時間和最晚下車時間的差值作為預計行駛時間，兩者的比值為訂單的預期行駛速度，對預期行駛速度要求低的訂單，分數更高；s（DP）ki是訂單上車點與司機當前位置距離得分，訂單上車點距離司機位置越近，該項得分越高。對司機k而言，訂單i的評分為

S_Oki=s（UP）i·UW+s（TP）i·TW+s（VP）i·VW+s（DP）ki·DW（1）

其中：UW、TW、VW和DW分別表示各因素所占權重，各項權重之和為1：

UW+TW+VW+DW=1（2）

訂單評分模型的決策變量：

S_O表示整個訂單匹配結果的評分總和，為所有司機對已分配訂單的評分累加，可進一步表示司機總收益最大：

2.2.2 拼車路徑規劃模型

1）符號說明及模型假設

考慮在拼車服務運營區內，司機k目前已接受了hk個訂單但尚未完成，訂單池里有n個訂單待分配。n為訂單總數，O為訂單集合，O={1，2，…，i，…，n}；司機起始位置VK0={0}，司機目標終點位置VKT={2n+1}，VS表示乘客上車節點集合，VS={1，2，…，i，…，n}；VE表示乘客下車節點集合，VE={n+1， n+2，…，n+i，…，2n}；V表示所有節點集合，V=Vk0∪VS∪VE∪VKT。

dij為節點i到j的距離；aki為司機k到達節點i的時間；［ei，lsi］為訂單i的乘客上車時間窗；lie為訂單i最晚到達時間窗；Ii為訂單i的預計收益。vk為司機行駛速度；Qk為司機乘客容量；qki為司機k離開節點i時所載乘客數量；qi表示需求點i的乘客數量；ski為司機k離開節點i的時間；wki為司機k在節點i的等待時間；α為行駛成本系數，β為延誤懲罰成本系數。

路徑規劃模型基于以下假設進行：a）在匹配和規劃過程中，車輛位置和拼車訂單的起止位置已經確定；b）在行駛過程中，禁止司機隨意搭乘未參與拼車的乘客；c）位置信息使用兩點間的直線距離，車輛勻速在規劃路徑上行駛，不考慮停啟時間、乘客上下車時間及交通擁堵導致的時間延誤。

2）數學模型

路徑規劃模型的決策變量由兩部分組成。0-1變量xkij表示司機行駛路線，若司機k由節點i行駛到節點j，則xkij=1，否則，xkij=0；0-1變量zki表示司機k完成訂單i時是否出現延誤的情況，若出現延誤，則zki=1，產生延誤懲罰，否則，zki=0。

司機收益為所有被服務乘客支付的拼車費用減去車輛行駛的總消耗以及延誤的懲罰成本。路徑規劃模型的目標函數為司機收益最大，其中第一部分表示所有訂單預計收益之和，第二部分表示司機的實際行駛成本，第三部分表示對司機未按時完成訂單的懲罰成本，則最大化司機總收益可以寫為

式（5）～（14）為相關約束條件。提供拼車服務的司機必須從當前位置出發：

在拼車服務過程中，每個訂單的上車點和下車點都必須被訪問：

計算車輛k到達節點j的時間，當該節點為起始節點時，到達時間為0；當該節點為非起始節點時，到達時間為司機離開前一節點的時間再加前一節點到本節點的行駛時間：

計算司機在節點i的等待時間：若節點i為下車節點，則司機在該節點無須等待；當節點i為上車節點時，（ei-aki）+表示ei-aki值非負的部分，若司機在乘客上車時間窗起始時間之前到達，即ei>aki，此時（ei-aki）+為ei-aki的值，表示司機需等到乘客上車時間窗起始時間，若司機在乘客上車時間窗起始時間之后到達，即ei＜aki，則該值為0，表示司機在該節點無須等待：

司機離開節點i的時間為司機到達節點i的時間加上司機在節點i的等待時間：

ski=aki+wki i∈V（11）

所有的拼車乘客都必須滿足先上車后下車約束：

aki≤akn+i i∈R（12）

計算車輛承載乘客數量：若節點j為起始節點，則此時承載乘客數量為0；若節點j為上車節點，則經過該節點后車輛承載乘客數量為經過上一節點承載乘客數量qki與需求點j的乘客數量qj加和，反之，若節點j為下車節點，則經過該節點后，車輛承載乘客數量為經過上一節點的乘客數量qki與需求點j的乘客數量qj作差：

車輛承載乘客數量不超過最大限制約束：

qkj≤Qk j∈V（14）

3 求解算法

3.1 雙層算法邏輯

本文提出的雙層算法，其上層邏輯采用貪心算法，對實時推薦的訂單通過評分機制進行評分，根據不同司機對不同訂單的評分結果，按照評分從高到低的順序為最高得分對應司機分配對應訂單，并為該司機進行路徑規劃。如果加入新訂單后的收益大于原有訂單所帶來的收益，則該司機接受該訂單，并將該訂單對所有司機的得分都清零；否則該司機不接受該訂單，僅將該司機對該訂單的得分清零。這個過程持續進行，直到所有司機對所有訂單的評分均為零。

下層邏輯為以收益最大為目標，考慮乘客上下車時間窗、延遲到達懲罰、承載乘客數量約束等現實因素，進行路徑規劃，該問題使用改進的遺傳算法進行求解。本文設計的雙層算法流程如圖5所示。

3.2 貪心算法

貪心算法是當前看來最優的選擇，本文采用的貪心策略并不是從整體上加以考慮作出的選擇，而只是在某種意義上的局部最優解算法，采取這樣的策略是為了提高運行速度。

在本文提出的雙層算法中，其上層貪心算法的邏輯即為通過某個評分機制將待分配訂單進行評分，由于某一區域內平臺實時訂單和司機數量均較多，首先基于評分結果向司機推薦分數最高的訂單，可以一定程度上提高求解速度。通過下層運算得到司機接受訂單后獲得的收益，若加入新訂單后的收益大于原有訂單組合的收益，則接受該訂單，否則不接受，直到無法接受任何訂單為止。

3.3 改進遺傳算法

3.3.1 編碼方式

為便于體現上車點與下車點的區別，本文采用自然數編碼的方式對兩者進行編碼，0，1，2，…，2n是2n+1個訪問點，其中，0為起點，即司機當前所在位置；1，3，5…，2n-1為上車點，分別對應第1，2，…，n號訂單，對應下車點為2，4，6，…，2n，即訂單i的上車點編碼為2i-1，下車點編碼為2i。以一個包含3個未完成訂單的情況為例，上車點與下車點的編碼如表1所示，起點為0。以上編碼組隨機排序組合成一條染色體，代表一條行駛路線，如0-1-5-6-3-4-2，其中，每個編碼對應染色體上的一個基因。

3.3.2 初始化種群及改進的個體構造方法

由于帶有上下車順序約束以及承載乘客數量約束，隨機生成的初始種群符合約束的概率較小，導致遺傳算法在后續運算中難以取得良好結果。為了提高初始種群的質量以及算法運算速度，本文提出兩個構造方法，在隨機生成初始種群的基礎上，對不符合約束的染色體重新構造。

1）上下車順序約束構造

若隨機生成的染色體中存在某個下車點在對應訂單的上車點之前訪問，則將該訂單的下車點與上車點位置對換，同時保持其余訪問點位置不變。例如，當前司機共有5個訂單，假設隨機生成的某一染色體為0-2-3-4-6-7-8-1-9-5-10，其中，1號訂單的上車點1出現在對應的下車點2之后，3號訂單的上車點5出現在對應的下車點6之后，不符合上下車順序約束，因此將基因1與2的位置對換，基因5與6的位置對換，其余基因位置保持不變，形成新的染色體，其操作如圖6所示。

2）承載乘客數量約束構造

司機訪問上車點后，車輛承載乘客數量增加，訪問下車點后，承載乘客數量減少。若在訪問某點后，車輛承載乘客數量超過容量，那么該點一定為上車點，同時，該上車點前一定有其他尚未下車的訂單的上車點。為了避免破壞上下車順序約束，本文以超出乘客數量約束的點所在的基因位為界限，找到該點前距該點最近的已經上車但尚未下車訂單的上車點，再找到該上車點對應的下車點，將該下車點前移至超出乘客數量約束的點所在基因的前一位。

以圖7為例，假設車輛承載乘客容量為2，每個訂單只有一位乘客。當車輛訪問上車點7后，訂單數量為3，乘客數量超過了容量限制，需要從上車點7向前尋找已經上車但未下車的訂單。顯然，點5是距離上車點7最近的上車點，且上車點5對應的訂單尚未下車。找到上車點5對應的下車點6，將6移至7前一位，原染色體中5與6之間的基因均依次后移一位，其余基因位置保持不變，形成新的染色體。

經過這樣的調整，染色體在滿足承載乘客數量約束的同時，也不會違反訂單的上下車順序約束，可以直接得到最終符合約束的可行解。

3.3.3 適應度函數

根據2.2.2節的拼車路徑規劃模型，目標函數為最大化司機總收益。在改進的遺傳算法中，適應度函數為拼車司機服務的收益，可以表示成目標函數max M相同的形式：

其中：三個部分分別表示所有訂單預計收益之和、實際行駛成本，以及未按時完成訂單的懲罰成本。根據適應度函數，可以計算出初始種群中各個體的適應度值。

3.3.4 遺傳算子設計

a）采用輪盤賭方法選擇算子。

b）交叉算子采用部分匹配交叉規則（partially mapped crossover，PMX）。隨機產生兩個隨機數，滿足0≤k1＜k2≤染色體長度，如k1= 3，k2=6作為截取染色體片段的起始位置，將截取到的兩個片段進行位置交換，可得到兩個新個體。如圖8所示，交叉的基因片段為“4-5-7-8”和“4-1-10-7”，將這兩段基因片段在父代染色體中互換，得到新的子代染色體。可見子代1中基因1、基因10重復出現，卻缺少基因5、8，子代2中基因5、8均出現兩次，卻缺少基因1、10，說明交叉得到的染色體很容易不符合約束。

為了解決交叉操作后基因重復的問題，本文的處理是保持被交換的片段不動，在沒有交換的片段中尋找重復值，再在交叉部分中找到對應位置的元素進行映射替換，15，1078，至新的子代沒有重復基因為止，如圖9所示。

c）根據預先設定的變異概率判斷父代染色體是否變異，若變異，則隨機選擇兩個基因位置，交換這兩個位置的基因，形成新的子代。

d）本文采用精英選擇策略進行種群更新，先進行當前種群的交叉和變異，交叉及變異得到的新的子代若不符合約束，同樣使用3.3.2節中所述方法將其改造，然后，根據染色體的適應度，從父代和子代群體中篩選出當前適應度最高的染色體，數量滿足群體大小，形成新的種群。

3.3.5 遺傳終止條件

為了確保算法盡可能接近最優解，同時減少運算時間，采用以下兩個迭代終止條件：a）若連續50次迭代的適應度相同，則終止迭代；b）迭代次數達到最高300次，則終止迭代。

4 算例分析

4.1 算例基礎數據

通過一個具體的算例對DMRS-DES模型的有效性進行驗證。算例包含5位司機，每位司機均有若干個未完成訂單，其各自未完成訂單的信息如表2所示。

此時，拼車平臺根據一定原則，為這些司機推薦了10個新訂單，訂單信息如表3所示。訂單評分模型權重及服務過程車輛的各項參數設置如表4所示，通過訂單評分模型得到司機對應各個訂單的百分制分數如表5所示。

4.2 算例實驗結果

本文利用MATLAB R2022a進行編程求解，所有數據均在AMD Ryzen 7 3700U with Radeon Vega Mobile Gfx2.30 GHz配置的計算機上進行仿真實驗。遺傳算法的參數設定為種群大小=60，交叉概率=0.9，變異概率=0.05。

當前待完成訂單的路徑規劃結果如表6所示，通過計算得出了每位司機的最優行駛路線、預計收益、延誤時間及行駛距離。

在現有訂單基礎上，利用設計的雙層算法，從10個推薦訂單中為司機分配合適的訂單。由于現實拼車調度問題的特點，求解模型的速度和決策難度的提高成為重要的考慮因素。為了驗證算法的計算速度，進行50次實驗，對程序運行時間進行統計，如圖10所示。50次實驗的程序運行時間均在5～8 s，僅有4次實驗的程序運行時間超過了7 s。程序運行平均時間為6.45 s，證明對10個推薦訂單的分配花費時間可接受。

表7和圖11以司機1為例，更直觀地展現了按照本文提出的雙層算法為司機分配訂單后，其預計收益的變化。可以看出，并非訂單數量越多收益越大，若多個訂單的下車時間窗過近或距離過遠，過多的訂單將導致送達時間延遲產生懲罰，進而降低收益。還需注意的是，初始的訂單評分越高只是表示“優先考慮”但并非“最終選擇”，如對司機1而言，雖然訂單16的評分為77，而訂單15的評分僅為51，根據評分順序模型，優先考慮了訂單16，但并沒有直接分配給司機1，最終僅為其分配了訂單14與訂單15，這種情況發生的原因是加入訂單16后的收益小于僅分配訂單14的收益。

表8展示了總收益最優的訂單分配結果。系統提供的10個訂單中，有8個訂單分別分配給幾位司機。而對于訂單13和17而言，無論分配給哪位司機，均會使其收益減少，進而減少系統的總收益。以司機1為例，為其分配訂單14和15后，其收益達到了103.63元，增加了84.43元，并且可以在沒有延誤的情況下完成兩個待完成訂單和兩個新分配的訂單。將其行駛路線染色體翻譯成最終結果為：司機1當前位置→訂單1上車→訂單14上車→訂單1下車→訂單2上車→訂單15上車→訂單15下車→訂單2下車→訂單14下車。

為了評估在考慮司機仍有未完成訂單的狀態下，DMRS-DES模型的調度效果，本文將采取隨機策略分配訂單，按最近上車點距離策略分配訂單，將其收益和延誤時間與本模型進行對比，對比結果如表9所示。

仿真模型輸出結果主要包括司機行駛距離、延誤時間和司機的收益變化三個參數。通過表9可以看到，采用不同的調度模型對司機的收益影響較大。以司機4為例，采用本模型為其在原有兩個未完成訂單的基礎上再分配訂單20，通過模型規劃的路線，預計其收益增加18.56元，且無延誤；若采取最近距離調度模型，由于系統推薦的10個訂單都離司機4較遠，則不會給司機4分配新的訂單，其收益不變；若采用隨機分配模型，則為其分配訂單17和18，則其預期收益降低34.75元，且延誤時間高達46.65 min。對實驗結果進行整體分析，本文模型在司機整體收益變化、行駛距離和延誤時間三個方面均顯著優于隨機調度模型和最近距離調度模型，說明DMRS-DES模型在最大化所有司機整體收益的同時，也可以較好地降低總行駛距離，減少延誤時間。

通過圖12可以看出，匹配成功的訂單數量增加，并不一定會導致司機收益的相應增長。若多個訂單的下車時間窗相近，將過多的訂單分配給司機可能會引起送達乘客的延遲，進而產生相應的懲罰，降低司機的收益。

圖13分別展示了不同的調度模型對總行駛距離及延誤時間的影響，可以看出，本文提出的調度模型在保證收益提升的前提下，相比較于其他模型也降低了行駛成本和延誤損失。DMRS-DES模型中未分配的訂單保留在訂單池內，可以在后續的調度循環中再進入訂單組合，進行進一步優化，這與實際情況相符，即拼車訂單并不一定會在被推薦后短時間內被司機接受。

5 結束語

本文根據拼車平臺調度的特點，提出DMRS-DES模型為拼車平臺訂單分配及路徑規劃提供決策參考。該模型中遵循為司機分配新訂單要保證其收益增加的基本原則，同時綜合考慮行駛成本及延誤懲罰，以實現收益最大化。本文設計了對應的雙層算法，將訂單分配與路徑規劃同時進行計算，先基于訂單評分決定進入訂單分配的次序，再進行下層的路徑規劃，決定是否分配該訂單，路徑規劃允許訂單交叉執行。在求解下層的路徑規劃模型中，本文設計了改進的遺傳算法，進行染色體的重新構造，使染色體滿足拼車的上下車順序及承載乘客數量約束。

通過MATLAB進行算例分析，驗證了模型與算法在小規模問題下的求解效果與速度。通過與隨機分配調度模型與最近距離調度模型進行對比，驗證了算法的有效性。結果表明，在拼車司機仍有未完成訂單的實際應用場景中，應用本文模型進行訂單分配能增加司機收益，同時減少總行駛距離與延誤時間。

在后續研究中，對仍有未完成訂單的司機如何進行拼車訂單和獨享訂單的聯合調度問題，可以作為進一步探討的方向。本文的研究成果可以擴展到更大規模的問題，當拼車平臺面對的司機和乘客數量更多時，其訂單分配方式的組合數量會呈指數增長，參考本文提出的評分方法進行訂單的初始篩選和排序，可以有效降低求解時間。

參考文獻：

［1］Benjaafar S， Bernhard H， Courcoubetis C. Drivers， riders and ser-vice providers： the impact of the sharing economy on mobility［C］//Proc of the 12th Workshop on Economics of Networks， Systems and Computation. New York：ACM Press， 2017： 1-6.

［2］Benjaafar S， Hu Ming. Operations management in the age of the sharing economy： What is old and what is new？［J］. Manufacturing & Service Operations Management， 2020，22（1）： 93-101.

［3］Wang Jingpeng， Huang Haijun. Operations on an on-demand ride service system with express and limousine［J］. Transportation Research Part B： Methodological， 2022，155： 348-373.

［4］Tirachini A. Ride-hailing， travel behaviour and sustainable mobility： an international review［J］. Transportation， 2020，47（4）： 2011-2047.

［5］Standing C， Standing S， Biermann S. The implications of the sharing economy for transport［J］. Transport Reviews， 2019，39（2）： 226-242.

［6］Si Hongyun， Duan Xu， Cheng Long， et al. Determinants of consu-mers’coni79WNU47wt8ICws6Amn0+Q==tinuance intention to use dynamic ride-sharing services［J］. Transportation Research Part D： Transport and Environment， 2022，104： 103201.

［7］Wang Xing， Agatz N， Erera A. Stable matching for dynamic ride-sharing systems［J］. Transportation Science， 2018，52（4）： 850-867.

［8］徐毅， 童詠昕， 李未. 大規模拼車算法研究進展［J］. 計算機研究與發展， 2020， 57（1）： 32-52. （Xu Yi， Tong Yongxin， Li Wei. Recent progress in large-scale ridesharing algorithms［J］. Journal of Computer Research and Development， 2020，57（1）： 32-52.）

［9］Qian Xinwu， Zhang Wenbo， Ukkusuri S V， et al. Optimal assignment and incentive design in the taxi group ride problem［J］. Transportation Research Part B： Methodological， 2017，103： 208-226.

［10］Vazifeh M M， Santi P， Resta G， et al. Addressing the minimum fleet problem in on-demand urban mobility［J］. Nature， 2018，557（7706）： 534-538.

［11］Tang Xiaocheng， Qin Zhiwei， Zhang Fan， et al. A deep value-network based approach for multi-driver order dispatching［C］//Proc of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining.New York：ACM Press， 2019： 1780-1790.

［12］吳玥琳， 袁振洲， 陳秋芳， 等. 考慮軌跡相似度的綜合客運樞紐出租車合乘方法研究［J］. 交通運輸系統工程與信息， 2020，20（2）： 188-195. （Wu Yuelin， Yuan Zhenzhou， Chen Qiufang， et al. Taxi pooling method of urban integrated passenger transport hub with trajectory similarity［J］. Journal of Transportation Systems Engineering and Information Technology， 2020，20（2）： 188-195.）

［13］Kucharski R， Cats O. Exact matching of attractive shared rides （ExMAS） for system-wide strategic evaluations［J］. Transportation Research Part B： Methodological， 2020，139： 285-310.

［14］De Palma A， Javaudin L， Stokkink P， et al. Ride-sharing with inflexible drivers in the Paris metropolitan area［M］//Transportation.Berlin：Springer， 2022： 1-24.

［15］Atasagun G C， Karaogˇlan I·. A mathematical model for the time dependent vehicle routing problem with simultaneous pick-up and deli-very［J］. Journal of the Faculty of Engineering and Architecture of Gazi University， 2019，34（4）： 1743-1755.

［16］Masoud N， Jayakrishnan R. A real-time algorithm to solve the peer-to-peer ride-matching problem in a flexible ridesharing system［J］. Transportation Research Part B： Methodological， 2017，106： 218-236.

［17］郭羽含， 伊鵬. 長期車輛合乘問題的復合變鄰域搜索算法［J］. 計算機應用， 2018，38（10）： 3036-3041，3052. （Guo Yuhan， Yi Peng. Hybrid variable neighborhood search algorithm for long-term carpooling problem［J］. Journal of Computer Applications， 2018，38（10）： 3036-3041，3052.）

［18］Xu Zhe， Li Zhixin， Guan Qingwen， et al. Large-scale order dispatch in on-demand ride-hailing platforms： a learning and planning approach［C］//Proc of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining.New York：ACM Press， 2018： 905-913.

［19］Hou Liwen， Li Dong， Zhang Dali. Ride-matching and routing optimisation： models and a large neighbourhood search heuristic［J］. Transportation Research Part E： Logistics and Transportation Review， 2018，118： 143-162.

［20］Braverman A， Dai J G， Liu Xin， et al. Empty-car routing in ridesharing systems［J］. Operations Research， 2019， 67（5）： 1437-1452.

［21］Chen Wenyi， Mes M， Schutten M， et al. A ride-sharing problem with meeting points and return restrictions［J］. Transportation Science， 2019，53（2）： 401-426.

［22］Simonetto A， Monteil J， Gambella C. Real-time city-scale ridesharing via linear assignment problems［J］. Transportation Research Part C： Emerging Technologies， 2019，101： 208-232.

［23］Xu Yi， Tong Yongxin， Shi Yexuan， et al. An efficient insertion ope-rator in dynamic ridesharing services［J］. IEEE Trans on Know-ledge and Data Engineering， 2020，34（8）： 3583-3596.

［24］Birx A， Disser Y. Tight analysis of the smartstart algorithm for online dial-a-ride on the line［J］. SIAM Journal on Discrete Mathema-tics， 2020，34（2）： 1409-1443.

［25］Xu Yixin， Kulik L， Borovica-Gajic R， et al. Highly efficient and scalable multi-hop ride-sharing［C］//Proc of the 28th International Conference on Advances in Geographic Information Systems. New York：ACM Press， 2020： 215-226.

［26］Ferreira D L， Nunes B A A， Campos C A V， et al. A deep learning approach for identifying user communities based on geographical pre-ferences and its applications to urban and environmental planning［J］. ACM Trans on Spatial Algorithms and Systems， 2020，6（3）： 1-24.

［27］Yang Hai， Qin Xiaoran， Ke Jieping， et al. Optimizing matching time interval and matching radius in on-demand ride-sourcing markets［J］. Transportation Research Part B： Methodological， 2020，131： 84-105.

［28］陳玲娟， 寇思佳， 柳祖鵬. 網約拼車出行的乘客車輛匹配及路徑優化［J］. 計算機與現代化， 2021（7）： 6-11. （Chen Lingjuan， Kou Sijia， Liu Zupeng. Passenger-vehicle matching and route optimization of network carpooling［J］. Computer and Modernization， 2021（7）： 6-11.）

［29］孫芮， 吳文祥. 基于分解算法的動態大規模合乘匹配-路徑規劃［J］. 科學技術與工程， 2022，22（4）： 1662-1668. （Sun Rui， Wu Wenxiang. Dynamic large-scale ride-matching and route planning based on decomposition algorithm［J］. Science Technology and Engineering， 2022，39（11）： 3351-3357.）

［30］王志建， 郭健， 張強. 考慮乘客信任程度的營運車輛合乘線路規劃［J］. 計算機應用研究， 2023，40（4）： 996-999. （Wang Zhijian， Guo Jian， Zhang Qiang. Planning of ride-sharing routes for operating vehicles considering degree of passenger trust［J］. Application Research of Computers， 20EXf6P9V/rwSx0tUAz4bNXQ==23，40（4）： 996-999.）

［31］Sun Luoyi， Teunter R H， Hua Guowei， et al. Taxi-hailing platforms： inform or assign drivers？［J］. Transportation Research Part B： Methodological， 2020，142： 197-212.

［32］晏鵬宇， 張逸冰， 殷允強. 乘客到達時間不確定的機場動態拼車策略與算法研究［J］. 運籌與管理， 2022， 31（8）： 129-136. （Yan Pengyu， Zhang Yibing， Yin Yunqiang. Dynamic matching and vehicle routing approach for airport online ride-sharing services considering uncertainty of passenger arrival times［J］. Operations Research and Management Science， 2022， 31（8）： 129-136.）

［33］袁鵬程， 林徐勛， 韓印. 考慮疫情擴散傳播風險的多目標拼車應急管理優化調度模型［J］. 計算機應用研究， 2022， 39（11）： 3351-3357. （Yuan Pengcheng， Lin Xuxun， Han Yin. Multi-objective optimal ridesplitting scheduling model considering risk of epidemic spread［J］. Application Research of Computers， 2022，39（11）： 3351-3357.）