[發明專利]一種從地圖數據中獲取多車輛導航路徑的方法

有效

• 申請號: 201110281769.1
• 申請日: 2011-09-21
• 公開（公告）號: CN102445208A
• 公開（公告）日: 2012-05-09
• 發明（設計）人: 戚銘堯
• 申請（專利權）人: 清華大學深圳研究生院
• 主分類號: G01C21/34
• 分類號: G01C21/34;G08G1/0968
• 代理公司: 深圳新創友知識產權代理有限公司 44223
• 代理人: 江耀純

1.一種從地圖數據中獲取多車輛導航路徑的方法，用于生成多車輛從配送中心出發途經若干服務點進行服務后回到配送中心的導航路徑，其特征在于，包括以下步驟：

1）數據獲取步驟：獲取地圖數據、以及車輛必須經過的所有服務點的服務點數據，該服務點數據至少包括：服務點的位置數據；

2）導航路徑生成步驟：根據所述地圖數據和所述服務點數據生成包含多條子線路的多車輛導航路徑，其包括以下子步驟：

2-1）初始導航路徑生成步驟：2-1-a）：選擇一個服務點作為初始點，在車輛從配送中心去往該初始點以及從該初始點返回配送中心的路徑中，插入若干服務點作為該路徑的途經點以形成一條子線路；2-1-b）：重復步驟2-1-a）以形成多條子線路，使得所有服務點均處于其中一條子線路的途經點，從而形成初始導航路徑；2-1-c）：通過所述地圖數據以及各服務點的位置數據計算出初始導航路徑的路程總長度S1；

2-2）第一優化步驟：2-2-a）：在初始導航路徑中，選擇任意一條子線路的一個途經點，將該途經點隨機地與同一條子線路或非同一條子線路的其他途經點進行交換、或者選擇任意一條子線路的一段路徑段隨機地與同一條子線路或非同一條子線路的其他路徑段進行交換以形成第一優化導航路徑，計算第一優化導航路徑的路程總長度S2，2-2-b）：若S2<S1，用第一優化導航路徑替代初始導航路徑并重復步驟2-2-a），否則，直接重復步驟2-2-a）并累計1次第一優化次數，當第一優化次數大于預定值時，退出第一優化步驟；

2-3）第二優化步驟：2-3-a）：在第一優化導航路徑中，隨機地將任意一條子線路中的一個途經點刪除，并重新將其隨機地插入至其原子線路或非原子線路中作為途經點以形成第二優化導航路徑，計算出第二優化導航路徑的路程總長度S3，2-2-b）：若S3<S2，用第二優化導航路徑替代第一優化導航路徑并重復步驟2-3-a），否則直接重復步驟2-3-a）并累計1次第二優化次數，當第二優化次數大于預定值時，退出第二優化步驟；

3）導航路徑輸出步驟：將步驟2-3）得到的第二優化導航路徑發送至被導航車輛的導航終端中。

2.根據權利要求1所述的從地圖數據中獲取多車輛導航路徑的方法，其特征在于：所述步驟2-1-a）中，插入服務點時，優先選擇插入費用函數最小的服務點進行插入，所述插入費用函數????????????????????????????????????????????????，其中，分別是一條子線路中的兩個服務點，是待插入的服務點，、、分別是車輛從服務點到、到、及到所需要的費用。

3.根據權利要求1所述的從地圖數據中獲取多車輛導航路徑的方法，其特征在于：所述步驟2-1-a）中，所述初始點選擇未插入子線路中的距離配送中心最遠的服務點。

4.根據權利要求1所述的從地圖數據中獲取多車輛導航路徑的方法，其特征在于：所述服務點數據還包括該服務點的貨物量，所述步驟2-1-a）中，當該子線路中的服務點的貨物量總和超過預設的值時，停止在該子線路中插入新的服務點；所述第一優化導航路徑、所述第二優化導航路徑中任意一條子線路中的服務點的貨物量總和也不能夠超過該預設的值。

5.根據權利要求1、2、3或4所述的從地圖數據中獲取多車輛導航路徑的方法，其特征在于：所述服務點數據還包括車輛到達該服務點的時間范圍要求，所述步驟2-1-a）中，當在子線路中插入新的服務點后車輛無法在要求的時間范圍內到達時，停止在該子線路中插入新的服務點。