劉海燕，余世欣

（成都理工大學(xué) 工程技術(shù)學(xué)院，四川 樂山614007）

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

劉海燕，余世欣

（成都理工大學(xué) 工程技術(shù)學(xué)院，四川 樂山614007）

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

配送模式；總路程模型；遺傳算法；優(yōu)化；最短路程

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

1 運行路線模式分析

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

2 模型的假設(shè)與建立

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

表1 前25個城市平面坐標

表2 后25個城市平面坐標

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

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

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

3 遺傳算法及其優(yōu)化過程

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

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

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

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

4）遺傳算法依據(jù)概率的可變規(guī)則來引領(lǐng)它的搜索方向，也就是說它是非確定性的。

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

圖1 優(yōu)化過程

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

4 仿真分析結(jié)果

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

圖2 城市分布圖

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

圖3 迭代運算過程

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

圖4 最佳路線圖

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

5 結(jié)束語

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

[1]王晶.淺談電子商務(wù)環(huán)境下企業(yè)物流管理的方法[J].現(xiàn)代商業(yè)，2014（26）:127-128.

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

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

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

[5]陳同英，遺傳算法在林木采伐作業(yè)信息管理中的應(yīng)用[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—），女，吉林長春人，碩士，講師。研究方向：信息管理、物流管理等相關(guān)的教學(xué)與科研。