基于混合NSGA-Ⅱ的有硬時(shí)間窗的多目標(biāo)車(chē)輛路徑問(wèn)題

吳天羿，劉建永＊，許繼恒，翁 杰,昝 良

(1.解放軍理工大學(xué)，南京210007；2南京軍區(qū)工程環(huán)境質(zhì)量監(jiān)督站南京210012)

基于混合NSGA-Ⅱ的有硬時(shí)間窗的多目標(biāo)車(chē)輛路徑問(wèn)題

吳天羿1，劉建永＊1，許繼恒1，翁 杰2,昝 良1

(1.解放軍理工大學(xué)，南京210007；2南京軍區(qū)工程環(huán)境質(zhì)量監(jiān)督站南京210012)

針對(duì)有硬時(shí)間窗的多目標(biāo)車(chē)輛路徑問(wèn)題，本文采取交叉、變異和精英保留相結(jié)合的選擇策略，分別以配送總時(shí)間、調(diào)用車(chē)輛數(shù)和配送總費(fèi)用為決策目標(biāo)，設(shè)計(jì)了混合NSGA-Ⅱ.首先，為提高初始種群的優(yōu)越性，引入了時(shí)差插入法；其次，以繼承父代的優(yōu)秀基因、加快種群的尋優(yōu)速度為目的，提出了新穎交叉算子并設(shè)計(jì)了新穎交叉運(yùn)算；再次，通過(guò)子路徑變異運(yùn)算以增加種群的多樣性；最后，構(gòu)造了基于密度的Pareto排序以保證種群分布的均勻性.本文不僅描述了算法的詳細(xì)步驟，而且通過(guò)實(shí)驗(yàn)就收斂代數(shù)、目標(biāo)函數(shù)和仿真結(jié)果進(jìn)行了比較與分析.結(jié)果表明，混合NSGA-Ⅱ較之基本算法有著更快的收斂速度和更好的收斂效果.

物流工程；NSGA-Ⅱ；多目標(biāo)；車(chē)輛路徑問(wèn)題；硬時(shí)間窗；時(shí)差插入法

1 引 言

有時(shí)間窗的車(chē)輛路徑問(wèn)題[1]，是指不僅考慮客戶對(duì)貨物需求數(shù)量的約束，還要考慮客戶對(duì)貨物送到時(shí)間的要求，包括軟時(shí)間窗的VRP(Vehicle Routing Problem with SoftTime Windows, VRPSTW)和有硬時(shí)間窗的VRP(Vehicle RoutingProblem with Hard Time Windows,VRPHTW)[2].所謂VRPSTW，是指車(chē)輛允許在最晚到達(dá)時(shí)間之后到達(dá)，倘若不能在規(guī)定的時(shí)間段內(nèi)到達(dá)，給予一定的懲罰；所謂VRPHTW，則是指車(chē)輛必須在規(guī)定的時(shí)間段內(nèi)到達(dá)，不允許晚到.針對(duì)VRPTW，國(guó)內(nèi)外都進(jìn)行了卓有成效的研究.

K C Tan[3,4]等研究了多種啟發(fā)式算法以解決帶時(shí)間窗的車(chē)輛路徑問(wèn)題，包括模擬退火算法、禁忌搜索算法及遺傳算法.在基于遺傳算法研究中，結(jié)合PFIH法以自然數(shù)序列作為染色體的表示手段進(jìn)行種群的初始化；在交叉運(yùn)算中討論了多種新型交叉算子，并融合混合爬山算法、自適應(yīng)變異機(jī)制，設(shè)計(jì)了改進(jìn)遺傳算法求解VRPTW問(wèn)題.Berger J[5]等提出了并行的雙種群遺傳算法，將車(chē)輛路徑的規(guī)劃目標(biāo)分解為最小化行駛路程和最小化違反時(shí)間窗約束的時(shí)間，同時(shí)對(duì)兩組種群分別進(jìn)化搜索.Braysy O[6]等系統(tǒng)研究了帶時(shí)間窗的車(chē)輛路徑問(wèn)題，在通用啟發(fā)式算法研究方面，對(duì)遺傳等算法及其相應(yīng)的改進(jìn)研究進(jìn)行了細(xì)致剖析，詳盡例舉了近年來(lái)的最新文獻(xiàn)資料，同時(shí)對(duì)包括染色體的表示、選擇、重組和變異等有代表性的研究成果進(jìn)行了分析與比較.Alvarenga G B[7]等以行駛距離為主要目標(biāo)，通過(guò)分區(qū)兩階段構(gòu)造，設(shè)計(jì)了帶時(shí)間窗的高效的遺傳算法.在和已有算法的運(yùn)行效果比較后，顯示了改進(jìn)算法的優(yōu)越性.

