劉　云，張惠珍

(上海理工大學(xué)　管理學(xué)院，上?！?00093)

多目標(biāo)帶時(shí)間窗的車(chē)輛路徑問(wèn)題的單親遺傳混合蟻群算法

劉云，張惠珍

(上海理工大學(xué)管理學(xué)院，上海200093)

摘要：考慮具有最大等待時(shí)間、最大運(yùn)輸時(shí)間限制且?guī)r(shí)間窗的車(chē)輛路徑問(wèn)題，建立了以車(chē)輛行駛路徑最短和使用車(chē)輛數(shù)最小為目標(biāo)的數(shù)學(xué)模型。將單親遺傳算法和基本蟻群算法相結(jié)合，使其優(yōu)勢(shì)互補(bǔ)，并利用單親遺傳算法的特點(diǎn)，構(gòu)建出兩種求解該問(wèn)題的單親遺傳混合蟻群算法，分別為：?jiǎn)吸c(diǎn)單親遺傳混合蟻群算法和多點(diǎn)單親遺傳混合蟻群算法。測(cè)試算例的結(jié)果表明：求解多目標(biāo)帶時(shí)間窗的車(chē)輛路徑問(wèn)題時(shí)，與基本蟻群算法相比，單親遺傳混合蟻群算法具有計(jì)算效率高、收斂性好等優(yōu)點(diǎn)，尤其單點(diǎn)單親遺傳混合蟻群算法不僅具有較好的計(jì)算性能，而且具有較高的穩(wěn)定性。

關(guān)鍵詞：交通工程；車(chē)輛路徑問(wèn)題；單親遺傳混合蟻群算法；多目標(biāo)；時(shí)間窗

0引言

帶時(shí)間窗的車(chē)輛路徑問(wèn)題[1](Vehicle Routing Problem with Time Windows, VRPTW)最早由Savelsbergh提出，是在車(chē)輛路徑問(wèn)題(Vehicle Routing Problem, VRP)的基礎(chǔ)上增加了客戶(hù)接受配送服務(wù)的時(shí)間窗要求，較VRP更貼近實(shí)際生活。VRPTW已被證實(shí)是一個(gè)NP難問(wèn)題，當(dāng)問(wèn)題規(guī)模較大時(shí)，精確算法難以求出其最優(yōu)解，因此，國(guó)內(nèi)外很多學(xué)者利用智能啟發(fā)式算法來(lái)尋找其滿意解。常見(jiàn)的求解VRPTW的智能啟發(fā)式算法有遺傳算法[2-3]、蟻群算法[4-7]、模擬退火算法[8-9]、粒子群算法[10-11]等。然而，迄今為止，這些智能啟發(fā)式算法大都被用于求解單目標(biāo)的車(chē)輛路徑問(wèn)題，在多目標(biāo)車(chē)輛路徑優(yōu)化問(wèn)題中涉及的并不多。隨著電子商務(wù)的迅速發(fā)展，物流配送任務(wù)日益龐大和復(fù)雜，追逐單一目標(biāo)最優(yōu)已經(jīng)無(wú)法滿足商家的發(fā)展要求，因此研究多目標(biāo)的車(chē)輛路徑問(wèn)題迫在眉睫。

多目標(biāo)車(chē)輛路徑問(wèn)題是指：給定若干具有一定需求量的客戶(hù)，若干具有一定裝載能力的車(chē)輛從配送中心出發(fā)，為客戶(hù)進(jìn)行配送服務(wù)后回到配送中心，同時(shí)使總路程最短、車(chē)輛數(shù)最少、費(fèi)用最省等多個(gè)目標(biāo)達(dá)到最優(yōu)。與帶時(shí)間窗的單目標(biāo)車(chē)輛路徑問(wèn)題相比，多目標(biāo)車(chē)輛路徑問(wèn)題更接近于現(xiàn)實(shí)生活，對(duì)實(shí)際問(wèn)題更有指導(dǎo)意義。本文所研究的多目標(biāo)VRPTW不僅要求完成配送任務(wù)的總路程最短和車(chē)輛數(shù)最少，而且車(chē)輛在配送過(guò)程中的等待時(shí)間和運(yùn)輸時(shí)間不能超過(guò)一定限制，本文將該問(wèn)題稱(chēng)之為“具有最大等待時(shí)間和運(yùn)輸時(shí)間限制的多目標(biāo)帶時(shí)間窗的車(chē)輛路徑問(wèn)題”。

