危险废物定位-运输路线安排问题模型和算法研究

万凤娇 张庆年 周业旺

(武汉理工大学交通学院 武汉 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.