資源描述：
《求解卸裝一體化車輛路徑問(wèn)題的改進(jìn)導(dǎo)向局部搜索算法.pdf》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、第15卷第18期2015年6月科學(xué)技術(shù)與工程VoJ_15No．18Jun．20151671—1815(2015)18—0066—05ScienceTechnologyandEngineering⑥2015Sci．Tech．Engrg．計(jì)算機(jī)技術(shù)求解卸裝一體化車輛路徑問(wèn)題的改進(jìn)導(dǎo)向局部搜索算法田冉孫林夫’唐慧佳趙進(jìn)超(西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院，成都610031；鄭州輕工業(yè)學(xué)院計(jì)算機(jī)與通信工程學(xué)院，鄭州450002)摘要針對(duì)卸裝一體化車輛路徑問(wèn)題，提出一種變懲罰函數(shù)的導(dǎo)向局部搜索算法(IGLS)。在傳統(tǒng)導(dǎo)向局部搜索算法
2、的基礎(chǔ)上加入了新的懲罰效用函數(shù)，當(dāng)傳統(tǒng)導(dǎo)向局部搜索算法陷入局部最優(yōu)時(shí)，變換懲罰策略后重新搜索，從而擴(kuò)展搜索的鄰域。通過(guò)和傳統(tǒng)導(dǎo)向局部搜索算法以及TS—GLS算法在不同算例上的仿真結(jié)果比較，驗(yàn)證了所提算法在解決卸裝一體化車輛路徑問(wèn)題上的有效性和穩(wěn)定性。關(guān)鍵詞卸裝一體化車輛路徑問(wèn)題變懲罰函數(shù)導(dǎo)向局部搜索懲罰策略中圖法分類號(hào)TP301；文獻(xiàn)標(biāo)志碼A裝卸一體化車輛路徑問(wèn)題(vehicleroutingprob．到更好的性能和收斂速度，但缺點(diǎn)是這類算法對(duì)初1emwithsimultaneousdeliveryandpickup，V
3、RPSDP)始解和鄰域的依賴較大。因此，選擇合適的鄰域和是車輛路徑問(wèn)題(capacitatedvehicleroutingprob-設(shè)計(jì)有效的局部最優(yōu)解逃離策略對(duì)算法性能至關(guān)lem，VRP)問(wèn)題的擴(kuò)展。其普遍存在于郵政、制造、重要。電商等企業(yè)的物流運(yùn)輸中，是降低物流成本，提高客在應(yīng)用傳統(tǒng)的導(dǎo)向局部搜索算法解決VRPSDP戶滿意的關(guān)鍵問(wèn)題。由于VRPSDP同VRP問(wèn)題都問(wèn)題時(shí)由于采用的懲罰策略在迭代過(guò)程中并無(wú)變屬于NP難題，因此目前國(guó)內(nèi)外對(duì)于VRPSDP的動(dòng)，就可能導(dǎo)致一些必然經(jīng)過(guò)的長(zhǎng)路徑被作為懲罰研究主要集中在各種元啟發(fā)
4、式算法和混合式的啟發(fā)邊而被懲罰，從而導(dǎo)致了算法在逃離局部最優(yōu)時(shí)經(jīng)算法上，在元啟發(fā)式算法方面：GajpalY、AiTJ、歷了大量的無(wú)用計(jì)算。因此提出一種新的變懲罰函TasanAS、Alfredo等分別采用蟻群算法、粒子數(shù)的導(dǎo)向局部搜索算法(improvedguidedlocal群算法、遺傳算法、禁忌搜索算法等來(lái)解決這一問(wèn)search)，采用多懲罰函數(shù)從而降低了單一懲罰函數(shù)題。在混合啟發(fā)式算法上，K．Ganesh等提出多階懲罰有效邊的可能性，擴(kuò)大了鄰域搜索范圍。同時(shí)段的改進(jìn)混合啟發(fā)式算法；J．Crispim等提出結(jié)合通過(guò)反復(fù)
5、搜索來(lái)減少初始解對(duì)算法的影響。最后通禁忌搜索和變鄰域下降搜索的混合算法；E．E．Za—過(guò)對(duì)28個(gè)算例的求解，表明了該算法的有效性和穩(wěn)chariadis等提出導(dǎo)引式局部搜索和禁忌搜索相結(jié)定性，為求解裝卸一體化車輛路徑問(wèn)題提供了新的合的混合算法。根據(jù)使用解的個(gè)數(shù)，又可將這些啟求解思路。發(fā)式算法分為兩類：基于個(gè)體的局部搜索方法(如模擬退火、禁忌搜索、導(dǎo)向局部搜索算法等)和基于1問(wèn)題描述群體的全局搜索方法(如遺傳算法、蟻群算法)。大1．1問(wèn)題描述量的研究表明基于個(gè)體的局部搜索方法往往能夠得裝卸一體化車輛路徑問(wèn)題可以定義為：設(shè)定有
6、向帶權(quán)圖G=(V，A，C)，其中V={iIi=0，1，?，2014年12月29日收到國(guó)家高技術(shù)研究發(fā)展計(jì)劃(863)n}是節(jié)點(diǎn)集合，節(jié)點(diǎn)0為出發(fā)地節(jié)點(diǎn)，(1～)為(2013AA040606)和四川省科技支撐計(jì)劃項(xiàng)目(2014GZ0142)資助第一作者簡(jiǎn)介：田冉(1981一)，男，河南南陽(yáng)人，博士研究生。E．客戶地節(jié)點(diǎn)；A={i，Ii，EV}表示弧集，C=mail：troom@163．com。{c1．(i，)∈A}為權(quán)重矩陣，C表示節(jié)點(diǎn)i到節(jié)通信作者簡(jiǎn)介：孫林夫(1963一)，男，浙江人，教授。研究方向：云點(diǎn)．的距離。設(shè)定
7、每個(gè)客戶節(jié)點(diǎn)i都有卸貨需求d制造，云服務(wù)平臺(tái)技術(shù)。E—mail：sunlf@vip．sina．com。和裝貨需求P，運(yùn)輸車輛的最大載貨量為Q。VRPS-DP則可以描述為：①每輛車都從0點(diǎn)出發(fā)，服務(wù)若18期田冉，等：求解卸裝一體化車輛路徑問(wèn)題的改進(jìn)導(dǎo)向局部搜索算法67干客戶后返回0點(diǎn)，形成一個(gè)解S；②每個(gè)客戶都僅總的弧長(zhǎng)。A為規(guī)范化系數(shù)，通常取0．01～0．10?。被服務(wù)一次，而且只能由某一車輛提供服務(wù)；③每個(gè)通過(guò)懲罰具有懲罰特征的解，保證了較好特征的可車輛的載重量都不超過(guò)Q；④所有客戶的裝卸貨需行解進(jìn)行鄰域搜索，通過(guò)目標(biāo)
8、函數(shù)的不斷修改，使得求都不超過(guò)Q；⑤總的運(yùn)輸距離s)最小。當(dāng)前局部極值不再具有局部最優(yōu)性，從而不斷迭代1．2解的可行性定義找到最優(yōu)解。對(duì)于VRPSDP的解S={rI．=1，?，k}，其中2．2懲罰效用函數(shù)設(shè)計(jì)r={ili∈[1，n]}，表示車輛的路徑，k為解中最由于傳統(tǒng)的懲罰效用函數(shù)U(S)尋找的是解大的車輛數(shù)。對(duì)于
