基于差分進化算法的卷煙配送路徑優化研究

2020-09-10 01:53:49李致遠王璐張磊王晉冰張杰林輝輪

交通科技與管理 2020年4期

李致遠王璐張磊王晉冰張杰林輝輪

摘要：本文提出了解決卷煙配送問題的差分進化算法。在繼承了傳統的遺傳算法解決路徑優化問題的諸多算法優點基礎上，差分進化算法具有更強的魯棒性，并且逼近效果更加顯著。由于卷煙配送問題有時間、精確度需求，因此，運用差分進化算法解決該問題具有顯著優勢。

關鍵詞：卷煙配送;路徑優化;差分進化算法

中圖分類號：TP18 文獻標識碼：A

0 引言

我國煙草公司客戶數量眾多、分布不均勻且客戶訂單大小有差異。因此煙草公司在進行卷煙配送時，如果事先沒有合理的卷煙配送路徑安排，就會導致運輸頻次過高以及資源浪費。因此，如何合理優化卷煙配送路徑，具有很大的現實意義。本文以貴州省煙草公司貴陽市公司為例，對其卷煙配送路徑選擇系統進行了優化，建立了精度、效率更高的卷煙配送路徑選擇模型，并采用差分進化算法進行模型求解。

1 卷煙配送路徑優化問題描述及數學模型

1.1 問題描述

VRP配送問題為大規模組合優化問題，而且隨著問題求解規模擴大而呈指數式增長。一般情況下，卷煙配送問題涉及幾千個配送節點，配送網絡路徑組合更是復雜，因此，采用經典VRP算法直接求解相當困難。考慮到卷煙配送問題的規律性和區域特點，對卷煙配送問題采用基于區域劃分的差分進化算法，將復雜的卷煙配送問題轉化為簡單的VRP問題求解。

1.2 數學模型

1.2.1 模型轉化

第一步：建立配送點區域單元集合，在同一區域單元，各配送點之間路徑距離相近，一般以相鄰多個街道作為一個區域單元，區域單元范圍以區域范圍內包含配送點的數量和統計配送量的多少來確定。區域單元集合的構建可以通過對現有配送方案進行聚類，構建初始區域單元集合，然后通過人工調整得到合理的區域單元集合。其中，采用正半矢公式進行兩配送點之間距離計算。

式中，和表示兩點的緯度，和表示兩點的經度，r表示地球半徑。

用該原則將貴陽市公司客戶進行區域劃分，結果如圖1所示。

第二步：針對每個區域，采用聚類算法將距離相近的客戶“打包”為一個配送域，并計算出每個配送域的中心位置及訂單總量。

以已劃分的花溪區為例，將該區域內相鄰的顧客劃分為不同的配送域，結果如圖2所示。

將每個配送域看作一個訂單，采用相關路徑規劃啟發式算法確定配送車輛及配送路線。針對每個配送域再次進行路徑規劃，最終求得整個區域所有客戶的具體配送方案。

1.2.2 傳統VRP模型

該模型中，目標函數（2）表示最小化車輛行駛路程，公式（3）表示所有配送域必須被訪問，且每個配送域只能訪問一次;公式（4，5，6）表示所有車輛都從起始點出發并最終回到起始點;公式（7）表示每輛車訪問的配送域訂單貨物總量不得超過車輛荷載量（若某個配送域的訂單貨物超出載荷量，可在第二階段的路徑規劃中安排多輛車進行配送）;公式（7）定義所有車輛實際運送卷煙量不得超過其規定載重;公式（8）定義決策變量為0-1整數變量。

2 模型求解

由于構建的模型對應的決策變量很多，若用傳統的遺傳算法對該實例中構建的VRP模型進行求解，則需要花費大量時間，且求出的結果精度較低。因此，本文提出了使用差分進化算法進行模型求解。通過進化個體編碼與解碼、初始種群產生、變異和交叉得出最優路徑。

3 實驗結果與分析

3.1 實驗結果

本文采用貴州省煙草公司貴陽分公司的數據，并結合提出的差分進化算法，對該公司卷煙配送路徑選擇模型進行求解，并將求解得出的配送路徑與現有配送路徑進行對比。

首先采用差分進化算法對各個配送域之間的配送路徑進行求解，所得結果如圖3所示。接著可采用同樣的方法對每個配送域中的客戶進行具體的路徑規劃，從而最終得到所有客戶的具體配送線路，所得結果如圖4所示。

最后用同樣算法算出每個區域的具體卷煙配送路徑（如圖5），并與原有的卷煙配送路徑進行比較（如圖6）。

3.2 結果分析

模擬仿真實驗結果表明，本研究所規劃的配送路線遠優于現有固定配送線路，并且更加靈活，節約了大量運輸成本，具有一定的應用潛力。

本文研究不足在于：目前本研究中計算客戶兩兩之間的距離是根據經緯度計算出兩點之間的直線距離，與實際的路網行駛距離會存在一定偏差。同時所采用的聚類算法是根據客戶位置進行自動劃分，未考慮道路實際情況，如采用人工標注將會更加準確。

參考文獻：

[1]齊佳婷.城市農產品冷鏈物流配送車輛路徑問題研究[D].浙江理工大學，2016.