最小-最大車輛路徑問題的禁忌搜索算法

《最小-最大車輛路徑問題的禁忌搜索算法》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。

1、最小-最大車輛路徑問題的禁忌搜索算法第25卷第1期(總第157期)2007年1月系統(tǒng)工程SystemsEngineeringV01.25.No.】Jan..2007文章編號:1001—4098(2007)Ol一0049—04最小一最大車輛路徑問題的禁忌搜索算法劉霞,齊歡(1.華中科技大學系統(tǒng)工程研究所,湖北武漢430074;2.江漢大學物理與信息工程學院,湖北武漢430056)摘要:在對最小一最大車輛路徑問題進行描述的基礎上.建立了該問題的基本數(shù)學模型.針對最小一最大車輛路徑問題的目標是最小化整個線路的最長子線路,本文提出了改進的禁忌搜索算法.并用一些典型算例進行了驗證.計算

2、結果表明.用該算法求解最小一最大車輛路徑問題,不僅可以取得較好的計算結果.而且算法的計算效率較高.收斂速度較快.關鍵詞:最小一最大車輛路徑問題;禁忌搜索;啟發(fā)式中圖分類號:o2l1文獻標識碼:A引言車輛路徑問題(VehicleRoutingProblem,VRP)是指對一系列發(fā)貨點(或收貨點)組成適當?shù)男熊嚶肪€,使車輛有序地通過它們,并能在滿足一定的約束條件下.達到諸如路程最短,費用最小或耗費時間盡量少等目的.該類問題具有很強的實際應用背景.而且屬于NP—hard.因此自它在1959年由Dantzig和Ramser首次提出以來就得到了專家學者的極大重視并進行了大量的研究[J]

3、.車輛路徑問題的求解方法可以分為三類:精確算法,經(jīng)典啟發(fā)式算法和現(xiàn)代啟發(fā)式算法.精確算法如樹搜索法,分枝定界法,整數(shù)線性規(guī)劃等.由于大部分實際問題都難以找到最優(yōu)解,因此這類算法往往只能用于求解小規(guī)模問題;經(jīng)典啟發(fā)式算法有節(jié)約法,構造法,兩階段法和不完全優(yōu)化算法等;現(xiàn)代啟發(fā)式算法是近2O年發(fā)展起來的智能算法,如模擬退火算法,遺傳算法,禁忌搜索算法和蟻群優(yōu)化等.在實際情況中,存在這樣的一類車輛路徑問題.它們的基本定義和約束條件與經(jīng)典VRP一致,但目標不是要求整個行車路線的路程最短或費用最少,而是要求整個線路中行程最長的子線路距離最短或時間最短.如出于社會因素考慮的校車行車線路制定

4、[4],郵遞員投送報紙,巡邏車隊的巡邏線路制定,緊急情況下空投物資的運送等.這類問題稱為最小一最大車輛路徑問題(Min—MaxVehicleRoutingProblem.MMVRP).本文將改進的禁忌搜索算法應用于最小.最大車輛路徑問題.并用實例進行測試.取得了很好的效果.2最小一最大車輛路徑問題最小一最大車輛路徑問題可以描述為:有一個中心倉庫.用0表示.擁有輛相同型號的車.容量都為Q,現(xiàn)有個客戶點的運輸任務需要完成,以1.2,…,表示.第個客戶點的貨運量為q(=1.2,….),且maxq~Q.每輛車從倉庫出發(fā).經(jīng)過一系列客戶點并裝載貨物,最終回到倉庫.規(guī)定每個客戶點的任務必

5、須且只能由一輛車來完成.要求整個線路中行程最長的子線路長度盡可能短具體的數(shù)學模型可表示如下:目標函數(shù):2=min{max(∑∑d)+),k=l,2,…,re(1)=D;D約束:∑∑=0=0.1,2,…,=0.1.2.…,(2)(3)∑一∑=0,k=o.1.2.…,州;戶一'1,2,….J=0i0(4)*收稿日期:2006一10—29基金項目:國家自然科學基金資助項目(60574088)作者簡介:劉霞(1977一),女.華中科技大學博士研究生,江漢大學講師,研究方向:系統(tǒng)集成與優(yōu)化;齊歡,男.華中科技大學教授,博士生導師,研究方向:復雜系統(tǒng)建模與仿真,系統(tǒng)分析與集成.,●l1=

6、:50系統(tǒng)工程2007焦∑∑q,k≤Q.k一1,2,…,(5)f一0J一0其中,表示車輛數(shù);表示客戶數(shù);d,,表示客戶到客戶的距離,若已知客戶節(jié)點的坐標,往往采用Euclidean方法計算距離;q.表示客戶i的貨運量;Q表示每輛車的裝載容量;如果車輛k從客戶離開到達客戶J.為1,否則為0;表示罰值,可設為一個較大的正數(shù).約束(2)和(3)保證每個客戶點有且僅有一輛車經(jīng)過一次;約束(4)保證了子線路的連續(xù)性,即車輛到達了一個貨物點,也必須從該點離開;約束(5)為容量約束,規(guī)定了每條子線路裝載的貨物量不能超出車輛的容量.為滿足條件(5),在目標函數(shù)中加入了罰值,即如果某條子線路裝

7、載的貨物量超出車輛的裝載容量,目標函數(shù)為max(∑∑d,,)+M.此時M為一個很大的正數(shù),否則…0=0目標函數(shù)為max(∑∑d,,),即M為0.一0J一03禁忌搜索禁忌搜索(TabuSearch,TS)的思想最早由Glover(1986)提出,它是對局部搜索的一種擴展,是一種全局逐步尋優(yōu)算法,是對人類智力過程的一種模擬.TS算法通過引入一個靈活的存儲結構和相應的禁忌準則來避免迂回搜索,并通過特赦準則來赦免一些被禁忌的優(yōu)良狀態(tài),進而保證多樣化的有效探索以最終實現(xiàn)全局優(yōu)化].禁忌搜索的基本流程可描述如下:(