垃圾分类收运模式下车辆路径问题建模与仿真

狄卫民 王 然

(郑州大学管理工程学院 河南 郑州 450001)

0 引 言

垃圾分类收运问题属于车辆路径问题范畴，为普遍推行垃圾分类制度，亟需解决垃圾分类收运车辆路径问题，建立与垃圾种类相匹配的低成本收运体系。

在传统车辆路径相关文献研究中，大多考虑了车辆装载能力限制。例如：贺冰倩等[2]考虑车辆最大载重量和最大体积约束，研究了快递收派混合车辆路径优化问题，设计了改进的禁忌搜索算法进行求解；吕俊杰等[3]则研究了基于客户分流策略的配送中心车辆路径问题，设计改进的遗传算法进行求解。针对单中心单车型车辆路径优化问题，胡乃平等[4]主要考虑时间约束建立数学模型，利用分解协调算法和遗传算法求解；Qi等[5]则考虑时间窗建立多目标数学模型，设计了一种基于模因算法的多目标进化算法求解。针对单中心多车型车辆路径优化问题，葛显龙等[6]主要考虑碳排放因素和时间窗建立数学模型，设计了一种结合聚类分析方法和扫描算法的混合遗传算法求解；何东东等[7]主要考虑车辆行驶过程中产生的油耗和碳排放量建立数学模型，设计了改进的禁忌搜索算法求解；郭海湘等[8]主要考虑车辆碳排放量建立数学模型，设计了混合启发式算法、混合遗传算法和混合蚁群算法进行求解。针对多中心多车型车辆路径优化问题，陈呈频等[9]建立整数规划模型，设计了多染色体遗传算法进行求解。

一些文献又考虑了产品的特殊性研究车辆路径优化问题。其中，针对多产品单车型车辆路径优化问题，陈久梅等[10]考虑不同生鲜农产品对冷藏环境的要求不同，建立生鲜农产品多隔室车辆路径优化模型，利用粒子群算法进行求解；Zhang等[11]又考虑产品体积限制和产品破损成本建立数学模型，利用遗传算法求解；Azi等[12]考虑车辆由于时间限制而执行多条路线的情况建立数学模型，设计了基于列生成算法的精确算法求解。针对多产品多车型车辆路径优化问题，刘家利等[13]考虑了企业运力不足时可租赁外部车辆的情况，建立混合整数规划模型，设计了两阶段自适应遗传算法求解。针对城市生活垃圾车辆收运路径优化问题，吴勇刚等[14]分别建立基于收运路程和基于车辆行驶时间的数学规划模型，利用遗传算法求解；雷悦等[15]则采用带站的标准数学模型，利用蜂群优化算法求解。然而这些文献均未考虑垃圾分类以及不同种类的垃圾需由不同类型车辆收运的情况。

综上，本文考虑垃圾分类以及垃圾种类-车辆类型匹配的情况，研究多种类多车型的垃圾收运车辆路径优化问题，建立数学模型，利用遗传算法求解。

1 问题描述与模型建立

1.1 问题描述

城市居民产生的生活垃圾，自行或由物业人员分类投放到指定垃圾站，每一个垃圾站内不同种类的垃圾需要由指定类型的车辆收运到垃圾中转站进行处理(例如：大件垃圾拆解、可回收物收集贮存、有害垃圾收集贮存、厨余垃圾预处理等)，处理后产生的固体垃圾再分别运到大型垃圾分拣中心、焚烧厂、填埋厂、回收厂等处理厂进行二次处理。由于集中到垃圾中转站的垃圾量较大，一般只需直运到各处理厂，因此不考虑该部分的车辆路径问题。又由于生活垃圾收运受到行政区规划的影响，本文只考虑单个行政区内含有一个垃圾中转站的情况。在车辆类型有限、垃圾种类有限、车辆类型与垃圾种类匹配、不同类型的车辆有不同的装载能力限制、垃圾站内每一种类型的垃圾量均不超过车辆最大装载能力限制的情况下，为了使车辆启动成本与运输成本之和最小，需要解决的问题有：

(1) 垃圾中转站需要分别拥有各类型车辆各几辆。

(2) 每一辆车需要服务哪几个垃圾站及其收运顺序。

1.2 符号说明