單親遺傳算法[12](Partheno-Genetic Algorithm, PGA)取消了傳統(tǒng)遺傳算法(Genetic Algorithm, GA)中的交叉算子，僅需一個(gè)父代，因此即使種群中的個(gè)體均相同，也不會(huì)影響遺傳操作，降低了對(duì)種群多樣性的要求。此外，單親遺傳算法在尋優(yōu)效率和“早熟收斂”上都較傳統(tǒng)遺傳算法具有優(yōu)勢(shì)[13]。而蟻群算法(Ant Colony Algorithm, ACA)具有魯棒性強(qiáng)、可以進(jìn)行分布式計(jì)算，易與其他算法有效結(jié)合等優(yōu)點(diǎn)，但其容易陷入局部最優(yōu)。本文針對(duì)具有最大等待時(shí)間、最大運(yùn)輸時(shí)間限制的多目標(biāo)帶時(shí)間窗的車(chē)輛路徑問(wèn)題，在單親遺傳算法和蟻群算法的基礎(chǔ)上，吸收這兩種方法的長(zhǎng)處和優(yōu)勢(shì)，克服它們的短處和缺陷，進(jìn)而提出混合型搜索多目標(biāo)車(chē)輛路徑問(wèn)題的啟發(fā)式優(yōu)化算法，并通過(guò)測(cè)試算例驗(yàn)證其求解性能。

1具有最大等待時(shí)間和運(yùn)輸時(shí)間限制的多目標(biāo)VRPTW

1.1問(wèn)題描述

本文研究的是總路程和車(chē)輛數(shù)均受限的多目標(biāo)VRPTW，該問(wèn)題不僅要求配送車(chē)輛完成配送任務(wù)所行駛的總路程最短，而且要求在總路程最短的基礎(chǔ)上完成任務(wù)所使用的車(chē)輛數(shù)最少。假設(shè)所有車(chē)輛都相同且容量相等，所探討的問(wèn)題也必須同時(shí)要滿足如下條件：

(1)服務(wù)約束：每輛車(chē)可以服務(wù)多個(gè)客戶(hù)，但一個(gè)客戶(hù)只能由一輛車(chē)服務(wù)。

(2)配送中心約束：所有車(chē)輛由單一配送中心出發(fā)，配送完路徑上所有的客戶(hù)后返回到配送中心。

(3)裝載量約束：每條路徑上所有客戶(hù)的需求量之和不能超過(guò)車(chē)輛的最大載重量WE。

(4)最大運(yùn)輸時(shí)間約束：每輛車(chē)的運(yùn)輸時(shí)間(行駛時(shí)間、服務(wù)時(shí)間以及等待時(shí)間之和)不能超過(guò)最大運(yùn)輸時(shí)間T。

(6)最大等待時(shí)間約束：車(chē)輛給任一客戶(hù)配送貨物時(shí)的等待時(shí)間不能超過(guò)W，車(chē)輛若早于客戶(hù)最早服務(wù)時(shí)間ei到達(dá)，則需等待一段時(shí)間，等待時(shí)間過(guò)長(zhǎng)會(huì)影響車(chē)輛的配送效率，增加企業(yè)成本。

1.2符號(hào)定義與數(shù)學(xué)模型

下面對(duì)具有最大等待時(shí)間和運(yùn)輸時(shí)間限制的多目標(biāo)帶時(shí)間窗的車(chē)輛路徑問(wèn)題建立數(shù)學(xué)模型。

決策變量：

數(shù)學(xué)模型：

(1)

(2)

S.T

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

模型中，式(1)和式(2)分別為要求總路程和車(chē)輛數(shù)最少的目標(biāo)函數(shù)；式(3)為車(chē)輛載重量限制；式(4)表示每一個(gè)客戶(hù)只能由一輛車(chē)服務(wù)；式(5)表示從配送中心出發(fā)的車(chē)輛在完成配送任務(wù)后要返回配送中心；式(6)表示車(chē)輛在服務(wù)完客戶(hù)i后緊接著服務(wù)客戶(hù)j；式(7)表示車(chē)輛在服務(wù)完客戶(hù)j之前只服務(wù)客戶(hù)i；式(8)表示消除子回路，式(6)～式(8)共同形成可行回路；式(9)為車(chē)輛運(yùn)行時(shí)間限制；式(10)為到達(dá)每個(gè)客戶(hù)的時(shí)間表達(dá)式；式(11)為時(shí)間窗限制；式(12)為等待時(shí)間表達(dá)式。

