[發明專利]一種基于打車熱點的動態拼車調度方法

有效

• 申請號: 201710185815.5
• 申請日: 2017-03-28
• 公開（公告）號: CN107103383B
• 公開（公告）日: 2020-07-14
• 發明（設計）人: 申彥明;高健人
• 申請（專利權）人: 大連理工大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/30
• 代理公司: 大連理工大學專利中心 21200
• 代理人: 梅洪玉

本發明屬于計算機應用技術領域，是一種基于打車熱點的動態拼車調度方法。該方法主要分為兩個階段，搜索階段和調度階段。搜索階段采用基于時間的二分搜索算法快速高效的檢索可能為乘客提供服務的出租車候選集。調度階段根據給出的動態拼車調度問題的定義，對候選集中的每輛出租車分別進行條件判斷，從中選出平均滿意度最大的出租車來為乘客提供服務，并針對空車調度，提出了一種基于熱點的優化調度策略。該方法可以為乘客實現個性化調度服務，并且簡單高效，具有很強的擴展性，對動態拼車調度方法的研究具有重要參考價值。

技術領域

本發明屬于計算機應用技術領域，涉及一種基于打車熱點的動態拼車調度方法。

背景技術

隨著城市汽車數量的爆炸性增長，引發了嚴重的交通擁堵和環境污染問題。拼車是一種有效的解決方案，它可以在滿足人們出行需求的同時，減少系統中汽車的數量，進而緩解交通擁堵和環境污染問題。

近年來，智能手機日益普及，而且智能手機GPS技術日漸成熟，這些都使得基于智能手機GPS數據提取出租車的實時運行狀態信息成為了可能，為城市出租車交通管理方法的研究和出租車市場的管理奠定了堅實的基礎。對于智能手機GPS數據的挖掘與應用，國內外的研究人員主要從將智能手機GPS數據應用于道路匹配、利用智能手機GPS數據估計道路狀態、利用智能手機GPS數據建立出租車調度系統和利用智能手機GPS數據研究乘客出行行為四個方面進行研究。

基于現有基礎，如何根據智能手機GPS獲得的實時位置數據實現一個高效的拼車調度方法現已成為研究的熱點問題。目前雖然已經有了許多這方面的研究，但是沒有充分利用人們的出行規律優化系統，方法都過于復雜，時間復雜度高，不利于實時應用場景。

發明內容

針對現有方法中存在的問題，本發明提出了一種基于打車熱點的動態拼車調度方法，該方法可以在最大化滿足乘客需求的前提下提供有效的實時拼車服務，同時可以顯著減少系統總的行駛距離。

用戶可以利用本技術提供的算法系統實現如下功能：對用戶的打車請求進行實時處理，選擇合適的出租車為其服務，并立即返回為其提供服務的出租車信息，該出租車也會立即收到一條乘客請求信息；存儲地圖數據；存儲歷史打車數據；打車熱點選取及需求量預測等。

本發明的技術方案：

定義1(路網定義)一個道路網絡G＝(V,E,W)由一個點集V和一個邊集E組成。每一條邊(v₁,v₂)∈E(v₁,v₂∈V)都被分配了一個權重W(v₁,v₂)代表在邊(v₁,v₂)上的旅行成本，這個權重可以是時間或者距離。給定路網中的兩個點o和d代表起點和終點，它們之間的路徑p是一個點的序列(v₀,v₁,...,v_n)，其中(v_i,v_i+1)是邊集E中的元素，v₀＝o并且v_n＝d。

定義2(打車請求)打車請求tr＝(t,o,d,wp,wd,det,r,cnt)，其中t是請求時間，o是起點，d是終點，wp是乘客可容忍的等待上車時間窗口大小，wd和det是拼車情況下乘客可容忍的繞道時間窗口大小和繞道距離大小，r是乘客滿意度中時間窗口所占比重，cnt是乘客數量。

定義3(有效出租車調度隊列)一個有效的出租車調度隊列S＝(v₁,v₂,...,v_2n)是一個由n個打車請求(tr₁,tr₂,tr₃,...,tr_n)的起點和終點組成的臨時序列，其中的v_i是打車請求中的起點或終點且v_i∈V，這些點的順序是由調度算法確定的，需要滿足如下四個條件：