免疫克隆算法在垃圾收集車輛調(diào)度問題中的應(yīng)用

【摘 要】本文通過對(duì)免疫克隆算法的研究提出一種垃圾收集車輛路徑優(yōu)化方案，并進(jìn)行仿真實(shí)驗(yàn)和分析。

【關(guān)鍵詞】垃圾收集 免疫克隆算法 路徑優(yōu)化

1 車輛調(diào)度問題

車輛調(diào)度問題（VRP）是由Dantzig和Rmaser提出來的，指的是考慮車輛裝載能力、車輛最大行駛距離等因素的前提下，根據(jù)顧客的需求，確定車輛的行駛路線，以總費(fèi)用最低為目標(biāo)，追求經(jīng)濟(jì)效益的最大化和實(shí)現(xiàn)過程的最優(yōu)化。如果把顧客看成一個(gè)對(duì)象，顧客所在的固定位置看成是節(jié)點(diǎn)，車輛調(diào)度問題可以描述為：求解在服務(wù)車輛有最大載重量和最大行駛距離的前提下，使得車輛對(duì)每一個(gè)節(jié)點(diǎn)的對(duì)象都能訪問、并且只能訪問一次的最短行程的派車方案。

2 免疫遺傳算法

生物在自然界中的生存繁衍，顯示出了其對(duì)自然環(huán)境的自適應(yīng)能力。受其啟發(fā)， 人們致力于對(duì)生物各種生存特性的機(jī)理研究和行為模擬，為人工自適應(yīng)系統(tǒng)的設(shè)計(jì)和開發(fā)提供了廣闊的前景。遺傳算法（Genetic Algorithms）就是這種生物行為的計(jì)算機(jī)模擬中令人矚目的重要成果?；趯?duì)生物遺傳和進(jìn)化過程的計(jì)算機(jī)模擬，遺傳算法使得各種人工系統(tǒng)具有優(yōu)良的自適應(yīng)能力和優(yōu)化能力。

3 免疫克隆算法解決問題的算法實(shí)現(xiàn)

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

4 數(shù)值實(shí)驗(yàn)與分析

假設(shè)有8個(gè)收集點(diǎn)和一個(gè)垃圾中轉(zhuǎn)中心的垃圾收集系統(tǒng)，各個(gè)收集點(diǎn)的需求為（i= l，2，…，8），中轉(zhuǎn)中心用兩輛車（載重量為8）收集，收集點(diǎn)與收集中心的距離如表一所示。要求優(yōu)化收集線路，使得收集成本最小化。

用基于克隆選擇的免疫遺傳算法對(duì)上述問題進(jìn)行求解，變異率如果太小， 則產(chǎn)生新的染色體概率小，導(dǎo)致不成熟的收斂；太大，可能使優(yōu)秀染色體的破壞機(jī)會(huì)增加， 甚至不能收斂， 應(yīng)多次實(shí)驗(yàn)調(diào)整或者采用自適應(yīng)方法調(diào)整變異率通過上機(jī)運(yùn)算，得到的線路有：

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

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

運(yùn)輸總距離 = 83.5

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

表1 收集點(diǎn)間距離以及收集量

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

參考文獻(xiàn)：

[1] 張震.城市貨運(yùn)汽車營運(yùn)組織最優(yōu)化的理論與方法.管理工程學(xué)報(bào)，Vol 9.No.3，P143-152.

[2] 蔡延光，錢積新，孫優(yōu)賢.多重運(yùn)輸調(diào)度問題基于雙表的并行表搜索算法.系統(tǒng)工程理論與實(shí)踐，1998，Vol.18，No.1l，p20-26.

作者簡介：

康彥（1982-），男，安徽合肥人，碩士，講師，主要研究方向：計(jì)算機(jī)應(yīng)用技術(shù)。

基金項(xiàng)目：

2013年高校省級(jí)自然科學(xué)研究項(xiàng)目“垃圾中轉(zhuǎn)站HY1600-2型全封閉垃圾壓縮機(jī)液壓測(cè)控系統(tǒng)研制”（KJ2013Z011）