資源描述：
《需求可拆分車輛路徑問題的迭代局部搜索算法研究》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、學(xué)校代碼：密級：公開碩士學(xué)位論文需求可拆分車輛路徑問題的迭代局部搜索算法研究作者姓名溫真真學(xué)科專業(yè)計算機科學(xué)與技術(shù)指導(dǎo)教師于劍教授培養(yǎng)院系計算機與信息技術(shù)學(xué)院二零一五年三月碩士學(xué)位論文需求可拆分車輛路徑問題的迭代局部搜索算法研究作者：溫真真導(dǎo)師：于劍北京交通大學(xué)年月學(xué)位論文版權(quán)使用授權(quán)書本學(xué)位論文作者完全了解北京交通大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定。特授權(quán)北京交通大學(xué)可以將學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進行檢索，提供閱覽服務(wù)，并采用影印、縮印或掃描等復(fù)制手段保存、匯編以供查閱和借閱。同意學(xué)校向國家有關(guān)部門或機構(gòu)送交論文的復(fù)印件和磁盤。學(xué)校可以為存在館
2、際合作關(guān)系的兄弟高校用戶提供文獻傳遞服務(wù)和交換服務(wù)。保密的學(xué)位論文在解密后適用本授權(quán)說明）簽字日期：丨：年飛月，日簽字曰期年月學(xué)校代碼：密級：公幵北京交通大學(xué)碩士學(xué)位論文需求可拆分車輛路徑問題的迭代局部搜索算法研究作者姓名：溫真真學(xué)號：導(dǎo)師姓名：于劍職稱：教授學(xué)位類別：工學(xué)學(xué)位級別：碩士學(xué)科專業(yè)：計算機科學(xué)與技術(shù)研究方向：人工智能北京交通大學(xué)年月致謝在畢業(yè)論文完成之際，衷心對在研究生學(xué)習(xí)期間為我提供無私幫助老師、同學(xué)和家人表示感謝。在研究生學(xué)習(xí)期間，于劍教授和林友芳教授他們淵博的知識開闊的視野給了我深深的啟迪；他們嚴(yán)謹(jǐn)細(xì)致、一絲不茍的作風(fēng)一直是我工作、學(xué)習(xí)中
3、的榜樣；他們循循善誘的教導(dǎo)和不拘一格的思路給予我無盡的啟迪。特別感謝董興業(yè)副教授在論文算法思路方面和論文寫作方面給予的無私指導(dǎo)，董興業(yè)副教授在組合優(yōu)化領(lǐng)域的專業(yè)知識為論文的推進工作給出了寶貴的指導(dǎo)意見，為最終算法的優(yōu)化成型起到了相當(dāng)重要的作用。也向教授向教授為數(shù)據(jù)集的搜集工作做出的大力支持表示衷心的感謝。在實驗室的工作學(xué)習(xí)生活中，韓升老師都為我提供了許多無私的指導(dǎo)和幫助。實驗室的師兄、師姐、師弟和師妹都給予了我熱情的幫助。最后，對一直為我提供支持和關(guān)懷的家人表示感謝，他們一直都是我堅強的后盾和溫暖的港灣，就是因為有他們的支持與理解我沒有顧慮地走到今天。北京交
4、通大學(xué)碩士學(xué)位論文摘要摘要需求可拆分車輛路徑問題（是帶容量限制車輛路徑問題（的變形，放松了模型中一個客戶的需求只能由一輛車提供服務(wù)的限制。為了解決，本文提出一種多起點的迭代局部搜索（算法。首先使用算法求解出一個大的旅行商問題（解，然后以車輛的容量為標(biāo)準(zhǔn)，分割大的解，使分割后的路徑滿足車輛的容量限制，作為算法的初始解。迭代局部搜索算法是針對客戶節(jié)點進行的，節(jié)點的局部搜索順序按照其刪除節(jié)約代價從大到小進行。通過將節(jié)點從當(dāng)前解中刪除然后將此節(jié)點重新插入到其在當(dāng)前解中的最優(yōu)位置。提出了一個適用于問題模型的貪婪的節(jié)點重新插入算法，嘗試通過這個簡單的重新插入算法來優(yōu)化當(dāng)
5、前解。在尋找最優(yōu)位置時，考慮節(jié)點的需求可拆分這一策略，即考慮需求可能被一個或多個車輛提供服務(wù)。如果經(jīng)過一定次數(shù)的連續(xù)的局部搜索，并且在這個過程中，當(dāng)前解的質(zhì)量均未得到提升，我們對當(dāng)前解進行擾動，然后從擾動得到的解出發(fā)，繼續(xù)進行局部搜索。為了在擴大搜索空間的同時保證重新開始局部搜索解的質(zhì)量，我們設(shè)計了一個精英解緩沖池策略，將一組得到最優(yōu)解可能性較大的精英解放入這個池中，從這個解中挑選進行擾動的解。本文的優(yōu)化目標(biāo)是最小化所有路徑的總長度。對擾動界限的設(shè)置和算法框架中精英解緩沖池大小的設(shè)置進行了實驗分析，為它們設(shè)置合理的參數(shù)值。分析了本文中提出的對節(jié)點進行排序算法
6、對實驗結(jié)果的影響，實驗證明了它的合理性。最后，算法在標(biāo)準(zhǔn)數(shù)據(jù)集上得到的實驗結(jié)果與當(dāng)前問題領(lǐng)域最先進的算法的對比實驗表明算法是具有競爭力的。關(guān)鍵詞：車輛路徑問題；需求可拆分；元啟發(fā)式算法；局部搜索；多起點北京交通大學(xué)碩士學(xué)位論文，，：北京交通大學(xué)碩士學(xué)位論文目錄目錄艘弓研究背景與意義國內(nèi)外研究現(xiàn)狀車輛路徑問題的分類的研究現(xiàn)狀的研究現(xiàn)狀的求解目標(biāo)研究內(nèi)容和目標(biāo)論文組織結(jié)構(gòu)相關(guān)理論知識數(shù)學(xué)模型和求解目標(biāo)問題復(fù)雜性和最優(yōu)解的特性時間復(fù)雜度最優(yōu)解特性啟發(fā)式算法傳統(tǒng)啟發(fā)式算法兀啟發(fā)式算法基于局部搜索的元啟發(fā)式算法迭代局部搜索算法禁忌搜索算法基于屬性的爬山者算法鄰域算子好
7、的啟發(fā)式算法的特點本章小結(jié)多起點迭代局部搜索算法基本定義構(gòu)造初始解京交通大學(xué)碩士學(xué)位論文目錄多起點迭代局部搜索算法算法思想算法框架鄰域算子算法思想算法框架擾動算法被擾動解的選擇擾動策略和擾動界限描述算法分析本章小結(jié)實驗結(jié)果實驗數(shù)據(jù)集及環(huán)境介紹實驗參數(shù)設(shè)置擾動界限參數(shù)設(shè)置精英解緩沖池大小的參數(shù)設(shè)置局部搜索節(jié)點排序策略實驗結(jié)果對比本章小結(jié)總結(jié)與展望論文總結(jié)研究展望參考文獻作者簡歷及攻讀碩士學(xué)位期間取得的研究成果獨創(chuàng)性聲明學(xué)位論文數(shù)據(jù)集北京交通大學(xué)碩士學(xué)位論文引言研究背景與意義采購，生產(chǎn)和分配是供應(yīng)鏈的三個傳統(tǒng)階段。近年來，生產(chǎn)設(shè)施內(nèi)部和外部之間材料和信息流的管理
8、己受到越來越多的關(guān)注。此外，運送貨物和商品的成本占供
