Categories
程式開發

淺談滴滴需求響應式公交背後的技術


淺談滴滴需求響應式公交背後的技術 1

淺談滴滴需求響應式公交背後的技術 2

桔妹導讀:所謂需求響應式公交,就是根據用戶出行需求,提供非固定路線的、能夠實時拼單的公交系統。目前滴滴動態公交可通過靈活調配運力、實時規劃行駛路線,為用戶提供經濟、直達、有座、高效的響應式公交服務。

1. 產品背景介紹

淺談滴滴需求響應式公交背後的技術 3

傳統公交系統以固定路線和時間表的形式給公眾提供出行服務。近年來,隨著信息技術的快速發展以及與各行業的深度融合,個性化服務逐漸興起。在公共交通領域,滴滴、Uber、Lyft等科技出行公司通過運用新技術賦能傳統出行行業,推出了更加便捷、優質的出行解決方案。

目前,全國每天約有2.5億人次選擇公共出行。滴滴本著讓出行更美好的願景,依靠掌握的高質量的交通大數據的優勢,不斷思索改進公共出行領域的解決方案,積極配合交管部門等合作夥伴一起用技術力量改善城市交通,普惠大眾出行。

在此背景下,滴滴需求響應式公交服務應運而生。其根據用戶的個性化出行需求靈活調整運力,針對客流和虛擬站點實時計算最優路徑,快速進行公交運力資源動態調配,實現全局效率最優。可有效彌補傳統公交在特定區域、特定時段內,運力和需求不匹配的問題,提升公共交通運行效率,有效滿足乘客出行的多元需求,有效提升用戶公共出行體驗,增加公共交通可達性。目前該業務已在青島、西安等多座城市落地,為用戶提供經濟、直達、有座、少步行的響應式公交服務。

在ToG、ToB的合作過程中,滴滴創新公交團隊主要致力於輸出產品技術能力,賦能B端,孵化多場景下多樣化的產品解決方案。公共出行的細分場景比較多樣化,有通勤、定點疏散、商務、旅遊、城際等類樞紐場景,有社區、產業園、大學城等類微循環場景,不同場景下可設計出不同的公交產品模式。同時需要一整套的運營體係來支持產品的運轉,若各B端自研,成本高、週期長、風險大。和滴滴需求響應式公交技術平台產品對接,可大大降低合作方成本,加速產品落地。同時助力提升公共出行信息化、網約化水平,讓乘客便捷獲取實時、準確的出行信息,讓運營主體實時監控車輛運營狀態、及時了解用戶訴求。

2. 公交業務模型

淺談滴滴需求響應式公交背後的技術 3

我們說出行問題,本質上是解決時空問題,公交出行同樣如此。下面通過對業務模型的抽象,拆解模型圖層,如下圖所示。第一層是靜態區域站點層,站點可以規劃設計大、中、虛擬站點;第二層是線路層,刻畫站點之間的通達路徑;第三層是一體化服務層,通過各種模式來進行人車接送,調度等服務。不同出行場景下,時空分佈存在差異,可以通過3層的不同模式來最優化公交服務。圖中右上角區域,出行時間、空間都很密集,這種場景下一般規劃大中站點、固定路線、投入大車、固定排班的樞紐模式為主;圖中左下角區域,出行時間、空間都不密集,這種情況下規劃虛擬小站、投入小車、實時聚合、動態的微循環模式為主;時間密集、空間不密集和空間密集、時間不密集兩種情況下,可結合樞紐和微循環組合模式去運營比較高效。

淺談滴滴需求響應式公交背後的技術 5

3. 產品服務架構

淺談滴滴需求響應式公交背後的技術 3

為了落地實現產品價值,基於滴滴基礎產研能力,滴滴實現了一整套動態公交產品服務。底層依托彈性雲平台、地圖、算法、調度引擎等基礎能力,構建了人、車、線動態智能匹配的服務。應用端包括乘客端,司機端,還有數據運營管理平台。

