金巳婷 呂 閃 吳陽明 王宇瑤

(大連交通大學(xué)電氣信息工程學(xué)院 大連 116028)

基于改進(jìn)遺傳算法的物流配送路徑優(yōu)化方法研究*

金巳婷 呂 閃 吳陽明 王宇瑤

(大連交通大學(xué)電氣信息工程學(xué)院 大連 116028)

基于目前快遞行業(yè)在配送過程中成本增加,速度減慢,服務(wù)質(zhì)量下降等問題,提出一種基于改進(jìn)遺傳算法的物流配送路徑優(yōu)化方法。在基本遺傳算法的基礎(chǔ)之上作出改進(jìn),加入時間窗約束,保證算法的實時實現(xiàn);優(yōu)化遺傳操作,提高搜索能力,從而保證尋優(yōu)速度,得出最優(yōu)配送路徑。經(jīng)過仿真后證明優(yōu)化策略可行,達(dá)到對配送過程的最優(yōu)化處理。

改進(jìn)遺傳算法; 路徑優(yōu)化; 時間窗約束

1 優(yōu)化概述

物流配送路徑的優(yōu)化是傳統(tǒng)的車輛路徑優(yōu)化問題,一直是物流行業(yè)的研究熱點,也有許多思想方法被不斷地提出、改進(jìn)。但此類問題大多數(shù)較為復(fù)雜,無法在短時間內(nèi)得出最優(yōu)解,因此在現(xiàn)階段的研究中,智能搜索的方法應(yīng)用較為廣泛[1～5]。但大多數(shù)方法只能解決局部區(qū)域內(nèi)的車輛路徑問題,在解決大規(guī)模車輛路徑問題時,運(yùn)算時間過長。針對這一問題,本文提出對傳統(tǒng)遺傳算法的改進(jìn)措施,使得大規(guī)模問題更容易求解,實現(xiàn)對配送路徑優(yōu)化處理的目標(biāo)。

2 構(gòu)建VRPTW模型

在現(xiàn)代物流配送過程中,車輛路徑的優(yōu)化是一項綜合性問題,受到廣泛關(guān)注,其路線安排可以描述為:在客戶需求位置、配送中心位置以及道路情況已知的情況下,對于m輛車,N個客戶,在客戶需求的時間窗范圍[a,b]內(nèi)安排確定的運(yùn)輸路線,使得成本最少,則可以構(gòu)建如下所示的VRPTW模型[6]:

目標(biāo)函數(shù):

(1)

約束條件:

(2)

(3)

Tj+Ti≤Tko,k=1,2,…,m

(4)

在目標(biāo)函數(shù)與約束條件中,各變量定義如表1所示。

表1 變量定義

默認(rèn)車輛從配送中心出發(fā)的起始時間為0時刻,定義變量xijk與yjk默認(rèn)值為1;式(2)表示配送車輛運(yùn)載容量約束;式(3)表示配送車輛的配送服務(wù)是封閉的,最后必須回到配送中心;式(4)表示配送車輛的服務(wù)時間與行駛時間不得超過規(guī)定的返回時間范圍。

3 改進(jìn)遺傳算法求解模型

本文對基本遺傳算法[7～10]進(jìn)行改進(jìn)來求解VRPTW模型,具體實現(xiàn)步驟如下:

1) 改進(jìn)染色體編碼

將配送中心設(shè)定為編號0,各個客戶按照1,2,…,N進(jìn)行編號,每個客戶編號固定不可變更,按客戶需求安排路徑子串,并首尾添0,形成染色體。如“0250”表示路徑0→2→5→0。

2) 種群初始化

考慮到實際情況,將初始種群規(guī)模設(shè)定為60。

3) 計算適應(yīng)度值

對目標(biāo)函數(shù)取倒數(shù),實現(xiàn)最大值與最小值之間的轉(zhuǎn)換。即

(5)

4) 迭代判斷及局部搜索

設(shè)置最大進(jìn)化代數(shù),求解時判斷每次的迭代代數(shù)是否達(dá)到最大值,若達(dá)到,則停止迭代。選取最優(yōu)個體進(jìn)行局部搜索,直到獲得最優(yōu)解。

5) 遺傳選擇操作

每一次遺傳操作均選擇最優(yōu)的個體直接復(fù)制到下一代,這樣減少算法的總體操作個數(shù),提高了尋優(yōu)速度。

6) 交叉變異處理

隨機(jī)選取交叉變異位置,一般來說,交叉變異的概率均由實驗得出,保證了種群多樣性與算法收斂性,確保最優(yōu)結(jié)果順利搜尋。

4 仿真結(jié)果分析

本文所提出的優(yōu)化算法主要是將基本遺傳算法與局部搜索算法結(jié)合,根據(jù)用戶要求的時間窗范圍,在不超載的情況下,當(dāng)時間窗范圍發(fā)生變化時,以最快速度尋求最優(yōu)解,并及時調(diào)整配送路線,獲得滿足優(yōu)化目標(biāo)的最優(yōu)路徑。

1) 對其搜索效果進(jìn)行驗證,仿真時,設(shè)置種群規(guī)模為60,交叉率Pc=0.95,變異率Pm=0.05。實驗結(jié)果對比如圖1所示。

圖1 算法改進(jìn)前后適應(yīng)度值對比圖

實驗結(jié)果表明,采用改進(jìn)后的算法在進(jìn)化代數(shù)達(dá)到一定值時,適應(yīng)度值明顯提高,證明優(yōu)化后的尋優(yōu)效果明顯,尋優(yōu)能力增強(qiáng),保證了算法的實時性。

2) 當(dāng)時間窗范圍發(fā)生變化時,對算法改進(jìn)前后的配送成本以及配送時間進(jìn)行比較,客戶的位置信息與時間窗范圍如表2～3所示。

