蘇揚
摘 要:通過引入懲罰函數(shù),建立適應(yīng)度函數(shù)的帶時間窗車輛路徑問題的遺傳算法模型,確認先后級與編碼、得到原始集體、確定終止準則,得出帶時間窗車輛路經(jīng)問題最優(yōu)解。結(jié)果表明:遺傳算法因為提升了檢索速度,并通過不斷的輪換、穿插、變形獲取最佳適應(yīng)度,不斷完善初始解,使得在解決帶時間窗車輛路徑問題取得了很好的成效。
關(guān)鍵詞:遺傳算法;帶時間窗;車輛路徑問題
中圖分類號:TB
文獻標識碼:A
doi:10.19311/j.cnki.1672-3198.2017.03.096
0 引言
近些年隨著現(xiàn)代物流業(yè)的崛起,交通運輸方式、傳統(tǒng)批發(fā)模式和倉儲正在向現(xiàn)代物流方向轉(zhuǎn)變,特別是不同配送模式的應(yīng)用、有效控制運輸時間和成本逐漸成為城市配送車輛路徑問題的一個重要目標。車輛路徑問題一直是車輛調(diào)度研究的重要方向,也是車輛路調(diào)度研究的重大難題之一,一直是國內(nèi)外學術(shù)界和工程界關(guān)注的重要研究課題。文獻[1]第一次提出車輛路徑問題集分割,考慮到可行解集,基于先前的研究構(gòu)建了最簡單的車輛路徑問題模型。文獻[2]提出動態(tài)規(guī)劃方法用于解決車輛路徑問題的車輛數(shù)量的固定,通過遞歸方法來解決。文獻[3]提出修改搜尋啟發(fā)式算法中可以用于TSP的最近的距離搜索,構(gòu)建相關(guān)評估函數(shù),然后尋求出了一個啟發(fā)式算法用來求解帶時間窗的車輛路徑問題。
但上述研究中帶時間窗的車輛路徑問題尚未獲得完全解決。因此為了達到最低總成本費用車輛得遴派,設(shè)計貨運工具、時間、線路的組合,確保每輛車服務(wù)的對象和運輸路線,以實現(xiàn)成本的最小化,并且使整個車輛行駛路程最合理,本文通過實際案例證明多目標遺傳算法來處理車輛路徑優(yōu)化問題的有效性。結(jié)果表明:通過實際案例通過設(shè)計基于遺傳算法的程序可求解出帶有時間窗車輛路徑的最優(yōu)解。
1 帶時間窗車輛路徑問題概述
1.1 概述
帶時間窗的車輛路由問題從一般車輛路由問題演變而來,它是對一般車輛路由問題的進一步擴展,在客戶指定的時間范圍內(nèi)分配貨物的一種車輛路徑問題。基于包含在一般車輛路徑問題中的約束條件,每個客戶又增加時間窗口約束的條件。一些具有時間窗的車輛路線優(yōu)化問題允許車輛在時間窗服務(wù)時間之前或之后到達客戶時間點,但必須接受某些懲罰。具有時間窗的車輛路線問題有兩個目的:一個是最小化車輛行進的距離;二是盡量減少客戶處罰現(xiàn)象的發(fā)生。
1.2 帶時間窗車輛路徑問題解決思路
依據(jù)本文基于車輛路徑問題相關(guān)理論知識建立了帶時間窗的車輛路徑優(yōu)化模型,通過遺傳算法模型來求出帶時間窗車輛路徑問題案例的最優(yōu)解。
2 遺傳算法模型的建立
2.1 遺傳算法概述
遺傳算法是基于生物優(yōu)勝劣汰和無規(guī)律挑選的全局搜索算法,其通過挑選,交織,突變等遺傳算子來模仿生物的基本演化進程,適應(yīng)度函數(shù)用于表示個體問題的解決方案的質(zhì)量。遺傳算法提供了一個解決復(fù)雜的系統(tǒng)優(yōu)化問題的一般框架,這不依賴于問題的特定領(lǐng)域。
2.2 構(gòu)建帶時間窗的車輛路徑問題遺傳算法模型
基于上述,本文將建立一種改進的車輛路線優(yōu)化模型,在傳統(tǒng)車輛配送成本最小化為目的,考慮到客戶的交貨時間得要求,使車輛達成最短的等待時間。目標A表示車輛操作的最小總成本,目標B表示車輛操作等待延遲的最小。
在模型中,至少需要[Σm_i/Q]車輛來達成目標。從模型中我們可以知道,上述公式建立了一種多個選擇和多個約束的改進模板??蛻艨梢粤私鈺r間滿意度,使接收場所在客戶心中形成良好的效果,從而達到長期的合作效果,從而為接收區(qū)帶來長期利益,而不僅僅是短期利益。
2.3 模型的程序設(shè)計
本文的設(shè)計,使用MATLAB進行設(shè)計。由于MATLAB最小的數(shù)據(jù)結(jié)構(gòu)是一個具有不受限大小的矩陣點,并且體系中列舉了大量的處理矩陣點函數(shù),因此,應(yīng)用MATLAB語言編程遺傳算法解決帶時間窗的車輛路徑問題,人口可以看作是一個矩陣處理,也有助于對計算問題的整體考慮和描述。
3 案例介紹
某企業(yè)有1個始發(fā)地和8個收貨點,每個收貨點的需求量為mi(噸),配送時間為si(時間),車輛運輸?shù)臅r間點限定在ei,li如表1。配貨點有五輛相同的運貨車,車輛可承擔的運貨量均為6噸,車輛運行時速為40千米。
在該示例中,車輛的負載容量是均勻的,均為8t,即mi=8。由于要使用的車輛的數(shù)量M是未知的,因此有必要估計M以布置路線。在這種情況下,參與運輸?shù)能囕v的數(shù)量可以由用戶選擇,或者所需的車輛的數(shù)量可以從相關(guān)文獻中的公式確定:
實際操作中受制約束條件增加,裝貨卸貨步驟越繁瑣,η值越小,實際應(yīng)用中,人機對話可以用來確定η的值,此處定義η值為0.85。
據(jù)此,可計算N=[(2+1.5+4.5+3+1.5+4+2.5+3)/(0.85×6)]+1=4,k=1,2,3,4。
初始種群數(shù)m=3,需求點n=8,初始種群S=50,進化代100,種群數(shù)9,隨機概率0.9和驟變概率0.04,經(jīng)過100次的運行計算,結(jié)果如表2。
所有路徑都滿足時間窗口和車輛容量的約束。此時,適應(yīng)度函數(shù)f(A,B)是通過權(quán)重系數(shù)法變換的無量綱函數(shù),表2中的數(shù)據(jù)代入公式:
4 結(jié)論
使用遺傳算法后,路徑長度,負載,等待時間,延遲時間都得到了改進。一般來說,為所有客戶提供服務(wù)所需的車輛數(shù)量越少,解決方案的性能越好。對于為客戶服務(wù)的相同數(shù)量的車輛,總行駛距離,總等待時間和總延遲時間較少,解決方案性能越高??梢钥闯觯z傳算法已經(jīng)獲得了良好的結(jié)果,因為該算法通過自然數(shù)不斷更新,重新?lián)駜?yōu),交叉,突變和最佳擬合的選擇來提高搜索效率并優(yōu)化初始解。
在本章中,給出了案例的簡要介紹和分析。該模型應(yīng)用于情況并通過遺傳算法求解。這種情況的最優(yōu)解是通過用MATLAB軟件編程并通過程序運行獲得的,遺傳算法解決車輛路由問題與時間窗的優(yōu)點。
參考文獻
[1]Balinski M L, Quandt R E. On an integer program for a delivery problem[J]. Operations Research, 1964, 12(2): 300-304.
[2]Eilon S, Watson-Gandy C D T, Christofides N. Distribution management[M]. London: Griffin, 1971.
[3]李大衛(wèi),王莉.一個求解帶有時間窗口約束的車輛路徑問題的啟發(fā)式算法[J].系統(tǒng)工程,2008,16(4):20-24.
[4]周生偉,蔣同海,張榮輝.改進遺傳算法求解VRP問題[J].計算機仿真,2013,30(12):140-143.
[5]蔣波.基于遺傳算法的帶時間窗車輛路徑優(yōu)化問題研究[D].北京:北京交通大學,2010.
[6]Calvete H I, Galé C, Oliveros M J, et al. A goal programming approach to vehicle routing problems with soft time windows[J]. European Journal of Operational Research, 2007, 177(3): 1720-1733.
[7]改進遺傳算法下的車輛路徑問題研究[J].電子測試,2016,(2):56-57.
[8]蔡菂迪.改進遺傳算法在車輛路徑問題中的研究應(yīng)用[D].哈爾濱:哈爾濱工程大學,2013.