謝秉磊[8]等將載重約束和時(shí)間窗約束轉(zhuǎn)化為目標(biāo)約束，建立了有軟、硬時(shí)間窗的VSP模型，在構(gòu)造最大保留交叉算子后實(shí)現(xiàn)了基于自然數(shù)編碼的遺傳算法.張麗萍[9]等建立了有時(shí)間窗車(chē)輛路徑問(wèn)題的通用數(shù)學(xué)模型，考慮時(shí)間窗和距離的權(quán)重因素，確定了分隊(duì)被服務(wù)的優(yōu)先次序；采用自然數(shù)編碼，以比例選擇和精華模型相結(jié)合的選擇策略，引入新穎交叉算子設(shè)計(jì)了改進(jìn)的遺傳算法.宋厚冰[10]等在染色體結(jié)構(gòu)中融入分組信息，并通過(guò)λ-交換局部搜索技術(shù)以改善可行解.以PMX法為交叉運(yùn)算，以兩點(diǎn)交換為變異運(yùn)算，構(gòu)造了一種更加接近最優(yōu)解的混合遺傳算法.

然而對(duì)某些特殊的車(chē)輛路徑問(wèn)題，為了盡量減少停留或暴露的時(shí)間，例如應(yīng)急救援、戰(zhàn)時(shí)物流等，有著更嚴(yán)格的時(shí)間窗約束.為此，本文將VRPHTW進(jìn)一步劃分，包括2種情況，一是有等待的VRPHTW，另一種是無(wú)等待的VRPHTW.兩者均要求車(chē)輛不能晚于分隊(duì)最晚的服務(wù)時(shí)間到達(dá)，但前者允許車(chē)輛提前到達(dá)分隊(duì)，但必須等到分隊(duì)允許服務(wù)的最早時(shí)間時(shí)才能進(jìn)行服務(wù)，而后者則不允許車(chē)輛提前達(dá)到，只有在規(guī)定的時(shí)間窗內(nèi)，才允許車(chē)輛到達(dá).在此，限定本文所研究的VRPHTW為無(wú)等待的VRPHTW.

另外，本文不僅要考慮耗時(shí)最少，有時(shí)還要顧及有限車(chē)輛的合理調(diào)度，以及車(chē)輛的運(yùn)輸費(fèi)用，所以車(chē)輛路徑問(wèn)題往往是一個(gè)多目標(biāo)優(yōu)化問(wèn)題.針對(duì)多目標(biāo)優(yōu)化問(wèn)題的算法研究，具有代表性的有小生境Pareto遺傳算法[11]、非支配排序遺傳算法[12]（Non-dominated Sorting in Genetic Algorithm,NSGA），以及改進(jìn)強(qiáng)度Pareto進(jìn)化算法[13]等.Deb等[14]在NSGA基礎(chǔ)上，提出了帶精英策略的快速非支配排序遺傳算法(NSGA-Ⅱ)，根據(jù)個(gè)體支配關(guān)系篩選優(yōu)劣，降低算法復(fù)雜度的同時(shí)保持了種群多樣性.

在上述研究基礎(chǔ)上，本文以配送時(shí)間最短、調(diào)用車(chē)輛最小和配送費(fèi)用最少等為決策目標(biāo)，研究了有硬時(shí)間窗的多目標(biāo)車(chē)輛路徑問(wèn)題，構(gòu)建了問(wèn)題的數(shù)學(xué)模型，設(shè)計(jì)了混合NSGA-Ⅱ，并通過(guò)實(shí)驗(yàn)對(duì)算法的收斂代數(shù)、目標(biāo)函數(shù)和仿真結(jié)果進(jìn)行了比較與分析.

2 模型建立

