基于粒子群算法的大件垃圾预约上门收运干扰管理研究

白晓燕

摘 要：为解决居民点大件垃圾尺寸变化对原始收运计划造成的扰动问题，提出扰动辨识和扰动度量方法，并以对收运系统扰动最小为目标，建立干扰管理模型。最后通过实例仿真实验，验证干扰管理模型和算法的有效性。

关键词： 大件垃圾;车辆调度;干扰管理;尺寸变化

文章编号： 2095-2163（2021）01-0079-06 中图分类号：X799.3 文献标志码：A

【Abstract】In order to solve the problem of door-to-door collection and transportation vehicle scheduling interference caused by the size change of bulky waste in residential areas， the disturbance identification method and disturbance measurement strategy are proposed according to the interference management idea， and the interference management model is established with the goal of minimum disturbance to the collection and transportation system. Finally， an example simulation experiment is used to verify the effectiveness of the interference management model and algorithm.

【Key words】bulky waste; vehicle scheduling; interference management; size change

0 引 言

大件垃圾指重量超过5kg或体积大于0.2m3或长度超过1m且整体性强而需要拆解后再利用或处理的废弃物[1]，通常都具有较高的回收价值。大件垃圾的收运系统由收集、运输、处理共同组成，各个环节相互协调、合理规划、优化调度才能使整个大件垃圾收运系统达到最优化。但随着居民预约上门收运的时间窗的变化、大件垃圾的尺寸变化（大件垃圾的长、宽、高的信息错误）等不可控制的客观环境发生变化，就会造成原定路線的最优方案的不能有效启动。结合干扰管理思想，对干扰事件进行扰动辨识和扰动度量，分析干扰事件发生后可能会引起变化的变量、对整个大件垃圾收运系统调度的影响及对扰动的变量进行偏离度量后，构建大件垃圾预约上门收运的干扰管理模型，为干扰事件发生时快速有效地启动应急预案，最大程度地降低干扰事件的影响，保证大件垃圾预约上门收运系统的持续高效的正常运转。

1 文献概述

干扰管理的作用旨在当干扰事件发生后，快速生成对系统扰动最小的调整计划，同时考虑费用，但是并非只是费用最小化。

干扰管理的研究越来越受到学界的关注，研究工作也在陆续展开。在有关干扰管理领域的研究方面，Yu等人[2]定义了干扰管理，Clausen等人[3]也基本认为干扰事件发生后，干扰管理的目标是使新方案相对于原方案的扰动最小。文献[4-9]都根据干扰管理思想，对不同干扰事件做出了一系列的研究处理，建立模型求解。

本文以干扰管理思想为基础，对大件垃圾预约上门收运系统中出现的大件垃圾尺寸变化的问题进行研究，针对大件垃圾预约上门收运系统的特点提出收运容积偏离、收运次数偏离、收运距离偏离和路线偏离四种扰动度量，提出大件垃圾预约上门收运干扰管理模型，通过对收运路线的局部实时调整，优化干扰事件发生前的初始计划路线，从而生成在线调整方案。

2 大件垃圾预约上门收运干扰管理模型

2.1 问题描述及假设

本文针对大件垃圾预约收运过程中居民点的大件垃圾尺寸发生变化时，所引起的大件垃圾收运车辆的调度干扰问题进行研究。干扰管理的目标是使管理后的新方案与初始方案的偏差最小且尽量保持初始方案的最优;基于对大件垃圾预约上门收运路线最优化研究的基础上进行干扰管理的研究。本文假设当干扰事件发生时，大件垃圾收运系统能够迅速获取所有收运车辆的位置、车厢装载情况等信息。在保证大件垃圾收运车辆车厢最大容积率和装载率的情况下，初始路线是收运距离最短的最优路线。

大件垃圾的预约收运过程：每辆大件垃圾收运车辆由车库出发，至下单预约收运服务的居民点进行大件垃圾的收运工作，收运完毕后再至下一居民点收运，直至车辆满载不能继续装载大件垃圾时，至大件垃圾处理厂卸空大件垃圾;每辆车依次循环工作，直至服务完所有的居民点，至大件垃圾处理厂卸空，车辆驶回车库。大件垃圾预约上门收运如图1所示。已知：

