求解帶裝載能力限制的開放式車輛路徑問題的遺傳算法

《求解帶裝載能力限制的開放式車輛路徑問題的遺傳算法》由會員上傳分享，免費在線閱讀，更多相關內容在工程資料-天天文庫。

1、第26卷第2期(總第170期)系統工程Vol.26,No.22008年2月SystemsEngineeringFeb.,2008文章編號:100124098(2008)0220078206X求解帶裝載能力限制的開放式車輛路徑問題的遺傳算法符卓,聶靖(中南大學交通運輸工程學院,湖南長沙410075)摘要:對帶裝載能力限制的開放式車輛路徑問題的求解進行了研究,提出了一種用于求解該問題的遺傳算法。對算法中幾個關鍵操作的不同實現方式的性能進行了比較。給出了算法對標準測試算例的運算結果,并與文獻中目前最好的

2、結果進行了比較和分析。關鍵詞:車輛路徑問題;開放式車輛路徑問題;遺傳算法;物流配送中圖分類號:U491文獻標識碼:A車輛路徑問題(vehicleroutingproblem,VRP)存在于合式VRP中,每一條路線都是哈密頓圈(Hamiltoniancy2物流配送運輸等運輸服務的運輸路線編排問題中,是近二cle),而在OVRP中是哈密頓路徑(Hamiltonianpath),兩十多年來運籌學界的研究熱點之一。其一般描述是:對一者都屬于NP2難問題。眾所周知,用精確算法求解NP2難問系列給定的客戶點,

3、要求確定適當的車輛行駛路線,使其題時,其算法的計算量一般將隨著問題規(guī)模的增大而呈指從車場(如配送中心等)出發(fā),有序地對它們進行服務,并數增長。從實際應用的角度來說,普遍接受的明智做法是在滿足一定的約束條件下(如車輛載重量、客戶需求量、時設計相應的啟發(fā)式算法,在可接受的時間內求出問題的近間窗限制等),使總運輸成本達到最小(如使用車輛數最優(yōu)解。少、車輛行駛總距離最短等)。本文將研究提出一種求解帶裝載能力限制的開放式為了便于對VRP進行系統的研究,運籌學界將其分車輛路徑問題的遺傳算法,并對所采用的新的遺

4、傳算子和[1]為兩大類:閉合式VRP和開放式VRP。當車輛完成運輸幾種改進策略對算法性能的影響進行對比,更進一步地,任務后必須返回原出發(fā)點時(即車輛的行駛路線是閉合式將計算結果與文獻中已有的其它算法的結果相比較,分析的),稱之為閉合式VRP,一般就簡稱為車輛路徑問題用遺傳算法求解OVRP的可行性和優(yōu)劣性。(VRP);當不要求車輛完成任務后返回原出發(fā)點,或者是要求其沿原去程路線返回時(即車輛的行駛路線是開放1問題的分析式的),稱之為開放式VRP(openvehicleroutingproblem,帶

5、裝載能力限制的OVRP(capacitatedOVRP,OVRP)。在不需要嚴格區(qū)分的場合,統稱為車輛路徑問題COVRP),是OVRP中的最基本類型。該問題的主要約束(VRP)。條件有,每條線路開始于車場,終止于某一個客戶點(或反VRP被提出來后,國內外學術界首先對以物流配送過來);每個客戶點由一輛車訪問(服務)一次且僅一次,且為應用背景的閉合式VRP進行了廣泛研究,取得了許多其需求量全部得到滿足;每一條路線上各客戶點的需求量令人注目的成果。而對于OVRP,盡管以往有過一些有關之和不超過其車輛裝載

6、能力。優(yōu)化目標一般包括:(1)最小的案例描述及其研究報道,但直到最近幾年,在閉合式化所使用的車輛數(假設每一條線路由一輛車負責,因此VRP的研究基礎上,才開始從理論上對其進行系統的研有時也稱最小化線路數),(2)最小化車輛總行駛路程或時究。文獻[2]對其研究進展進行了簡要的歸納和分析。間。對于VRP,其求解算法的研究一直是研究的重點和難Sariklis和Powell是最早對COVRP進行研究的學點。與閉合式VRP相比,在OVRP中沒有車輛必須返回原者,他們提出了一個基于最小生成樹的兩階段啟發(fā)式算出

7、發(fā)點的限制,但這并沒有使問題變得簡單和容易。在閉法[3]。在算法的第一階段,首先根據車輛的裝載能力對客X收稿日期:2007209222;修訂日期:2007211223基金項目:國家自然科學基金資助項目(70671108)作者簡介:符卓(19602),男,中南大學交通運輸工程學院教授,博士生導師,研究方向:交通運輸規(guī)劃與管理,物流配送管理。第2期符卓,聶靖:求解帶裝載能力限制的開放式車輛路徑問題的遺傳算法79戶點進行分組,并使得所形成的組數為最少,然后通過按用的車輛數目為K.給定的規(guī)則不斷調整客戶點

8、的分配,以降低各組中的運輸階段2:根據初始化條件隨機生成初始解。為了提高費用。在第二階段,通過對各組求解一個帶有罰值的最小初始解的多樣性及其質量,分別按如下兩種方式各生成種生成樹問題來產生開放式路徑,且通過迭代使不可行解逐群的一半組成。步轉變?yōu)榭尚薪?。①按K隨機生成初始解,不在乎其是否可行。以項數在此基礎上,我們也對COVRP進行了研究,提出了為(N+K)生成序列Y,其中N為客戶點數目,K為當前最一個用禁忌搜索這一現代啟發(fā)式算法來構造的求解算好解中所使用的車輛數目;該序列首項為0,