考虑工作量平衡的餐饮垃圾多行程收运路线优化

张燕，李子鑫，刘进平

(大连海事大学，交通运输工程学院，辽宁大连 116026)

0 引言

作为具有悠久饮食文化的国家，近年来随着经济发展和城市化进程的加快，我国城市的各大餐馆和企事业单位食堂产生的餐饮垃圾也随之激增。为改善环境，更有效地利用资源，很多城市开始试点餐饮垃圾分类收运和处理。然而，高收运成本成为推进餐饮垃圾分类管理的一大障碍，如何以更低的成本完成餐饮垃圾的分类收运成为实施垃圾分类管理的重中之重[1]。同时，随着智慧城市成为未来城市的发展理念，很多行业和企业尝试采用优化算法降本增效，但大多数算法只关注成本，没有考虑工作人员的人本需求[2]。本文针对餐饮垃圾的收运特点提出相应的收运模型及算法，致力于在降低餐饮垃圾分类收运成本的同时，提升驾驶员的工作满意度，对于提升城市废物管理水平，推动城市的可持续发展具有重要意义。

在以往的相关研究中，不少学者针对居民生活垃圾的收运路线优化问题进行了研究。例如，LEI等[3]考虑生活垃圾的周期性收运路线优化和车辆调度问题，建立多周期的车辆路径问题模型，并采用两阶段算法求解问题；ASEFI 等[4]考虑多种废物类型的收运问题，建立车队规模和混合车辆路径优化问题模型，并对小规模问题进行求解；ALIAHMADI等[5]考虑运营成本和收运时间两个目标，建立带时间窗的多行程车辆路径问题模型，并采用多目标优化算法求解问题；闫芳等[6]结合智能垃圾桶提出动态生活垃圾收运优化策略，通过粒子群算法获得初始收运方案，然后，采用重置优化算法实时调整收运路径。同时，也有学者结合新的技术方法，例如，李明月等[7]考虑时间成本及环境成本，提出一种基于GIS技术与改进蚁群算法的垃圾收运路径优化方法；GLAESER 等[8]针对地下废物收运系统，建立以收运成本最小化为目标的垃圾箱分配和车辆路径问题的数学模型，并设计变邻域启发式算法求解问题。

与城市生活垃圾的收运不同，餐饮垃圾的收运路线优化问题需要考虑以下因素：首先，由于各个餐饮企业及企事业单位食堂产生餐饮垃圾量和高峰时段不同，因此，需要针对不同的企业类型设置不同的收运频率、收运时段和服务时间窗，以便均衡各个时段的垃圾收运量；第二，餐饮垃圾含水量大，难以压缩，餐饮垃圾收运车在每个收运时段内需要多次进出餐饮垃圾处理厂进行卸货；第三，城市餐饮企业集中于商业区或者小吃街附近，因此，在设计优化路线时需考虑实际道路的拥堵因素以及限行要求。

因此，餐饮垃圾的收运路线优化是一个考虑时间窗约束的多行程车辆路径问题(Multi-Trip Vehicle Routing Problem with Time Windows,MTVRPTW)，学者们针对该问题提出了不同的模型和算法。例如，FRANCOIS 等[9]建立以总行驶距离为目标函数的多行程车辆路径数学模型，并设计带有多行程算子的自适应大邻域搜索算法；彭勇等[10]考虑带时间窗的多行程交换箱甩挂路径问题，并设计混合遗传算法，以充分利用司机日常工作时间；PAN 等[11]以最小总运输距离为目标，研究城市物流配送中时变路网下的多行程车辆路径问题，并采用混合元启发式算法求解问题。但是，现有研究大多考虑的都是单一车场，且大多是以总行驶距离或时间为目标函数，缺少针对餐饮垃圾的收运特点所提出的相应模型和算法。

本文首先建立具有时间窗约束的多行程餐饮垃圾收运问题的混合整数规划模型，并根据问题特点设计混合自适应大邻域搜索算法。在模型和算法中，考虑驾驶员的各项工作需求，例如，保障驾驶员的午休以及工作强度不超标，保证驾驶员之间的工作平衡；同时，还考虑城市实际路网的拥堵情况，得到既节省成本又降低碳排放，还能提高驾驶员工作满意度的最优路线。

