[發明專利]一種有效的車輛路徑優化系統

有效

• 申請號: 201710687033.1
• 申請日: 2017-08-11
• 公開（公告）號: CN107292460B
• 公開（公告）日: 2020-10-30
• 發明（設計）人: 潘榮蘭
• 申請（專利權）人: 重慶博尼施科技有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08;G06N3/12
• 代理公司: 北京華識知識產權代理有限公司 11530
• 代理人: 趙永強

1.一種有效的車輛路徑優化系統，其特征是，包括數據獲取模塊、算法執行模塊和路徑輸出模塊，所述數據獲取模塊用于獲取車輛路徑優化所需的相關信息，所述算法執行模塊采用改進的遺傳算法對車輛路徑進行優化，具體包括：

步驟1，采用基于客戶全排列的自然數編碼方式，初始化生成染色體群，并確保其可行性；

步驟2，根據適應度函數計算初始群體中各個體的適應度值，并保存適應度值最大個體的適應度值和染色體；

步驟3，在指定的遺傳代數內進行遺傳操作，通過隨機選擇、交叉和變異操作，從而產生一群更適應環境的個體；

步驟4，執行條件判定，用于設定終止條件，當遺傳算法滿足終止條件時即停止算法運行；所述算法執行模塊的步驟2根據適應度函數計算初始群體中各個體的適應度值，其采用一種改進的適應度函數，定義有k個配送點，則適應度函數為：

式中，d(r_m,r_n)為第m個配送點到第n個配送點之間的距離，d_max為路徑配送的最大配送距離，r₀表示物流配送中心，r_k表示最后一個配送點，d表示配送路徑的總距離，δ和μ分別為配送距離和時間效應成本的權重，T表示配送的時間效應成本，L_i為第i個配送點的規定送達時間，t_i為第i個點的實際送達時間，P為允許時間誤差，c₁為時間懲罰系數；所述路徑輸出模塊用于輸出遺傳算法終止后所得的最優車輛路徑。

2.根據權利要求1所述的一種有效的車輛路徑優化系統，其特征是，所述數據獲取模塊獲取的相關信息包括：客戶點的數目、配送中心和客戶點的位置坐標。

3.根據權利要求2所述的一種有效的車輛路徑優化系統，其特征是，算法執行模塊中步驟3在制定的遺傳代數內進行如下遺傳操作，具體為：

a.通過選擇操作產生新一代個體；

b.采用改進的交叉概率算法計算剩余個體的交叉率p_c，并且對這些剩余個體以計算所得的交叉率p_c進行交叉操作；

式中，f_max表示種群最大適應度值，f_avg表示種群平均適應度值，f′表示要交叉的個體適應度值，k₁和k₃為常數值，且0k₁,k₃1,f_min表示種群最小適應度值；

c.利用改進的變異概率算法計算剩余個體的變異率p_m，并且對這些個體以概率p_m進行變異操作；

式中，f_min表示種群最小適應度值，f_max表示種群最大適應度值，f_avg表示種群平均適應度值，f″表示要變異的個體適應度值，k₂和k₄為常數值，且0k₂,k₄1。