面向路网结构的垃圾分类车辆调度研究

杨春霞,赵 霞,王 皓,王晓军

(太原科技大学 交通与物流学院,太原 030024)

据统计,2020年全国已有237个城市启动垃圾分类,将垃圾分为湿垃圾、可回收垃圾、干垃圾和有害垃圾四类。其中不少地方的中间垃圾收运环节仍混装收运,该环节费用占垃圾处理系统总费用60%～80%[1],因此,对垃圾分类车辆调度进行研究,能解决城市垃圾分类实施中的短板,具有现实意义。

目前,根据约束条件和优化目标的不同,国内外现有研究可以分为以下几大类:(1)带容量约束[2]的收运调度问题,如丁伟[3]以伊斯坦布尔城市为例,建立了有车辆容量约束的车辆路径问题模型,并设计了相应的遗传算法;李佳书[4]通过研究满载与非满载结合的车辆调度问题,构建了一种较为完善的废弃物回收网络。(2)多目标优化的收运调度问题,如赵今越等[5]以最小化运输成本和车辆固定成本为目标建立了数学模型; Shan-Huen Huang等[6]将废物收集问题看作为一个集合到达和车辆路径问题,提出了一种双层优化模型。(3)带时间窗约束[7]的收运调度问题,如Benjamin等[8]考虑处置设施时间窗,对公共废物收集问题进行了回收路径的优化;李珍萍等[9]对同一顾客多种需求的服务时间具有固定先后顺序的车辆路径问题进行优化。

垃圾分类背景下,传统车辆调度问题的解决办法已不太适用。垃圾车不仅存在多种车型,调度模式也发生了变化。于伟[10]研究了中转站优化方法及其生活垃圾收运模式;王晨頔[11]在分类基础上,对生活垃圾清运车辆进行了优化研究。上述研究在建模时均将垃圾收集点、中转站和处理厂等当成节点,但节点与节点间能直接连接且路径唯一,没有考虑到实际路网结构及节点间可能存在多路径的情况。为此,本文首先基于路网结构,引入虚拟的网络节点,将垃圾清运过程中与垃圾投放点相关的路口作为节点一起进行车辆的路线规划,更准确地进行车辆调度,给出垃圾分类调度优化模型;其次,在算法方面遗传算法[12]对于复杂多目标优化问题有较好的求解适应性;粒子群算法在大规模连续优化问题上有较好的适应性[13]。分别采用两种算法对模型进行求解,以提供优化性更好的调度路径。

1 问题描述

本文中路网被抽象为由垃圾收集点、处理中心、停车场以及实际路段共同组成的无向图,垃圾收集点之间若有直线相连则表明可以直接到达,直线段的长度为两收集点之间的实际距离;若无直线相连接,则表明两收集点要通过路网节点才能相连接,此时不能将两点之间的直线距离作为车辆调度的实际距离。

将处理中心、垃圾投放节点以及虚拟的网络节点简化为节点,引入路网节点之后实际路网的抽象结构图如图1所示。

图1 实际路网抽象结构图Fig.1 Abstract structure diagram of actual road network

在图1中,W表示垃圾处理中心,a-p表示垃圾投放节点,1-13表示路网节点,节点之间的线段表示道路实际路网结构。

2 垃圾分类收运调度优化模型

2.1 模型假设

以垃圾分类收运模式为基础,将垃圾车调度问题转化为多处理中心、多车辆、多车型、多路径、有容量约束且带有时间窗的车辆调度问题。

主要假设条件如下:(1)将收集区域内的每一个社区视为一个垃圾投放节点,每日垃圾产生量已知,且湿垃圾、可回收垃圾和干垃圾按一定比例投放;(2)以实际路网为基础设置垃圾投放点、处理厂、停车场等节点位置。引入虚拟网络节点,其对应垃圾产生量为0;(3)设有6吨箱式车、6吨压缩车、9吨压缩车三种车型,每种车型数量充足,其中箱式车装可回收物和干垃圾,压缩车装湿垃圾;(4)清运车辆的工作时间与垃圾投放点的开放时间相一致,在时间窗范围内,车辆可以多次往返于垃圾投放点进行清运工作;(5)清运车辆在到达处理场进行卸料作业时,实行先到先服务的原则;(6)单个清运车辆可服务于多个垃圾投放节点,即单个垃圾投放点的产生量不大于服务于该点的车辆载重限制;(7)所有车辆从停车场出发在进行多次清运工作后最终必须返回停车场。

2.2 基本参数

