本文選題：NP難問(wèn)題 + P-中心問(wèn)題�。� 參考：《華中科技大學(xué)》2015年碩士論文

【摘要】：由Hakami在1964年提出的P-center問(wèn)題作為一個(gè)經(jīng)典的NP難問(wèn)題在物流設(shè)施規(guī)劃,通信網(wǎng)絡(luò)設(shè)計(jì)以及警局、醫(yī)院、消防站等有公共服務(wù)標(biāo)準(zhǔn)要求的諸多行業(yè)中有廣闊的應(yīng)用前景。尤其是物流行業(yè),作為電子商務(wù)的基石,隨著電子商務(wù)的興起,其地位的重要性日漸凸顯。設(shè)施選址問(wèn)題作為物流業(yè)的核心問(wèn)題得到了國(guó)際學(xué)者的積極研究。P-center問(wèn)題作為各類(lèi)型選址問(wèn)題的基礎(chǔ),是一個(gè)具有重大研究?jī)r(jià)值以及現(xiàn)實(shí)挑戰(zhàn)性的課題。求解NP難問(wèn)題的常用算法有三種:精確算法、近似算法和啟發(fā)式優(yōu)化算法。精確算法一定可以給出最優(yōu)解,但是由于NP問(wèn)題具有指數(shù)級(jí)的復(fù)雜度,通常只能使用精確算法解決小規(guī)模實(shí)例,大規(guī)模的問(wèn)題實(shí)例則無(wú)法使用精確算法在可接受的時(shí)間范圍內(nèi)求解出最優(yōu)解。近似算法雖能保證最壞情況下得到的解與最優(yōu)解的誤差在一定的范圍內(nèi),但其實(shí)際計(jì)算結(jié)果卻往往不能夠令人滿(mǎn)意。啟發(fā)式優(yōu)化算法往往能夠在求解精度和求解時(shí)間上達(dá)到很好的平衡,因而成為一種廣泛被學(xué)者研究的算法。本文以Pullan的PBS-1算法中的局部搜索算法為基礎(chǔ),提出一種基于禁忌搜索的GRASP(Greedy Randomized Adaptive Search Procedures)算法—TSGRASP。為了驗(yàn)證TSGRASP的效果,本文選取了148個(gè)P-center標(biāo)準(zhǔn)算例的進(jìn)行測(cè)試,實(shí)驗(yàn)結(jié)果顯示TSGRASP算法在11個(gè)算例的求解上找到了更優(yōu)的解,而其他算例的求解結(jié)果至少可以和PBS-1算法持平。并且值得一提的是,相比PBS-1算法,TSGRASP算法在求解時(shí)間上也有明顯的提高。實(shí)驗(yàn)結(jié)果表明,與當(dāng)今國(guó)際上最優(yōu)秀的算法相比較,本文所提出的TSGRASP算法在P-center問(wèn)題的求解上非常具有競(jìng)爭(zhēng)力。
[Abstract]:The P-center problem proposed by Hakami in 1964 as a classical NP-hard problem has a broad application prospect in logistics facilities planning, communication network design, police stations, hospitals, fire stations and many other industries with the requirements of public service standards.Especially the logistics industry, as the cornerstone of electronic commerce, with the rise of electronic commerce, the importance of its status is increasingly prominent.As the core problem of logistics industry, facility location problem has been actively studied by international scholars. P-center problem, as the basis of various types of location problems, is of great research value and practical challenge.There are three common algorithms for solving NP-hard problems: exact algorithm, approximate algorithm and heuristic optimization algorithm.The exact algorithm can give the optimal solution, but due to the exponential complexity of the NP problem, the exact algorithm can only be used to solve the small scale cases.Large-scale problem examples can not solve the optimal solution in an acceptable time range by using an exact algorithm.Although the approximate algorithm can guarantee the error between the solution and the optimal solution in a certain range in the worst case, the actual calculation results are often not satisfactory.Heuristic optimization algorithm is often able to achieve a good balance between precision and time, so it has become a widely studied algorithm.Based on the local search algorithm in Pullan's PBS-1 algorithm, a Tabu search based GRASP(Greedy Randomized Adaptive Search procedure algorithm (TSGRASP) is proposed in this paper.In order to verify the effectiveness of TSGRASP, 148 P-center standard examples are selected for testing. The experimental results show that the TSGRASP algorithm has found a better solution on 11 examples, while the other examples have at least the same results as the PBS-1 algorithm.And it is worth mentioning that compared with PBS-1 algorithm, TSGRASP algorithm also has significant improvement in solving time.The experimental results show that the TSGRASP algorithm proposed in this paper is very competitive in solving the P-center problem compared with the best algorithms in the world.
【學(xué)位授予單位】：華中科技大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類(lèi)號(hào)】：TP301.6

【參考文獻(xiàn)】

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

1 蔣建林;徐進(jìn)澎;文杰;;基于單親遺傳模擬退火算法的頂點(diǎn)p-中心問(wèn)題[J];系統(tǒng)工程學(xué)報(bào);2011年03期

2 黎青松,楊偉,曾傳華;中心問(wèn)題與中位問(wèn)題的研究現(xiàn)狀[J];系統(tǒng)工程;2005年05期

3 張?zhí)N博 ,岳亮;物流服務(wù)配送中心選址問(wèn)題淺析[J];物流科技;2004年09期

4 袁慶達(dá),陳旭梅,黎青松;基于“服務(wù)型”物流戰(zhàn)略的p-Center選址問(wèn)題研究[J];西南交通大學(xué)學(xué)報(bào);2001年03期

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

1 呂志鵬;蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)的現(xiàn)實(shí)求解方法[D];華中科技大學(xué);2007年

，

本文編號(hào)：1745148