为便于模型建立，设定如下符号：有m个垃圾站，记为I={1,2,…,m}；1个垃圾中转站，记为m+1；g种车辆类型，记为W={1,2,…,g}；h辆车，记为V={1,2,…,h}；s种垃圾类型，记为P={1,2,…,s}；w类型车辆的运载能力记为Capw；w类型车辆的单位距离运输成本记为cw；w类型车辆的启动费用记为rw；垃圾站i的p类垃圾的量记为dip；记节点a、b∈U={1,2,…,m,m+1}，节点a与节点b之间的距离记为tab；若车辆v属于w类型车辆，则ovw为1，否则为0；若w类型车辆可收运p类垃圾，则qwp为1，否则为0。决策变量：若车辆v启动，则xv为1，否则为0；若车辆v从节点a到节点b，则yabv为1，否则为0。

1.3 数学模型

建立如下数学模型：

(1)

(2)

(3)

(4)

yaiv+yiav≤1a,i=1,2,…,m，v=1,2,…,h

(5)

(6)

yabv≤xva,b=1,2,…,m+1，v=1,2,…,h

(7)

xv∈{0,1}v=1,2,…,h

(8)

yabv∈{0,1}a,b=1,2,…,m+1，v=1,2,…,h

(9)

式(1)为目标函数，表示最小化车辆启动成本和运输成本之和；式(2)表示每个垃圾站i只有1辆w类型车辆经过；式(3)表示车辆v必须从垃圾中转站j出发并返回；式(4)表示车辆v最多服务某一垃圾站i一次；式(5)表示车辆v只能在垃圾站之间单向行驶；式(6)表示车辆v的装载能力限制；式(7)表示车辆v启动约束；式(8)、式(9)为0-1约束。

2 算 法

考虑到建立的多种类多车型垃圾收运车辆路径优化模型的复杂性，采用遗传算法进行求解。根据模型多维度的特点，提出基于车辆类型的染色体编码方法、基于车辆装载能力限制的染色体解码方法，算法主要功能模块如下。

2.1 染色体编码

基于车辆类型的染色体编码方法，能够保证每个垃圾站内的每种垃圾都能够被相匹配的车辆收运1次，满足垃圾种类-车辆类型匹配和车辆服务限制约束。编码步骤为：

(1) 垃圾站编号为1-m，对于某一类型车辆，按照实值编码规则，生成一个由数字1-m组成、数字不重复随机排列的长度为m的基因串，表示该类型车辆的收运路径。

(2) 共有g种类型车辆，则生成g个长度为m的基因串，将其横向连接，生成一条长度为g×m染色体A，所有类型车辆的收运路径，如图1所示。

图1 基于车辆类型的染色体编码示意图

2.2 染色体解码

基于车辆装载能力限制的染色体解码方法中，首先，按照车辆装载能力限制，对染色体进行解码得到该条染色体对应的各类型车辆初始数量以及每一辆车的初始收运路径；然后，在车辆装载能力范围内，通过调整车辆数量和车辆路径对该初始解进行改进，确定最终车辆数量以及各车辆的收运路径。解码步骤为：

(1) 选取某一类型车辆服务的垃圾站所对应的基因串B，基于车辆装载能力限制进行解码，使每一辆车经过一个先从垃圾中转站驶出，然后在装载能力限制内经过最大数量的垃圾站，最后驶入垃圾中转站的完整过程。一辆车装载完毕，启动下一辆车，直到所有垃圾站内的由该种类型车辆收运的垃圾装载完毕。如图2所示，其中“→”表示路径指向。

图2 初始解码示意图

(2) 增加一辆同类型车辆，记其编号为n+1，初始路径为m+1→m+1，初始装载量Cap=0，初始运输成本变化值ΔEi(n+1)=0。

(3) 基因串B上的某一垃圾站i，其在原车辆路径中的前后节点分别为a、b；将该垃圾站i插入新增车辆路径中，新增车辆路径的车辆运输成本增加值最小的插入点为最优插入点，其前后节点分别为a′、b′。于是，垃圾站i转入新增车辆路径后运输成本的变化值Δei=cwo(n+1)w(-tai-tib+tab-ta′b′+ta′i+tib′)。图3以垃圾站1插入到新增车辆的初始路径中的过程为例进行示意。

图3 插入过程示意图

(4) 对每一个垃圾站i计算Δei，取最小值为ΔEi。若ΔEi<0且Cap+dip≤Capw，令ΔEi(n+1)=ΔEi，执行本次插入，并更新相关参数，返回步骤(3)；否则，转到步骤(5)。

(6) 若所有类型车辆路径均已解码完毕，结束；否则，返回步骤(1)。

2.3 适应度计算