1 问题描述与模型建立

1.1 问题描述

本文考虑城市中的餐饮垃圾收运路线优化问题，其中，餐饮垃圾的收运来源包括各种不同类型的餐馆和企事业单位食堂。首先，根据各类型餐馆和单位食堂的营业特点，设定两种收运频率：每天两次或每天一次。对于夜市及早餐为主的餐饮企业，每天上午(时段1)收运一次，对于不供应晚餐的企事业单位食堂等，每天下午(时段2)收运一次；对于全天营业的餐馆及食堂，每天上午和下午各收运一次。

餐饮垃圾的收运网络由餐饮垃圾的收运点、车场和餐饮垃圾处理厂组成。每辆餐饮垃圾收运车在每个收运时段内完成一个混合的多行程任务，如图1 所示。每辆车收运任务的第一段行程为开放式行程，车辆从车场空车出发，沿途访问收运点之后，到达处理厂卸货，之后的收运任务是以处理厂为中心的多个闭合式行程，最后一段是完成收运任务后空载返回车场的行程。

图1 混合多行程的餐饮垃圾收运路线示例Fig.1 Illustration of hybrid multi-trip food waste collection route

驾驶员在上午时间段的收运任务完成后，返回车场午休后，再进行下午的收运。驾驶员每天的工作任务总时长不超过最长工作时间，并且各个驾驶员之间的工作量尽可能平衡。同时，本文考虑车辆在实际道路行驶过程中的拥堵因素，将车辆在任意两点间的行驶时间计为正常行驶时间加上拥堵时间。假设餐饮垃圾的处理设施容量足够大，每个收运点的餐饮垃圾不允许分批收运。该问题的目标是在保证驾驶员工作量不超标且平衡的情况下为每个时段设计合理的收运路线，从而最小化收运过程中的车辆固定成本和燃油成本。

1.2 模型参数与变量

(1)相关集合

Na={1,2,…,n}——所有餐饮垃圾收运点的集合，其中，n为收运点数目；

Ne={0,1,2,…,n,n+1}——包含车场、收运点和处理厂的扩展集合，其中，0为车场，n+1 为餐饮垃圾处理厂；

Np——在时段p收运的所有收运点集合；

V={1,2,…,Vmax}——收运车辆集合，其中，Vmax为收运车辆的总数量；

P={1,2,…,T}——餐饮垃圾收运时段集合。

(2)参数定义

对于收运点(i,j)∈Ne，车辆k∈V，时段p∈P，定义以下参数。

tˉij——收运车在收运点(i,j)间的正常行驶时间(min)；

Qmax——餐饮垃圾收运车的最大净载量(kg)；

cV——收运车的单位固定运营成本(元·d-1·辆-1)，包含车辆折旧和驾驶员薪酬；

cS——收运车在拥堵和装卸服务时的怠速燃油成本(元·min-1)；

cD——收运车正常行驶时的单位燃油成本(元·min-1)；

H——收运车在每个时段内可以进行多行程收运的最大次数；

M——极大的正数。

(3)决策变量

1.3 数学模型

根据以上参数和变量定义，本文所考虑的带时间窗约束的混合多行程的餐饮垃圾收运问题(HMTVRPTW)的数学模型(模型M)为

目标函数式(1)表示最小化所有时段的总收运成本，包括车辆的固定运营成本、车辆在交通拥堵以及装卸作业时的怠速燃油成本和正常行驶时的燃油成本。

式(2)～式(15)是关于混合多行程收运路线的约束。其中，式(2)表示第一段的开放行程需要从车场出发；式(3)表示收运车的第一段开放行程中不可以从车场直接到达处理厂；式(4)表示最后一段的空载行程必须返回车场；式(5)和式(6)表示实际派出收运车的数量不超过最大数量；式(7)表示收运车需完成当前时段内所有收运点的收运任务；式(8)表示收运车不访问不属于当前时段的收运点；式(9)表示收运车在每个收运点收运完成后，需离开；式(10)表示各收运点自身无路径产生；式(11)表示收运车访问收运点之后，需前往处理厂卸货，不可以从收运点直接返回车场；式(12)表示每个时段内收运车执行多行程的最大数量限制；式(13)～式(15)表示收运车被使用时才会产生多行程路径。