淺談滴滴需求響應式公交背後的技術 7

4. 產品界面

淺談滴滴需求響應式公交背後的技術 3

下面是動態公交產品效果截圖。前3張是乘客端,用戶選擇上下車站點,出發時間等實時呼叫或者預約出行,等待系統響應,響應之後,乘客可以看到車輛車牌號、車輛位置、預計到站時間等信息引導用戶乘坐。後1張是司機端,司機接到分配的行程任務後,會按照順序接送乘客。

淺談滴滴需求響應式公交背後的技術 9

5. 多樣化場景支持

淺談滴滴需求響應式公交背後的技術 3

公交出行的場景本身會比較多樣化,有通勤場景,有樞紐疏散場景,有商務,旅遊,城際,社區,產業園大學城等各種不同場景,不同場景下可能適合設計不同的公交產品模式來服務。

下圖是一個客運站樞紐疏散場景,開通分時段班次動態線路。青島西站出站乘客呼叫預約,系統根據不同上下車站點,動態聚合,規劃動態路線,將乘客疏散到下邊的大片區域。

淺談滴滴需求響應式公交背後的技術 11

下图是一个大学城区域,投入中小巴运营,固定站点,完全不固定线路。片区內乘客可实时呼叫或者预约,系统实时聚合匹配,实时生成动态路线,司机按照系统派发任务,按顺序接送乘客。

淺談滴滴需求響應式公交背後的技術 12

為了支撐實現多樣化產品,我們做了對業務模型的統一抽象。對公交服務來說,核心模塊設計包括站線模式、成行模式、調車模式、合乘模式、計價支付模式、取消模式等。線站模式包括固定線路、不固定線路、部分約束固定等模式;成行模式包括固定班次成行、拼夠人數成行,票款達標等模式;調車模式包括固定排定計劃、實時動態最優、輪循等模式;合乘模式包括排班乘坐、效率優先合乘、乘客體驗均衡等模式;計價模式包括固定票價、階梯票價、里程計價等模式;支付模式包括前支付、後支付、不支付等模式;取消模式包括不可取消,免費取消,懲罰取消等。在這個業務模型中每種模式都模版化,運營方可以根據場景實際情況,自由靈活選擇組合,快速創造落地運營新產品。

淺談滴滴需求響應式公交背後的技術 13

6. 線站模型升維

淺談滴滴需求響應式公交背後的技術 3

需求響應式公交集合了網約車的便利和公交的優惠,是傳統公交的一種創新,其本質還是一種公共交通形式,強調規劃性,需要有線站模型的規劃設計。

为了表达多样化的产品运营形态,我们升维了线站模型,从目前行业內以线为主,升级拓展为网状结构,配合站站通达性约束图,打开线路的表达空间,能创造出更多可能的灵活线路形态。

淺談滴滴需求響應式公交背後的技術 15

公交的運營主體是各地的公交集團、客運公司、小範圍的園區、社區管委會等。不同的運營主體,根據自身的需要,運營特點以及當地交通規則以及實際情況,會設計差異化的線路約束。

比較典型的線路通達性設計約束有:

部分或全部站點可能要求有相對站序,不允許逆站序行駛,通常見於火車站到市區,機場到市區的這種集散地疏散場景。​要求設置一個或多個必經站,通常見於旅遊景區、車站、學校等。允許系統動態微調乘客下單的上車站點,以提升車輛的運營效率,比如將乘客的上車站點修改到馬路對面,通常見於園區,或者城區無方向的微循環場景,減少車輛的調頭。特殊情況下,站點之間的路徑軌跡要按照運力方實際線下經驗規劃的路徑來設置,而不是按照導航服務的動態推薦線路來規劃。

類似的場景還有很多。從功能上看,似乎都是互不相關的定制化需求,但是從技術層面,我們可以把這些需求都統一抽象成一個特殊有向圖的表達。如果需要站點相對有序,我們可以通過配置站點的連通性,來達到同樣的效果。如果需要換站,我們可以通過訓練和挖掘手段,來找出可以換站條件的站點,並通過引擎算法的支撐來實現最終的效果。

