論文-禁忌搜索算法

1、基于禁忌搜索算法的車輛路徑選擇摘要：本文從 VRP的提出背景與求解方法出發(fā)，闡釋了禁忌搜索算法的原理與影響算法性 能的關(guān)鍵因素，進而將禁忌搜索算法的思想運用于解決車輛路徑問題，在VRP問題初始解的基礎(chǔ)上，用禁忌搜索算法優(yōu)化車輛配送路線，設(shè)計出直觀且策略易于理解的客戶直接排列的解的表示方法，最后將該算法用C語言實現(xiàn)并用于求解 VRP問題，測試結(jié)果表明該算法可行且解的質(zhì)量較高。關(guān)鍵詞：車輛路徑問題；禁忌搜索；鄰域；禁忌表1 .引言物流配送過程的成本構(gòu)成中，運輸成本占到52%之多，如何安排運輸車輛的行駛路徑，使得配送車輛依照最短行駛路徑或最短時間費用，在滿足服務(wù)時間限制、車輛容量限制、行駛里程限制等

2、約束條件下，依次服務(wù)于每個客戶后返回起點，實現(xiàn)總運輸成本的最小化，車輛路徑問題正是基于這一需求而產(chǎn)生的。求解車輛路徑問題（ Vehicle Routing Problem 簡記 VRP）的方法分為精確算法與啟發(fā)式算法，精確算法隨問題規(guī)模的增大，時間復雜度與空間復雜度呈指數(shù)增長，且 VRP問題屬于NP-hard問題，求解比較困難，因此啟發(fā)式算法成為 求解VRP問題的主要方法。禁忌搜索算法是啟發(fā)式算法的一種，為求解VRP提供了新的工具。本文通過一種客戶直接排列的解的表示方法，設(shè)計了一種求解車輛路徑問題的新的禁忌搜索算法。因此研究車輛路徑問題， 就是要研究如何安排運輸車輛的行駛路線，使運輸車輛依照最

3、短的行駛路徑或最短的時間費用，依次服務(wù)于每個客戶后返回起點，總的運輸成本實現(xiàn)最小。2 .車輛路徑問題的禁忌搜索算法2.1 車輛路徑問題的描述車輛路徑問題的研究目標是對一系列送貨點或取貨點，確定適當?shù)呐渌蛙囕v行駛路線，使車輛有序地通過它們，在滿足一定的約束條件（如貨物需求量、發(fā)送量交發(fā)貨時間、車輛容量限制、行駛里程限制、時間限制等）下，達到一定的目標（如路程最短、費用最小、時間盡量少、使用車輛盡量少等 ）。參見下圖2.1所示：其中0表示配送中心，18表示客戶 編號。圖2.1車輛路徑問題在本文中為使得問題易于理解， 將該問題描述為：有一定數(shù)量的客戶， 各自有不同數(shù)量 的貨物需求，且每個客戶的位置和

4、需求量一定， 一個物流中心提供這些貨物，并有一個車隊 負責分送貨物，每臺配送車輛的載重量一定，這里假設(shè)車輛的型號一致，即最大載重量和最遠行駛里程數(shù)相同， 要求合理安排車輛配送路線， 使配送總路程最短，同時得滿足一定的約 束條件，即每條路線總需求量之和不得超過配送車輛的載重量、每條路線行駛的里程數(shù)不得超過配送車輛的最遠里程數(shù)、每一客戶需求必須滿足且僅由一臺車輛配送。禁忌搜索算法描述禁忌搜索算法思想最早由 Glover在1986年提出的，是一種全局逐步尋優(yōu)算法。其求解 的過程是先求得一初始解， 然后在鄰域中搜索較佳解或是移動到較差的區(qū)域搜索該區(qū)域最佳 解，并且記錄曾經(jīng)搜尋的路徑，作為下次搜索的依據(jù)

5、，以避免陷入局部最優(yōu)解中。它引入了一個禁忌表記錄下已經(jīng)搜索過的局部最優(yōu)點，在下一次搜索中利用禁忌表中的信息不再或者有選擇地搜索這些點，以此來跳出局部最優(yōu)點，從而實現(xiàn)全局優(yōu)化。將禁忌搜索的思想條理化，可描述如下圖 2.2所示：圖2.2禁忌搜索算法框架3車輛路徑問題的禁忌搜索算法實現(xiàn)3.1算法思路本文先用插入式啟發(fā)算法得到車輛路徑問題的初始可行解，再利用禁忌搜索算法對初始解進行改造。具體步驟如下：(1)構(gòu)造初始解時，先用客戶直接排列的解的表示方法，隨機生成某一不重復的客戶排列 序列，然后按照車輛路徑問題的約束條件，依次將解的元素(客戶)劃入各條配送路徑中， 由此產(chǎn)生車輛路徑問題的初始解，計算出當前