（1）车库和居民点，居民点和居民点，居民点和处理厂，处理厂和车库的距离;

（2）各居民点的大件垃圾进行装箱处理后的长（lik）、宽（wik）、高（hik）、体积（vik）和质量（qik）;

（3）各居民点的大件垃圾数量（ei）;

（4）车库、各居民点、处理厂的地理位置（坐标）;

（5）收运车辆车厢的额定载重（Q）和额定体积（L*W*H）{即：车厢的长（L）、宽（W）、高（H）}，和车厢沿X、Y、Z轴的重心范围;

（6）收运车辆的行驶速度（即：距离/速度=行驶时间）;

（7）每个居民点被服务的时间si。

其中，假设每件大件垃圾的被收运时间为0.2，si=居民点的大件垃圾数ei*0.2;收运车辆在处理厂的停留时间=大件垃圾装载总数*0.2。

2.2 扰动辨识

2.3 扰动度量

干扰管理的思想就是生成对系统扰动最小的调整方案，且考虑原目标函数最优化。对此拟展开研究论述如下。

（1）大件垃圾收运容积偏离的度量。数学公式可写为：

其中，Δνik表示居民点i处的第k件大件垃圾的体积变化量，Δνik=Vgp-V0gp，V0gp表示原路线车辆p第g次装载体积，Vgp表示新路线车辆p第g次装载体积; gp表示新路线车辆p收运的次数;μ表示与原路线相比，新路线中大件垃圾增加单位体积的惩罚参数。

（2）收运次数的偏离。数学公式可写为：

其中，gp表示车辆p收运的次数，g0p表示原路线车辆p收运的次数。

（3）收运距离偏离的度量。数学公式可写为：

其中，C0表示初始方案中所有居民点的集合; c1表示增派一辆收运车辆的固定成本;c2表示收运车辆行驶单位距离的成本;x0ijp表示初始方案中的决策变量;xijp表示干扰管理方案中的决策变量;d0ij表示初始方案中居民点i，j之间的距离;dij表示干扰管理方案中居民点i，j之间的距离;CLp表示车辆p尚未完成上门收运的居民点集合。

（4）路线偏离的度量。数学公式可写为：

其中，+、-分别表示和大件垃圾收运原路线相比，新路线中新增/减少一条边的惩罚参数;r+p表示属于大件垃圾收运新路线但不属于原路线的线边集合;r-p表示属于大件垃圾收运原路线但不属于新路线的线边集合。

2.4 扰动恢复策略

根据符俊波等人提出的扰动恢复策略，本文结合大件垃圾收运过程及收运特点，提出自救策略、邻近救援策略和增派救援策略3种大件垃圾收运车辆的扰动恢复策略[9]。

2.5 建立虚拟收集点

本文为统一车辆收运状态，引入大件垃圾虚拟收集点概念[9]，将所有的收运车辆统一至车库或者大件垃圾处理厂。按照干扰发生时收运车辆状态建立虚拟收集点，对此可做阐释分述如下：

（1）大件垃圾收运车辆正在行驶至下一居民点的途中，则将收运车辆前往的居民点设为收集点。

（2）大件垃圾收运车辆正在对居民点进行收运服务，则将该居民点设为虚拟收集点。

（3）大件垃圾收运车辆在车库/处理厂，则无需设立虚拟收集点[9]。

2.6 干扰管理模型建立

本次研究得到的大件垃圾预约上门收运干扰管理的数学模型详见如下。

（1）目标函数。对应的数学公式可表示为：

（2）保证虚拟收集点第一个得到服务，且最终从大件垃圾处理厂返回到车库。对应数学公式可表示为：

（3）每个居民点被服务且只被服务一次。对应数学公式可表示为：