有硬時(shí)間窗的多目標(biāo)車(chē)輛路徑問(wèn)題可以描述為：若干輛汽車(chē)從一個(gè)配送中心出發(fā)，向n個(gè)分隊(duì)送貨，客戶集合為C={i},i=0,1,...,n(其中i=0代表配送中心)，完成任務(wù)后再返回配送中心.已知配送中心坐標(biāo)C0(x,y)、分隊(duì)坐標(biāo)Ci(x,y)、相應(yīng)需求量di(其中d0=0)，以及服務(wù)時(shí)間sertime，繼而可求得分隊(duì)距配送中心的距離c0i，以及兩分隊(duì)之間的距離cij.設(shè)車(chē)輛總數(shù)為K，車(chē)輛到達(dá)分隊(duì)Ci的時(shí)間為ti，在滿足車(chē)輛最大載重量W和分隊(duì)收貨時(shí)間段[ai,bi]等約束，要求選擇合理的配給方案和配送路線，以最短配送時(shí)間、最小調(diào)用車(chē)輛數(shù)和最少配送費(fèi)用完成運(yùn)輸任務(wù).

2.1 問(wèn)題假設(shè)

(1)每個(gè)分隊(duì)只接受一輛車(chē)配送，其需求量不大于車(chē)的最大載重，服務(wù)時(shí)間恒定且相同；

(2)每輛車(chē)的最大載重恒定且相同，配送貨物品種單一，不得超載行駛；

(3)調(diào)用的車(chē)輛數(shù)不得超過(guò)車(chē)輛總數(shù)，且不得重復(fù)調(diào)用；

(4)每個(gè)分隊(duì)有嚴(yán)格的時(shí)間窗約束，即車(chē)輛到達(dá)分隊(duì)的時(shí)間必須介于該分隊(duì)所允許的最早和最晚收貨時(shí)間區(qū)間之內(nèi)；

(5)每輛車(chē)的出發(fā)時(shí)間不一，但必須在優(yōu)化的出發(fā)時(shí)間窗內(nèi)出發(fā)；

(6)模型的適應(yīng)度值以車(chē)輛的配送總距離為衡量標(biāo)準(zhǔn).

2.2 參數(shù)定義

除了上述描述的參數(shù)，模型的主要參數(shù)定義及描述如表1所示.

表1 參數(shù)設(shè)置Table 1 Parameter setting

2.3 函數(shù)構(gòu)造

結(jié)合配送時(shí)間最短和調(diào)用車(chē)輛數(shù)最少的要求，建立帶硬時(shí)間窗的多目標(biāo)車(chē)輛路徑數(shù)學(xué)模型.

①配送時(shí)間最短，即所有車(chē)輛在完成任務(wù)回到配送中心后的總時(shí)間最短，包括行駛時(shí)間和服務(wù)時(shí)間.

②調(diào)用車(chē)輛數(shù)最小，即執(zhí)行配送任務(wù)的用車(chē)數(shù)最少.

③配送費(fèi)用最少，包括駕駛員的出車(chē)費(fèi)用Q1，以及車(chē)輛每公里的行駛耗費(fèi)Q2.

其中，式(4)表示車(chē)輛不得超載；式(5)表示分隊(duì)的時(shí)間窗約束；式(6)表示分隊(duì)僅能接受一輛車(chē)配送；式(7)表示兩變量的約束關(guān)系；式(8)、式(9)、式(10)表示每輛車(chē)始于配送中心又終于配送中心；式(11)表示子回路排除約束.

3 混合NSGA-Ⅱ分析

有硬時(shí)間窗的多目標(biāo)混合NSGA-Ⅱ,首先采用時(shí)差插入法進(jìn)行種群的初始化；接著采用交叉、變異和精英保留[15]相結(jié)合的選擇策略，前NC/2個(gè)子代染色體由父代NC個(gè)染色體依次首尾新穎交叉生成，中間NC/4個(gè)由NC/4個(gè)隨機(jī)父代染色體子路徑變異生成，剩余NC/4個(gè)由父代染色體前NC/4個(gè)作為精英保留生成；最后通過(guò)基于密度的Pareto排序生成子代種群.

3.1 染色體編碼

染色體中的分隊(duì)編碼信息以參數(shù)Serial{k}(i)描述，其中k表示第k輛車(chē)，i表示第k輛車(chē)所配送的第i個(gè)分隊(duì).例1，染色體Serial={(4,7,10),(8,5,9,2, 3),(6,1)}，表示該染色體有3條子路徑，10-4-7-10-0，20-8-5-9-2-3-0，30-6-1-0.

