免疫克隆算法在垃圾收集車輛調度問題中的應用

【摘 要】本文通過對免疫克隆算法的研究提出一種垃圾收集車輛路徑優化方案，并進行仿真實驗和分析。

【關鍵詞】垃圾收集 免疫克隆算法 路徑優化

1 車輛調度問題

車輛調度問題（VRP）是由Dantzig和Rmaser提出來的，指的是考慮車輛裝載能力、車輛最大行駛距離等因素的前提下，根據顧客的需求，確定車輛的行駛路線，以總費用最低為目標，追求經濟效益的最大化和實現過程的最優化。如果把顧客看成一個對象，顧客所在的固定位置看成是節點，車輛調度問題可以描述為：求解在服務車輛有最大載重量和最大行駛距離的前提下，使得車輛對每一個節點的對象都能訪問、并且只能訪問一次的最短行程的派車方案。

2 免疫遺傳算法

生物在自然界中的生存繁衍，顯示出了其對自然環境的自適應能力。受其啟發， 人們致力于對生物各種生存特性的機理研究和行為模擬，為人工自適應系統的設計和開發提供了廣闊的前景。遺傳算法（Genetic Algorithms）就是這種生物行為的計算機模擬中令人矚目的重要成果?；趯ι镞z傳和進化過程的計算機模擬，遺傳算法使得各種人工系統具有優良的自適應能力和優化能力。

3 免疫克隆算法解決問題的算法實現

本節采用免疫克隆算法，來解決CVRP問題。通過一個實例證明該算法具有很好的全局和局部收斂能力，并且收斂速度快等特點。下面詳細說明免疫克隆算法求解CVRP問題步驟。步驟1：抗體編碼。本文采用簡單直觀的自然數編碼方法，用0表示垃圾中轉中心，用1，2，…，L表示各收集點。由于在垃圾中轉中心有K輛汽車，則最多存在K條收集路徑，每條收集路徑都始于收集中心，也終于垃圾中轉中心。為了在編碼中反映車輛收集的路徑，采用了增加K+1個虛擬垃圾中轉中心的方法，分別用L+1、L+2、…、L+K-1表示。這樣1，2，…，L+K-1這L+K-1個互不重復的自然數的隨機排列就構成一個個體，并對應一種收集路徑方案。

4 數值實驗與分析

假設有8個收集點和一個垃圾中轉中心的垃圾收集系統，各個收集點的需求為（i= l，2，…，8），中轉中心用兩輛車（載重量為8）收集，收集點與收集中心的距離如表一所示。要求優化收集線路，使得收集成本最小化。

用基于克隆選擇的免疫遺傳算法對上述問題進行求解，變異率如果太小， 則產生新的染色體概率小，導致不成熟的收斂；太大，可能使優秀染色體的破壞機會增加， 甚至不能收斂， 應多次實驗調整或者采用自適應方法調整變異率通過上機運算，得到的線路有：

路線1：0->4->2->6->0

路線2：0->3->7->5->8->1->0

運輸總距離 = 83.5

通過分析，此方案是此問題的一個可行解。

表1 收集點間距離以及收集量

結語：本文垃圾收集中的路徑最優化問題，提出了利用免疫算法求解該問題時存在的一些不足，通過改進此算法，增加了克隆選擇的機制，有效的彌補了免疫遺傳算法的不足。并通過較小規模的垃圾收集問題的仿真分析，得到了較好的效果。并且將這一理論思想應用到垃圾收集中轉系統當中。不足之處：沒有完全考慮到路徑等因素對收集路徑最優化問題影響，對系統的解決完全是建立在理想情況下的。

參考文獻：

[1] 張震.城市貨運汽車營運組織最優化的理論與方法.管理工程學報，Vol 9.No.3，P143-152.

[2] 蔡延光，錢積新，孫優賢.多重運輸調度問題基于雙表的并行表搜索算法.系統工程理論與實踐，1998，Vol.18，No.1l，p20-26.

作者簡介：

康彥（1982-），男，安徽合肥人，碩士，講師，主要研究方向：計算機應用技術。

基金項目：

2013年高校省級自然科學研究項目“垃圾中轉站HY1600-2型全封閉垃圾壓縮機液壓測控系統研制”（KJ2013Z011）