亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

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

        2016-06-30 01:59:12張惠珍
        公路交通科技 2016年6期
        關(guān)鍵詞:多目標(biāo)交通工程

        劉 云,張惠珍

        (上海理工大學(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

        猜你喜歡
        多目標(biāo)交通工程
        基于生態(tài)流量區(qū)間的多目標(biāo)水庫(kù)生態(tài)調(diào)度模型及應(yīng)用
        交通工程檢測(cè)行業(yè)現(xiàn)狀研究及對(duì)策分析
        改進(jìn)布谷鳥(niǎo)搜索算法在無(wú)功優(yōu)化中的應(yīng)用
        科技視界(2016年25期)2016-11-25 20:56:25
        基于可靠性的應(yīng)急物流多目標(biāo)選址問(wèn)題模型研究
        商(2016年30期)2016-11-09 08:27:28
        提高交通工程機(jī)械管理與維護(hù)工作的措施探究
        論如何做好交通工程施工現(xiàn)場(chǎng)管理
        交通工程施工現(xiàn)場(chǎng)的管理
        基于多目標(biāo)的土木工程專(zhuān)業(yè)科研創(chuàng)新人才培養(yǎng)模式探索
        一種基于URWPGSim2D啟發(fā)式博弈策略設(shè)計(jì)
        農(nóng)村公路交通安全分析與對(duì)策研究
        商(2016年13期)2016-05-20 10:23:42
        欧美日韩精品| 亚洲一区二区三区激情在线观看| 在线人成视频播放午夜| 桃花影院理论片在线| 2021久久最新国产精品| 日本亚洲一级中文字幕| 亚洲无毛成人在线视频| 久久久亚洲欧洲日产国码aⅴ| 亚洲国产成人久久一区| 久草热这里只有精品在线| 亚洲第一页在线免费观看| 国产一区二区三区日韩精品| 日日澡夜夜澡人人高潮| 久久福利青草精品资源| 国产剧情亚洲一区二区三区| 中文字幕一区二区三区四区五区| 九九精品国产亚洲av日韩| 伊人久久亚洲综合影院首页| 国产三级在线观看不卡| 久久久国产精品无码免费专区| 国産精品久久久久久久| 亚洲欧美日韩国产综合久| 日本女优禁断视频中文字幕| 亚洲国产精品成人久久| 亚洲永久精品ww47| 亚州五十路伊人网| 国产精品亚洲一区二区麻豆| 亚洲精品乱码8久久久久久日本| 中文文精品字幕一区二区| 亚洲国产成人av第一二三区| 日本精品视频一区二区三区四区| 国产丝袜视频一区二区三区| 日韩亚洲中文图片小说| 亚洲精品国产av成拍| 放荡的少妇2欧美版| 激情另类小说区图片区视频区| 中文字幕五月久久婷热| 男女边摸边吃奶边做视频韩国| 麻豆精品久久久久久久99蜜桃| 欧洲日韩视频二区在线| 日韩一二三四区在线观看|