許春玲

(東北師范大學(xué)人文學(xué)院 信息技術(shù)學(xué)院，長(zhǎng)春 130117)

垃圾處理問題最短路徑的Dijkstra算法

許春玲

(東北師范大學(xué)人文學(xué)院 信息技術(shù)學(xué)院，長(zhǎng)春 130117)

通過對(duì)問題的分析和假設(shè)，建立了線性規(guī)劃的數(shù)學(xué)模型，運(yùn)用Dijkstra算法提供了一個(gè)最優(yōu)的方案，采用Lingo軟件得到了全局最優(yōu)解。

線性規(guī)劃;最短路徑;Dijkstra算法

0 引言

人類每日會(huì)產(chǎn)生大量的垃圾，大量的垃圾未經(jīng)分類回收再使用并任意棄置會(huì)造成環(huán)境污染。從國(guó)外許多大城市對(duì)生活垃圾分類的方法來看，一般都是根據(jù)垃圾的成分構(gòu)成、產(chǎn)生量，結(jié)合本地垃圾的資源利用和處理方式來進(jìn)行分類。我國(guó)生活垃圾一般可分為四大類:可回收垃圾、櫥余垃圾、有害垃圾和其他垃圾。目前常用的垃圾處理方法主要有:綜合利用、衛(wèi)生填埋、焚燒發(fā)電、堆肥、資源返還。

在深圳，垃圾分為四類:櫥余垃圾、可回收垃圾、有害垃圾和其他不可回收垃圾。所有垃圾將從小區(qū)運(yùn)送到附近的轉(zhuǎn)運(yùn)站，再運(yùn)送到少數(shù)幾個(gè)垃圾處理中心。櫥余垃圾和可回收垃圾，經(jīng)過處理，回收和利用，產(chǎn)生經(jīng)濟(jì)效益，而有害垃圾和其他不可回收垃圾只有消耗處理費(fèi)用，不產(chǎn)生經(jīng)濟(jì)效益。

大型櫥余垃圾處理設(shè)備，處理能力200噸/日，投資約為4500萬元，運(yùn)行成本為150元/噸;小型餐廚垃圾處理機(jī)，處理能力為200－300公斤/日，投資額為28萬元，運(yùn)行成本為200元/噸。櫥余垃圾處理后產(chǎn)物價(jià)格在1000－1500元/噸。

假定現(xiàn)有垃圾轉(zhuǎn)運(yùn)站規(guī)模與位置不變條件下，給出大、小型設(shè)備(櫥余垃圾)的分布設(shè)計(jì)，同時(shí)在目前的運(yùn)輸裝備條件下給出清運(yùn)路線的具體方案，以期達(dá)到最佳經(jīng)濟(jì)效益和環(huán)保效果。

1 問題分析

對(duì)于拖車調(diào)度方案的設(shè)計(jì)，不僅需要考慮使拖車的行走路線最短，而且還要考慮垃圾的累積運(yùn)輸?shù)幕ㄙM(fèi)問題，因此，我們的目標(biāo)函數(shù)應(yīng)該是使得所有運(yùn)輸?shù)幕ㄙM(fèi)最少。在建模過程中，按照深圳市南山區(qū)地圖，我們把整個(gè)線路圖分成三個(gè)區(qū)域，每個(gè)區(qū)域都要考慮投入的拖車臺(tái)數(shù)，投入拖車數(shù)量，計(jì)算出各路徑運(yùn)輸?shù)幕ㄙM(fèi)，再根據(jù)題目中拖車總數(shù)、轉(zhuǎn)運(yùn)站的轉(zhuǎn)運(yùn)量進(jìn)行計(jì)算。

根據(jù)目前深圳市南山區(qū)垃圾轉(zhuǎn)運(yùn)站及垃圾轉(zhuǎn)運(yùn)量等情況統(tǒng)計(jì)表，我們將這些轉(zhuǎn)運(yùn)站編號(hào)，共38個(gè)轉(zhuǎn)運(yùn)站，如表1所示。

表1垃圾轉(zhuǎn)運(yùn)站編號(hào)表

續(xù)表

2 模型假設(shè)與符號(hào)說明

2.1 模型假設(shè)

(1)假設(shè)各站點(diǎn)每天的垃圾量不變;

(2)假設(shè)各站點(diǎn)的垃圾都必須在當(dāng)天清理完畢;

(3)不考慮拖車在行駛過程中的塞車、拋錨等出現(xiàn)故障的情況;

(4)不允許運(yùn)輸車和拖車有超載現(xiàn)象;

(5)每個(gè)轉(zhuǎn)運(yùn)站點(diǎn)均位于街道旁，保證運(yùn)輸車和拖車行駛順暢;

(6)廚余垃圾處理前后重量不變;

(7)假設(shè)可以在小區(qū)垃圾點(diǎn)建立轉(zhuǎn)運(yùn)站。

2.2 符號(hào)說明

(1)x1為大型餐廚設(shè)備臺(tái)數(shù);

(2)x2為小型餐廚設(shè)備臺(tái)數(shù);

(3)Z為效益;

(4)X為總收益;

(5)F1為拖車燃油費(fèi);

(6)F2為設(shè)備運(yùn)行成本;

(7)F3為司機(jī)工資。

3 模型的建立與求解

3.1 模型的建立

3.1.1 餐廚設(shè)備的分布設(shè)計(jì)模型

對(duì)于餐廚垃圾處理設(shè)備的分布設(shè)計(jì)，我們建立單目標(biāo)線性規(guī)劃模型使得餐廚垃圾處理設(shè)備分布的最合理，模型如圖1所示。

