張睿涵

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

關(guān)鍵詞：模擬退火算法 元胞自動(dòng)機(jī)模擬仿真

1問題的分析

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

為了達(dá)到節(jié)約成本、提高效率的目的，我們針對(duì)北京師范大學(xué)校園的垃圾管理現(xiàn)狀，力求設(shè)計(jì)出一個(gè)合理的清運(yùn)線路以滿足北師大校園中所有垃圾桶的清運(yùn)工作，同時(shí)假設(shè)垃圾清運(yùn)車只在規(guī)定道路行駛。

2模型的建立

2.1繪制道路信息

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

利用Matlab構(gòu)建出地圖矩陣，見圖1.

2.2計(jì)算垃圾清運(yùn)時(shí)間

在我們的模型中，垃圾車總花費(fèi)時(shí)間T分為行駛時(shí)間T，和清理垃圾時(shí)間T。，有T=Tr+Te，其中總花費(fèi)時(shí)間Te=∑Te，而每個(gè)垃圾桶清理花費(fèi)時(shí)間Tei可由每日統(tǒng)計(jì)規(guī)律可以求得，我們不妨假設(shè)為120s/個(gè)，計(jì)垃圾桶的數(shù)量為rirub。對(duì)于行駛時(shí)間Tr=∑vij，我們不妨假設(shè)在每個(gè)區(qū)域有Vij≤Vave，其中Vave為校園內(nèi)車輛上限速度，故可得行駛時(shí)間T，=sr/vave，此時(shí)，求解總時(shí)間最短的問題轉(zhuǎn)化為求路程S.最小的問題，即對(duì)應(yīng)清運(yùn)垃圾的最優(yōu)順序。

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

由前面的分析可知，理想模型與實(shí)際模型的根本不同點(diǎn)就在于對(duì)Srij估計(jì)方法的不同，下面我們就Srij的不同估計(jì)方法展開討論。

2.3估計(jì)距離參數(shù)

2.3.1理想模型中Srij的估計(jì)

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

其中（xi，yi），（xj，yj）為第i個(gè)和第j個(gè)垃圾桶的坐標(biāo)。

2.3.2實(shí)際模型中Srij的估計(jì)

在實(shí)際模型中，我們需要考慮不同清運(yùn)點(diǎn)之間的真實(shí)行駛距離，對(duì)此采用元胞自動(dòng)機(jī)的方法進(jìn)行模擬。我們對(duì)垃圾桶按“先列后行”的規(guī)則進(jìn)行編號(hào)，若要對(duì)第i個(gè)垃圾桶到第j個(gè)垃圾桶的距離Srij進(jìn)行估計(jì)，則計(jì)算模擬垃圾車在兩點(diǎn)之間運(yùn)行的步長(zhǎng)，這里根據(jù)計(jì)數(shù)方法的不同介紹兩種估計(jì)方法。

八領(lǐng)域（Around8）計(jì)數(shù)法：我們將垃圾車不可走的方向賦予無窮大（inf）的值，同時(shí)還要求垃圾車以一定概率（不妨設(shè)為0.7）向終點(diǎn)距離（Aroundlen）的最小值方向移動(dòng)一格，如果生成的隨機(jī)數(shù)大于此概率，則在Aroundlen

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

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

第二步，對(duì)第]組（trim），第點(diǎn)位置為（Xtrlin（i），Ytrlin（i）），按∣N*（Xtrlin（i）- XpointB，Ytrlin（i）- YpointB）排序，取其中最小的作為第j個(gè)臨時(shí)終點(diǎn)trace（j）.

借助這兩套方法可以求出第1個(gè)垃圾桶到第]個(gè)垃圾桶之間的真實(shí)距離，再取兩者最小值作為Srij，如此處理的原因是當(dāng)垃圾桶數(shù)量很大時(shí)不可能枚舉所有路徑，所以要通過簡(jiǎn)化算法來實(shí)現(xiàn)對(duì)Srij的估計(jì)。第二種方法優(yōu)勢(shì)在于可以最快地找出比較好的路徑且很穩(wěn)定，但是由于沒有隨機(jī)性，求出來的解可能不是最優(yōu)解，所以需要第一種方法補(bǔ)充。

2.4模擬退火尋求最優(yōu)路徑

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

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

3模型的求解

理想模型中，使用Matlab進(jìn)行2000次模擬仿真計(jì)算后得到S，ii=584個(gè)單位。而實(shí)際模型中，計(jì)算得到Srij的結(jié)果為Srij=631個(gè)單位。

將上述結(jié)果用北師大校園實(shí)際道路體現(xiàn)即為圖2：

圖2校園道路路線

最后結(jié)合調(diào)查結(jié)果得知校園限速內(nèi)為5km/h，從而v-ave≈2.47單位/秒。

故理想模型中清運(yùn)垃圾車花費(fèi)總時(shí)間為

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

實(shí)際模型中垃圾車花費(fèi)總時(shí)間為

4結(jié)論

該模型較好地解決了校園垃圾最優(yōu)清運(yùn)路線的規(guī)劃問題，同時(shí)適用于多分支結(jié)構(gòu)和網(wǎng)狀結(jié)構(gòu)分布，例如同城市物流網(wǎng)點(diǎn)分布、總子公司分布、通信領(lǐng)域的網(wǎng)點(diǎn)分布等。另外一個(gè)優(yōu)點(diǎn)是算法簡(jiǎn)單容易實(shí)現(xiàn)，而且借助了模擬退火算法，比較容易理解。

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

參考文獻(xiàn)

[1]司守奎、孫兆亮，現(xiàn)代優(yōu)化算法，數(shù)學(xué)建模算法與應(yīng)用，12 （1）：323 329