[發明專利]一種生成路線的方法和裝置

在審

• 申請號: 201911045390.3
• 申請日: 2019-10-30
• 公開（公告）號: CN112749822A
• 公開（公告）日: 2021-05-04
• 發明（設計）人: 陳浪;董紅宇;步允千
• 申請（專利權）人: 北京京東振世信息技術有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06F17/15
• 代理公司: 中原信達知識產權代理有限責任公司 11219
• 代理人: 張一軍;王安娜

1.一種生成路線的方法，其特征在于，包括：

基于貪心算法生成路線；其中，每條路線包括至少一個地點；

去除所述路線中的若干個地點，將未分配的地點加入到去除地點后的所述路線中，從而迭代生成多組路線；

分別計算每組路線的目標函數值，選擇目標函數值最大的一組路線作為最終的路線。

2.根據權利要求1所述的方法，其特征在于，基于貪心算法生成路線，包括：

將與出發點的加權分數最高的地點加入到當前路線中，以所述地點作為當前地點，將與所述當前地點的加權分數最高的地點加入到所述當前路線中，直到所述當前路線的總行駛時間達到上限，從而生成一條路線；

重復生成路線的步驟，直到路線的數量與人員的數量相同。

3.根據權利要求2所述的方法，其特征在于，采用如下方法計算出發點與任意一個地點的加權分數：

根據出發點的位置坐標和所述地點的位置坐標，計算所述出發點與所述地點之間的距離；

根據所述出發點與所述地點之間的距離、所述地點的優先級、距離的加權系數和優先級的加權系數，計算所述出發點與所述地點的加權分數。

4.根據權利要求1所述的方法，其特征在于，去除所述路線中的若干個地點，將未分配的地點加入到去除地點后的所述路線中，從而迭代生成多組路線，包括：

判斷迭代次數是否達到最大迭代次數；若是，則停止迭代；若否，則去除前一次迭代生成的路線中的若干個地點，將未分配的地點加入到去除地點后的所述路線中，生成一組路線；

經過多次迭代，生成多組路線。

5.根據權利要求4所述的方法，其特征在于，去除前一次迭代生成的路線中的若干個地點，包括：

隨機去除前一次迭代生成的至少一個路線中指定數量的地點；或者，

隨機選擇前一次迭代生成的至少一個路線中的一個地點，將所述地點及其鄰域內的地點從所述至少一個路線中去除。

6.根據權利要求4所述的方法，其特征在于，將未分配的地點加入到去除地點后的所述路線中，包括：

在滿足總行駛時間上限約束的條件下，對于去除地點后的每條路線：將任意一個未分配的地點加入到該條路線中，分別計算該條路線中各個地點與所述未分配的地點的加權分數，以最高的加權分數作為所述未分配的地點在該條路線中的加權分數；

比較各個未分配的地點在該條路線中的加權分數的大小，篩選出最高的加權分數對應的未分配的地點以及路線，將所述未分配的地點加入到所述路線中。

7.根據權利要求4所述的方法，其特征在于，將未分配的地點加入到去除地點后的所述路線中，包括：

在滿足總行駛時間上限約束的條件下，對于每一個未分配的地點：將所述未分配的地點分別加入到去除地點后的每條路線中，分別計算加入所述未分配的地點后的每條路線的目標函數值；根據加入所述未分配的地點后的每條路線的目標函數值篩選出所述未分配的地點對應的最優路線和次優路線；計算所述最優路線的目標函數值與所述次優路線的目標函數值之間的差值；

篩選出所述最優路線的目標函數值與所述次優路線的目標函數值之間的差值最大的未分配的地點，將所述未分配的地點加入到所述未分配的地點對應的最優路線中。

8.根據權利要求7所述的方法，其特征在于，根據加入所述未分配的地點后的每條路線的目標函數值篩選出所述未分配的地點對應的最優路線和次優路線，包括：

計算加入所述未分配的地點前的每條路線的第一目標函數值，計算加入所述未分配的地點后的每條路線的第二目標函數值；

針對每條路線，計算第一目標函數值與第二目標函數值的差值；

按照所述第一目標函數值與第二目標函數值的差值由大到小的順序對各條路線進行排序，從而篩選出所述未分配的地點對應的最優路線和次優路線。

9.根據權利要求1所述的方法，其特征在于，所述路線的目標函數描述為：

所述路線中的地點的數量與優先級較高的地點未被加入所述路線的懲罰之和。