基于模擬退火算法的校園垃圾清運最優線路研究

張睿涵

摘要：目前，垃圾清理問題已經成為阻礙社會發展的一大重要因素，往往清理垃圾的成本與垃圾問題的解決本身有著密切的關聯，合理的清運線路既能節約成本又能提高效率。本文以北京師范大學校園為例，旨在運用數學建模方法實現校園垃圾回收最優方案。首先基于模擬退火算法得到理想模型中不考慮道路實際情況的垃圾清運路線，然后使用MATLAB進行元胞自動機模擬仿真得到實際路線信息，最后將實際路線信息替換理想模型中的距離信息，最終建立求解最優垃圾清運路線的數學模型，同時給出北師大校園垃圾的最優清理方案。

關鍵詞：模擬退火算法 元胞自動機模擬仿真

1問題的分析

垃圾清運指垃圾的收集和運輸，校園垃圾收運系統包括垃圾的收集、運輸和轉運三個部分，在這其中收集和運輸是每個系統共有的，而轉運過程則視垃圾產生源至垃圾處理場的運輸距離及收集車輛狀況而改變。

為了達到節約成本、提高效率的目的，我們針對北京師范大學校園的垃圾管理現狀，力求設計出一個合理的清運線路以滿足北師大校園中所有垃圾桶的清運工作，同時假設垃圾清運車只在規定道路行駛。

2模型的建立

2.1繪制道路信息

首先，我們通過實地勘察繪制出北師大校園地形圖并在地圖中標出各個垃圾桶的位置坐標，在此過程中我們將距離較近的幾個垃圾桶位置合并為同一個垃圾清運點，從而節省效率。隨后，我們對北師大的校園地圖進行合理的簡化與建模，將長約為814m，寬約為787m的校園簡化為110維矩陣，其中非道路部分、道路部分、垃圾清運點分別用0、l、2表示，相鄰矩陣點之間代表約8米步長。

利用Matlab構建出地圖矩陣，見圖1.

2.2計算垃圾清運時間

在我們的模型中，垃圾車總花費時間T分為行駛時間T，和清理垃圾時間T。，有T=Tr+Te，其中總花費時間Te=∑Te，而每個垃圾桶清理花費時間Tei可由每日統計規律可以求得，我們不妨假設為120s/個，計垃圾桶的數量為rirub。對于行駛時間Tr=∑vij，我們不妨假設在每個區域有Vij≤Vave，其中Vave為校園內車輛上限速度，故可得行駛時間T，=sr/vave，此時，求解總時間最短的問題轉化為求路程S.最小的問題，即對應清運垃圾的最優順序。

對于坐標圖G=（V，E），其中V是頂點集，E是邊集，設S一（S。）是頂點1和頂點j之間距離所組成的距離矩陣，s，即為一條通過所有頂點且每個頂點只通過一次的最短路徑回路。我們要對每一組垃圾桶序號v={V1，v2，…U}求得一個清理順序，記為T={t1，t.，t2…tn}，其中t、∈V（i=l，2，3…n）.所以我們應先對每兩個垃圾桶之間的距離Sij進行估計，再利用模擬退火算法求出最短路徑S，及其最優順序path，即可得到關于垃圾車總花費時間最小值的數學模型.

由前面的分析可知，理想模型與實際模型的根本不同點就在于對Srij估計方法的不同，下面我們就Srij的不同估計方法展開討論。

2.3估計距離參數

2.3.1理想模型中Srij的估計

在理想模型中，我們直接考慮不同垃圾清運點間的直線距離，忽略具體的道路情況，將垃圾轉運問題轉化為一個簡單的旅行商問題。但是考慮到北師大校園較小，所以我們修正了模擬退火算法中的距離求解方法，將原本根據經緯度計算距離的公式替換為歐式距離，故可以通過以下公式求得，

其中（xi，yi），（xj，yj）為第i個和第j個垃圾桶的坐標。

2.3.2實際模型中Srij的估計

在實際模型中，我們需要考慮不同清運點之間的真實行駛距離，對此采用元胞自動機的方法進行模擬。我們對垃圾桶按“先列后行”的規則進行編號，若要對第i個垃圾桶到第j個垃圾桶的距離Srij進行估計，則計算模擬垃圾車在兩點之間運行的步長，這里根據計數方法的不同介紹兩種估計方法。

八領域（Around8）計數法：我們將垃圾車不可走的方向賦予無窮大（inf）的值，同時還要求垃圾車以一定概率（不妨設為0.7）向終點距離（Aroundlen）的最小值方向移動一格，如果生成的隨機數大于此概率，則在Aroundlen

拐點計數法：在進行元胞自動機模擬之前，我們要先在道路矩陣中設置出所有拐點（crossing）.同時，在八領域計數法的基礎上，找出所有介于pointA和pointB之間的拐點并計算其位置（trace），緊接著再按照如下步驟找出一組拐點序列trace作為臨時終點pointC，最后讓垃圾車逐步從pointA走到pointB并計數，步驟如下：

第一步，先設置法向量N= （Ypoints - YpointA，XpoauA - XpointB），對trace按列位置分組。

第二步，對第]組（trim），第點位置為（Xtrlin（i），Ytrlin（i）），按∣N*（Xtrlin（i）- XpointB，Ytrlin（i）- YpointB）排序，取其中最小的作為第j個臨時終點trace（j）.

借助這兩套方法可以求出第1個垃圾桶到第]個垃圾桶之間的真實距離，再取兩者最小值作為Srij，如此處理的原因是當垃圾桶數量很大時不可能枚舉所有路徑，所以要通過簡化算法來實現對Srij的估計。第二種方法優勢在于可以最快地找出比較好的路徑且很穩定，但是由于沒有隨機性，求出來的解可能不是最優解，所以需要第一種方法補充。

2.4模擬退火尋求最優路徑

在得到Srq的值后，先指定一條行駛順序path，通過隨機調換path中垃圾桶的清理順序，計算路程改變量df，如果df<0則認為得到了更優的清理順序，從而將此作為新的path，而如果df≥O則采取。

的概率（T=1）接受這種改變。最終計算迭代L=20000次后所求得的path，這時最優順序即為path.

3模型的求解

理想模型中，使用Matlab進行2000次模擬仿真計算后得到S，ii=584個單位。而實際模型中，計算得到Srij的結果為Srij=631個單位。

將上述結果用北師大校園實際道路體現即為圖2：

圖2校園道路路線

最后結合調查結果得知校園限速內為5km/h，從而v-ave≈2.47單位/秒。

故理想模型中清運垃圾車花費總時間為

Tsum= Tr+∑T.=Sr/Vave+∑TC，≈237+∑Tcis=4557s

實際模型中垃圾車花費總時間為

4結論

該模型較好地解決了校園垃圾最優清運路線的規劃問題，同時適用于多分支結構和網狀結構分布，例如同城市物流網點分布、總子公司分布、通信領域的網點分布等。另外一個優點是算法簡單容易實現，而且借助了模擬退火算法，比較容易理解。

同時模型也存在著一些不足，比如該問題在站點眾多，運輸半徑較大的情況下，垃圾運輸車運量的不足可能會造成無法滿足其中任一點的垃圾清運工作，此時模型可能需要改進。

參考文獻

[1]司守奎、孫兆亮，現代優化算法，數學建模算法與應用，12 （1）：323 329