式(16)～式(18)为收运车容量相关的约束。其中，式(16)表示各收运点的垃圾量需一次性收集完；式(17)表示收运车收运的垃圾不超过其最大净载量；式(18)表示开放行程中，收运车需在车场空车出发，并在到达处理厂后卸空垃圾。

式(19)～式(26)为时间相关的约束。其中，式(19)表示加上拥堵时间后的收运车实际行驶时间；式(20)～式(23)表示收运车到达各点的访问时间需满足路线访问顺序；式(24)表示收运车的到达时间必须小于各收运点的最晚收运时间窗；式(25)和式(26)为工作平衡性约束。

2 问题求解与算法设计

本文建立的模型M为混合整数规划模型，对于小规模问题，采用AMPL+GUROBI直接求解，得到最优解。当问题规模较大时，模型M无法在有效时间内求解。为满足求解大规模实际问题的需要，本文设计了混合自适应大邻域搜索算法(Hybrid Adaptive Large Neighborhood Search algorithm,HALNS)，在短时间内得到问题的近似最优解。

2.1 启发式算法的设计及实现

自适应大邻域搜索算法(Adaptive Large Neighborhood Search,ALNS)是在大邻域搜索算法(Large Neighborhood Search,LNS)的基础上，加上算子权重的自适应调整，即在每次迭代时会根据当前解的质量更新算子的权重，从而使算法在寻优过程中能自主调整各个算子被选择的概率。本文提出的HALNS 算法在ALNS 算法的基础上，加入局部搜索算子，以提升算法的寻优能力。HALNS 算法的整体流程如图2所示。

图2 HALNS算法流程Fig.2 Flowchart of HALNS

2.2 初始解的构造及初始解

根据问题多行程路线的特点，本文采用三维矩阵对解进行编码，如图3所示。所有车的路线组成一个完整的解，每辆车的路线由多个行程组成。为保证解的可行性，需要保证每辆车的行程总数不超过车辆最大行程数，且每段行程的收运量均不超过收运车的最大容量。

为获得初始可行解，采用贪婪算法构造初始路线，具体过程如下：首先，按节点编号顺序选择收运点，以加入空车的行程路线，当该行程中垃圾量达到收运车的最大载量Qmax时，新增下一段行程，并将剩余的收运点增加到新行程中，循环此过程直至该收运车的总行驶时间达到驾驶员的工作最晚时间；然后，选取新的收运车，并重复上述步骤；直至该时段所有收运点均完成。

2.3 适应度函数

为满足收运时间窗和驾驶员工作平衡的约束，构造带惩罚函数的适应度函数fs，即

式中：zs——当前解s的目标函数；

Es，Ls——当前解s中，违反式(25)和式(26)的工作时间；

η——惩罚系数(经实验，取η=500)，表示当前解s违反时间窗式(25)和式(26)时的单位时间惩罚成本。

适应度函数fs的值越小，表明当前解的质量越高。

2.4 邻域解的更新及算子设计

根据问题特性，本文设计了3 种移除算子和2 种插入算子，以获得新的邻域解。为产生新的邻域解，需要先从当前解中移除m个收运点，再将这些点插入到新的位置里。在每次迭代中，移除的收运点数目m从范围中随机产生，其中，|Np|表示当前时段收运点的总数量，λ1和λ2分别表示要移除的收运点占总收运点数的下界与上界比例值(0＜λ1＜λ2＜1)。经实验，本文选取λ1=0.10，λ2=0.25。各个算子的规则如下。

(1)移除算子

①R1随机移除

从当前解中随机移除一个收运点。

②R2最差点移除

移除使当前解适应度值增加最多的收运点。定义当前解s 中收运点i 的边际成本，其中，表示从当前解s 中移除收运点i 后的适应度值，将最大的点移除。

③R3相关移除

根据收运节点之间的相似度进行移除[12]，即先随机移除一个收运点i，再移除与收运点i相似度最高的收运点j。本文通过距离、交通状况、时间窗要求及餐饮垃圾量这4方面衡量相似度，收运节点i和j的相似度R(i,j)为

