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

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

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 黨蘭學(xué);大規(guī)模混載校車路徑問題優(yōu)化算法研究[D];河南大學(xué);2014年

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

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

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

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

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

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

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

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

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

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

9 金光宇;面對小零售商戶的庫存路徑問題的聚類算法研究[D];清華大學(xué);2013年

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

，

本文編號：1962237