圖1 lingo求解代碼與結(jié)果

運(yùn)用Lingo軟件［1－2］求解，得到需要大型設(shè)備3臺(tái)，不需要小型設(shè)備，這樣的結(jié)果使得投資額最低，并且能夠處理所有垃圾。

3.1.2 拖車調(diào)度方案的模型

對(duì)于拖車的調(diào)度方案，我們分三個(gè)區(qū)域建立單目標(biāo)規(guī)劃的非線性模型使得運(yùn)輸費(fèi)用最小，模型如下:

第一區(qū)域拖車調(diào)度:

根據(jù)我們對(duì)具體距離的整合，運(yùn)用Dijkstra算法［3］，我們首先將這些點(diǎn)連成通路，然后對(duì)這些點(diǎn)進(jìn)行分析，得到很多條路線，但是經(jīng)過計(jì)算我們發(fā)現(xiàn)最短路徑，并且調(diào)動(dòng)拖車也更方便，符合現(xiàn)實(shí)意義。

算法:

步驟一:任取一頂點(diǎn)2，與2相鄰的頂點(diǎn)有8，20兩點(diǎn)，8點(diǎn)最接近于2點(diǎn)，聯(lián)2點(diǎn)和8點(diǎn).

步驟二:圖中其他點(diǎn)與S={2，8}兩點(diǎn)相聯(lián)接的點(diǎn)有20，7，13，而且L20=4，L7=7.2，L13=7.7，因此，極小值為min{L20，L7，L13}=L20=4.因此，根據(jù)算法，我們需要連接2點(diǎn)和20點(diǎn)。

步驟三:圖中其他點(diǎn)與S={2，8，20}相鄰接的點(diǎn)有7點(diǎn)和13點(diǎn)，而且L7=7.2，L13=7.7，因此，極小值為min{L7，L13}=L7=7.2.故連接8點(diǎn)和7點(diǎn)。

步驟四:如此反復(fù)進(jìn)行上面的各個(gè)步驟，直到所有的頂點(diǎn)都連接起來為止，如圖2所示。

由圖2可以看出，最短路徑中只有2條路徑有交叉點(diǎn)，其他路徑互不干擾，結(jié)果很理想。從圖2中，清晰可見各個(gè)路徑的情況，我們可以通過這些路徑得到不同路徑的最優(yōu)解和最優(yōu)值。

圖2 第一區(qū)域拖車調(diào)度的最短路徑

用7臺(tái)拖車即可按要求清理完第一區(qū)域中的垃圾，所以，垃圾處理中心只需投入7臺(tái)拖車即可完成任務(wù)。各拖車行走的路徑如表2所示:

表2 第一區(qū)域拖車路徑表

第二區(qū)域、第三區(qū)域拖車調(diào)度:

分析方法如同第一區(qū)域，算法如同第一區(qū)域。第二區(qū)域拖車調(diào)度的最短路徑如圖3所示，共需4量拖車，各拖車行走的路徑如表3所示;第三區(qū)域拖車調(diào)度的最短路徑如圖4所示，共需5量拖車，各拖車行走的路徑如表4所示。

圖3 第二區(qū)域拖車調(diào)度的最短路徑

圖4 第三區(qū)域拖車調(diào)度的最短路徑

表3 第二區(qū)域拖車路徑表

表4 第三區(qū)域拖車路徑表

3.2 模型的求解

櫥余設(shè)備的分布用以上的分布設(shè)計(jì)，也找到了最短路徑，這樣的分布合理，可以達(dá)到最佳效益。假設(shè)從小區(qū)到轉(zhuǎn)運(yùn)站的運(yùn)輸車運(yùn)費(fèi)為X，則由Z=X－F1－F2－F3，可得效益的結(jié)果，運(yùn)用Matlab軟件對(duì)第一、第二、第三區(qū)域經(jīng)濟(jì)效益進(jìn)行計(jì)算，結(jié)果70263.927元/日。

4 結(jié)語

本文主要是尋找垃圾清運(yùn)的最短路徑，由于線路復(fù)雜，選擇中心比較難，我們采用了分區(qū)域分解方法，并配合數(shù)值計(jì)算軟件，將復(fù)雜的實(shí)際問題轉(zhuǎn)化成可處理的數(shù)學(xué)模型，從而求解相應(yīng)的數(shù)學(xué)模型。

［1］ 韓中庚.數(shù)學(xué)建模競(jìng)賽·獲獎(jiǎng)?wù)撐木x與點(diǎn)評(píng)［M］.北京:科學(xué)出版社，2007.

［2］ 謝金星，薛毅.優(yōu)化建模與LINDO/LINGO軟件［M］.北京:清華大學(xué)出版社，2006.

［3］ 盧開澄，盧華明.圖論及其運(yùn)用［M］.2版.北京:清華大學(xué)出版社，2005.

Dijkstra Algorithm for the Shortest Path of Garbage Treatment Problem

XU Chun-ling
(College of Information Technology，College of Humanities and Sciences of Northeast Normal University，Changchun 130117，China)

Based on analysis and assumptions，this paper establishes a mathematics model of linear programming，presents an optimal plan by Dijkstra algorithm and gets global optimal solution with Lingo software.

linear programming;shortest path;Dijkstra algorithm

TP301.6

A

1009－3907(2011)12－0064－04

2011-10-26

吉林省教育廳科研項(xiàng)目(吉教科合字2011第208號(hào))

許春玲(1973-)，女，吉林長(zhǎng)春人，講師，主要從事軟件工程及其算法應(yīng)用的研究。

責(zé)任編輯:鐘 聲