式中：dij——收运点i和j之间的距离；

cij——收运点之间的交通状况；

|li-lj|——收运点之间最晚开始服务的时间差异；

|qi-qj|——收运点之间的需求差异；

ϑ、ρ、σ、ς——影响因素的权重。

R(i,j)越小，表示相似度最大。

(2)插入算子

①INS1贪婪插入

将从当前时段的收运路线中移除的收运点插入到使得当前解的适应度值增加最少的位置。

②INS2最大后悔值准则插入

令fk表示当前解的适应度值，用fik表示当前解插入收运点i后第k低的适应度值，令ΔFk=fik-fk，当k≤k'时，满足ΔFk≤ΔFk'，定义后悔值ci=ΔF2-ΔF1，表示把收运点i插入到当前解的最优位置和次优位置的差值，将最大后悔值的收运点插入到当前解中。

(3)局部搜索算子

使用移除和插入算子产生新的邻域解之后，采用局部搜索算子改善产生的邻域解，改善后的解作为当前解。每次迭代的改进次数为ω次，每次使用的算子从以下5种随机选择。

①LS1转移(Shift)

随机选择一辆车，从该车的一段行程中随机选择一个收运点，移动到其他行程中。

②LS2交换(Swap)

随机选择两辆车，从已有行程中随机选择两个收运点，交换两收运点位置。

③LS3 2-opt搜索

从某一行程中随机选择两个收运点，翻转两点之间的收运点顺序。

④LS4 2-opt*搜索

随机选择两辆车，从不同行程路径中随机选择两个收运点，交换该两点之后的收运路径。

⑤LS5 平衡性改进(Balance)

对于工作结束时间超过驾驶员最晚工作时间的多行程路线，从中随机选取一段行程，并将其插入到另外一条工作时间较短的多行程路线中，使各个路线的总工作时间尽可能平衡。

对于经过局部搜索改进的邻域解，需要使用如下规则判断是否将其接受为新的当前解。当新解优于当前最好解时，则接受新解；否则，根据模拟退火接受准则，以概率接受新解，其中，f'为新解的适应度值，f为当前解的适应度值，D表示当前温度，其初始温度为D=D0，每次迭代后，D通过D=θD更新，0＜θ ＜1，本文选取D0=30，θ=0.94。最后，若算法连续迭代φ次未能更新解，或达到最大迭代次数ψ时，算法终止。本文选取φ=30，ψ=300。

(4)算子权重的更新

在迭代下一代邻域解之前，需要依据当前解的质量更新移除和插入算子的权重。令po表示算子o被选择的概率，表示在第t次迭代时算子o的权重，算子被选择的概率以及算子权重的迭代方法为

设定移除和插入算子每20代更新一次，其中，算子o的初始得分为10；算子更新参数α=0.7；表示算子o在第t次更新时，在近20代迭代中被选中的次数；表示算子o在第t次更新时，在近20次迭代中得到的解的总评分。评分方式如下：若在迭代后得到的邻域解snew不劣于当前的全局最好解sbest，得 分40；若sbest≤snew≤sold，则得分30；若snew＞sold，但该解被接受，则得分20；否则，得分为0。

3 算例验证

为验证所建立的数学模型和提出算法的有效性，采用不同规模的算例，将GUROBI 求解数学模型M得到的解与HALNS和ALNS算法得到的解进行比较。

3.1 算例设置

本文从Solomon 标准算例库中选取不同规模的车辆路径问题算例，并对原数据进行以下调整，适应求解本文问题：(1)划分两个收运时段，将需求点划分为3种收运方式(上午、下午及上下午)，并调整需求点的时间窗和收运量；(2)原数据中仅含有车场，无处理厂，本文选取接近中心的位置虚拟为处理厂位置，并设定车辆在处理厂的卸料时间为5 min；(3)为适应多行程收运，缩减了车容量；(4)原数据中不考虑拥堵，故该部分将拥堵时间设置为0；(5)原数据中不含收运成本，本文设定每辆车的固定使用成本为200 元·时段-1，燃油成本为1 元·min-1。具体参数的调整情况如表1所示。