6、解的目標函數(shù)值，這里的目標函數(shù)值為各車輛配送路徑的里程數(shù)總和。(2)通過隨機交換兩客戶位置來生成當前解的鄰域解，則有C2n=n*(n-1)/2個客戶直接排列序列，然后按照車輛路徑問題的約束條件，依次將解的元素(客戶)劃入各條配送路徑中，由此計算出各鄰域解的目標函數(shù)值。(3)根據(jù)藐視準則來評價當前解的鄰域解，更新當前解與禁忌表。若候選解的目標值優(yōu)于當前的最優(yōu)目標值，不管其禁忌屬性如何， 更新為當前最優(yōu)解并更新禁忌表， 否則判別該方 案的兩個客戶交換是否被禁忌： 若被禁忌，選取次優(yōu)解后繼續(xù)該步驟； 若未被禁忌，更新該 解為當前解并更新禁忌表。(4)若所有的候選對象均被禁忌，則根據(jù)隊列FIFO原則，

7、對禁忌表中隊頭元素取消其禁忌屬性；禁忌表的更新為將其中所有的禁忌對象的禁忌長度減1,禁忌長度為0的對象取消其禁忌屬性。(5)重復迭代指定步長的(2)(4),輸出車輛配送方案的最終結(jié)果。3.2程序設(shè)計簡介算法中，無論是初始解的構(gòu)造還是鄰域內(nèi)尋優(yōu)，都涉及到對大量配送點進行的操作，如構(gòu)造初始解時，針對車輛路徑問題的約束條件將客戶劃分到不同的路徑中；更新禁忌表時的將禁忌對象放入表中以及滿足藐視準則時的禁忌對象的解禁。程序中針對該問題，采用了隊列的形式，通過改進的隊列基本操作來實現(xiàn)路徑的分配與禁忌表的更新問題。下面給出定義的幾個結(jié)構(gòu)體：typedef struct QHodei“定義禁忌對象的存儲結(jié)構(gòu)i

8、-nt -舞螢struct 0Hode*next進先出原則出隊struict CPoint"該結(jié)構(gòu)體用于定義坐標點 lint x; int V 二struct“定義每個鄰域解的路徑存儲方案結(jié)構(gòu) lot *base; lit Front; lint rear;>SqiQuue;int Flag設(shè)置簿忌對痛禁忌步長>QHode ,«|ueuePtr;typedef struct“定義禁忌表的存儲結(jié)構(gòu)QueuePtr front;QueuePtr rear;>Linl<Queije;typedlef struct(“定義當前解的鄰域解的目標函數(shù)算的建儲結(jié)構(gòu)

9、 double3”用于在錄各方案耀崔妙 Mnl門啊;“用于標記該方案是否可用>dist3ince;(1)客戶位置的無重復隨機生成以及客戶需求量的隨機生成實際配送系統(tǒng)中的客戶的地理位置相對獨立，且彼此之間服從獨立均勻分布，為簡易起見，程序中對客戶的地理位置分布與客戶的需求量只簡單地使用C語言中的rand()函數(shù)進行隨機分配，其中物流中心的地理位置默認為(0, 0),為了保證生成的客戶位置沒有重復，用 c_locationj.x=c_locationi.x && c_locationj.y=c_locationi.y語句來判定，其中c_location數(shù)組采用 CPoint結(jié)

10、構(gòu)體，用于存儲客戶的位置，demand數(shù)組用于存儲客戶需求量，這兩個數(shù)組均被定義為全局變量。 (2)客戶隨機序列的生成算法中采用客戶直接排列的解的表示方式，隨機生成初始解，即無重復的客戶隨機排列序列數(shù)組A。(3)初始解的車輛路徑分配將客戶隨機序列數(shù)組 A中的各個值賦值到i_now數(shù)組中，i_now數(shù)組用于記錄當前的最 優(yōu)解，定義車輛的最大負載量vehicle_Max ,這里假設(shè)物流中心車輛的型號一致并且不考慮車輛的最大行駛距離。(4)當前解的鄰域結(jié)構(gòu)通過依次交換兩客戶位置來生成當前解的鄰域解，則有C2n=n*(n-1)/2個客戶直接排列序列。i_now的鄰域解，用數(shù)組 exchange_sol

