資源描述:
《最小_最大車輛路徑問題的禁忌搜索算法》由會員上傳分享,免費在線閱讀,更多相關內(nèi)容在行業(yè)資料-天天文庫。
1、第25卷第1期(總第157期)系統(tǒng)工程Vol.25,No.12007年1月SystemsEngineeringJan.,2007文章編號:1001-4098(2007)01-0049-04最小-最大車輛路徑問題的禁忌搜索算法1,21劉霞,齊歡(1.華中科技大學系統(tǒng)工程研究所,湖北武漢430074;2.江漢大學物理與信息工程學院,湖北武漢430056)摘要:在對最小-最大車輛路徑問題進行描述的基礎上,建立了該問題的基本數(shù)學模型。針對最小-最大車輛路徑問題的目標是最小化整個線路的最長子線路,本文提出了改進的禁忌搜索算法,并用一些典型算例進行了驗證。計算結果表明,用該算法求解最小-最大車輛路
2、徑問題,不僅可以取得較好的計算結果,而且算法的計算效率較高,收斂速度較快。關鍵詞:最小-最大車輛路徑問題;禁忌搜索;啟發(fā)式中圖分類號:O211文獻標識碼:A法應用于最小-最大車輛路徑問題,并用實例進行測試,取1引言得了很好的效果。車輛路徑問題(VehicleRoutingProblem,VRP)是指2最小-最大車輛路徑問題對一系列發(fā)貨點(或收貨點)組成適當?shù)男熊嚶肪€,使車輛有序地通過它們,并能在滿足一定的約束條件下,達到諸最小-最大車輛路徑問題可以描述為:有一個中心倉如路程最短、費用最小或耗費時間盡量少等目的。該類問庫,用0表示,擁有m輛相同型號的車,容量都為Q,現(xiàn)有題具有很強的實際應
3、用背景,而且屬于NP-hard,因此自n個客戶點的運輸任務需要完成,以1,2,…,n表示,第i它在1959年由Dantzig和Ramser首次提出以來就得到個客戶點的貨運量為qi(i=1,2,…,n),且maxqi4、表示如下:優(yōu)解,因此這類算法往往只能用于求解小規(guī)模問題;經(jīng)典目標函數(shù):啟發(fā)式算法有節(jié)約法、構造法、兩階段法和不完全優(yōu)化算nnkz=min{max(∑∑dijxij)+M},k=1,2,…,m(1)法等;現(xiàn)代啟發(fā)式算法是近20年發(fā)展起來的智能算法,如i=0j=0模擬退火算法、遺傳算法、禁忌搜索算法和蟻群優(yōu)化等。約束:nm在實際情況中,存在這樣的一類車輛路徑問題,它們k∑∑xij=1,j=0,1,2,…,n(2)的基本定義和約束條件與經(jīng)典VRP一致,但目標不是要i=0k=1nm求整個行車路線的路程最短或費用最少,而是要求整個線xk=1,i=0,1,2,…,n(3)∑∑ijj=0k=1路中行
5、程最長的子線路距離最短或時間最短,如出于社會nn[4]kk因素考慮的校車行車線路制定,郵遞員投送報紙,巡邏∑xip-∑xpj=0,k=0,1,2,…,m;p=1,2,…,ni=0j=0車隊的巡邏線路制定,緊急情況下空投物資的運送等。這(4)類問題稱為最小-最大車輛路徑問題(Min-MaxVehicleRoutingProblem,MMVRP)。本文將改進的禁忌搜索算收稿日期:2006-10-29基金項目:國家自然科學基金資助項目(60574088)作者簡介:劉霞(1977-),女,華中科技大學博士研究生,江漢大學講師,研究方向:系統(tǒng)集成與優(yōu)化;齊歡,男,華中科技大學教授,博士生導師,研
6、究方向:復雜系統(tǒng)建模與仿真,系統(tǒng)分析與集成。50系統(tǒng)工程2007年nn和節(jié)約法相結合,生成初始解。步驟如下:k∑∑qixij≤Q,k=1,2,…,m(5)i=0j=0(1)從客戶列表中隨機選擇一個節(jié)點,作為一條子線其中,m表示車輛數(shù);n表示客戶數(shù);dij表示客戶i到客戶路經(jīng)過的第一個客戶節(jié)點,同時將該節(jié)點從客戶列表中刪j的距離,若已知客戶節(jié)點的坐標,往往采用Euclidean方除,并設該客戶節(jié)點為當前節(jié)點current,此時該子線路裝法計算距離;qi表示客戶i的貨運量;Q表示每輛車的裝載的貨物量demand=q(current),長度distance=d(de-k載容量;如果車輛k從客
7、戶i離開到達客戶j,xij為1,否則pot,current)+d(current,depot)。為0;M表示罰值,可設為一個較大的正數(shù)。(2)若客戶列表為空,表明所有客戶節(jié)點都已被分約束(2)和(3)保證每個客戶點有且僅有一輛車經(jīng)過配,初始解產(chǎn)生,結束;否則轉步驟(3)。一次;約束(4)保證了子線路的連續(xù)性,即車輛到達了一(3)以當前節(jié)點current為基礎,采用節(jié)約法計算子個貨物點,也必須從該點離開;約束(5)為容量約束,規(guī)線路的下一節(jié)點。即