对每一条染色体，将其解码结果代入目标函数计算目标函数值，令其倒数为适应度。

2.4 遗传操作

(1) 选择。采用轮盘赌法执行选择操作。用上一代保存的适应度最优的个体替换最劣个体，采用轮盘赌法执行选择操作。

(2) 交叉。采用交叉两个染色体对应两点之间基因串的方法执行交叉操作。以交叉概率随机选择进行交叉的两个染色体，然后随机选择某一种类垃圾的收运路径，确定交叉位置所在区间，接着随机选择该区间上的两点，确定交叉位置，最后交叉两点之间的相同基因，避免交叉后路径中出现数字重复的情况。例如交叉的两个基因段为[1 2 3 4]和[2 5 6 1]，交叉后形成的新基因段为[2 3 4 1]和[1 2 5 6]。

(3) 变异。采用同一染色体上两点互换变异的方法执行变异操作。以变异概率随机选择进行变异的两个染色体，然后随机选择某一种类垃圾的收运路径，确定变异位置所在区间，接着随机选择该区间上的一点以及其邻点，确定变异位置，最后互换两点之间的基因。

3 仿 真

3.1 仿真构建

以郑州市高新区某垃圾中转站服务片区作为仿真区域，区域内设有17处垃圾站，用编号1-17表示，垃圾中转站用编号18表示，各设施位置如图4所示。通过高德地图开放平台测量各垃圾站之间、垃圾中转站与垃圾站之间的车辆行驶最短距离作为节点之间的距离，如表1所示。节点之间的车辆往返路径受到城市道路约束，导致节点之间的往返距离存在差异。

图4 设施位置示意图

表1 各节点之间车辆行驶距离 km

续表1

类型1车辆为密封清运车、类型2车辆为密封专用车、类型3车辆为普通车，最大装载量分别为6、3、5(单位：t)，车辆单位距离运输成本分别为4、3、3.5(单位：元/km)，车辆启动成本每天分别为150、120、100(单位：元/辆)。生活垃圾分为厨余垃圾、可回收物、有害垃圾和其他垃圾四类，每个垃圾站内不同种类的垃圾量如表2所示。其中厨余垃圾由类型1车辆收运，有害垃圾由类型2车辆收运，可回收垃圾和其他垃圾由类型3车辆收运。设定遗传算法参数中种群大小100，最大迭代次数2 000次，交叉概率0.7，变异概率0.2。

表2 垃圾站内不同种类的垃圾量 t/天

续表2

3.2 仿真结果

利用MATLAB语言编程，在计算机上运行239.83 s结束，迭代趋势如图5所示，最小成本和平均成本均随着迭代次数的增加而降低，二者之间的间距也逐渐趋于稳定。在计算机上多次运行，运行时间均在189 s～317 s之间。可见，遗传算法有效，并且能够在短时间内给出模型的满意解。

图5 遗传算法迭代趋势图

运行结果显示，总成本为1 740.8元，最优染色体为[ 1 4 15 16 6 7 8 10 12 17 9 5 14 2 13 11 3 | 4 15 16 13 14 11 17 10 5 8 1 6 9 7 12 2 3 | 1 15 14 7 12 17 3 9 5 8 4 13 11 16 6 10 2 ]，为便于展示，将不同类型车辆的收运路径用“|”间隔。最优染色体解码后得到12条收运路线，如表3所示，该垃圾中转站需拥有5辆类型1车辆分别收运路线1-5上的厨余垃圾，2辆类型2车辆分别收运路线6-7上的有害垃圾，5辆类型3车辆分别收运路线8-12上的可回收垃圾和其他垃圾。可以看出，在垃圾种类和车辆类型必须匹配的条件下，不同类型车辆的收运路径均不相同，所有垃圾站内不同种类的垃圾都被收运至垃圾中转站，表明模型及算法均有效。

表3 车辆收运路径

图6以路线1为例进行示意，由于车辆行驶路径受城市道路约束，导致同一车辆的收运路径存在交叉的情况，这符合实际。

图6 路线1的车辆收运路径示意图

4 结 语

本文根据《生活垃圾分类制度实施方案》具体内容，在垃圾分类收运背景下，研究多种类多车型垃圾分类收运车辆路径优化问题，采用遗传算法予以求解，通过仿真验明了模型及算法的有效性。本文为解决生活垃圾分类收运车辆规划问题提供思路，期望促进垃圾分类形成前端分类投放、中端分类收运、末端分类处理的完整体系。