收运网络用有向图G={VE}表示收运网络,其中V表示模型所涉及到的投放点集合,收运节点i,j∈V;W为投放点集合,qi表示垃圾投放点i的生活垃圾清运需求量;[ai,bi]为投放点i的时间窗;P表示停车场集合,p为停车场节点;F为处理厂集合;C表示车辆集合,对车辆编号c∈C,φc为其固定成本,Lc为行驶距离;K表示车次集合,车次编号k∈K;mk为车次k的最大载重限制;yik为车次k在收运节点i收集的垃圾量;dij表示垃圾投放节点i,j之间的距离;vij表示垃圾投放节点i到节点j的行驶时间;α表示垃圾投放节点之间的单位运输成本;tjk表示车次k在处理厂j内的排队等待时间;h表示车辆在处理场卸料作业的时间;σ为拥堵系数;ε表示在时间窗允许的范围外所需要的惩罚成本;θ表示清运车辆作业时的单位等待时间成本;τi表示在垃圾投放点i进行收集作业的时间;τj表示在处理场j进行卸料作业的时间;wpk为车次k到达停车场p的时间;wik车次k到达垃圾投放节点i的时间;S1、E1分别表示垃圾清运车辆工作的开始和结束时间。

定义以下决策变量:Xik表示车次k是否前往垃圾投放点i进行收运作业,是则为1,否则为0;Yik表示车次k是否在清运时间窗范围内到达垃圾投放点i,是则取1,否则为0;xijk表示车次k是否经过路径(i,j),是则取值1,否则为0;Zijk表示车次k经过路径(i,j)时是否拥挤,是则取值1,否则为0;Uck表示车次k对应的车辆标号是否为c,是则取值1,否则为0.

2.3 多目标优化模型

建立同时考虑成本和时间的多目标优化模型,如式(1)所示。F1表示清运车辆在处理场内的排队等待总时间最小,见式(2).F2表示垃圾清运总成本最小,包括车辆固定成本、运输成本以及时间窗范围外作业的惩罚成本三部分,其中运输成本包括停车场到垃圾收集点的运输成本、车辆在垃圾收集点之间的运输成本、垃圾投放点到处理厂之间的运输成本以及处理厂到停车场的运输成本之和,详见式(3).

F=min{F1,F2}

(1)

F1=∑k∈K∑j∈Ftjk

(2)

∑k∈K∑i∈W∑j∈Fdijxijk+

∑k∈K∑j∈F∑i∈Wdjixjik+

(3)

主要约束条件如下:

∑k∈K∑j∈G∪Fxijk≥1,∀i∈G∪F

(4)

∑i∈G∪F∪Pxigk-∑j∈G∪Fxgik=0

v1=G∪F∪P,∀i∈G

(5)

∑i∈Gxilk-∑j∈G∪Pxljk=0,

∀l∈W;k∈K

(6)

∑i∈Gyik=mk,∀k∈K

(7)

∑i∈Gxpik=∑j∈Fxjpk≥1,∀k∈K

(8)

∑k∈Kyik=qi,∀i∈G

(9)

∑k∈Kqi≤∑k∈Kmk

(10)

yik≤uik≤mk,k∈K

(11)

0≤yik≤∑j∈G∪F∪Pqixjik,∀i∈G,k∈K

(12)

xijk≤TE-TS,∀c∈C

(13)

公式(4)表示一个垃圾投放点可以由多个车次进行收运服务;公式(5)表示收运车辆在垃圾投放点完成收运工作以后需要立即离开;公式(6)表示收运车辆在处理厂完成卸料作业离开后,要去往干垃圾投放点进行收运作业或者去往停车场;公式(7)表示某类垃圾收运车辆k在垃圾投放点可以进行多次收集作业,直到达到该类车辆最大载重时前往处理场卸料;公式(8)表示收运车辆k从停车场出发去往垃圾收集点的次数和车辆k从处理场回到停车场的次数相同,且过程不止一次;公式(9)表示垃圾收运车辆去往投放点i进行多次收运作业后所收集的垃圾总量等于该投放点的生活垃圾清运需求量;公式(10)表示清运车辆k的最大载重量要满足垃圾投放点i的生活垃圾清运需求量;公式(11)表示在清运车辆k在垃圾投放点i进行收运作业时垃圾收运量不能少于该点的垃圾产生量,同时去往处理厂时垃圾的收运量不能超过清运车辆的最大载重限制;公式(12)表示清运车辆k在垃圾投放点i的垃圾收运量非负,且当车辆经过该点时才能发生收运行为;公式(13)表示清运车辆k的总工作时间要在时间窗范围内。

3 实例分析

3.1 收运路网结构图

3.1.1 节点坐标