（4）每条收运路线上的大件垃圾总质量不得超过车辆的最大装载质量，总体积不得超过车辆的最大装载体积。对应数学公式可表示为：

（5）保证每件大件垃圾必须全部在收运车辆车厢内部。对应数学公式可表示为;

（6）为保证收运车辆行驶安全，每辆车中的所有的大件垃圾重心必须在一定的安全范围之内。对应数学公式可表示为;

其中，i，j=1，2，3…，n表示居民点的集合;i，j=0′表示处理厂的集合，i，j=0表示车库;qi表示居民点i处的大件垃圾总质量;vi表示居民点i处的大件垃圾数量;tij表示车辆在弧（i，j）的行驶时间;si表示居民点i需被服务的时间;wip表示车辆p到达居民点i的时间;居民点i下单预约大件垃圾上门收运服务的时间范围[ai，bi];L/W/H表示大件垃圾收运车辆车厢的长、宽、高;Q表示收运车辆车厢的最大装载质量;V（L*W*H）表示收运车辆车厢的最大装载体积;（XIikp，YIikp，ZIikp）表示车辆p在居民点i处收运的第k个大件垃圾在车辆车厢中的正面右上角坐标;（XIikp，YIikp，ZIikp）表示车辆p在居民点i处收运的第k个大件垃圾在车辆车厢中的侧面左下角坐标;[x1，x2]表示收运车辆车厢沿X轴的重心范围要求; [y1，y2]表示收运车辆车厢沿Y轴的重心范围要求; [z1，z2]表示收运车辆车厢沿Z轴的重心范围要求;ei表示居民点i处的大件垃圾数量;Iik表示居民点i处的第k件大件垃圾，k=1，2，3，…，ei;lik、wik、hik、qik分别表示第i个居民点处的第k件大件垃圾的长、宽、高及质量， k=1，2，3…，ei;P=（1，2，3，…，p）表示车辆集合，也可表示取货路线数量;Iikp表示居民点i处的第k件大件垃圾装在收运车辆p中;Ijlp表示居民点j处的第l件大件垃圾装在收运车辆p中;CL表示干扰发生后新建立的收集点的集合;CM表示虚拟收集点的集合，CM∈CL。

3 模型算法设计

干扰事件下的收运车辆调度与三维装箱联合优化問题，是较为复杂的组合优化问题，用普通的优化方法难以在短时间内求出最优解，甚至是有效解。粒子群算法实现容易、收敛快、精度高，所以本文引用文献[10]提出的多相量子粒子群算法，结合车厢装载检验算法来解决此类问题，车厢装载检验算法主要检验各收运车辆在其收运过程中车厢中放置的大件垃圾是否满足三维装载约束，保证大件垃圾能够成功装载。大件垃圾车厢装载检验算法流程见图2。

4 实例分析

数值试验平台为Matlab 9.0，计算机CPU为英特尔酷睿 5、2.6 GHz，8 GB内存，64位Windows10操作系统。

4.1 具体问题描述

案例数据如下：有15个居民点下单预约上门收运大件垃圾服务，当天车库提供服务的收运车辆可用时间窗范围为[0，12]，收运车辆行驶速度为50，收运车辆数为3。本文规定车辆车厢的重心范围约束分别为[0，50]、[5，20]、[0，30]。各居民点需被服务时间跟大件垃圾数成正比，每件大件垃圾需求的服务时间为0.2。各居民点处的大件垃圾数在[1，3]之间随机生成，每件大件垃圾的长、宽、高分别在[0.2L，0.6L]、[0.2W，0.6W]、[0.2H，0.6H]之间随机生成。

车库的位置坐标（x0，y0）、处理厂坐标（x0′，y0′） 、收运车辆车厢的长、宽、高及最大载重，见表1。

居民点位置坐标，各居民点处大件垃圾个数ei、总质量qi，及居民下单预约大件垃圾上门收运服务的时间窗范围[ai，bi]、各居民点总服务时间si，见表2。各居民点处每件大件垃圾的长、宽、高及质量见表3。

4.2 初始最优路线参数设置

