本文選題：組合優(yōu)化 + 限容量弧路徑問(wèn)題��； 參考：《中國(guó)科學(xué)技術(shù)大學(xué)》2016年博士論文

【摘要】：限容量弧路徑問(wèn)題是一個(gè)經(jīng)典的組合優(yōu)化問(wèn)題。它可以歸結(jié)為在一個(gè)給定的連通圖上尋找經(jīng)過(guò)圖中某些邊并滿(mǎn)足特定約束條件的最優(yōu)回路集。限容量弧路徑問(wèn)題在現(xiàn)實(shí)生活中有著極為廣泛的應(yīng)用,如冬季路面撒鹽、城市垃圾清理及物流運(yùn)輸?shù)葘?shí)際應(yīng)用均可被抽象為限容量弧路徑問(wèn)題。此類(lèi)問(wèn)題在現(xiàn)代工業(yè)和民生中有著重要的地位。因此,近年來(lái),限容量弧路徑問(wèn)題獲得了越來(lái)越多的研究關(guān)注,發(fā)展出各式各樣的問(wèn)題模型與求解方法。然而,研究工作與實(shí)際應(yīng)用間尚存在一定的差距。大部分研究工作均局限于確定性問(wèn)題模型,且所能求解的問(wèn)題規(guī)模較小,而實(shí)際應(yīng)用中往往存在許多不確定因素,問(wèn)題規(guī)模也往往超出已有方法的能力范圍,因而導(dǎo)致這些研究工作無(wú)法直接應(yīng)用于大部分的實(shí)際問(wèn)題�；诖�,本文主要研究上述有著廣泛應(yīng)用需求卻在一定程度上被研究者們忽視的問(wèn)題模型—非確定限容量弧路徑問(wèn)題與大規(guī)模限容量弧路徑問(wèn)題。本文研究的第一個(gè)問(wèn)題——非確定限容量弧路徑問(wèn)題是近年來(lái)提出的新的問(wèn)題變種。該問(wèn)題考慮了實(shí)際應(yīng)用中的四個(gè)不確定因素：任務(wù)的需求量,邊的消耗,任務(wù)的存在性以及邊的存在性,問(wèn)題目標(biāo)為求解所有可能的環(huán)境下魯棒性最優(yōu)的解。相比以往的確定性問(wèn)題模型,非確定限容量弧路徑問(wèn)題更貼近實(shí)際應(yīng)用,然而,由于其提出時(shí)間較晚且求解難度較大,現(xiàn)有的研究中尚不存在針對(duì)該問(wèn)題模型的有效解法�？紤]到在許多實(shí)際問(wèn)題中,我們往往無(wú)法得知問(wèn)題所包含隨機(jī)變量的底層分布,從而無(wú)法建立對(duì)應(yīng)的概率模型對(duì)其進(jìn)行求解。因此,本文采用樣本近似的方法來(lái)對(duì)非確定問(wèn)題進(jìn)行建模,將原問(wèn)題表達(dá)為一組確定的樣本問(wèn)題,并求解針對(duì)樣本問(wèn)題集的魯棒解。我們首先選擇期望性能作為魯棒性評(píng)價(jià)標(biāo)準(zhǔn),提出基于多種群的模因算法(Memetic Algorithm with Multiple Population, MAMP)。MAMP的核心思想在于：對(duì)每個(gè)樣本維護(hù)一個(gè)種群,在算法運(yùn)行過(guò)程中通過(guò)種群選擇機(jī)制從樣本實(shí)例層面調(diào)控算法的搜索偏好,避免算法陷入較易求解的樣本而忽略了較難求解的樣本；在局部搜索過(guò)程中,使用合并-拆分算子從問(wèn)題解的層面調(diào)控算法的搜索方向,避免算法在單個(gè)樣本實(shí)例解空間中陷入局部最優(yōu)。實(shí)驗(yàn)表明,通過(guò)上述兩個(gè)層面對(duì)算法搜索方向的引導(dǎo),MAMP相比現(xiàn)有算法具有更好的尋求全局最優(yōu)解的能力。但由于使用了較為耗時(shí)的局部搜索算子以及對(duì)中間解的適應(yīng)度評(píng)估較為耗時(shí),MAMP算法需要更多的運(yùn)行時(shí)間。隨后,我們采用最壞情況下的性能作為魯棒性評(píng)價(jià)標(biāo)準(zhǔn)。針對(duì)搜索過(guò)程中解的適應(yīng)度評(píng)估較為耗時(shí)的問(wèn)題,設(shè)計(jì)了一個(gè)可以避免無(wú)效適應(yīng)度計(jì)算的隨機(jī)局部搜索方法,并將其與分布估計(jì)算法結(jié)合,得到一個(gè)兼顧性能與效率的算法Estimation of Distribution Algorithm with Stochastic Local Search (EDASLS)。該算法通過(guò)學(xué)習(xí)種群中優(yōu)質(zhì)個(gè)體所蘊(yùn)含的任務(wù)之間緊密度的信息,建立分布模型。然后利用此模型生成新的解并在隨機(jī)局部搜索中避免無(wú)效的適應(yīng)度計(jì)算。實(shí)驗(yàn)表明,EDASLS可獲得比其他算法魯棒性更優(yōu)的解。在算法的運(yùn)行時(shí)間上,EDASLS也表現(xiàn)出較強(qiáng)的優(yōu)勢(shì),在適應(yīng)度評(píng)估次數(shù)相同的情況下,EDASLS需要的運(yùn)行時(shí)間更短。更進(jìn)一步的實(shí)驗(yàn)表明,EDASLS的優(yōu)越性主要?dú)w功于隨機(jī)局部搜索,該方法可以在不影響算法性能的前提下,大大提升算法運(yùn)行速度。本文研究的另一個(gè)問(wèn)題——大規(guī)模限容量弧路徑問(wèn)題本質(zhì)上是一個(gè)基本限容量弧路徑問(wèn)題,但是由于其問(wèn)題規(guī)模較大,現(xiàn)有的研究方法均無(wú)法在可接受的時(shí)間內(nèi)給出問(wèn)題的一個(gè)質(zhì)量上可被接受的解�；谏鲜鲈�,本文提出一個(gè)基于層次分解的對(duì)問(wèn)題規(guī)模具有可擴(kuò)展性的算法Scalable Approach based on Hierarchical Decomposition (SAHiD),該算法的可擴(kuò)展性表現(xiàn)在當(dāng)問(wèn)題規(guī)模(任務(wù)數(shù))急速增長(zhǎng)時(shí),算法仍能在給定的較短時(shí)間(例如30分鐘)內(nèi)給出一個(gè)質(zhì)量較優(yōu)的解。通過(guò)對(duì)任務(wù)集以層次分解的方式進(jìn)行組合排序,SAHiD可以快速生成具有較高質(zhì)量的初始解。上述層次分解操作耗時(shí)極短,因而可被嵌入迭代搜索過(guò)程中以不斷提升解的質(zhì)量。為了驗(yàn)證SAHiD算法的可擴(kuò)展性,我們根據(jù)合肥市和北京市的真實(shí)交通路網(wǎng)生成了兩個(gè)問(wèn)題規(guī)模逐漸增大的測(cè)試集Hefei與Beijing,并在上述問(wèn)題集上將SAHiD與現(xiàn)有的求解傳統(tǒng)限容量弧路徑問(wèn)題的優(yōu)秀算法和專(zhuān)為大規(guī)模問(wèn)題設(shè)計(jì)的算法進(jìn)行了比較。實(shí)驗(yàn)結(jié)果表明,無(wú)論是從(得到質(zhì)量相當(dāng)?shù)慕庑枰?運(yùn)算時(shí)間還是從(給定時(shí)間內(nèi)能求得的)解的質(zhì)量來(lái)看,SAHiD表現(xiàn)出優(yōu)異的性能,而現(xiàn)有的算法性能則不盡如人意。尤其是在規(guī)模較大(任務(wù)數(shù)超過(guò)400)的問(wèn)題實(shí)例上,現(xiàn)有優(yōu)秀算法均無(wú)法在給定時(shí)間內(nèi)給出該問(wèn)題的一個(gè)質(zhì)量上可被接受的次優(yōu)解。在現(xiàn)有的規(guī)模最大的問(wèn)題集egl-large上,SAHiD雖然不能得到最優(yōu)的最終解,但在計(jì)算時(shí)間相當(dāng)少的情況下,SAHiD可以得到比其他算法更優(yōu)秀的解。因此,在需要較快得到問(wèn)題的解(分鐘級(jí)甚至是秒級(jí))的情況下,SAHiD是一個(gè)更好的選擇。
[Abstract]:In recent years , the problem of limited capacity arc path has been more and more closely related to the practical application . However , because of the fact that there are many uncertain factors in the practical application , the problem of limited capacity arc path is not directly applicable to most practical problems . The core idea of MAMP is to maintain a population for each sample . In the process of algorithm operation , the search preferences of the algorithm are adjusted from the sample case level through the population selection mechanism , so that the algorithm is avoided into a sample which is easy to be solved , and the sample which is difficult to be solved is ignored ;
In the process of local search , we use the merging - splitting operator to adjust the searching direction of the algorithm from the plane of the problem solution and avoid the local optimal solution in the solution space of the single sample .
【學(xué)位授予單位】：中國(guó)科學(xué)技術(shù)大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2016
【分類(lèi)號(hào)】：TP301.6

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 裴紅云;周永務(wù);;庫(kù)存路徑問(wèn)題的一個(gè)新策略[J];合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年05期