通過配置,挖掘,訓練等手段,構造出一個特殊有向圖結構,並且運用到引擎內,最終轉化成不同“定制化”需求,我們稱之為需求響應式公交的線網模型。

7. 區域和站線規劃

淺談滴滴需求響應式公交背後的技術 3

由於是公交的屬性,比較強調區域,站線的規劃。在規劃方面,基於客流大數據,應用聚類等相關算法進行計算分析,並且求解最優閉包區域,建議站點設置,最優途徑路線等。

淺談滴滴需求響應式公交背後的技術 17

8. 車輛排班和調度

淺談滴滴需求響應式公交背後的技術 3

不同的運營商,在不同場景下,運營方式是多種多樣的。有在一個範圍內車輛不停巡遊的場景,也有在多個場站之間定時排班的場景,還有在多個場站之間按需排班的場景。公交運營方通常會有一個線下調度員,專門負責車輛的調度工作,如何使用線上數據和技術手段,替換或者輔助車輛調度,並滿足多種不同的場景需求,也是需求響應式公交面臨的一個重要問題。

針對實際情況,我們提煉出了靜態和動態兩種調度模式。

靜態調度:根據分時段客流量以及方向分佈,還有分時段路況等信息規劃運力或者班次投入計劃。並且利用智能算法,綜合考慮司機工作時長要求、疲勞駕駛、休息週期、駕駛表現,以及車輛續駛里程、加油充電週期、全程用時等相關信息,智能計算推薦排班,然後人工快速選擇和校正,高效產生最優排班計劃。

淺談滴滴需求響應式公交背後的技術 19

動態調度:動態生成合乘路線之後,調度引擎會實時為其尋找最優的車輛進行匹配和分配任務。系統會結合規則、車輛狀態、車輛位置等一系列因素去評估和計算,如果通過計算判定路線任務可以被響應,就會對行程路線和車輛進行任務綁定,車輛接到任務按順序接送乘客。

淺談滴滴需求響應式公交背後的技術 20

上圖是一個簡單的示意圖,途中,B1,B2車輛已經分配行程任務,正在執行既有行程,有2個未分配行程的車輛B3和B4,實時在線等待派發任務,同時在該時刻我們聚合形成了一個新的行程,後續出現的訂單可以繼續在行程上聚合拼單,同時告知用戶,行程已經拼成,車輛信息稍後告知但是暫時沒有合適的車。我們會根據運力規則,路況,預測發單情況去實時更新最合適的車輛,最終指定車輛B4去執行該未分配車輛的行程。

9. 系統核心架構

淺談滴滴需求響應式公交背後的技術 3

需求響應式公交主要由乘客端、司機端、管理後台和引擎幾個部分組成。整個系統從用戶呼單為起點開始運轉,訂單經過分析處理後放入訂單池,訂單池以某個特定的頻率向引擎發起拼單請求,引擎分析請求,適配合適的算法,給訂單撮合最優的車輛,並給車輛規劃出接送人的順序,然後將結果返回給後台系統進行緩存。司機端和乘客端接收後台的信息進行展示並對信息進行迭代更新,這樣,就構成了一個完整的系統閉環。

整個系統的架構簡圖如下:

淺談滴滴需求響應式公交背後的技術 22

10. 拼單和規劃引擎

淺談滴滴需求響應式公交背後的技術 3

動態公交拼單和規劃引擎主要是解決多車、多單在時間和空間上的匹配問題,在滿足各種先決條件下,盡可能多的拼成訂單,同時確保司乘體驗。公交車輛車型多樣,有幾座的,也有幾十座以上的,相比網約車,動態公交在每個車輛怎麼分配多個訂單、多個訂單如何組合不同路線兩個維度上多了延伸,而這種維度上的增加帶來的是組合上指數級的增長。

淺談滴滴需求響應式公交背後的技術 24