2單親遺傳混合蟻群算法的設(shè)計(jì)

2.1單親遺傳算法

單親遺傳算法的遺傳算子包括基因重組算子和基因突變算子?；蛑亟M算子又可分為基因換位算子、基因移位算子以及基因倒位算子。單親遺傳算法所有的遺傳操作都可分為單點(diǎn)基因操作和多點(diǎn)基因操作。本文所用的遺傳算子為單、多點(diǎn)基因換位算子和單、多點(diǎn)基因移位算子，現(xiàn)分別介紹如下：

(1)基因換位算子

基因換位是指交換一條染色體中某兩個(gè)(些)基因的位置[14]，被交換的基因位置隨機(jī)生成。

單點(diǎn)基因換位：

基因移位是指將一條染色體中某個(gè)(些)子串中基因的位置依次后移，并把該子串中的最后一個(gè)基因移到最前面的位置[14]，子串長(zhǎng)度隨機(jī)生成。

單點(diǎn)基因移位：

多點(diǎn)基因移位：

2.2蟻群算法

蟻群算法是意大利學(xué)者M(jìn)．Dorigo等人通過(guò)模擬蟻群覓食行為提出的一種基于種群的模擬進(jìn)化算法。蟻群算法采用分布式并行計(jì)算機(jī)制，易與其他方法結(jié)合，具有較強(qiáng)的魯棒性等特點(diǎn)。但該算法亦有搜索時(shí)間較長(zhǎng)，易陷入局部最優(yōu)的缺點(diǎn)。路徑上信息素的更新和螞蟻狀態(tài)的轉(zhuǎn)移是蟻群算法的重要組成部分。本文針對(duì)基本蟻群算法收斂速度慢和易陷入局部最優(yōu)等缺點(diǎn)，螞蟻的狀態(tài)轉(zhuǎn)移規(guī)則采用了確定性選擇和偽隨機(jī)比例選擇相結(jié)合的方法，以便有效抑制算法的早熟現(xiàn)象，并加快算法的求解速度。

2.2.1信息素更新規(guī)則

本文利用式(13)～(15)對(duì)客戶(hù)i和客戶(hù)j路徑上的信息素進(jìn)行更新：

(13)

(14)

(15)

2.2.2狀態(tài)轉(zhuǎn)移規(guī)則

本文采用了確定性選擇和偽隨機(jī)比例選擇相結(jié)合的方法確定螞蟻的狀態(tài)轉(zhuǎn)移，即當(dāng)螞蟻位于客戶(hù)i時(shí)，會(huì)以概率q0使用確定性選擇規(guī)則或以概率1-q0使用偽隨機(jī)比例選擇規(guī)則(pseudo random proportional action choice rule)選擇下一個(gè)客戶(hù)j。

確定性選擇規(guī)則：

(16)

偽隨機(jī)比例規(guī)則：

(17)

2.3單親遺傳混合蟻群算法的步驟

將單親遺傳算法和蟻群算法相融合，本文構(gòu)建了求解多目標(biāo)車(chē)輛路徑問(wèn)題(1)～(12)的單親遺傳混合蟻群算法，其算法框圖如圖1所示。

圖1　算法流程圖Fig.1　Flowchart of algorithm

單親遺傳混合蟻群算法的優(yōu)化步驟如下：

步驟1：初始化各參數(shù)，確定螞蟻數(shù)m和最大迭代次數(shù)NC_max。

步驟2：m只螞蟻從配送中心出發(fā)。對(duì)于螞蟻k，按照式(16)、(17)計(jì)算其轉(zhuǎn)移概率，確定下一個(gè)服務(wù)的客戶(hù)j，若客戶(hù)j滿足載重量(3)、車(chē)輛運(yùn)行時(shí)間(9)、 時(shí)間窗(11)、等待時(shí)間(12)等約束條件，則將客戶(hù)j加入螞蟻k的禁忌表中;否則，車(chē)輛回到配送中心，并重新啟動(dòng)下一輛車(chē)執(zhí)行未完成的配送任務(wù)。

