危險廢物定位-運輸路線安排問題模型和算法研究

萬鳳嬌 張慶年 周業旺

(武漢理工大學交通學院 武漢 430063)

隨著社會經濟的日益發展和人類生產、生活水平的提高,城市廢棄物數量逐年增大,在廢棄物中危險廢棄物占3%～5%,在處理和運輸過程中會對土壤、水體、大氣造成持續性污染并難以消除,對人體健康帶來極大的潛在危害.因此,危險廢物的運輸和設施選擇問題引起了國內外廣泛的關注,許多專家學者對其進行了研究[1-6].從現存的模型中可以看出,沒有一個模型綜合考慮以下所有的因素:(1)最小化成本;(2)風險最小化;(3)最大化風險公平性;(4)廢物與廢物之間以及廢物與處理技術之間的相容性;(5)廢物處置設施產生的廢物殘渣的相關問題;(6)廢物的可回收利用問題.本文在安全和經濟的情況下,綜合考慮了以上現實因素,采用最優化理論,建立危險廢物的定位-路線安排問題的數學模型,以達到危險廢物系統管理的費用最小化和環境影響最小化.

1 數學模型

1.1 假設和符號說明

為了簡化模型,給出以下假設:(1)危險廢物和廢物殘渣的單位運輸成本已知,且與運輸距離成正比;(2)所有的危險廢物使用同一類型的卡車運輸;(3)每輛車在完成全部運輸任務后回到出發點;(4)在處理場和最終處置點開設了2種處理技術:焚燒和化學處理;(5)處理處置設施中所采用的處理技術有容量設置;同時給定:N=(V,A)表示運輸網絡;G={1,…,g}是生產節點集合;T={1,…,t}是可能的處理處置節點集合;Tr={1,…,tr}是運輸節點集合;W={1,…,w}是危險廢物類型的集合;Q={1,…,q}是處理技術的集合;K={1,…,k}是入口中心的節點集合.

定義參數變量如下.

Dk-在入口中心k(k∈K)中生產出的危險廢物量;ci,j-危險廢物從節點i運輸到節點j的單位運輸成本,(i,j)∈A;cri,j-廢物殘渣從節點i運輸到節點j的單位運輸成本,(i,j)∈A;f tq,i-在節點i(i∈T)處采用一種處理技術q(q∈Q)的年固定成本;fdi-在節點i(i∈T)處設立一個處理中心的年固定成本;cq,i-在節點i(i∈T)處處理技術q(q∈Q)的處理能力;cmq,i-在處理中心i(i∈T)處需要采用處理技術q(q∈Q)處理的危險廢物的最小量;Wk-入口中心k(k∈K)中的入口數量;Li,k-處理點i(i∈T)到入口中心k(k∈K)之間的距離;RS-設施風險輻射半徑;RT-運輸風險輻射半徑;πi,k-風險影響參數,它是距離 Li,k的遞減凸函數;βw,q-利用處理技術q(q∈Q)處理后的第 w(w∈W)類危險廢物的回收利用率;rw,q-第w(w∈W)類危險廢物利用處理技術q(q∈Q)處理后的減少率.

決策變量 hw,i,j-從節點i到節點j運輸的第w(w∈W)類危險廢物的量,(i,j)∈A;hri,j-從節點i到節點j運輸的廢物殘渣的量,(i,j)∈A;hw,q,i-在節點i(i∈T)用處理技術q(q∈Q)處理第w(w∈K)類危險廢物的量;w di-在處置點i(i∈T)被處置的廢物殘渣的量;comw,q=1,如果處理技術q(q∈Q)與第w(w∈W)類危險廢物相容,否則,comw,q=0;dsi=1,如果在處置點i(i∈T)設立處置場,否則,dsi=0;tq,i=1,如果在處置點i(i∈T)設置處理技術Tr={1,…,tr}是運輸節點集合;W={1,…,w}q(q∈Q),否則,tq,i=0;xi=1,如果在節點i(i∈T)設施處置處理中心,否則,xi=0;Ji,k=1,如果人口中心k(k∈K)在處理處置中心i(i∈T)的風險輻射半徑RS內,否則,Ji,k=0;Zi,j,k=1,如果人口中心k(k∈K)在節點i到節點j的連線上,(i,j)∈A,否則,Zi,j,k=0.