2 王建新;楊志彪;陳建二;;最長(zhǎng)路徑問(wèn)題研究進(jìn)展[J];計(jì)算機(jī)科學(xué);2009年12期

3 段鳳華;何小年;孫彥彬;;近年來(lái)庫(kù)存路徑問(wèn)題研究動(dòng)態(tài)及展望[J];計(jì)算機(jī)工程與應(yīng)用;2012年04期

4 范麗梅;;多源車(chē)輛最優(yōu)路徑問(wèn)題研究[J];計(jì)算機(jī)光盤(pán)軟件與應(yīng)用;2012年23期

5 劉潔;何彥鋒;;城市垃圾收集車(chē)輛弧路徑問(wèn)題研究[J];成都大學(xué)學(xué)報(bào)(自然科學(xué)版);2013年04期

6 劉樹(shù)德;李淑華;;用單板機(jī)實(shí)現(xiàn)網(wǎng)絡(luò)最優(yōu)路徑問(wèn)題的動(dòng)態(tài)規(guī)劃分析求解[J];遼寧化工;1986年03期

7 陳久梅;;兩級(jí)定位-路徑問(wèn)題的人工蜂群算法[J];計(jì)算機(jī)工程;2014年01期

8 黨蘭學(xué);侯彥娥;孔云峰;;校車(chē)路徑問(wèn)題的約束檢測(cè)算法[J];計(jì)算機(jī)應(yīng)用研究;2014年05期

