[發明專利]一種路線優化方法以及系統

在審

• 申請號: 201710255192.4
• 申請日: 2017-04-19
• 公開（公告）號: CN107038504A
• 公開（公告）日: 2017-08-11
• 發明（設計）人: 陶書紅;劉靜;徐婷;崔蘭英;王愛麗
• 申請（專利權）人: 上海卓易電子科技有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04
• 代理公司: 北京科億知識產權代理事務所(普通合伙)11350
• 代理人: 肖平安

技術領域

本發明涉及信息技術，尤其涉及一種路線優化方法以及系統。

背景技術

如今大量的外賣公司涌入市場，比如美團外賣，百度外賣等，外賣的便捷性使得其在生活中越來越普及。一般而言，用戶在下單時，會選擇預計送達時間，當外賣數量很多，外賣配送員如何安排路線，以便按時，高效得將外賣送達顯得格外重要。

路線涉及到數學領域上的一個著名問題，即旅行商問題(TSP,Traveling Salesman Problem)，該問題是在尋求單一旅行者由起點出發，通過所有給定的需求點之后，最后再回到原點的最小路徑成本。具體解決該問題的算法主要采用啟發式近似算法，例如蟻群算法、遺傳算法、免疫算法、模擬退火算法、蛙跳算法等等。傳統的外賣配送方法可以采用這些算法，以達到從起點出發，最后回到終點，途徑一個或者多個送餐地點，并且走過的路徑最短，使得資源最為節約。但是新型的送餐方法對于每一份外賣的送餐時間有要求，某些用戶需要在一個時間點之前送達，或者在一個時間段內送達，傳統的TSP問題無法解決，亟待一種能夠對于龐大的數據量，在滿足送達時間的基礎上優化路線的方法。

發明內容

本發明的目的在于提出一種路線優化方法以及系統，能夠滿足每一個目標送達時間的基礎上優化路線。

為解決上述問題，本發明提供一種路線優化方法，包括：

一種路線優化方法，包括：

獲取當前地點S、一個或者多個目標送達地點Pi以及目標送達時間Ti(i＝1···n，n為大于等于1的整數)；

計算優化路線并展示。

進一步的，在上述方法中，所述計算優化路線并展示，包括：

對一個或者多個所述目標送達地點Pi，根據所述目標送達時間Ti從小到大進行排序，依次將所述目標送達地點Pi加入到所述優化路線中。

進一步的，在上述方法中，所述計算優化路線并展示，包括：

當將所述目標送達地點Pi加入到所述優化路線中時，查找加入到所述優化路線中的上一個所述目標送達地點Pi-1到所述目標送達地點Pi的所有路徑，根據所有路徑的擁堵程度Cij、距離Dij、預計送達時間Eij(j＝1··m，m為大于等于1的整數)，選擇最優路徑。

進一步的，在上述方法中，所述根據所有路徑的擁堵程度Cij、距離Dij、預計送達時間Eij(j＝1··m，m為大于等于1的整數)，選擇最優路徑，包括：

獲取所述所有路徑的擁堵程度Cij、距離Dij，計算出預計送達時間Eij；

篩選出所述預計送達時間Eij小于等于所述目標送達時間Ti的路徑；

根據用戶輸入的或者默認設置的擁堵程度Cij、距離Dij的權重W1，W2計算出所述路徑的推薦度R＝Cij*W1+Dij*W2，選擇所述推薦度最高的路徑。

進一步的，在上述方法中，所述選擇最優路徑后，包括：

檢測所述最優路徑一定閾值地理范圍內，是否有未加入的目標送達地點Pl(l為大于等于1的整數)并且current time(當前時間)+T(Pi-1，Pl)+T(Pl，Pi)≤Ti，若存在Pl，將所述目標送達地點Pl插入到所述最優路線中。

根據本發明的另一方面，本發明提供一種路線優化系統，所述系統，包括：

獲取系統，用于獲取當前地點S、一個或者多個目標送達地點Pi以及目標送達時間Ti(i＝1···n，n為大于等于1的整數)；

處理系統，用于計算優化路線；

展示系統，用于展示所述優化路線。

進一步的，在上述系統中，所述處理系統，用于：

對一個或者多個所述目標送達地點Pi，根據所述目標送達時間Ti從小到大進行排序，依次將所述目標送達地點Pi加入到所述優化路線中。

進一步的，在上述系統中，所述處理系統，用于：

當將所述目標送達地點Pi加入到所述優化路線中時，查找加入到所述優化路線中的上一個所述目標送達地點Pi-1到所述目標送達地點Pi的所有路徑，根據所有路徑的擁堵程度Cij、距離Dij、預計送達時間Eij(j＝1··m，m為大于等于1的整數)，選擇最優路徑。

進一步的，在上述系統中，所述處理系統，用于：

獲取所述所有路徑的擁堵程度Cij、距離Dij，計算出預計送達時間Eij；

篩選出所述預計送達時間Eij小于等于所述目標送達時間Ti的路徑；

根據用戶輸入的或者默認設置的擁堵程度Cij、距離Dij的權重W1，W2計算出所述路徑的推薦度R＝Cij*W1+Dij*W2，選擇所述推薦度最高的路徑。