基于遺傳算法的帶時(shí)間窗車輛路徑問(wèn)題模型

蘇揚(yáng)

摘 要：通過(guò)引入懲罰函數(shù)，建立適應(yīng)度函數(shù)的帶時(shí)間窗車輛路徑問(wèn)題的遺傳算法模型，確認(rèn)先后級(jí)與編碼、得到原始集體、確定終止準(zhǔn)則，得出帶時(shí)間窗車輛路經(jīng)問(wèn)題最優(yōu)解。結(jié)果表明：遺傳算法因?yàn)樘嵘藱z索速度，并通過(guò)不斷的輪換、穿插、變形獲取最佳適應(yīng)度，不斷完善初始解，使得在解決帶時(shí)間窗車輛路徑問(wèn)題取得了很好的成效。

關(guān)鍵詞：遺傳算法；帶時(shí)間窗；車輛路徑問(wèn)題

中圖分類號(hào)：TB

文獻(xiàn)標(biāo)識(shí)碼：A

doi：10.19311/j.cnki.1672-3198.2017.03.096

0 引言

近些年隨著現(xiàn)代物流業(yè)的崛起，交通運(yùn)輸方式、傳統(tǒng)批發(fā)模式和倉(cāng)儲(chǔ)正在向現(xiàn)代物流方向轉(zhuǎn)變，特別是不同配送模式的應(yīng)用、有效控制運(yùn)輸時(shí)間和成本逐漸成為城市配送車輛路徑問(wèn)題的一個(gè)重要目標(biāo)。車輛路徑問(wèn)題一直是車輛調(diào)度研究的重要方向，也是車輛路調(diào)度研究的重大難題之一，一直是國(guó)內(nèi)外學(xué)術(shù)界和工程界關(guān)注的重要研究課題。文獻(xiàn)[1]第一次提出車輛路徑問(wèn)題集分割，考慮到可行解集，基于先前的研究構(gòu)建了最簡(jiǎn)單的車輛路徑問(wèn)題模型。文獻(xiàn)[2]提出動(dòng)態(tài)規(guī)劃方法用于解決車輛路徑問(wèn)題的車輛數(shù)量的固定，通過(guò)遞歸方法來(lái)解決。文獻(xiàn)[3]提出修改搜尋啟發(fā)式算法中可以用于TSP的最近的距離搜索，構(gòu)建相關(guān)評(píng)估函數(shù)，然后尋求出了一個(gè)啟發(fā)式算法用來(lái)求解帶時(shí)間窗的車輛路徑問(wèn)題。

但上述研究中帶時(shí)間窗的車輛路徑問(wèn)題尚未獲得完全解決。因此為了達(dá)到最低總成本費(fèi)用車輛得遴派，設(shè)計(jì)貨運(yùn)工具、時(shí)間、線路的組合，確保每輛車服務(wù)的對(duì)象和運(yùn)輸路線，以實(shí)現(xiàn)成本的最小化，并且使整個(gè)車輛行駛路程最合理，本文通過(guò)實(shí)際案例證明多目標(biāo)遺傳算法來(lái)處理車輛路徑優(yōu)化問(wèn)題的有效性。結(jié)果表明：通過(guò)實(shí)際案例通過(guò)設(shè)計(jì)基于遺傳算法的程序可求解出帶有時(shí)間窗車輛路徑的最優(yōu)解。

1 帶時(shí)間窗車輛路徑問(wèn)題概述

1.1 概述

帶時(shí)間窗的車輛路由問(wèn)題從一般車輛路由問(wèn)題演變而來(lái)，它是對(duì)一般車輛路由問(wèn)題的進(jìn)一步擴(kuò)展，在客戶指定的時(shí)間范圍內(nèi)分配貨物的一種車輛路徑問(wèn)題?；诎谝话丬囕v路徑問(wèn)題中的約束條件，每個(gè)客戶又增加時(shí)間窗口約束的條件。一些具有時(shí)間窗的車輛路線優(yōu)化問(wèn)題允許車輛在時(shí)間窗服務(wù)時(shí)間之前或之后到達(dá)客戶時(shí)間點(diǎn)，但必須接受某些懲罰。具有時(shí)間窗的車輛路線問(wèn)題有兩個(gè)目的：一個(gè)是最小化車輛行進(jìn)的距離；二是盡量減少客戶處罰現(xiàn)象的發(fā)生。

1.2 帶時(shí)間窗車輛路徑問(wèn)題解決思路

依據(jù)本文基于車輛路徑問(wèn)題相關(guān)理論知識(shí)建立了帶時(shí)間窗的車輛路徑優(yōu)化模型，通過(guò)遺傳算法模型來(lái)求出帶時(shí)間窗車輛路徑問(wèn)題案例的最優(yōu)解。

2 遺傳算法模型的建立

2.1 遺傳算法概述

遺傳算法是基于生物優(yōu)勝劣汰和無(wú)規(guī)律挑選的全局搜索算法，其通過(guò)挑選，交織，突變等遺傳算子來(lái)模仿生物的基本演化進(jìn)程，適應(yīng)度函數(shù)用于表示個(gè)體問(wèn)題的解決方案的質(zhì)量。遺傳算法提供了一個(gè)解決復(fù)雜的系統(tǒng)優(yōu)化問(wèn)題的一般框架，這不依賴于問(wèn)題的特定領(lǐng)域。

2.2 構(gòu)建帶時(shí)間窗的車輛路徑問(wèn)題遺傳算法模型