假設某個場景下有M輛車、N個訂單同時拼單,可能的組合方案(車單無序組合)會有

淺談滴滴需求響應式公交背後的技術 25

種;另,某個方案上有K輛車拼成,某輛車上有Q個訂單,則該方案下的解會有

淺談滴滴需求響應式公交背後的技術 26

種組合;則,理論上,M車N單可能的組合方案數級別為:

淺談滴滴需求響應式公交背後的技術 27

如此規模的VRP問題,暴力檢索是不可想像的。小規模區域下,可以通過傳統運籌學範疇的算法精確求解;當針對區域規模較大時,精確求解是不切實際的,需要尋找合理的智能算法,既要考慮搜索性能,也要合理規避陷入局部最優。為了更好的應對這種NP-難問題,尋找更好的次優解是我們解決問題的關鍵。

動態公交VRP問題,有它獨特的限制要求(車載量限制、用戶時間窗限制、站點順序限制等等),這種情況下一個合理的初始解很重要,能夠較大程度上縮減搜索規模,這裡我們可以結合拼單邏輯,啟發式生成初始解;搜索過程中引入禁忌表避免重複操作;採用變領域搜索避免陷入局部最優等等,在集中性和疏散性之間達到較好的平衡。另外,目標函數決定了搜索的方向,如何設計合理的目標函數,如何平衡拼單率和體驗之間的關係,一直是我們探索的方向。目前我們也在佈局通過機器學習智能推薦合理站點、引導車輛合理分佈等供需自動平衡方案。同時我們也在利用已有的歷史訂單數據和用戶行為數據通過深度學習的方法積極搭建我們的仿真係統,為針對不同運營區域獨立建模搭建基礎。

11. 開放平台

淺談滴滴需求響應式公交背後的技術 3

出於賦能公交行業的目的, 除支持滴滴主app呼單外,我們還提供一個開放平台合作模式,依靠開放平台客戶可以更加自主化的實現自身需求。

淺談滴滴需求響應式公交背後的技術 29

公交是一個多方合作的業務,技術平台以開放平台的模式來構建。使用開放api的方式,支持了多種方式的合作可能,運營方可以直接在滴滴app上運營產品,也可以通過我們提供的開放api和sdk接入到自有系統和app產品運營。

目前我們的產品和系統還有很多不完善的地方,也面對著很多的技術難點,歡迎大家對我們提出您寶貴的意見,幫助我們更好的成長,謝謝。

夢在遠方,路在腳下,我們致力於為您提供最佳公共出行解決方案!

本文作者

淺談滴滴需求響應式公交背後的技術 30

2016年加入滴滴,創新公交負責人,主要負責動態公交整體業務架構設計。

淺談滴滴需求響應式公交背後的技術 31

2018年加入滴滴,主要負責創新公交乘客端后端、開放平台和仿真平台等工作。

淺談滴滴需求響應式公交背後的技術 32

2016年加入滴滴,主要負責動態公交的司機端后端和規劃引擎等工作。

淺談滴滴需求響應式公交背後的技術 33

2019年加入滴滴,主要負責動態公交規劃引擎和可視化平台等工作。

團隊招聘

滴滴地圖與公交事業部創新公交團隊,依托滴滴地圖導航技術和基礎數據能力,使用機器學習和智能優化方法等技術,致力於為用戶提供靈活、高效的公共出行解決方案。

團隊長期招聘研發工程師,包括前端、後端、引擎策略等方向,歡迎有興趣的小伙伴加入,可投遞簡歷至[email protected],郵件請郵件主題請命名為「姓名-應聘部門-應聘方向」。

淺談滴滴需求響應式公交背後的技術 34

延伸閱讀

淺談滴滴需求響應式公交背後的技術 35

淺談滴滴需求響應式公交背後的技術 36

淺談滴滴需求響應式公交背後的技術 37

內容編輯| Charlotte

聯繫我們| [email protected]

淺談滴滴需求響應式公交背後的技術 38