步驟3：所有客戶(hù)服務(wù)結(jié)束后，螞蟻完成一次周游，此時(shí)得到問(wèn)題的一個(gè)可行解。更新螞蟻數(shù)k=k+1，若k≤m，轉(zhuǎn)步驟2；否則，轉(zhuǎn)步驟4。

步驟4：從m只螞蟻的禁忌表中選出最優(yōu)路徑，并對(duì)其進(jìn)行單親遺傳操作(采用不同的基因移位、基因換位操作，即可產(chǎn)生不同的單親遺傳混合蟻群算法),即將該最優(yōu)解路徑A看成一個(gè)染色體，按一定的概率q對(duì)其作移位或換位變換，生成一條新路徑B。

步驟5：若路徑B的目標(biāo)函數(shù)值優(yōu)于路徑A的目標(biāo)函數(shù)值，則更新最優(yōu)路徑和最優(yōu)解，同時(shí)將禁忌表中路徑A更新為路徑B，以新的禁忌表更新信息素；否則，最優(yōu)路徑、最優(yōu)解、禁忌表保持不變。

步驟6：根據(jù)信息素更新規(guī)則，式(13)～(15)對(duì)信息素進(jìn)行更新，并清空禁忌表。更新迭代次數(shù)NC=NC+1 ，若NC≤NC_max，轉(zhuǎn)步驟2。

步驟7：輸出當(dāng)前最優(yōu)解和最優(yōu)路徑。

3實(shí)例計(jì)算

為了測(cè)試算法的計(jì)算性能，本文利用基本蟻群算法、單點(diǎn)單親遺傳混合蟻群算法和多點(diǎn)單親遺傳混合蟻群算法對(duì)文獻(xiàn)[15]中的測(cè)試算例進(jìn)行求解，并對(duì)比分析各種算法的求解效率與精度。

從這一土地流轉(zhuǎn)的案例中，我們可以看到，農(nóng)村土地流轉(zhuǎn)實(shí)踐并非只要按照《土地承包法》的法律條文和完全的市場(chǎng)競(jìng)爭(zhēng)原則，承包人與農(nóng)戶(hù)就可以面對(duì)面地討價(jià)還價(jià)并達(dá)成流轉(zhuǎn)協(xié)議。土地流轉(zhuǎn)的過(guò)程其實(shí)是一個(gè)復(fù)雜的社會(huì)建構(gòu)過(guò)程，在這一過(guò)程中，資本角色、政府角色和農(nóng)戶(hù)角色都可能要根據(jù)特定的社會(huì)情境選擇各自的行動(dòng)策略，并圍繞土地流轉(zhuǎn)目標(biāo)建構(gòu)起流轉(zhuǎn)優(yōu)先權(quán)的社會(huì)意義，也就是要賦予農(nóng)村土地權(quán)屬和邊界的變動(dòng)以合適的理由或解釋?zhuān)礊槭裁匆M(jìn)行土地流轉(zhuǎn)，為什么要把土地流轉(zhuǎn)給特定承包者。

測(cè)試算例中各參數(shù)設(shè)定情況如下：利用最大載重量WE為8 t的最少車(chē)輛向20個(gè)客戶(hù)(客戶(hù)數(shù)據(jù)如表1所示)提供配送服務(wù)，每輛車(chē)的最大運(yùn)行時(shí)間T為8 h，車(chē)輛等待時(shí)間wi上限為4.5 h(為避免初次迭代時(shí)無(wú)法確定第一個(gè)客戶(hù)，故等待時(shí)間上限為客戶(hù)中最遲的時(shí)間窗開(kāi)始時(shí)刻，即為客戶(hù)編號(hào)10的時(shí)間窗開(kāi)始時(shí)刻4.5 h)，車(chē)輛的運(yùn)行速度v保持恒定為40 km/h。配送中心坐標(biāo)位置為(70 km，70 km)，配送中心的需求量、服務(wù)時(shí)間、時(shí)間窗均為0。

表1　客戶(hù)數(shù)據(jù)