基于上述，本文將建立一種改進(jìn)的車輛路線優(yōu)化模型，在傳統(tǒng)車輛配送成本最小化為目的，考慮到客戶的交貨時(shí)間得要求，使車輛達(dá)成最短的等待時(shí)間。目標(biāo)A表示車輛操作的最小總成本，目標(biāo)B表示車輛操作等待延遲的最小。

在模型中，至少需要[Σm_i/Q]車輛來(lái)達(dá)成目標(biāo)。從模型中我們可以知道，上述公式建立了一種多個(gè)選擇和多個(gè)約束的改進(jìn)模板。客戶可以了解時(shí)間滿意度，使接收?qǐng)鏊诳蛻粜闹行纬闪己玫男Ч瑥亩_(dá)到長(zhǎng)期的合作效果，從而為接收區(qū)帶來(lái)長(zhǎng)期利益，而不僅僅是短期利益。

2.3 模型的程序設(shè)計(jì)

本文的設(shè)計(jì)，使用MATLAB進(jìn)行設(shè)計(jì)。由于MATLAB最小的數(shù)據(jù)結(jié)構(gòu)是一個(gè)具有不受限大小的矩陣點(diǎn)，并且體系中列舉了大量的處理矩陣點(diǎn)函數(shù)，因此，應(yīng)用MATLAB語(yǔ)言編程遺傳算法解決帶時(shí)間窗的車輛路徑問(wèn)題，人口可以看作是一個(gè)矩陣處理，也有助于對(duì)計(jì)算問(wèn)題的整體考慮和描述。

3 案例介紹

某企業(yè)有1個(gè)始發(fā)地和8個(gè)收貨點(diǎn)，每個(gè)收貨點(diǎn)的需求量為mi（噸），配送時(shí)間為si（時(shí)間），車輛運(yùn)輸?shù)臅r(shí)間點(diǎn)限定在ei，li如表1。配貨點(diǎn)有五輛相同的運(yùn)貨車，車輛可承擔(dān)的運(yùn)貨量均為6噸，車輛運(yùn)行時(shí)速為40千米。

在該示例中，車輛的負(fù)載容量是均勻的，均為8t，即mi=8。由于要使用的車輛的數(shù)量M是未知的，因此有必要估計(jì)M以布置路線。在這種情況下，參與運(yùn)輸?shù)能囕v的數(shù)量可以由用戶選擇，或者所需的車輛的數(shù)量可以從相關(guān)文獻(xiàn)中的公式確定：

實(shí)際操作中受制約束條件增加，裝貨卸貨步驟越繁瑣，η值越小，實(shí)際應(yīng)用中，人機(jī)對(duì)話可以用來(lái)確定η的值，此處定義η值為0.85。

據(jù)此，可計(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，需求點(diǎn)n=8，初始種群S=50，進(jìn)化代100，種群數(shù)9，隨機(jī)概率0.9和驟變概率0.04，經(jīng)過(guò)100次的運(yùn)行計(jì)算，結(jié)果如表2。

所有路徑都滿足時(shí)間窗口和車輛容量的約束。此時(shí)，適應(yīng)度函數(shù)f（A，B）是通過(guò)權(quán)重系數(shù)法變換的無(wú)量綱函數(shù)，表2中的數(shù)據(jù)代入公式：

4 結(jié)論

使用遺傳算法后，路徑長(zhǎng)度，負(fù)載，等待時(shí)間，延遲時(shí)間都得到了改進(jìn)。一般來(lái)說(shuō)，為所有客戶提供服務(wù)所需的車輛數(shù)量越少，解決方案的性能越好。對(duì)于為客戶服務(wù)的相同數(shù)量的車輛，總行駛距離，總等待時(shí)間和總延遲時(shí)間較少，解決方案性能越高。可以看出，遺傳算法已經(jīng)獲得了良好的結(jié)果，因?yàn)樵撍惴ㄍㄟ^(guò)自然數(shù)不斷更新，重新?lián)駜?yōu)，交叉，突變和最佳擬合的選擇來(lái)提高搜索效率并優(yōu)化初始解。

在本章中，給出了案例的簡(jiǎn)要介紹和分析。該模型應(yīng)用于情況并通過(guò)遺傳算法求解。這種情況的最優(yōu)解是通過(guò)用MATLAB軟件編程并通過(guò)程序運(yùn)行獲得的，遺傳算法解決車輛路由問(wèn)題與時(shí)間窗的優(yōu)點(diǎn)。

參考文獻(xiàn)

[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)，王莉.一個(gè)求解帶有時(shí)間窗口約束的車輛路徑問(wèn)題的啟發(fā)式算法[J].系統(tǒng)工程，2008，16（4）：20-24.

[4]周生偉，蔣同海，張榮輝.改進(jìn)遺傳算法求解VRP問(wèn)題[J].計(jì)算機(jī)仿真，2013，30（12）：140-143.

[5]蔣波.基于遺傳算法的帶時(shí)間窗車輛路徑優(yōu)化問(wèn)題研究[D].北京：北京交通大學(xué)，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ìn)遺傳算法下的車輛路徑問(wèn)題研究[J].電子測(cè)試，2016，（2）：56-57.

[8]蔡菂迪.改進(jìn)遺傳算法在車輛路徑問(wèn)題中的研究應(yīng)用[D].哈爾濱：哈爾濱工程大學(xué)，2013.