表1 算例规模及相关参数Table 1 Instance setting and parameters

3.2 算例验证

算例R1～R5的求解结果如表2所示，每个算例均采用3 种方法求解，即AMPL+GUROBI 9.5.2 直接求解模型、ALNS 算法和HALNS 算法。其中，ALNS算法采用与HALNS算法相同的初始解产生方案，以及相同的移除和插入算子，但没有加入局部搜索算子。HALNS 算法中，根据算例规模的不同设定不同的局部搜索次数值(ω)，其中，R1和R2中，ω=50；R3 中，ω=100；R4 中，ω=200；R5 中，ω=1000。HALNS 和ALNS 的算法均采用Python编程实现。

表2 算例求解结果对比Table 2 Comparison of solutions obtained by different algorithms

表2 的后两列给出每个算例求解10 次后得到的平均求解时间和平均目标值。可以看出，对于小规模算例R1～R3，虽然直接采用GUROBI求解模型M 需要较长时间，但是，可以得到问题的最优解或近似最优解。HALNS算法和ALNS算法的求解时间较短，但不是每次求解都可以得到最优解。相比较之下，HALNS 算法得到最优解的次数多于ALNS 算法，所以，HALNS 算法的平均目标值低于ALNS 算法。当算例规模增大时，GUROBI 无法在合理时间内得到最优解，但HALNS 和ALNS 算法都能在短时间内得到近似最优解，且HALNS 算法在解的质量和求解时间上明显优于ALNS算法，所以，HALNS算法更适合求解大规模问题。综上，算例求解结果验证了本文模型的正确性以及HALNS算法的有效性。

3.3 驾驶员工作平衡性检验

算例R1～R5 在有平衡性约束和无平衡约束的情况下得到的结果对比如表3 所示。令ΔTB表示考虑平衡约束时驾驶员的工作时间差(最大工作时长减最小工作时长)，ΔTN表示不考虑平衡约束时驾驶员的总工作时间差，当考虑平衡约束时，对驾驶员的工作量平衡性的改善程度为αB；同样，令CB表示考虑平衡约束时的总成本，CN表示不考虑平衡约束时的路线总成本，考虑平衡约束后总成本的增加程度为αC，即

表3 工作平衡性对比结果Table 3 Comparison of workload balancing

表4 油耗参数定义与取值Table 4 Definition and value for parameters related to fuel consumption

从表3 可以看出，当考虑工作量平衡性约束时，总成本虽有小幅增加(小于2%)，但驾驶员的工作平衡性能得到大幅度改善，尤其当算例规模增大时，考虑平衡性约束的优势更为明显。

4 实例分析

为进一步验证本文的模型和算法在求解实际问题时的有效性，选取大连市中山区的餐饮垃圾收运网络作为实际案例进行分析。在实例求解中，根据实际调研的结果以及相关文献中的数据，设定相关数据。

4.1 实例数据

(1)收运点及产生量

首先，依据大连市目前餐饮垃圾的分类实施情况，收运来源仅考虑大中型餐饮企业和各企事业单位食堂。本文通过调研得到大连市中山区的228 个餐饮垃圾收运点，并将其位置信息导入到地理信息系统软件(ARCGIS)中，如图4所示。根据文献[13]确定大中型餐饮企业餐饮垃圾的产生量均值分别为360 kg·d-1和191 kg·d-1，以均值上下浮动10%为取值范围随机产生不同餐饮企业的产生量。企事业单位食堂的餐饮垃圾产生量根据各企事业单位的在职人数乘以人均日餐饮垃圾产生量(0.23 kg·d-1·人-1)得到。同时，根据各餐饮企业的性质和营业高峰期，确定上下午两个收运时段和两种收运频率。其中，营业高峰期为晚上的餐饮企业在每天的时段1，即8:00-12:00收运；营业高峰期在早上和中午的餐饮企业在每天的时段2，即14:00-18:00收运；全天营业的餐饮企业在时段1和时段2各收运一次。

图4 大连市中山区餐饮垃圾收运点示例Fig.4 Illustration of food waste collection points in Zhongshan District,Dalian

(2)收运车辆油耗及道路拥堵系数