3.2 基于時(shí)差插入法的種群初始化

由于傳統(tǒng)算法中種群初始化的隨機(jī)性，致使初始種群的優(yōu)越性差距很大，極易產(chǎn)生大量無(wú)效的染色體，延遲了收斂代數(shù)和運(yùn)行時(shí)間.為提高可行解的生成概率以及加快較優(yōu)解的生成效率，混合NSGA-Ⅱ引入了時(shí)差插入法[16]進(jìn)行種群初始化，定義如下：

定義1車(chē)輛在分隊(duì)Cj（前一分隊(duì)為Ci）的最早完成時(shí)間為

EFj=max{aj+sertime,EFi+dij+sertime}定義2車(chē)輛在分隊(duì)Cj（后一分隊(duì)為Ck）的最遲開(kāi)始時(shí)間為

定義3設(shè)Cj和Ck為任意兩分隊(duì)，EFj為Cj的最早完成時(shí)間，LSk為Ck的最遲開(kāi)始時(shí)間，定義時(shí)差TDj,k為兩者之差.

定理1設(shè)Cj和Ck為路徑上的連續(xù)兩分隊(duì)，將待插分隊(duì)Ct插入Cj和Ck之間的充要條件是：

設(shè)Serial{k}為當(dāng)前可行子路徑，計(jì)劃將Ct插入到當(dāng)前路徑，則具體步驟是：

(1)首先判斷插入后車(chē)輛的載重是否超重，若滿足約束，繼續(xù)(2)；否則，進(jìn)行下一條子路徑Serial {k+1}的判斷；

(2)計(jì)算Serial{k}中每個(gè)分隊(duì)的EFi和LSi(i=1, 2,…,m),且m=length(Serial{k})；

(3)從Ct的第一個(gè)可能插入位置Serial{k}(i)、Serial{k}(i+1)開(kāi)始，計(jì)算該位置的時(shí)差TDSerial{k}(i),Serial{k}(i+1)、EFt以及插入后目標(biāo)函數(shù)f1的增量；

(4)選擇插入位置滿足定理1且目標(biāo)函數(shù)f1增量最小的位置，將Ct插入；

(5)依次更新Ct后各分隊(duì)的EFi、LSi；

(6)插入完畢，等待下一輪插入.

3.3 新穎交叉運(yùn)算

綜合考慮VRPHTW問(wèn)題的單車(chē)服務(wù)分隊(duì)數(shù)和剩余載重因素，在最大保留交叉的基礎(chǔ)上提出了新穎交叉算子Hk.其基本思路是，任選2條父代染色體，以各染色體的子路徑為交叉單元，分別將各條中Hk值最大的一段子路徑移至對(duì)方染色體的首部，刪除原染色體中重復(fù)的元素，得到兩條新染色體并對(duì)其進(jìn)行載重和時(shí)間窗約束的子路徑劃分.以子路徑Serial{k}為例，Hk定義如下：

式中 m為此子路徑所包含的節(jié)點(diǎn)數(shù)，m=length (Serial{k})；M為一常量系數(shù)，是經(jīng)過(guò)若干次實(shí)驗(yàn)得出的子路徑平均節(jié)點(diǎn)數(shù).第一項(xiàng)考慮了需求量因素，即當(dāng)前車(chē)輛的載重越大，則交叉時(shí)優(yōu)先被選擇，以盡可能實(shí)現(xiàn)車(chē)輛滿載的目標(biāo)；第二項(xiàng)考慮了當(dāng)前車(chē)輛配送的分隊(duì)數(shù)，即配送的分隊(duì)越多，則優(yōu)先被選擇，以達(dá)到減少車(chē)輛調(diào)用數(shù)的目的.

新穎交叉運(yùn)算的特點(diǎn)是保證父代染色體相同時(shí)，仍然能產(chǎn)生新的個(gè)體，滿足種群多樣性的要求，從而避免了傳統(tǒng)算法“早熟收斂”的缺點(diǎn).另外，新穎交叉運(yùn)算由于采用的是子路徑段移位方式，很好地保留了父代染色體的局部最優(yōu)解，使得父代的部分優(yōu)秀基因能夠遺傳到下一代.

3.4 子路徑變異運(yùn)算