本文利用MATLAB R2011a 對(duì)基本蟻群算法、單點(diǎn)單親遺傳混合蟻群算法和多點(diǎn)單親混合蟻群算法進(jìn)行編程實(shí)現(xiàn)，3種算法在 Intel Core i3-2310M 2.10 GHz (6.00GB RAM)，操作系統(tǒng)為Win7的環(huán)境下運(yùn)行。為便于比較，3種算法中各參數(shù)設(shè)定相同的數(shù)值，參數(shù)設(shè)定情況為：螞蟻數(shù)m=20，最大迭代次數(shù)NC_max=200，信息素?fù)]發(fā)系數(shù)ρ=0.1，信息素強(qiáng)度Q= 15，信息素因子α=1，顯著性因子β=1，時(shí)間窗緊度因子γ=2，節(jié)約量因子ε= 3，轉(zhuǎn)移概率q0=0.6，換位算子概率q=0.7。

3種算法隨機(jī)運(yùn)行25次，優(yōu)化結(jié)果如表2所示?；鞠伻核惴ㄇ蟪龅淖顑?yōu)路徑長(zhǎng)度為1 201.923 km,最優(yōu)車(chē)輛數(shù)為8輛，算法運(yùn)行平均耗時(shí)為65.84 s；單點(diǎn)單親遺傳混合蟻群算法求出的最優(yōu)路徑長(zhǎng)度為1 157.415 km,最優(yōu)車(chē)輛數(shù)為7輛,算法運(yùn)行平均耗時(shí)為56.25 s；多點(diǎn)單親遺傳混合蟻群算法求出的最優(yōu)路徑長(zhǎng)度為1 189.409 km,最優(yōu)車(chē)輛數(shù)為7輛,算法運(yùn)行平均耗時(shí)為57.63 s?？梢?jiàn)，單點(diǎn)單親遺傳混合蟻群算法與多點(diǎn)單親遺傳混合蟻群算法具有較高的求解效率，其求得的解均優(yōu)于基本蟻群算法求得的解，并且單點(diǎn)單親遺傳混合蟻群算法的求解性能更優(yōu)于多點(diǎn)單親遺傳混合蟻群算法。

表2　3種算法計(jì)算結(jié)果的比較

經(jīng)過(guò)多次測(cè)試運(yùn)算發(fā)現(xiàn)，單點(diǎn)單親遺傳混合蟻群算法在其他參數(shù)保持不變的情況下，改變轉(zhuǎn)移概率q0的取值，計(jì)算結(jié)果能夠得到進(jìn)一步優(yōu)化。當(dāng)q0=0.4時(shí)，隨機(jī)運(yùn)行單點(diǎn)單親遺傳混合蟻群算法10次所得的車(chē)輛數(shù)均為7，路徑長(zhǎng)度的標(biāo)準(zhǔn)差為16.435 km。較低的標(biāo)準(zhǔn)差說(shuō)明單點(diǎn)單親遺傳混合蟻群算法具有較好的穩(wěn)定性。

單點(diǎn)單親遺傳混合蟻群算法10次運(yùn)行結(jié)果的最優(yōu)路徑長(zhǎng)度為1 095.510 km，車(chē)輛數(shù)為7輛，最優(yōu)配送方案的路線圖如圖2所示(1代表配送中心，2-21代表20個(gè)客戶(hù)的編號(hào))。7輛車(chē)的配送路線分別為：

車(chē)輛1：1-8-4-1；

車(chē)輛3: 1-2-3-18-1；

車(chē)輛4: 1-19-15-12-6-1；

車(chē)輛5: 1-11-14-21-7-1；

車(chē)輛6: 1-20-13-1；

車(chē)輛7: 1-9-17-1。

圖2　最優(yōu)配送方案路徑圖(單位：km)Fig.2　Routes of optimal delivery scheme(unit:km)

4結(jié)論