9 劉佳;夏少芳;呂亞男;陳立潮;;復(fù)雜網(wǎng)絡(luò)中最短K條路徑問(wèn)題的求解算法研究[J];計(jì)算機(jī)應(yīng)用;2008年04期

10 金莉;朱云龍;申海;;三級(jí)物流網(wǎng)絡(luò)選址-路徑問(wèn)題建模與求解算法研究[J];控制與決策;2010年08期

相關(guān)博士學(xué)位論文 前5條

1 王娟;針對(duì)非確定和大規(guī)模限容量弧路徑問(wèn)題的近似算法[D];中國(guó)科學(xué)技術(shù)大學(xué);2016年

2 李引珍;不確定環(huán)境下交通運(yùn)輸網(wǎng)絡(luò)路徑求解方法及應(yīng)用研究[D];西南交通大學(xué);2005年

3 傅成紅;多周期庫(kù)存路徑問(wèn)題及其算法研究[D];中南大學(xué);2010年

4 黨蘭學(xué);大規(guī)�；燧d校車(chē)路徑問(wèn)題優(yōu)化算法研究[D];河南大學(xué);2014年

5 趙達(dá);隨機(jī)需求庫(kù)存—路徑問(wèn)題研究[D];西南交通大學(xué);2012年

相關(guān)碩士學(xué)位論文 前10條

1 陳靜;基于電子商務(wù)環(huán)境下的庫(kù)存—路徑問(wèn)題優(yōu)化研究[D];華南理工大學(xué);2015年

2 李惠;電煤海運(yùn)庫(kù)存—路徑問(wèn)題研究[D];大連海事大學(xué);2015年

3 張濤;快遞智能投遞最優(yōu)路徑問(wèn)題研究[D];成都理工大學(xué);2015年

4 黃慶偉;帶容量約束的開(kāi)放式弧路徑問(wèn)題的算法研究[D];天津大學(xué);2014年

5 孫錫梅;同時(shí)配送和回收需求的容量約束弧路徑問(wèn)題[D];天津大學(xué);2014年

6 牛寧;改進(jìn)蟻群算法求解多目標(biāo)校車(chē)路徑優(yōu)化問(wèn)題[D];河南大學(xué);2015年

7 宋頌頌;低碳化選址—路徑問(wèn)題優(yōu)化模型研究[D];東北大學(xué);2012年

8 王如勇;電子商務(wù)環(huán)境下城市共同配送選址—路徑問(wèn)題研究[D];華中科技大學(xué);2013年

9 金光宇;面對(duì)小零售商戶(hù)的庫(kù)存路徑問(wèn)題的聚類(lèi)算法研究[D];清華大學(xué);2013年

10 郭昊;考慮退貨的選址—庫(kù)存—路徑問(wèn)題集成優(yōu)化模型與算法研究[D];華中師范大學(xué);2013年

，

本文編號(hào)：1962237