1.2 建立數學模型

式(1)為總成本最小化目標函數,包括危險廢物運輸成本、廢物殘渣運輸成本、使用某一處理技術的年固定成本和處理處置中心的年固定成本;式(2)為風險最小化目標函數,用暴露在風險中的人口數量作為風險衡量標準;式(3)為風險公平性最大化目標函數;約束條件(4)為危險廢物的流量平衡約束,保證將所有生產出的不可回收利用的危險廢物運輸到處理中心進行處理;約束條件(5)為廢物殘渣的流量平衡約束,保證將所有生產出的廢物殘渣和不可回收利用的廢物殘渣運輸到最終處置中心處置;約束條件(6)為容量約束,保證利用處理技術q處理危險廢物的量不能超過此處理技術的處理能力;約束條件(7)為需求最小量約束,如果沒有超過處理技術q的最小處理量,則不能開設此處理技術;約束條件(8)為相容性約束,保證某類危險廢物僅由一種與其相容的處理技術進行處理;約束條件(9),(10),(11)為非負約束;約束條件(12),(13)保證決策變量為整數.

2 算 法

2.1 算法思路

把上述定位-運輸路線安排問題(LRP)分解成2個子問題進行求解:定位-配給問題(LA)和運輸-車輛路線安排問題(VRP).國外許多學者[7-9]對LRP的解決方法進行了探討,所采用的方法可以分為2種:精確算法和啟發式算法.由于定位問題和運輸路線安排問題都屬于 NP-hard問題,所以LRP問題也屬于NP-hard問題,對于這類問題,在大多數情況下,要用精確算法來解決十分困難,很多時候要采用啟發式算法.因此,本文采用2階段禁忌搜索-蟻群混合算法.對于定位問題,采用禁忌搜索算法求解[10],然后將蟻群算法[11-12]嵌在禁忌搜索的框架中,根據所確定的定位方案求出一個比較好的運輸路線,由此得到的LRP問題的總費用作為解的評價指標.

2.2 禁忌搜索-蟻群混合算法的求解步驟

1)隨機選取2個地點建立處理和最終處置中心作為算法的初始解,用蟻群算法求出路線安排并據此求出LRP的目標函數值,令其為歷史最優解;建立交換型操作禁忌表和增加型操作禁忌表.

2)判斷是否滿足停止條件,如果滿足算法停止條件,則輸出最優解;否則轉到3).

3)在當前解的交換型鄰域中選取若干個解,檢查禁忌表,對于不被禁忌的操作做目標函數值預測,采用預測值最優的交換型操作形成新的當前解,用蟻群算法求解出新的當前解的目標函數值.更新交換型操作禁忌表和歷史最優解.

4)計算禁忌搜索算法交換型操作的次數,如果經過Sm ax次交換操作歷史最優解仍然沒有提高,則轉到5);否則轉到3).

5)在當前解的增加型領域中選取若干個解,檢查禁忌表,對于預測值最優的增加型操作形成新的當前解,用蟻群算法求出新的當前解的目標函數值.更新增加型操作禁忌表和歷史最優解.

6)轉到2).

在此,由于篇幅有限,不單獨介紹禁忌搜索算法和蟻群算法的求解步驟.

3 算 例

圖1 運輸網絡