本文對(duì)具有最大等待時(shí)間和運(yùn)輸時(shí)間限制的多目標(biāo)帶時(shí)間窗的車(chē)輛路徑問(wèn)題建立了數(shù)學(xué)模型，然后針對(duì)該問(wèn)題，將單親遺傳算法與蟻群算法相結(jié)合，使兩種算法相互取長(zhǎng)補(bǔ)短，設(shè)計(jì)出求解多目標(biāo)車(chē)輛路徑問(wèn)題的單親遺傳混合蟻群算法。求解測(cè)試算例表明：在基本蟻群算法中引入單親遺傳算子操作后，能夠有效改善基本蟻群算法收斂速度慢和易陷入局部最優(yōu)的缺點(diǎn)。本文所設(shè)計(jì)的單親遺傳混合蟻群算法不僅具有較好的求解性能，而且能夠有效求解多目標(biāo)帶時(shí)間窗的車(chē)輛路徑問(wèn)題，尤其單點(diǎn)單親遺傳混合蟻群算法具有較高的計(jì)算效率和較高的穩(wěn)定性，是求解多目標(biāo)帶時(shí)間窗的車(chē)輛路徑問(wèn)題的一種有效算法。

本文所提出的單親遺傳混合蟻群算法不僅為多目標(biāo)車(chē)輛路徑問(wèn)題的求解提供了一種較為有效的工具和手段，而且本文研究?jī)?nèi)容也拓寬了蟻群算法的改進(jìn)方法。

參考文獻(xiàn)：

References:

[1]SAVELSBERGH M W P. Local Search in Routing Problems with Time Windows [J]. Annals of Operations Research, 1985, 4(1): 285-305.

[2]URSANI Z, ESSAM D, CORNFORTH D, et al. Localized Genetic Algorithm for Vehicle Routing Problem with Time Windows [J]. Applied Soft Computing, 2011, 11 (8):5375-5390.

[3]GHOSEIRI K, GHANNADPOUR S F. Multi-objective Vehicle Routing Problem with Time Windows Using Goal Programming and Genetic Algorithm [J]. Applied Soft Computing, 2010, 10 (4):1096-1107.

[4]DING Q L ，HU X P, SUN L J, et al. An Improved Ant Colony Optimization and Its Application to Vehicle Routing Problem with Time Windows [J]. Neurocomputing, 2012,98(12): 101-107.

[5]張勇. 基于改進(jìn)蟻群算法物流配送路徑優(yōu)化的研究 [J]. 控制工程, 2015, 22(2):252-256.

ZHANG Yong. Study of Optimizing Logistic Distribution Routing Based on Improved Ant Colony Algorithm[J]. Control Engineering of China, 2015, 22(2):252-256.

[6]何小鋒,馬良.帶時(shí)間窗車(chē)輛路徑問(wèn)題的量子蟻群算法 [J]. 系統(tǒng)工程理論與實(shí)踐,2013, 33 (5):1255-1261.

HE Xiao-feng, MA Liang. Quantum-inspired Ant Colony Algorithm for Vehicle Routing Problem with Time Windows [J]. Systems Engineering-Theory & Practice, 2013, 33 (5):1255-1261.

[7]溫惠英,徐建閩.基于改進(jìn)型蟻群算法的車(chē)輛導(dǎo)航路徑規(guī)劃研究 [J]. 公路交通科技,2009,26(1):125-129.WEN Hui-ying, XU Jian-min. Research on Vehicle Routing Problem Based on Improved Ant Colony Algorithm[J]. Journal of Highway and Transportation Research and Development, 2009, 26(1):125-129.

[8]王超,穆東. 基于模擬退火算法求解VRPSPDTW問(wèn)題 [J]. 系統(tǒng)仿真學(xué)報(bào), 2014, 26(11): 2618-2623.

WANG Chao, MU Dong. Solving VRPSPDTW Problem Using Simulated Annealing Algorithm[J]. Journal of System Simulation, 2014, 26(11): 2618-2623.

[9]馬華偉,靳鵬,楊善林.時(shí)變車(chē)輛路徑問(wèn)題的啟發(fā)式算法 [J].系統(tǒng)工程學(xué)報(bào),2012,27(2):256-262.

MA Hua-wei, JIN Peng, YANG Shan-lin. Heuristic Methods for Time-dependent Vehicle Routing Problem [J]. Journal of System Engineering, 2012, 27(2):256-262.

[10]寧濤,陳榮,郭晨, 等. 一種基于雙鏈量子編碼的動(dòng)態(tài)車(chē)輛路徑問(wèn)題解決策略 [J]. 運(yùn)籌學(xué)學(xué)報(bào), 2015,19(2):72-82.

