車輛路徑問題的禁忌搜索算法研究

《車輛路徑問題的禁忌搜索算法研究》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、車輛路徑問題的禁忌搜索算法研究郎茂祥，胡思繼（北方交通大學(xué)交通運輸學(xué)院，北京100044）摘要：論文在對車輛路徑問題進行簡單描述的基礎(chǔ)上，通過設(shè)計一種新的解的表示方法構(gòu)造了求解該問題的一種新的禁忌搜索算法，并進行了實驗計算。計算結(jié)果表明，用本文設(shè)計的禁忌搜索算法求解車輛路徑問題，不僅可以取得很好的計算結(jié)果，而且算法的計算效率較高，收斂速度較快，計算結(jié)果也較穩(wěn)定。關(guān)鍵詞：車輛路徑問題；禁忌搜索算法；優(yōu)化StudyontheTabuSearchAlgorithmforVehicleRoutingProblemLANGMao-xiang，HUSi-ji（Schoolof

2、TrafficandTransportation，NorthernJiaotongUniversity，Beijing100044，China）Abstract：Onthebasisofdescribingthevehicleroutingproblembriefly,thispaperpresentsanewsolutionindicatingmethodthenbuildsanewtabusearchalgorithmfortheproblemandmakesomeexperimentalcomputations.Thecomputationalresults

3、demonstratesthatthehighqualitysolutionstothevehicleroutingproblemcanbeobtainedbyusingthenewtabusearchalgorithm,andthenewalgorithmisalsoefficientandrobust.Keywords：vehicleroutingproblem;tabusearchalgorithm;optimal1引言車輛路徑問題（VRP，VehicleRoutingProblem）是由Dantzig和Ramser于1959年提出的[1]。該問題一直是運籌

4、學(xué)與組合優(yōu)化領(lǐng)域的前沿與熱點問題。在現(xiàn)實生產(chǎn)和生活中，郵政投遞問題、飛機、鐵路列車、水運船舶及公共汽車的調(diào)度問題、電力調(diào)度問題、管道鋪設(shè)問題、計算機網(wǎng)絡(luò)拓撲設(shè)計問題等都可以抽象為車輛路徑問題。研究車輛路徑問題具有重要的理論和現(xiàn)實意義。車輛路徑問題作為一個NP難題，隨著客戶數(shù)量的增加，可選的車輛路徑方案數(shù)量將以指數(shù)速度急劇增長。因此，用啟發(fā)式算法求解該問題就成為人們研究的一個重要方向。求解車輛路徑問題的方法很多，常用的有旅行商法、動態(tài)規(guī)劃法、節(jié)約法、掃描法[2]、分區(qū)配送算法[3]、方案評價法等。禁忌搜索算法的出現(xiàn)，為求解車輛路徑問題提供了新的工具。Gendreau

5、、Jiefeng、Barbarosoglu、蔡延光等都曾利用禁忌搜索算法求解車輛路徑問題[4-8]，并取得了一些研究成果。但現(xiàn)有研究成果多將車輛路徑問題描述為一個網(wǎng)絡(luò)圖問題，因此在設(shè)計其禁忌搜索算法時多采用有向邊排列的解的表示方法，基于這種解的表示方法所構(gòu)造的禁忌搜索算法具有以下缺點：（1）由于解的表示不太直觀，使得算法策略不僅較為復(fù)雜，而且不易理解；（2）解中的元素較多，不僅占用的計算機存儲量較大，而且求解時計算時間較長，搜索效率較低；（3）算法迭代過程中產(chǎn)生的解中不可行解很多，從而大大影響了算法的收斂速度。為了克服現(xiàn)有禁忌搜索算法的缺點，本文在對車輛路徑問題進

6、行簡單描述的基礎(chǔ)上，提出了一種新的解的表示方法——客戶直接排列的解的表示方法，并基于這種解的表示方法構(gòu)造了求解車輛路徑問題的一種新的禁忌搜索算法，并通過實驗計算證明了這種新的禁忌搜索算法的良好尋優(yōu)性能。52車輛路徑問題的禁忌搜索算法的設(shè)計2.1車輛路徑問題的描述為了使問題易于理解，本文用一個配送車輛調(diào)度問題描述車輛路徑問題。該問題可以描述為：從某物流中心用多臺配送車輛向多個客戶送貨，每個客戶的位置和需求量一定，每臺配送車輛的載重量一定，其一次配送的最大行駛距離一定，要求合理安排車輛配送路線，使配送總里程最短，并滿足以下約束條件：（1）每條配送路徑上各客戶的需求量之

7、和不超過配送車輛的載重量；（2）每條配送路徑的長度不超過配送車輛一次配送的最大行駛距離；（3）每個客戶的需求必須滿足，且只能由一臺配送車輛送貨。2.2禁忌搜索算法的原理和實現(xiàn)步驟利用禁忌搜索算法求解組合優(yōu)化問題時，首先按照隨機方法產(chǎn)生一個初始解作為當(dāng)前解，然后在當(dāng)前解的鄰域中搜索若干個解，取其中的最好解作為新的當(dāng)前解。為了避免對已搜索過的局部最優(yōu)解的重復(fù)，禁忌搜索算法使用禁忌表記錄已搜索的局部最優(yōu)解的歷史信息，這使得算法可在一定程度上避開局部最優(yōu)點，從而開辟新的搜索區(qū)域。用禁忌搜索算法求解組合優(yōu)化問題時，其實現(xiàn)步驟為（以目標(biāo)函數(shù)求最小為例）：第一步：選定一個初始解

8、xnow；