基于改進遺傳算法的物流配送路徑優化方法研究*

金巳婷 呂 閃 吳陽明 王宇瑤

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

基于改進遺傳算法的物流配送路徑優化方法研究*

金巳婷 呂 閃 吳陽明 王宇瑤

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

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

改進遺傳算法; 路徑優化; 時間窗約束

1 優化概述

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

2 構建VRPTW模型

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

目標函數:

(1)

約束條件:

(2)

(3)

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

(4)

在目標函數與約束條件中,各變量定義如表1所示。

表1 變量定義

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

3 改進遺傳算法求解模型

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

1) 改進染色體編碼

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

2) 種群初始化

考慮到實際情況,將初始種群規模設定為60。

3) 計算適應度值

對目標函數取倒數,實現最大值與最小值之間的轉換。即

(5)

4) 迭代判斷及局部搜索

設置最大進化代數,求解時判斷每次的迭代代數是否達到最大值,若達到,則停止迭代。選取最優個體進行局部搜索,直到獲得最優解。

5) 遺傳選擇操作

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

6) 交叉變異處理

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

4 仿真結果分析

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

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

圖1 算法改進前后適應度值對比圖

實驗結果表明,采用改進后的算法在進化代數達到一定值時,適應度值明顯提高,證明優化后的尋優效果明顯,尋優能力增強,保證了算法的實時性。

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

表2 客戶位置信息(km)

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

表3 客戶時間窗范圍

試驗結果表明,優化前后,雖然運輸的時間略有增加,但配送成本明顯降低,達到優化目的。

5 結語

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

[1] 關偉,王萬平,于緒利.遺傳算法在貨物配送問題中的應用[J].交通運輸系統工程與信息,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] 張良智,姜華平.基于遺傳算法的交通流量組合預測[J].山東交通學院學報,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] 唐坤.車輛路徑問題中的遺傳算法設計[J].東華大學學報(自然科學版),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].系統工程理論與實踐,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] 蔣波.基于遺傳算法的帶時間窗車輛路徑優化問題研究[D].北京:北京交通大學,2010. JIANG Bo. Research on the vehicle routing problem with time windows based on genetic algorithm[D]. Beijing: Beijing Jiaotong University,2010.

[7] 陳松巖,張良智,華相剛.遺傳算法在車輛路徑問題中的優化[J].山東交通學院學報,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] 周森.基于遺傳算法的物流運輸中的車輛路徑問題研究[D].北京:對外經濟貿易大學,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] 趙辰.基于遺傳算法的車輛路徑優化問題研究[D].天津:天津大學,2012. ZHAO Chen. Research on the optimization of vehicle routing problem based on genetic algorithm[D]. Tianjin: Tianjin University,2012.

[10] 詹孝龍.遺傳算法在帶時間窗的車輛路徑問題中的應用[D].贛州:江西理工大學,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日

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

TP301

10.3969/j.issn.1672-9722.2017.04.007