NING Tao, CHEN Rong, GUO Chen, et al. A Scheduling Strategy for Dynamic Vehicle Routing Problem Based on Double Chains Coding [J]. Operations Research Transactions, 2015, 19(2):72-82.

[11]溫惠英,孫博. 基于離散粒子群算法的協(xié)同車(chē)輛路徑問(wèn)題 [J]. 公路交通科技, 2011,28(1):149-153,158.WEN Hui-ying, SUN Bo. Resolving Collaborative Vehicle Route Problem Based on Discrete Particle Swarm Optimization[J]. Journal of Highway and Transportation Research and Development, 2011, 28(1):149-153,158.

[12]李茂軍,童調(diào)生. 單親遺傳算法及其全局收斂性分析 [J]. 自動(dòng)化學(xué)報(bào), 1999, 25(1):71-75.LI Mao-jun, TONG Tiao-sheng. A Partheno Genetic Algorithm and Analysis on Its Global Convergence [J]. Acta Automatica Sinica, 1999, 25(1): 71-75.

[13]肖鵬,李茂軍,張軍平,等. 車(chē)輛路徑問(wèn)題的單親遺傳算法 [J]. 計(jì)算技術(shù)與自動(dòng)化, 2000,19(1):26-30.XIAO Peng, LI Mao-jun, ZHANG Jun-ping, et al. Partheno Genetic Algorithm for Vehicle Routing Problem [J]. Computing Technology and Automation, 2000, 19(1):26-30.

[14]李茂軍,羅日成,童調(diào)生. 單親遺傳算法的遺傳算子分析[J]. 系統(tǒng)工程與電子技術(shù), 2001,23(8):84-87.LI Mao-jun, LUO Ri-cheng, TONG Tiao-sheng. Analysis on the Genetic Operators of Partheno-Genetic Algorithm[J]. Systems Engineering and Electronics, 2001, 23(8):84-87.

[15]李建,張永,達(dá)慶利. 第三方物流多車(chē)型硬時(shí)間窗路線問(wèn)題研究 [J]. 系統(tǒng)工程學(xué)報(bào), 2008,23(1):74-80.LI Jian, ZHANG Yong, DA Qing-li. Research on Heterogeneous Vehicle Routing Problem with Hard Time Windows for the Third Party Logistics [J]. Journal of System Engineering, 2008, 23(1):74-80.

A Partheno-genetic Hybrid Ant Colony Algorithm for Solving Multi-objective Vehicle Routing Problem with Time Window

LIU Yun, ZHANG Hui-zhen

(School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China)

Abstract：Considering the vehicle routing problem which has the restriction of maximum vehicle waiting time, maximum vehicle transport time and time windows, a mathematical model for the shortest length of vehicle travel and the minimum number of the using vehicles as the multi-objective is established. Then, 2 partheno-genetic hybrid ant colony algorithms for solving the problem are proposed by combining partheno-genetic algorithm with basic ant colony algorithm to have their complementary advantages and the features of partheno-genetic algorithm, which are monogene partheno-genetic hybrid ant colony algorithm and polygenic partheno-genetic hybrid ant colony algorithm. The result of the test case shows that the partheno-genetic hybrid ant colony algorithm has the advantages of better computational efficiency and convergence, and especially monogene partheno-genetic hybrid ant colony algorithm is more stable and has better computational performance.

Key words：traffic engineering；vehicle routing problem；partheno genetic hybrid ant colony algorithm；multi-objective；time window

收稿日期：2015-08-20

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目(71401106)；高等學(xué)校博士學(xué)科點(diǎn)專(zhuān)項(xiàng)科研基金聯(lián)合課題項(xiàng)目(20123120120005)；上海市教育委員會(huì)科研創(chuàng)新項(xiàng)目(14YZ090)；上海高校青年教師培養(yǎng)計(jì)劃項(xiàng)目(slg12010)

作者簡(jiǎn)介：劉云(1992-)，女，江蘇鹽城人，碩士研究生.(duianly0915@163.com)

doi:10.3969/j.issn.1002-0268.2016.06.015

中圖分類(lèi)號(hào)：TP18

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

文章編號(hào)：1002-0268(2016)06-0095-06