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

許春玲

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

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

許春玲

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

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

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

0 引言

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

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

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

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

1 問題分析

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

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

表1垃圾轉(zhuǎn)運站編號表

續(xù)表

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

2.1 模型假設(shè)

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

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

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

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

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

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

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

2.2 符號說明

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

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

(3)Z為效益;

(4)X為總收益;

(5)F1為拖車燃油費;

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

(7)F3為司機工資。

3 模型的建立與求解

3.1 模型的建立

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

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

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

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

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

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

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

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

算法:

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

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

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

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

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

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

用7臺拖車即可按要求清理完第一區(qū)域中的垃圾，所以，垃圾處理中心只需投入7臺拖車即可完成任務(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è)計，也找到了最短路徑，這樣的分布合理，可以達到最佳效益。假設(shè)從小區(qū)到轉(zhuǎn)運站的運輸車運費為X，則由Z=X－F1－F2－F3，可得效益的結(jié)果，運用Matlab軟件對第一、第二、第三區(qū)域經(jīng)濟效益進行計算，結(jié)果70263.927元/日。

4 結(jié)語

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

［1］ 韓中庚.數(shù)學建模競賽·獲獎?wù)撐木x與點評［M］.北京:科學出版社，2007.

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

［3］ 盧開澄，盧華明.圖論及其運用［M］.2版.北京:清華大學出版社，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

吉林省教育廳科研項目(吉教科合字2011第208號)

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

責任編輯:鐘 聲