粒子群算法的参数设置为：种群规模popsize=50，最大迭代次数为gen=100，将算法通过Matlab语言实现，得出大件垃圾收运车辆最优上门收运路线见表4、表5。

为验证干扰管理的管理有效性，设计干扰事件：大件垃圾收运车辆对居民点12进行上门收运完成后，在至居民点1收运途中，得知居民点1处的大件垃圾的尺寸与居民预约时不符，其高度由14变成18，根据扰动辨识规则Δv31≤V012但ZI112≥H，居民点1处大件垃圾尺寸的变化对大件垃圾预约上门收运系统产生扰动，原收运计划不可行，需要重新制定上门收运计划。干扰发生时刻为5.09，根据本文虚拟收集点的定义，得到干扰发生时，虚拟收集点集合为[14，4，1，8，2]，已完成收运的收集点集合为[6，7，13，11，3，12，15，10，9，5]。

4.3 干扰管理优化结果

粒子群算法的参数设置和初始方案相同，干扰管理模型中参数设置为：

μ=0.05，θ=10，c1=100，c2=1，+=1，-=1。用本文设计的干扰管理模型对产生的扰动进行恢复，根据仿真实验知应采取邻近救援策略，得到干扰管理结果见表6、表7。

为验证本文构建模型的有效性，选择传统的干扰处理方法-重调度法进行仿真实验结果的对比，实验结果见表8。

结果表明，总体上干扰管理优化结果明显优于重调度结果，大件垃圾预约上门收运干扰管理模型有效，解决了预约上门收运过程中因居民点处大件垃圾尺寸变化对收运系统造成的影响，能够快速进行扰动恢复，最大程度降低扰动影响，对有关大件垃圾预约上门收运方式的深入研究做了铺垫。

5 结束语

本文以大件垃圾预约上门收运系统中的大件垃圾尺寸发生变化时的干扰事件进行研究，根据大件垃圾收运系统的特点，提出相应的扰动辨识和扰动度量方法，建立干扰管理模型，最后通过实例仿真实验验证了干扰管理模型的有效性，保障了在干扰事件发生时快速生成扰动恢复策略。本文是干扰管理在大件垃圾预约上门收运系统中的成功运用，为解决三维装箱车辆调度领域中干扰管理所面对的现实问题进行了有益的探索。

参考文献

[1]GB/T25175-2010. 大件垃圾收集和利用技术要求[S]. 北京：中华人民共和国国家质量监督检验检疫总局，中国国家标准化管理委员会，2010.

[2]YU Gang， QI Xiangtong. Disruption management： Framework， models and applications [M]. Beijing： World Scientific Publishing Co. Pte. Ltd.， 2004.

[3]CLAUSEN J， HANSEN J， LARSEN J. Disruption management operations research between planning and execution[J]. OR/MS today， 2001， 28（5）：40-43.

[4]王旭坪，許传磊，胡祥培.有顾客时间窗和发货量变化的车辆调度干扰管理研究[J].管理科学，2008，21（5）：111-120.

[5]张钦，潘暑风.物流配送延迟的一个干扰管理模型[J].系统工程，2008，26（10）：13-16.

[6]王征，胡祥培，王旭坪.行驶时间延迟下配送车辆调度的干扰管理模型与算法[J].系统工程理论与实践，2013，33（2）：378-387.

[7]马慧民，罗长见.城市生活垃圾收运车辆调度干扰管理研究[J].工业工程，2015，18（3）：92-97.

[8]阮俊虎，王旭坪.中转点变化的应急医疗物资联合运送干扰管理研究[J].运筹与管理，2016，25（4）：114-124.

[9]符俊波，马慧民，张爽，等.有垃圾量变动的生活垃圾收运车辆调度干扰管理研究[J].上海理工大学学报，2017，39（4）：368-375.

[10]宁涛，王旭坪，胡祥培.行驶受扰延迟下配送车辆调度的干扰管理决策模型[J].系统工程理论与实践，2019，39（5）：1235-1245.