11、ution記錄。用與初始分配方案相似的算法，可 以求出exchange_solution數(shù)組中每一個車輛分配路線的車輛數(shù)以及車輛所行駛的總里程數(shù)， 分別記錄到數(shù)組 N_num和s中。（5）尋找當前解鄰域結(jié)構(gòu)的評價值最優(yōu)方案先從數(shù)組s中尋找到車輛行駛里程數(shù)最短的方案，記其下標為ibest,判斷該方案是由當前解的哪兩個客戶交換得到的，記作i_x和i_y。根據(jù)禁忌準則對該局部最優(yōu)解進行處理，可以替換為當前最優(yōu)解的條件有二：（1）這兩個元素的交換是可行的、未被禁忌的；（2）其解優(yōu)于當前解，不管其是否禁忌均替換當前最優(yōu)解，更新禁忌表，將禁忌表中各禁忌對象的禁忌步長減1,當禁忌步長為。時，取消禁忌對象的禁

12、忌屬性，而當替換方案中的所有對象均 被禁忌后，根據(jù) FIFO原則，取消隊頭元素的禁忌屬性。4 .算例分析這里用Microsoft Visual C+對車輛路徑問題的禁忌搜索算法進行編程， 通過對相對獨立 的隨機分布在（0, 100平方公里范圍內(nèi)的指定客戶數(shù)、且客戶的需求為的（0,指定的客戶數(shù)范圍內(nèi)的隨機數(shù)的 VRP實例進行求解，進行了實驗計算。設(shè)在某物流中心有10臺配送車輛，車輛的最大載重量均為 10單位，在不考慮車輛一次 配送的最大行駛距離的情況下，需要向 10個客戶運送貨物，作者利用計算機隨機產(chǎn)生了范 圍在0100內(nèi)的10個客戶的位置坐標 （坐標無重復情況）以及客戶的貨物需求量，其中物流中

13、心的坐標默認為（0, 0）,各個客戶的坐標位置與需求量如下圖2.3所示，要求合理安排配送車輛的行車路徑，使配送的總里程數(shù)最短。為簡便起見，本文設(shè)各客戶相互之間及物流中心與客戶之間的距離均采用直線距離，該距離可根據(jù)客戶和物流中心的坐標計算得到， 如下圖2.4所示?？蛻艟幪?2345678910橫坐標X7101417202023232730縱坐標y2573542513131797928貨物需求量22354961063圖2.3禁忌搜索算法相關(guān)信息圖2.4客戶地理位置分布情況及車輛路徑分配由算法的運行結(jié)果可知：初始解方案中所調(diào)派的車輛數(shù)為7、車輛所行駛的總里程數(shù)為731.46,車輛的配送方案為0-4-

14、0、0-7-0、0-8-0、0-6-0、0-9-10-0、0-3-2-5-0、0-1-0,而用禁忌搜索算法對初始解進行改進后所得到的最終方案為：車輛數(shù)為 6、車輛所行駛的總里程 數(shù)為 353.96,車輛的分配方案為0-1-7-0、0-4-0、0-6-0、0-8-0、0-10-3-2-0、0-5-9-0,車輛所行駛的總里程數(shù)得到很大程度的改善，且得到全局較優(yōu)解所花費的時間僅為0.05s。5 總結(jié)本文基于車輛路徑問題的簡單描述，采用客戶直接排列的解的表示方法，相比較現(xiàn)有研究成果將車輛路徑問題描述為網(wǎng)絡(luò)圖問題的有向邊排列方法，表示更加直觀、算法策略更加簡單并易于理解，而且算法在迭代過程中產(chǎn)生的解均為可行解，算法的收斂速度得到明顯改善。 實驗的計算結(jié)果表明，用禁忌搜索算法求解車輛路徑問題能夠跳出局部最優(yōu)解，實現(xiàn)全局最優(yōu)化，所得到的最終解決方案相比較初始方案質(zhì)量更優(yōu)，尋優(yōu)性能良好。參考文獻：1 李軍，郭耀輝車輛優(yōu)化調(diào)度理論與方法M 北京：中國物資出版社，2