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

在審

• 申請?zhí)枺?/td>: 201710597594.2
• 申請日: 2017-07-20
• 公開（公告）號: CN107358326A
• 公開（公告）日: 2017-11-17
• 發(fā)明（設(shè)計）人: 張文星
• 申請（專利權(quán)）人: 深圳市凱立德科技股份有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08
• 代理公司: 北京凱特來知識產(chǎn)權(quán)代理有限公司11260
• 代理人: 鄭立明,鄭哲

技術(shù)領(lǐng)域

本發(fā)明涉及計算機信息處理技術(shù)領(lǐng)域，尤其涉及一種單車多點配送線路處理方法。

背景技術(shù)

隨著物流行業(yè)的快速發(fā)展，人們對物流的配送時效有了更高的要求，同時物流經(jīng)營企業(yè)也希望提高配送效率，以提升企業(yè)競爭力。因而，提高物流配送服務水平、降低物流配送成本已經(jīng)成為物流配送過程中配送線路規(guī)劃的基本要求。在配送線路規(guī)劃過程中，通常涉及的便是單車多點配送線路的規(guī)劃。

單車多點配送線路是指單個貨運車輛配送多個地點的貨物時，在這種情況下，需要對配送點進行合理的排序，從而使得配送線路更為合理，節(jié)約貨運車輛的行駛里程及時間，進而達到提高配送效率的目的。

目前，通常采用的配送線路排序優(yōu)化方法多由貨運車輛駕駛?cè)藛T自行完成，由于在規(guī)劃配送線路過程中缺少地圖數(shù)據(jù)，因而其并不能很好的做到配送線路中的各個配送點的排序得到合理的優(yōu)化，進而影響了配送效率。

發(fā)明內(nèi)容

本發(fā)明的目的是提供一種單車多點配送線路處理方法，從而可以基于地圖數(shù)據(jù)對各個配送點進行合理地排序，有利于提高物流配送效率。

本發(fā)明的目的是通過以下技術(shù)方案實現(xiàn)的：

一種單車多點配送線路處理方法，包括：

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

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

所述采用節(jié)約算法對單點對多配送點的線路進行規(guī)劃的步驟包括：

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

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

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

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

所述預定的條件包括：

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

和/或，

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

和/或，

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

和/或，

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

所述利用遺傳算法對所述初始配送線路參數(shù)進行優(yōu)化處理的步驟包括：

根據(jù)所述初始配送線路參數(shù)創(chuàng)建初始配送線路群，所述初始配送線路群包含多種配送線路；

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

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

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

在所述初始配送線路群中選擇配送線路的步驟包括：

產(chǎn)生一個在區(qū)間[0，1]的隨機浮點數(shù)R；

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

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

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

在以新的配送替換原配送線路，或保留原配送線路后，該方法還包括：

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