交叉可以把父代優(yōu)秀的基因傳遞到子代，使子代具有優(yōu)于父代的性能.但當(dāng)子代不如父代個(gè)體優(yōu)良時(shí)，會(huì)產(chǎn)生早熟收斂.為增強(qiáng)種群進(jìn)化的多樣性，混合算法采用隨機(jī)子段變異運(yùn)算.以例1為例，首先合并染色體Serial的各子路徑，形成一條M個(gè)元素的自然數(shù)序列；其次，隨機(jī)地選取序列中的2段元素，交換相互的位置，形成新序列；最后，參照載重和時(shí)間窗約束進(jìn)行子路徑分解，具體示意如圖1所示.

圖1 子路徑變異運(yùn)算Fig.1 Sub-paths mutation operation

3.5 基于密度的Pareto排序

多目標(biāo)優(yōu)化算法的目的之一就是使解空間廣泛而均勻分布于問(wèn)題的非劣最優(yōu)域.NSGA-Ⅱ通過(guò)Pareto排序賦予每個(gè)個(gè)體相應(yīng)的層級(jí)，然后根據(jù)層級(jí)及其對(duì)應(yīng)的聚焦距離進(jìn)行篩選以構(gòu)造新種群.

個(gè)體的聚焦距離[17]是針對(duì)每一層非支配集定義的，是計(jì)算同一層每個(gè)個(gè)體與其相鄰兩個(gè)體在所有子目標(biāo)函數(shù)值上的差之和.設(shè)有r個(gè)子目標(biāo)，則個(gè)體i的聚焦距離為

通過(guò)選取每一層聚焦距離較大的個(gè)體優(yōu)先進(jìn)入下一代種群，保證了種群分布的均勻性和多樣性.然而聚焦距離的計(jì)算在保證種群多樣性的同時(shí)，很可能淘汰分布性較好的個(gè)體[18].以雙目標(biāo)優(yōu)化為例，如圖2所示，個(gè)體a、b很緊密，而離其他的個(gè)體比較遠(yuǎn)，則計(jì)算聚焦距離后，相對(duì)于保留a、b其中之一的理想狀況，a、b很可能同時(shí)被淘汰或者同時(shí)被保留，造成種群分布的不均勻.另外，c、d、e由于分布的比較均勻，也存在被同時(shí)淘汰的可能，影響了種群的分布性.

圖2 雙目標(biāo)個(gè)體擁擠度Fig.2 Double objective individuals crowded degree

圖3 基于密度的Pareto排序Fig.3 The Pareto sorting based on the density

在傳統(tǒng)算法Pareto排序基礎(chǔ)上，本文在精英保留過(guò)程中融入了個(gè)體密度信息（即支配某個(gè)體的所有個(gè)體數(shù)之和）作為排序依據(jù).將Pareto排序劃分為兩個(gè)階段.第一階段為，針對(duì)同一層級(jí)的個(gè)體，按密度信息進(jìn)行升序排序；第二階段為，在此基礎(chǔ)上，按個(gè)體的聚焦距離進(jìn)行降序排序.如此，基于密度的Pareto排序不僅考慮了個(gè)體的非支配排序，又結(jié)合了個(gè)體的密度信息，保證了種群分布的均勻性及收斂的穩(wěn)定性.基于密度的Pareto排序示意如圖3所示.

4 算法步驟

混合NSGA-Ⅱ流程如圖4所示.

圖4 算法流程圖Fig.4 A lgorithm flow

5 實(shí)驗(yàn)比較與分析

本文的混合NSGA-Ⅱ采用Matlab 2010b實(shí)現(xiàn)仿真，以Solomon的VRPTW標(biāo)準(zhǔn)問(wèn)題集中的RC1/ RC108數(shù)據(jù)為算例.初始取值為：分隊(duì)數(shù)n=100 (個(gè))，車(chē)輛總數(shù)K=50(輛)，最大載重W=200(噸)，種群數(shù)NC=100，迭代數(shù)iter=500，Q1=1000，Q2=2，新穎交叉算子Hk中的系數(shù)M在多次實(shí)驗(yàn)后設(shè)定為M=20.

5.1 收斂代數(shù)及目標(biāo)函數(shù)

