[發明專利]一種基于出租車軌跡數據的盈利路線規劃方法

在審

• 申請號: 201811541105.2
• 申請日: 2018-12-17
• 公開（公告）號: CN109800903A
• 公開（公告）日: 2019-05-24
• 發明（設計）人: 徐小龍;邱玉華
• 申請（專利權）人: 南京郵電大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/30;G06K9/62
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 向文

1.一種基于出租車軌跡數據的盈利路線規劃方法，其特征在于：包括如下步驟：

1)對出租車軌跡數據進行預處理，預處理用于剔除噪聲數據，提高數據質量；

2)最佳客源點的挖掘：通過兩次聚類算法從海量的出租車軌跡數據中挖掘出價值密度最高的最佳客源點；

3)盈利路線的規劃：基于步驟2形成的最佳客源點的集合，將基于點到點的路線規劃問題轉化為TSP數學模型，采用啟發式算法進行路線規劃，并用單位時間盈利函數來評判路線的盈利能力。

2.根據權利要求1所述的一種基于出租車軌跡數據的盈利路線規劃方法，其特征在于：所述步驟1中預處理依次包括數據的清洗、抽樣和分區三個步驟。

3.根據權利要求2所述的一種基于出租車軌跡數據的盈利路線規劃方法，其特征在于：所述數據的清洗是將原始的出租車軌跡數據進行清洗，用于去除軌跡數據中的異常點，所述異常點包括缺省數值和錯誤數值；所述數據的抽樣采用混合抽樣的方法，用于保證數據分布不失真的情況下稀釋數據密度；所述數據的分區包括將出租車的軌跡數據按照城市核心區域分布進行區域劃分。

4.根據權利要求1所述的一種基于出租車軌跡數據的盈利路線規劃方法，其特征在于：所述步驟2中兩次聚類算法依次分別為基于密度的聚類算法和基于劃分的聚類算法，所述步驟2具體為：首先是利用基于密度的聚類算法得到出租車軌跡數據中的簇，基于每一個簇，再利用基于劃分的聚類算法得到簇的中心點，所得中心點即為最佳客源點。

5.根據權利要求4所述的一種基于出租車軌跡數據的盈利路線規劃方法，其特征在于：所述基于密度的聚類算法的計算流程如下：

2.1)讀取出租車軌跡數據；

2.2)輸入參數；

2.3)從軌跡數據中的任意點開始，查找所有的密度可達對象；

2.4)識別該點是否是核心點，若是，轉步驟2.5；若否，將該點標記為噪聲點，轉步驟2.3；

2.5)將該點鄰域內所有的點作為種子點繼續考察，直到找到一個完整的簇；

2.6)判斷是否存在未處理的點，若是，轉步驟2.3；若否，將不屬于任何簇的點標記為噪聲點；

2.7)輸出聚類結果。

6.根據權利要求4或5所述的一種基于出租車軌跡數據的盈利路線規劃方法，其特征在于：所述基于劃分的聚類算法的計算流程如下：

3.1)輸入簇中的軌跡數據和聚類中心；

3.2)初始化聚類中心；

3.3)針對簇中的每個軌跡點，計算它到聚類中心的距離并將其分到距離最小的聚類中心所對應的類中；

3.4)針對每個類別，重新計算它的聚類中心；

3.5)判斷數據是否收斂，若是，轉步驟3.6；若否，轉步驟3.3；

3.6)輸出聚類結果。

7.根據權利要求1所述的一種基于出租車軌跡數據的盈利路線規劃方法，其特征在于：所述步驟3中利用啟發式算法求解最佳盈利路線的具體流程為：

4.1)算法的初始化；

4.2)獲取司機當前位置，搜索周邊的最佳客源點；

4.3)求解最佳客源點的遍歷順序；

4.4)判斷是否滿足條件，若是，轉步驟4.5；若否，迭代次數加1，轉步驟4.3；

4.5)輸出結果。

8.根據權利要求1所述的一種基于出租車軌跡數據的盈利路線規劃方法，其特征在于：所述步驟3中單位時間盈利函數M為：

M＝(I-C)/T (1)

其中I為總的收益，C為總成本，T為駕駛時長，其中

出租車接到乘客，當載客里程S在基價公里數S₀以內時，總的收益就是基本租價I₀；當載客公里數S超過基價公里數S₀時，超過部分按照每公里的計價標準系數K₀進行計算，

C＝K₁*(S+L) (3)

S是載客里程，L是空載里程，K₁是油價消費，

T＝(S+L)/V (4)

V代表出租車司機在城市道路駕駛的平均速度。