基于遺傳算法的物流車輛派送管理

劉海燕，余世欣

（成都理工大學 工程技術學院，四川 樂山614007）

基于遺傳算法的物流車輛派送管理

劉海燕，余世欣

（成都理工大學 工程技術學院，四川 樂山614007）

為了提高物流車輛的運營效率和節約其成本，分析與描述了多車輛同時服務于多城市的配送模式，然后建立了4輛車配送50個城市的運輸總路程模型，接著利用遺傳算法的優化技術對運行路線進行最優性的規劃。仿真結果表明：遺傳算法經過3712次的迭代獲得最優解，50個城市分別有且只有1輛車經過，4輛車的最短總路程為812.1628公里。

配送模式；總路程模型；遺傳算法；優化；最短路程

隨著電子商務技術發展的日新月異，物流行業自身管理與運營的水平的提高也需要順勢而為，否則這塊“短板”將會制約電子商務行業整體的發展。對于物流行業，高效率是其管理的核心宗旨，而運營成本的最小化是反映管理水平的重要指標。提高交通運輸工具以及行駛線路等方面的作業水平都會對物流費用產生積極性影響[1]，因此合理規劃與管理車輛行駛路線可以有效降低運營成本。可以采用計算離散客戶之間的節約值和運用EXCEL2000中的規劃求解最佳路徑兩種方法來規劃行駛線路[2]。該方法需要通過表格數據運算處理，較為繁瑣；利用GIS（地理信息系統）技術使得企業隨時可以查看任何區域的電子地圖，從而得到有效的路徑規劃[3]，該方法相當于提供電子地圖，而對多個目的地址的路線不能進行有效規劃；還可以采用遺傳算法進行車輛路徑規劃[4]，而該文獻假設的模型只有一個中心站點，整個區域內只有1輛貨車運行。文中先針對多車輛、多節點的運行路線模式進行描述分析，然后建立50個獨立城市、4輛車共同派送的物流配送模型，最后在遺傳算法的理論基礎之上對運行路線進行優化選擇。結果表明：遺傳算法經過3712次的迭代獲得最優解，其最短總路程為812.1628公里。

1 運行路線模式分析

已知物流公司設定某一固定集散點中心，自身擁有N輛車，專門為M個固定位置的城市配送貨物（M＞N），那么物流公司管理人員面臨的問題就是：如何規劃N輛車進行物流配送的路線，使得每一個城市目的地均有且只有1輛車到達送貨，而且所有車輛完成各個城市的配送任務所往返的路程總和要最短。所以該情況不是一個簡單的電子地圖問題，而是一個數值優化問題。對于多輛汽車共同配送的情況，可以按照一定的分解策略把整個過程看成多個單輛汽車的配送路徑優化問題，這樣只要找到每輛汽車的最優配送路徑以后，然后根據相應的原則再來求和，最后就能得到整個物流配送過程的最優配送路徑規劃。下面需要先建立問題的數學模型，然后采用遺傳算法進行優化處理。

2 模型的假設與建立

假定已知物流公司設定的固定集散點中心平面坐標為（X，Y）=（64，8），自身擁有N=4輛車，專門為M=50個固定位置的城市配送貨物，這50個固定位置的城市平面坐標如表1和表2所示。

表1 前25個城市平面坐標

表2 后25個城市平面坐標

由于我們需要每一個城市目的地均有且只有1輛車到達送貨，這里把各個城市與車輛的之間的配送情況用變量Pij表示，其下標i代表第i輛車；下標j代表第j個城市。變量Pij取值如式（1）:

再根據各個城市相互之間的地理坐標數據，表示各個車輛的運輸路徑之和（即優化目標函數）為式（2）：

在式（2）中，dkij代表第k輛車經過兩個相鄰城市i、j之間的距離，而代表各個城市與車輛之間配送情況的變量Pkij有4組取值：P1ij、P2ij、P3ij、P4ij；這4組中的組合變量ij取值要各不相同。根據表1和表2的坐標數據采用遺傳算法進行求解最佳優化結果。

3 遺傳算法及其優化過程

遺傳算法原理來源于生物進化原理的靈感，它是一種全局搜索算法，其求解問題的基本思路為：把待求解的問題變量表示成“染色體”，變量的多個取值就構成一群染色體，把多個不同的“染色體”變量置于問題的“環境中”，根據適者生存、優勝劣汰的生物進化原則，在這些“染色體”中選擇適應度較高的染色體進行復制，再通過交叉和變異產生出下一代適應度更高的染色體；如此反復循環，經過若干次數的迭代，最終收斂到一個最高適應度的個體上，也就得到問題的最佳優化結果[5]。遺傳算法的特點[6]主要有以下幾點：

1）傳統搜索算法是從單個初始值進行迭代搜索最優解，這樣容易產生過早收斂。而遺傳算法從問題解的串集開始搜索，避免“早熟現象”帶來的局部最優解問題。

2）遺傳算法并行處理染色體中的不同個體基因，也就是在整個搜索空間里對所有解進行適應度計算，降低出現局部最優解的優化結果。