針對(duì)配送時(shí)間、調(diào)用車(chē)輛數(shù)，以及配送費(fèi)用函數(shù)的目標(biāo)值，對(duì)比未改進(jìn)的基本NSGA-Ⅱ，混合算法通過(guò)基于時(shí)差插入法的初始化提高了解空間的優(yōu)越性；通過(guò)新穎交叉和子路徑變異，在繼承父代的優(yōu)秀基因的同時(shí)，增加了種群的多樣性；通過(guò)基于密度的Pareto排序，保持了種群分布的均勻性和收斂的穩(wěn)定性.兩算法目標(biāo)函數(shù)的迭代趨勢(shì)如圖5、圖6、圖7所示，從圖6、圖7可知，混合算法在收斂速度上較之基本算法有了極大程度的提高；從圖5可知，一定程度上避免了基本算法的早熟現(xiàn)象，且收斂效果優(yōu)于基本算法.

5.2 仿真結(jié)果

仿真實(shí)驗(yàn)后，基于基本NSGA-Ⅱ和混合NSGA-Ⅱ算法的有硬時(shí)間窗的多目標(biāo)車(chē)輛路徑規(guī)劃的示意如圖8、圖9所示，最佳方案為配送時(shí)間1 501.32，調(diào)用13輛車(chē)，耗費(fèi)15 740.

圖5 配送時(shí)間迭代趨勢(shì)及比較Fig.5 Iterative trend and comparison of transportation time

圖6 調(diào)用車(chē)輛數(shù)迭代趨勢(shì)及比較Fig.6 Iterative trend and comparison of used vehicles

圖7 配送費(fèi)用迭代趨勢(shì)及比較Fig.7 Iterative trend and comparison of transportation fee

圖8 基本算法規(guī)劃效果Fig.8 Planning effect of the basic algorithm

圖9 混合算法規(guī)劃效果Fig.9 Planning effect of the hybrid algorithm

相應(yīng)的最優(yōu)規(guī)劃方案如表2所示.

表2 規(guī)劃方案Table 2 Planning scheme

6 研究結(jié)論

本文針對(duì)有硬時(shí)間窗的多目標(biāo)車(chē)輛路徑問(wèn)題，通過(guò)基于時(shí)差插入法的種群初始化、新穎交叉、子路徑變異，以及基于密度的Pareto排序，采取交叉、變異和精英保留相結(jié)合的選擇策略，設(shè)計(jì)了混合NSGA-Ⅱ.通過(guò)對(duì)Solomon問(wèn)題集的數(shù)據(jù)測(cè)試和算法比較，驗(yàn)證了混合算法的有效性和優(yōu)越性.

[1]李軍，郭耀煌.物流配送車(chē)輛優(yōu)化調(diào)度理論與方法[M].北京:中國(guó)物資出版社,2001，2.[LI J,GUO Y H.Logis?tics vehicle scheduling theory and methods[M].Beijing: China Material Press,2001，2.]

[2]Braysy O,Gendreau M.Vehicle routing problem with time windows,Part II:Metaheuristics[J].Transportation Science,2005,39(1):119-139.

[3]K C Tan,L H Lee,Q L Zhu,et al.Heuristic methods for vehicle routing problem with time windows[J].Artificial Intelligence in Engineering,2001,15:281-295.

[4]K C Tan,L H Lee,K Ou.Artificial intelligence heuris?tics in solving vehicle routing problems with time win?dows constraints[J].Engineering Applications of Artifi?cial Intelligence,2001,14:825-837.

[5]Berger J,Barkaoui M.A parallel hybrid genetic algo?rithm for the vehicle routing problem with time windows [J].Computers and Operations Research,2004,31:2037-2053.

[6]Braysy O,Dullaert W,Gendreau M.Evolutionary algo?rithms for the vehicle routing problem with time windows [J].Journal of Heuristics,2004,10:587-611.

[7]Alvarenga G B,Mateus G R,Tomi G.A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows[J].Computers and Opera?tions Research,2007,34:1561-1584.

[8]謝秉磊,李軍,郭耀煌.有時(shí)間窗的非滿載車(chē)輛調(diào)度問(wèn)題的遺傳算法[J].系統(tǒng)工程學(xué)報(bào),2000,15(3):290-294. [XIE B L,LI J,GUO Y H.Genetic algorithm for vehicle scheduling problem of non-full loads with time windows [J].Journal of Systems Engineering,2000,15(3):290-294.]