假設一個運輸網路有3個危險廢棄物產生點,4個潛在的處理中心和2個潛在最終處理中心(見圖1).連線之間的人口數和潛在風險見表1.假設在廢物產生點產生3種類型的危險廢棄物,其具體信息見表2.在3種類型的危險廢棄物中,金屬廢物與石化產品不相容,與殺蟲劑相容,而殺蟲劑與石化產品不相容.金屬廢物、石化產品和殺蟲劑的單位運輸成本分別為4.0,5.5,5.0元(t·km-1),它們的潛在風險分別為0.25,0.3,0.35;處理中心可以選擇2種處理技術:固化技術和焚燒技術.成本和風險系數,剩余物產生系數以及各技術的處理能力見表3和表4.廢物殘渣的單位運輸成本為2元/(t·km-1),潛在風險為0.1.

表1 連線之間相關信息

表2 產生的危險廢棄物的量

表3 處理設施的情況

表4 最終處理設施的情況(填埋)

用文中提出的禁忌搜索-蟻群混合算法求解問題,算法運行的參數設置為:禁忌搜索增加型操作的最大次數為3,連續交換操作最大次數為5,禁忌表長度為5;蟻群算法的人工智能體數量設為5,迭代次數為30次,ρ設為0.92;混合算法的停止條件為連續進行增加型操作達到最大次數后解的質量仍沒有提高.采用MATLAB語言編程.經過計算后,選擇了3個處理中心1,5,9和一個最終處置中心2.具體運輸路線為:3-1-2;4-1-2;4-9-2;7-9-2;7-5-2.

4 結束語

從可持續發展的角度考慮,為了減少廢棄物對環境帶來的危險性,本文創新性的研究了危險廢物管理中設施定位和運輸路線安排問題,并結合實際情況構建了多目標混合整數規劃模型,模型充分考慮危險廢物管理中所面臨的現實問題.此外,由于定位-運輸路線安排問題屬于NP-hard問題,文中提出了一種新型的兩階段混合啟發式算法:禁忌搜索-蟻群算法求解問題.這種方法可以在較短的時間內解決大規模的定位-運輸路線安排問題并獲得較好的結果.

[1]Zografos K G,Samara S.Combined location-routing model for hazardous waste transportation and disposal[J].Transportation Research Record.1990,1245:52-59.

[2]ListG,M irchandoni P.An integrate network/p lanar multiobjec tivemodel for routing and siting for hazardousmaterials and wastes[J].Transportation Science.1991,25(2):146-156.

[3]Revelle C,Cohon J,Shobrys D.Simultaneous siting and routing in the disposal o f hazardous w astes[J].Transportation Science,1991,25(2):38-45.

[4]Current J,Ratick S.A model to assess risk,equity and efficiency in facility location and transportation of hazardous materials[J].Location Science,1995,3(3):187-201.

[5]Nema A K,Gupta SK.Optim ization of regionalhazardousw astemanagement systems:an imp roved formulation[J].Waste Management.1999,19:41-51.

[6]Alumur S,Kara B Y.A new model for the hazardous w aste location-routing p rob lem[J].Com puters&Operations Research,2005,6:1-18.

[7] 李 青,劉兆健,薛 軍,孫光圻.用于定位-運輸路線安排問題的禁忌搜索-蟻群混合算法[J].可持續發展的中國交通,2005:234-239.

[8] 王雪峰,孫小明,鄭柯威,楊芳.定位-車輛路徑問題的兩階段混合啟發式算法[J].上海交通大學學報,2006(9):1529-1535.

[9]Tuzun D,Burke L I.A two-phase tabu search approach to the location routing problem[J].European Journa l of Operational Research,1999,116(1):87-99.

[10]郭崇慧,覃華勤.一種改進的禁忌搜索算法及其在選址問題中的應用[J].運籌與管理,2008,17(2):18-23.

[11] 崔雪麗,馬 良,范炳全.車輛路徑問題(VRP)的螞蟻搜索算法[J].系統工程學報,2004,19(4):418-442.

[12]李卓君.混合蟻群算法求解物流配送路徑問題[J].武漢理工大學學報:交通科學與工程版,2006,30(2):306-309.