表2 客戶位置信息(km)

當(dāng)時間窗范圍發(fā)生變化后,利用改進(jìn)的遺傳算法對車輛路徑進(jìn)行重新優(yōu)化,得到兩次實驗結(jié)果為:優(yōu)化前的配送成本為367.5(元/天),優(yōu)化后的配送成本為284.7(元/天);優(yōu)化前的運(yùn)輸時間為12(小時/天),優(yōu)化后的運(yùn)輸時間為15(小時/天)。

表3 客戶時間窗范圍

試驗結(jié)果表明,優(yōu)化前后,雖然運(yùn)輸?shù)臅r間略有增加,但配送成本明顯降低,達(dá)到優(yōu)化目的。

5 結(jié)語

針對目前快遞行業(yè)的現(xiàn)狀以及客戶的不同需求建立了車輛路徑問題的優(yōu)化模型以及采用遺傳算法對模型進(jìn)行求解、仿真,實驗結(jié)果表明基于遺傳算法的路徑優(yōu)化方法能夠有效解決帶有軟時間窗的路徑優(yōu)化問題,且運(yùn)行結(jié)果可靠,證明優(yōu)化策略有效可行。

[1] 關(guān)偉,王萬平,于緒利.遺傳算法在貨物配送問題中的應(yīng)用[J].交通運(yùn)輸系統(tǒng)工程與信息,2002,2:19-23. GUAN Wei, WANG Wanping, YU Xuli. The application of Genetic Algorithms in goods distribution problem[J]. Transportation Systems Engineering and Information,2002,2:19-23.

[2] 張良智,姜華平.基于遺傳算法的交通流量組合預(yù)測[J].山東交通學(xué)院學(xué)報,2005,2:76-79. ZHANG Liangzhi, JIANG Huaping. Traffic flow combination forecasting based on genetic algorithm[J]. Journal of Shandong Jiaotong University,2005,2:76-79.

[3] 唐坤.車輛路徑問題中的遺傳算法設(shè)計[J].東華大學(xué)學(xué)報(自然科學(xué)版),2002,1:66-70. TANG Kun. Genetic algorithm design for vehicle routing problem[J]. Journal of Donghua University(Natural Sciences),2002,1:66-70.

[4] Barrie M, Baker MA, Ayechew. Agenetic algorithm for thevehicle routing problem[J]. Computers & Operations Research,2003,30:787-800.

[5] 姜大立,楊西龍,杜文,等.車輛路徑問題的遺傳算法研究[J].系統(tǒng)工程理論與實踐,1999,6:41-46. JIANG Dali, YANG Xilong, DU Wen, et al. Research on genetic algorithm of the vehicle routing problem[J]. System Engineering Theory and Practice,1999,6:41-46.

[6] 蔣波.基于遺傳算法的帶時間窗車輛路徑優(yōu)化問題研究[D].北京:北京交通大學(xué),2010. JIANG Bo. Research on the vehicle routing problem with time windows based on genetic algorithm[D]. Beijing: Beijing Jiaotong University,2010.

[7] 陳松巖,張良智,華相剛.遺傳算法在車輛路徑問題中的優(yōu)化[J].山東交通學(xué)院學(xué)報,2006,3:42-47. CHEN Songyan, ZHANG Liangzhi, HUA Xianggang. Optimization of Genetic algorithm in vehicle routing problem[J]. Journal of Shandong Jiaotong University,2006,3:42-47.

[8] 周森.基于遺傳算法的物流運(yùn)輸中的車輛路徑問題研究[D].北京:對外經(jīng)濟(jì)貿(mào)易大學(xué),2006. ZHOU Sen. Research on the vehicle routing problem in logistics transportation based on genetic algorithm[D]. Beijing: University of International Business and Economics,2006.

[9] 趙辰.基于遺傳算法的車輛路徑優(yōu)化問題研究[D].天津:天津大學(xué),2012. ZHAO Chen. Research on the optimization of vehicle routing problem based on genetic algorithm[D]. Tianjin: Tianjin University,2012.

[10] 詹孝龍.遺傳算法在帶時間窗的車輛路徑問題中的應(yīng)用[D].贛州:江西理工大學(xué),2014. ZHAN Xiaolong. The application of genetic algorithm in vehicle routing problem with time windows[D]. Ganzhou: Jiangxi University of Technology,2014.

Method of Logistics Distribution Routing Optimization Based on Improved Genetic Algorithm

JIN Siting LV Shan WU Yangming WANG Yuyao

(School of Electrical and Information Engineering, Dalian Jiaotong University, Dalian 116028)

Based on the increase of the costs during distribution in current courier industry like slow speed, decline of service quality and so on, a method of logistics distribution routing optimization is proposed based on improved genetic algorithm. Improvements are made based on the basic genetic algorithm, time windows constraint to ensure real-time implementation of the algorithm, operation of genetic is optimized, the search ability is improved to ensure optimization speed, and the optimal distribution path is obtained. After simulation, the optimization strategy is proved to be feasible, and the optimization of the distribution process is achieved.

improved genetic algorithm, routing optimization, time windows constraint Class Number TP301

2016年10月9日,

2016年11月17日

金巳婷,女,碩士,研究方向:嵌入式技術(shù)、通信及關(guān)鍵技術(shù)。呂閃,女,碩士,研究方向:信號與信息處理、通信及關(guān)鍵技術(shù)。吳陽明,男,碩士,研究方向:信號與信息處理、通信及關(guān)鍵技術(shù)。王宇瑤,女,碩士,研究方向:軌道交通信號與控制、通信及關(guān)鍵技術(shù)。

TP301

10.3969/j.issn.1672-9722.2017.04.007