以某市H区为例,建立收运路网结构图。该区的垃圾收运网络中共包含67个节点,其中包括一个停车场(编号1)、一个垃圾处理中心(编号2)、一个可回收资源分拣中心(编号3)、23个垃圾投放节点(编号4-26).通过Google Earth软件确定各节点经纬度坐标,如图2所示。

图2 去除街道影像后H区垃圾投放点位置Fig.2 Location of garbage dropping point in H district after removing street image

以坐标为(112.531235,37.954798)的点为坐标原点,得到垃圾投放节点在地图上的位置及其相对位置坐标。

3.1.2 路网节点坐标

将各节点及路径的相对坐标提取出来,建立路网结构图,如图3所示。根据路径连接情况,引入41个虚拟节点(编号27-67),虚拟节点的垃圾产生量为0,时间窗为24小时。以图3为基础,将个节点连接起来,形成可行的路径网络,如图4所示。

图3 垃圾收运网络节点路网结构图Fig.3 Road network structure diagram of garbage collection and transportation network nodes

图4 垃圾收运网络节点连接示意图Fig.4 Schematic diagram of node connection of garbage collection and transportation network

3.2 各类垃圾主要参数取值

垃圾投放点中,时间窗及清运数量见表1.

表1 垃圾收运网络各节点相关信息表Tab.1 Relevant information table of each node of garbage collection and transportation network

根据调研确定:箱式车、两种不同载重的压缩车的固定成本分别是460.00元/车/天、451.13元/车/天和546.03元/车/天;燃油费用分别为15.63元/千米、12.80元/千米和37.85元/千米。垃圾收运车辆在投放点的装卸时间为5 min,在处理场卸料时间为10 min,车辆在卸料完成后进行车辆维护的时间为15 min,可回收垃圾在可回收资源中心的卸料时间为10 min.车辆在进行清运时车辆行驶速度假设为30 km/h,当在拥堵时间段早高峰[7,9]和晚高峰[17,19]时,车辆速度降为正常行驶速度的一半,为15 km/h.

3.3 模型算法验证

3.3.1 算法参数

(1)PSO基本参数确立

设置粒子种群大小为100,由于随着迭代的进行,惯性因子应该逐渐减小,因此将惯性权重参数取为ω,在进行迭代计算时来提高粒子群寻找最优解的能力;学习因子设置为c1=c2=1.494 5,粒子的最大速度设置为vmax,控制在[-0.1,0.1]范围内;自变量取值范围设置为[0,1],迭代次数为400次。

(2)GA基本参数确立

设置初始种群大小为100,将染色体编码方式确定为自然数编码,每一个数字代表一个网络节点,每一串数字代表网络节点被服务的先后顺序,即车辆调度路径。在选择遗传算子时采用锦标赛法,从种群的n个个体中随机抽取k个个体,并按照锦标赛的方法选择出适应度更高的个体;设置算法交叉概率P1=0.65,变异后概率P2=0.05.

3.3.2 算法效率分析

本文将垃圾清运时间分为早晚清运时间两种情况进行车辆调度,在不同时间窗内得出三种不同类型垃圾的收运路线。利用MATLAB 软件进行算法迭代,对早晚班清运迭代400次的结果进行分析,如图5、图6所示。由此可知PSO算法适应度值更小,其效果更好。

图5 迭代400次下的早班垃圾清运效果曲线图Fig.5 Effectcurve of early shift garbage removal after 400 iterations

图6 迭代400次下的晚班垃圾清运效果曲线图Fig.6 Effect Curve of night shift garbage removal after 400 iterations

3.3.3 车辆收运路线方案

根据模型进行求解,可以得出不同类型垃圾分类单独收运时早晚班清运的模型对比分析如表2所示。

表2 早晚班分类单独收运模型结果分析Tab.2 Result analysis of separate collection and transportation model for morning and evening shift classification

通过表2可知,粒子群算法下模型的收运结果优于遗传算法,故选取粒子群算法的模型结果作为垃圾分类收运车辆调度的依据。

4 结论

首先,通过实验分析结果可以看出:(1)以实际路网结构为基础,确定垃圾投放点、处理厂及停车场的实际位置;同时将行驶道路及节点纳入模型,获得了可行的路径方案。(2)通过对垃圾分类收运问题的系统分析,确定该问题的研究范畴,是对现有垃圾收运的有效拓展。(3)经计算,与遗传算法相比,粒子群算法获得较优的方案,且效率也得到提升。此外,本文假设垃圾产生量每天都是固定的,而现实中垃圾产生量是存在波动的。确定垃圾产生量的置信区间,再对收运进行优化,这也是未来可以研究的方向。