3）遺傳算法只是采用適應度函數值來選擇代遺傳的個體進行優化求解，不需要增加額外的搜索空間知識或其它輔助信息。由于適應度函數的定義域可以不受限制，也不會受連續可微的約束性。鑒于此因，遺傳算法的應用領域較為廣泛。

4）遺傳算法依據概率的可變規則來引領它的搜索方向，也就是說它是非確定性的。

5）遺傳算法具有自重組、自適應和自學習的3大特點。它利用求解的迭代過程中獲得的信息自行組織搜索時，適應度值較大的基因個體具有較高的遺傳到下一代的概率，并重新形成適應度更高的個體結構。優化過程如圖1所示。

圖1 優化過程

在圖1的步驟中，首先進行初始化，將表1、表2的50個城市地理坐標信息加載進來，然后創建包含40個個體的種群，每個個體包含兩個變量值，分別表示兩個城市的序號組合與是否經過該相鄰城市；這樣利用其值計算適應度，并根據適應度高（總距離最短）的染色體選出來進行交叉、變異、遷徙，然后重新計算適應度值，迭代完5 000次以后，輸出最優解。

4 仿真分析結果

先把各個已知城市的坐標數據錄入文本文檔，以供程序初始化時采用load指令加載調用，根據建立的數學模型和遺傳算法流程，編寫MATLAB試驗程序，驗證其設計的效果。

圖2 城市分布圖

根據表1和表2的坐標數據繪制成各個被配送城市的平面分布圖如圖2所示，可以看出：Y坐標方向的最大距離差在100公里左右，X坐標方向的最大距離差在120公里左右，4輛車負責完成這50個分布城市的非重復性配送任務，并返回物流公司的集散中心。

圖3 迭代運算過程

圖3 是通過遺傳算法優化路線時總距離最優解隨著迭代次數的變化過程跟蹤，可以看出：總距離由一個較大的距離數值開始急劇下降，前1段迭代過程中的收斂速度較快，然而在第607次迭代左右得到一個局部較優解，不過隨著迭代次數的增加，總距離的較優解依然在變化，也就是該遺傳算法既較好地避免了過早收斂的問題，也具備較快的收斂速度。最終在第3712次迭代處取得最優解，即最小總路程數為812.2公里。

圖4 最佳路線圖

通過遺傳算法優化求解得到的4輛車配送路線圖如圖4所示。在圖4中，4輛物流車從集散點出發，分別沿著4條不同的線路對50個獨立城市進行配送，各個城市被完全覆蓋，而且只有1輛車經過，最遠路程的是第4輛車，最近路程是第2輛車，統計出4輛車的總路程為812.1628公里，相應的迭代次數為3712次，其值與圖3的最優迭代解相吻合。

5 結束語

文中從降低物流車輛運營成本的角度出發，分析與描述了多車輛共同派送于多城市的運行路線模式，然后建立了相應的物流配送模型，接著利用遺傳算法的優化技術對運行路線進行最優性的規劃選擇，仿真結果表明：4輛車分別沿著4條不同的線路完成50個城市的配送任務，各個城市有且只有1輛車經過，4輛車的總路程為812.1628公里。

[1]王晶.淺談電子商務環境下企業物流管理的方法[J].現代商業，2014（26）:127-128.

[2]易華平，淺談兩種配送路線求解方法的比較[J].商場現代化，2007.12，（524）:110-111

[3]王鈺，物流信息技術管理方法研究[J].數字技術與應用，2015（10）:80-80

[4]付瑞，張紀會.基于遺傳算法的電子商務物流配送研究[J].青島大學學報（工程技術版），2015，30（1）:81-86

[5]陳同英，遺傳算法在林木采伐作業信息管理中的應用[J].運籌與管理，2001，10（4）：96-101

[6]百度百科，遺傳算法[EB/OL].http://baike.baidu. com/linkurl=BTbVRoxHmTNjVe7DJFPHsXoJDb 3R4TrvfvgvmWyuGH4gMlp6oz0IqhrjWF7KyEAtdF dCCqkdAx4QKBcwec2ziK.

Management for delivery of logistics vehicle based on genetic algorithm

LIU Hai-yan，YU Shi-xin
（College of Engineering and Technology，Chengdu University of Technology，Leshan 614007，China）

In order to improve the logistics vehicle operating efficiency and save the cost，analysis and describes the distribution pattern of multiple vehicles at the same time in the service of the multiple cities，then sets up the distribution model of the total transportation distance of 4 cars which distribute for 50 cities，then plans the running routes by using the genetic algorithm's optimization technique.The simulation results shows that Genetic algorithm （ga）obtains the optimal solution after 3712 times iterations，50 cities have respectively only 1 car by passing，and the shortest total distance of 4 cars passing is 812.1628 km.

distribution mode；the total distance model；genetic algorithm；optimization；the shortest distance

TN0

：A

：1674-6236（2017）02-0037-03

2016-01-27稿件編號：201601248

劉海燕（1979—），女，吉林長春人，碩士，講師。研究方向：信息管理、物流管理等相關的教學與科研。