在实例求解时，本文根据实际调研的车辆数据，结合BARTH 等[14]开发的Comprehensive Emission Model 计算收运车以不同速度行驶的油耗，其中，收运车辆以速度v行驶t段时间的油耗为

另外，本文对速度和载重量对于油耗的影响进行灵敏度分析发现，餐饮垃圾收运车的油耗量对速度的敏感性较高，而对载重量的敏感性较低。因此，本文按照收运车辆在城区和非城区的实际行驶路程采用两种速度。根据文献[5,15]，并结合实际调研，设定收运车辆在城区的运行速度v为30 km·h-1，在非城区的行驶速度v为70 km·h-1。当收运车遇到拥堵路段或在收运点和垃圾处理厂进行作业时，收运车处在怠速状态，根据文献[16]设定收运车辆怠速时油耗FC为2.20 L·h-1。收运车的净载量设定为2.5 t，车辆固定成本为500元·时段-1(每个时段为4 h)，柴油价格为7.2元·L-1。

为确定主要道路的拥堵系数，首先，通过高德地图获取大连市中山区的历史交通拥堵数据，并通过计算得到主干道路在各个时段的拥堵系数，如表5 所示；然后，通过拥堵系数得到车辆在路线上的拥堵时间(拥堵时间为两点距离乘拥堵系数)。

表5 常发生拥堵的主干路及拥堵系数Table 5 Congestion coefficients of some main roads

4.2 结果分析

采用HALNS算法求解实例得到的车辆路线如表6所示，其中，HALNS 算法每次迭代的局部搜索次数ω设定为1000，连续迭代未更新解次数φ=30，最大迭代次数ψ=200。

表6 HALNS算法求解实例得到的收运路线Table 6 Food collection routes obtained by HALNS for real case

HALNS算法与当前某餐饮垃圾智能收运系统中采用的优化算法(BAU)求解结果的对比情况如表7所示。其中，BAU中采用两阶段方法，首先，将收运区域划分为6 个子区域；然后，求解一个旅行商问题，得到各个区域的收运路线。同时，当前实际优化算法设定每个收运点的收运频率均为每天一次，也未考虑驾驶员的工作量平衡情况以及道路拥堵情况。

表7 餐饮垃圾收运路线优化结果对比Table 7 Comparison of food waste collection route solutions

表7 的对比结果表明，本文提出的HALNS 算法能对收运路线进行更合理的安排，不仅可以降低14.3%的总收运成本，还能在少用1 辆车的情况下减少2%的总工作时间，使驾驶员的工作平衡性提升57.3%。另外，从环境角度，通过在模型中考虑拥堵时间，使求解结果能更有效地规避拥堵路段，使收运过程中的碳排放量降低12.7%。

5 结论

本文拓展了对于车辆路线优化方面的研究，为城市餐饮垃圾的收运提供了降本增效的实际解决方案，对于提升城市管理水平，加快智慧城市的建设，促进经济、社会和环境的可持续发展具有重要意义。本文得到的主要结论如下：

(1)所建立的模型M 和提出的算法HALNS 能在降低成本的同时提高驾驶员工作量的平衡性。首先，通过将收运点划分到不同收运时段，均衡各个时段的垃圾收运量；然后，在优化每个时段的收运路线时，考虑驾驶员的工作量平衡约束。优化结果表明，在成本增加值不超过2%的情况下，可以将工作量的平衡性提高36%～98%，而且算例的规模越大，对于不平衡性的改善效果越明显。

(2)采用模型和算法能有效求解具有时间窗约束的多行程餐饮垃圾收运问题。对于小规模问题，直接求解所建立的混合整数规划模型能得到问题的最优解；对于中大规模算例，采用提出的HALNS算法能在较短时间内得到问题的近似最优解。

(3)研究思路及算法适用于实际问题的求解与优化。以大连市中山区的餐饮垃圾收运为例，考虑实际路网的道路拥堵情况和驾驶员的工作平衡性约束等现实因素时，相比当前实际应用的优化算法，HALNS算法能在经济方面降低14.3%的总收运成本，环境方面降低12.7%的碳排放量，社会方面减少驾驶员总的工作时长，并将工作量的不平衡性改善57.3%。