[發明專利]一種單車多點配送線路處理方法

在審

• 申請號: 201710597594.2
• 申請日: 2017-07-20
• 公開（公告）號: CN107358326A
• 公開（公告）日: 2017-11-17
• 發明（設計）人: 張文星
• 申請（專利權）人: 深圳市凱立德科技股份有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08
• 代理公司: 北京凱特來知識產權代理有限公司11260
• 代理人: 鄭立明,鄭哲

1.一種單車多點配送線路處理方法，其特征在于，包括：

基于地圖數據，采用節約算法對單點對多配送點的線路進行規劃，獲得規劃后的初始配送線路參數，所述多配送點包括物流配送過程中的兩個或兩個以上的配送點，所述單點是指物流配送過程中的配送起點或配送終點；

利用遺傳算法對所述初始配送線路參數進行優化處理，獲得實際配送線路參數。

2.根據權利要求1所述的方法，其特征在于，所述采用節約算法對單點對多配送點的線路進行規劃的步驟包括：

將所述單點分別與每個所述配送點相連，并計算由所述單點分別配送到所述配送點的第一距離值；

連接多個配送點中兩個所述配送點，并計算由所述單點依次配送到該兩個所述配送點的第二距離值；

計算連接所述兩個所述配送點后得到的第二距離值與所述第一距離值的差值作為距離節約值；

在將所有所述配送點中任意兩個配送點對應的距離節約值計算完成后，從大到小依次選擇所述距離節約值對應的兩個配送點，并根據預定的條件確定是否在所述兩個配送點之間建立線路連接，直到所有距離節約值均被選擇處理完成。

3.根據權利要求2所述的方法，其特征在于，所述預定的條件包括：

所述兩個配送點是否均不在已構成的線路上；或者，在已構成的線路上，但不是線路的內點；或者，在已構成的不同線路上，均不是內點，且一個是線路起點，另一個為線路終站；

和/或，

所述兩個配送點連接后，是否超出配送方的配送能力限制；

和/或，

所述兩個配送點連接后，配送過程中的線路總運輸時間是否符合要求；

和/或，

所述兩個配送點連接后，由一個配送點到達另一個配送點的時間是否符合要求。

4.根據權利要求1至3任一項所述的方法，其特征在于，所述利用遺傳算法對所述初始配送線路參數進行優化處理的步驟包括：

根據所述初始配送線路參數創建初始配送線路群，所述初始配送線路群包含多種配送線路；

根據每個配送線路的適應值在所述初始配送線路群中選擇配送線路，所述適應值是指配送線路的配送代價的評價值；

對選擇的配送線路中包含的配送點進行配送線路之間的交叉重組處理及配送線路自身的變異處理，并計算經交叉重組及變異處理后的新的配送線路的適應值；

若所述新的配送線路的適應值優于原配送線路的適應值，則以新的配送替換原配送線路，否則，保留原配送線路。

5.根據權利要求4所述的方法，其特征在于，在所述初始配送線路群中選擇配送線路的步驟包括：

產生一個在區間[0，1]的隨機浮點數R；

如果R<Q1，則選擇初始配送線路群中的第一個配送線路；否則選擇一個使Qi-1<R<＝Qi成立的第i個配送線路，其中，i大于等于1且小于等于初始配送線路群包含的所有配送線路的總數量，Qi為每個配送線路的累積概率，所述累積概率為根據每個配送線路的選擇概率計算確定，所述選擇概率為根據每個配送線路的適應值計算確定。

6.根據權利要求4所述的方法，其特征在于，

所述配送線路之間的交叉重組處理的步驟包括：在當前配送線路中，排除排在第一位的最優配送線路外，在其他配送線路中隨機或順序選擇兩對進行交叉重組；

所述變異處理的步驟包括：對交叉重組后的配送線路包含的配送點隨機選擇兩個進行交換位置處理。

7.根據權利要求4所述的方法，其特征在于，在以新的配送替換原配送線路，或保留原配送線路后，該方法還包括：

重新對所述變異處理后的配送線路包含的配送點再次進行變異處理，直到達到預定的變異處理次數；

重新根據每個配送線路的適應值在所述初始配送線路群中選擇一個配送線路，且所述重新操作的次數等于所述初始配送線路群包含的配送線路數量。

8.一種單車多點配送線路處理裝置，其特征在于，包括：

線路初始規劃單元，用于基于地圖數據，采用節約算法對單點對多配送點的線路進行規劃，獲得規劃后的初始配送線路參數，所述多配送點包括物流配送過程中的兩個或兩個以上的配送點，所述單點是指物流配送過程中的配送起點或配送終點；

實際配送線路規劃單元，用于利用遺傳算法對所述線路初始規劃單元獲得的初始配送線路參數進行優化處理，獲得實際配送線路參數。