資源描述：
《求解vrp問題的改進(jìn)和聲搜索算法的分析》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、萬方數(shù)據(jù)l緒論聯(lián)網(wǎng)呈現(xiàn)飛速發(fā)展的趨勢(shì)，深入研究VRP問題不僅有重要的科學(xué)理論意義，同時(shí)具有巨大的經(jīng)濟(jì)效益。VRP是一類NPhard的網(wǎng)絡(luò)和組合優(yōu)化問題，只有一些規(guī)模較小的問題(不超過30個(gè)客戶)可以通過精確算法計(jì)算出最優(yōu)解。對(duì)更大規(guī)模的VRP問題，解空間的范圍就超過了精確解法的計(jì)算能力，要在有限的計(jì)算資源和計(jì)算時(shí)問下求得最優(yōu)解，幾乎是不可能的。對(duì)這種規(guī)模的車輛路徑問題，比較好的方法是使用一種啟發(fā)式算法。啟發(fā)式算法在求解VRP時(shí)雖然犧牲了一些求解精度，卻大大提高了解決問題的速度。目前，常用來解決車輛路徑問題的啟
2、發(fā)式算法主要有遺傳算法，粒子群算法，禁忌搜索等。其中和聲搜索算法作為一種比較新的全局優(yōu)化啟發(fā)式算法，在實(shí)踐中已經(jīng)取得了比遺傳算法，粒子群算法等更好的結(jié)果，因此受到越來越多學(xué)者的重視。為了提高我國企業(yè)物流的配送優(yōu)化能力，降低貨物的流通成本，本文在國內(nèi)外現(xiàn)有的研究工作的基礎(chǔ)上，對(duì)和聲搜索算法進(jìn)行了深入的研究，提出了改進(jìn)和聲搜索算法CVRP求解算法。與用基本和聲算法求解VRP相比，求解精度和速度均大大提高，相比較其他啟發(fā)式算法，改進(jìn)的和聲算法也有著明顯優(yōu)勢(shì)。1．2國內(nèi)外7RP問題的研究VRP問題可以描述為：一定數(shù)量
3、的客戶，各自有不同數(shù)量的物流需求，配送中心根據(jù)客戶的需求，規(guī)劃車隊(duì)行車路線，在滿足一定的約束的條件下，達(dá)到諸如路程最短、成本最小、耗費(fèi)時(shí)間最短等目標(biāo)。VRP問題最初由Danting和Ramser于1959年提出。經(jīng)過幾十年的發(fā)展，出現(xiàn)了許多分支，包括：帶時(shí)間窗車輛路徑問題、多配送中心車輛路徑問題、容量限制車輛路徑問題、基于站點(diǎn)的車輛路徑問題、開放式車輛路徑問題、同時(shí)取送貨車輛路徑問題等。國外對(duì)車輛路徑問題的研究開展的較早，具有代表性的工作主要包括：Heung．SukHwang等人在對(duì)帶時(shí)間窗車輛路徑問題(VR
4、PTw)的研究中，將原本只用于求解旅行商問題(TSP)的模型應(yīng)用在求解VRP問題上，并通過改良遺傳算法的突變、復(fù)制的方式和親代的選擇方法，創(chuàng)新地提出了一種求解VRP問題改進(jìn)的遺傳算法。實(shí)驗(yàn)結(jié)果表明，采用的改進(jìn)算法結(jié)果要優(yōu)于原有求解方法，而且該方法對(duì)不同規(guī)模的問題也有較強(qiáng)的適應(yīng)性。Chiang和Russell提出了基于模擬退火(SimulateAnnealing，SA)結(jié)合禁忌搜索的3萬方數(shù)據(jù)1緒論方法來求解VRP，利用了TS中禁忌列表來提高SA的尋優(yōu)能力，同時(shí)算法評(píng)估了在Solomon測(cè)試集上的表現(xiàn)，實(shí)驗(yàn)結(jié)果
5、比僅采用一種啟發(fā)式算法更好，證明了混合式啟發(fā)算法有著明顯的優(yōu)勢(shì)，值得繼續(xù)深入探討。Yoshiike，Takefuji等人提出了一種新穎的方法。該算法求解VRP的過程為兩個(gè)階段，其中第一個(gè)階段用最大的神經(jīng)元VRP模型簡化問題，便于分組。YingjieZhong，MichaelH．Cole等人使用帶引導(dǎo)的局部搜索算法來求解帶時(shí)間窗車輛路徑問題，這種方法的一個(gè)缺陷是求解過程會(huì)有違反時(shí)間窗約束的情況發(fā)生，所以又融入了分組規(guī)劃法，同時(shí)引入2-opt算子，1-move算子，交換算子等。經(jīng)過改進(jìn)后，算法可以在約束條件范圍內(nèi)
6、求得較高質(zhì)量的解。此外，Desaulniers、Hong和Park、Toth和Vigo、Baker和Sheasby等人使用了其他算法來求解VRP，例如，通過神經(jīng)網(wǎng)絡(luò)，數(shù)學(xué)規(guī)劃等方法來解決VRP。國內(nèi)研究VRP問題起步于20世紀(jì)90年代初。我國學(xué)者普遍使用啟發(fā)式算法，以提高求解效率，并適用于不同類型的VRP的，研究取得了顯著的成果：羅敏華研究了用蟻群算法求解帶容量限制的VRP。算法模擬了螞蟻的覓食過程，用螞蟻的信息素來構(gòu)筑車輛行駛的路徑，同時(shí)用節(jié)約算法提高初始解的質(zhì)量。作者用蟻群算法解決了同時(shí)限制載重和行駛距離
7、的車輛路徑問題(DCvI沖)，針對(duì)螞蟻的數(shù)量如何影響尋優(yōu)過程這個(gè)問題，作者經(jīng)過研究表明較少的螞蟻可以達(dá)到同樣的效果。王佳容等人利用人工神經(jīng)網(wǎng)絡(luò)(舢州)和時(shí)間分割、禁忌搜索相結(jié)合的方法來解決軟時(shí)間窗車輛調(diào)度問題。為了使更多的時(shí)間服務(wù)較早和較晚的客戶可以有最優(yōu)的分群，該方法根據(jù)客戶需求所在的位置，通過自組織神經(jīng)網(wǎng)絡(luò)構(gòu)建網(wǎng)格地圖，將用戶分群，同時(shí)檢查的時(shí)間窗口每一組客戶距離倉庫的遠(yuǎn)近。結(jié)果表明，該方法對(duì)解決帶時(shí)間窗車輛路徑問題是有效的。肖鵬等人改進(jìn)了遺傳算法的編碼方式并構(gòu)造了一種偽克隆遺傳算法，在其中采用了一種等位
8、基因換位算子，實(shí)驗(yàn)表明在解決客戶數(shù)目較少的VRP時(shí)效果明顯。王正彬等人研究了現(xiàn)實(shí)中的物流運(yùn)輸過程，對(duì)VRP模型進(jìn)行了改進(jìn)，在其中增加了車輛運(yùn)輸?shù)南拗茥l件，并用啟發(fā)式算法進(jìn)行了求解。1．3和聲搜索算法的研究現(xiàn)狀和聲搜索算法(harmonysearchalgorithm，HS)是韓國學(xué)者Geem在2001年提出的一種4萬方數(shù)據(jù)1緒論新穎的元啟發(fā)算法【3】，算法的靈感來自于音樂家自然演奏過程中尋求一個(gè)更好