[9]張麗萍,柴躍廷,曹瑞.有時(shí)間窗車(chē)輛路徑問(wèn)題的改進(jìn)遺傳算法[J].計(jì)算機(jī)集成制造系統(tǒng)2002,8(6):451-454. [ZHANG L P,CHAI Y T,CAO R.Improved genetic al?gorithm for vehicle routing problem with time windows [J].Computer Integrated Manufacturing Systems,2002,8 (6):451-454.]

[10]宋厚冰,蔡遠(yuǎn)利.帶時(shí)間窗的車(chē)輛路徑混合遺傳算法[J].交通運(yùn)輸工程學(xué)報(bào),2003,3(4):112-115.[SONG H B, CAI Y L.Hybrid genetic algorithm of vehicle routing with time windows[J].Journal of Traffic and Transporta?tion Engineering,2003,3(4):112-115.]

[11]Horn J,Nafpliotis N,Goldberg D E.A niched pareto ge?netic algorithm for multiobjective optimization[C].IEEE World Congress on Computational Intelligence,1994,1: 82-87.

[12]Srinivas N,Deb K.Multiobjective optimization using nondominated sorting in genetic algorithm[J].Evolution?ary Computation,1994,2:221-248.

[13]Zitzler E,Laumanns M,Thiele L.SPEA2:Improving the strength pareto evolutionary algorithm for multiobjective optimization[C].Proceedings of the Evolutionary Meth?ods for Design,Optimization and Control,2002:19-26.

[14]Deb K.A fast and elitist multi-objective genetic algo?rithm:NSGA-II[J].IEEE Trans on Evolutionary Compu?tation,2002,6(2):182-197.

[15]Thibaut V,Teodor G C,Michel G,et al.A Hybrid genet?ic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-win?dows[J].Computers&Operations Research,2013：475-489.

[16]潘立軍,符卓.求解帶時(shí)間窗取送貨問(wèn)題的遺傳算法[J].系統(tǒng)工程理論與實(shí)踐,2012,32(1):120-126.[PAN L J,FU Z.Genetic algorithm for the pickup and delivery problem with time windows[J].Systems Engineering-Theory and Practice,2012,32(1):120-126.]

[17]Deb K.A fast and elitist non-dominated sorting genetic algorithm for multi-objective optimization:NSGA-II [R].KanGAL Report 200001,Indian Institute of Tech?nology,Kanpur,India.

[18]文詩(shī)華,鄭金華.NSGA-Ⅱ中一種改進(jìn)的分布性保持策略[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(33):49-53.[WEN S H,ZHENG J H.Improved diversity maintenance strate?gy in NSGA-Ⅱ[J].Computer Engineering and Applica?tions,2010,46(33):49-53.]

Multi-objective Vehicle Routing Problem with Hard Time Windows Based on Hybrid NSGA-Ⅱ

WU Tian-yi1，LIU Jian-yong1，XU Ji-heng1，WENG Jie2，ZAN Liang1
(1.PLAUniversity of Science and Technology,Nanjing 210007,China；2 Nanjing Military Region Engineering Environmental Quality Supervision Station,Nanjing,210012)

In view of the multi-objective vehicle routing problem with hard time windows,this paper which includes the selection strategy of crossover,mutation and elite reserve designs the hybrid NSGA-Ⅱwith the purpose of short distribution time,small used vehicles and little distribution fee.Firstly,the time difference insertion algorithm is introduced to improve the initial population superiority.Secondly,the novel crossover operator and the novel crossover operation are proposed,in order to inherit the good genes from the parent population and accelerate the optimization speed.Then the sub-paths mutation is introduced to increase the population diversity.At last,the Pareto sorting is constructed based on the density to ensure the uniformity of the population distribution.The paper not only describes the algorithm’s detail steps,but also compares and analyzes the convergence algebra,the objective function and the simulation results through the experiment. The results show that the hybrid NSGA-Ⅱhas a faster convergence speed and a better convergence effect than the basic algorithm.

logistics engineering;NSGA-Ⅱ;multi-objective;vehicle routing problem;hard time windows; time difference insertion algorithm

1009-6744（2014）02-0176-08

U1

A

2013-08-05

2013-11-19錄用日期：2013-11-29

吳天羿（1984-），男，江蘇南通人，博士生.*通訊作者：506397338@qq.com