上海理工大学学报  2017, Vol. 39 Issue (4): 368-375   PDF    
有垃圾量变动的生活垃圾收运车辆调度干扰管理研究
符俊波1, 马慧民2, 张爽1, 雷悦2     
1. 上海理工大学 管理学院, 上海 200093;
2. 上海电机学院 商学院, 上海 201306
摘要: 为解决由垃圾收集点垃圾量变化引发的生活垃圾收运车辆调度干扰问题,提出基于干扰管理思想的扰动恢复策略和方案.通过分析干扰事件对垃圾收运系统的扰动,构建垃圾收运车辆调度的扰动辨识和扰动度量,并以新方案与原方案偏差最小为目标,建立扰动恢复数学模型.设计基于车辆收运路径编码方式的遗传算法,求解该类问题.为统一车辆收运状态,引入虚拟收集点概念,并对干扰管理目标函数中的惩罚参数进行研究.最后,通过实例进行仿真实验,并与重调度结果进行比较,验证干扰管理模型和遗传算法的有效性.研究结果表明,干扰管理可以有效降低计划偏离度,并合理控制成本.
关键词: 生活垃圾     车辆调度     垃圾量变动     干扰管理     遗传算法    
Disruption Management of Garbage Collection and Transportation Vehicle Routing Under the Changing of Garbage Amount
FU Junbo1, MA Huimin2, ZHANG Shuang1, LEI Yue2     
1. Business School, University of Shanghai for Science and Technology, Shanghai 200093, China;
2. Business School, Shanghai Dianji University, Shanghai 201306, China
Abstract: To deal with the disruption on the garbage collection and transportation vehicle routing caused by the changing of garbage amount at garbage collection point, disruption recovery strategies and solutions were put forward based on the disruption management theory.By analyzing the influence of interference events on the waste collection and transportation system, the disturbance identification and disturbance measurement of vehicle routing were studied, and a mathematical disruption recovery model was established aiming at minimizing the deviation from the original plan.A genetic algorithm based on the vehicle collection and transportation route encoding was designed to solve the problem.In order to unify the vehicle collection and transportation state, the concept of virtual collection point was introduced, and the penalty parameter in disruption management plan was studied.In the end, through simulation experiments and comparing with the rescheduling results, the effectiveness of the disruption management model and genetic algorithm was verified.The results show that the disruption management can reduce the plan deviation effectively, and control the cost reasonably.
Key words: garbage     vehicle routing     garbage amount change     disruption management     genetic algorithm    

生活垃圾收运系统是由收集、运输和中转3个环节组成, 各个环节合理配置、协调配合, 才能获得最大的环境、社会和经济效益.但随着车辆故障、交通拥堵、垃圾量变动等不确定事件的发生, 垃圾收运系统时常受到干扰.不仅影响收运系统的正常运行, 甚至造成环境的污染.因此, 如何准确辨识不确定事件对垃圾收运系统的扰动, 并迅速做出调整方案, 使系统以最小代价尽快恢复正常运行, 是生活垃圾收运车辆调度研究的一个重要问题.

1 文献研究综述

处理车辆调度干扰问题的经典方法有:随机车辆路径方法、鲁棒优化方法、scheduling和rescheduling方法.干扰管理与上述经典方法不同, 它不是针对干扰事件发生后的状态完全重新建模和优化, 而是最小化干扰对原计划冲击的一种管理方法.Yu等[1]给出了干扰管理的定义, 该定义可分为3层意思理解:第一层是制定并执行最优或次优计划; 第二层是识别干扰事件; 第三层是形成有效的使系统扰动最小的干扰管理新方案.Clausen等[2]也基本认为干扰事件发生后, 干扰管理的目标是使新方案相对于原方案的扰动最小.

干扰管理需要根据实际情况, 针对不同的干扰事件建立相应的恢复模型和有效的求解算法, 以便快速、及时地给出处理干扰事件的最优调整方案.目前, 干扰管理思想己经在航班计划[3]、生产调度[4]、供应链协调[5]、项目管理[6-7]等方面得到了应用.在车辆调度方面, 胡祥培等[8]从客户不满意度、配送成本以及路径偏离程度3个方面度量物流配送系统中的扰动, 采用禁忌搜索算法对有需求量变动的干扰事件进行了仿真实验.王旭坪等[9-10]分析了顾客时间窗变化和发货量变化这两个干扰事件对配送系统造成的扰动.丁秋雷[11]运用行为科学中行为感知与运筹学中定量的研究手段, 分析了客户时间窗变化这类干扰事件对受扰主体的影响.阮俊虎等[12]分析的是直升机和车辆联合运送中出现中转点变化的干扰问题.马慧民等[13]针对城市生活垃圾收运中出现的车辆故障这一干扰事件, 提出了基于初始计划偏离的扰动度量方法, 建立了相应的干扰管理模型.上述研究在特定类型干扰问题的建模和求解方面取得了一定的成果, 然而在扰动度量惩罚参数的取值上缺乏分析.生活垃圾收运系统干扰管理的研究目前尚未形成理论体系, 包括扰动辨识分析、扰动度量方法, 以及大规模问题的实时求解算法等内容都有待深入研究.

本文以干扰管理思想为基础, 对服务型生活垃圾收运系统中出现的有垃圾收集点垃圾量变化的问题进行研究, 针对生活垃圾收运系统的特点提出路线偏离、载重偏离、收运次数偏离和收运费用偏离4种扰动度量, 设计基于车辆收运路径的自然数编码表示方法, 探究路线偏离惩罚参数的合理取值范围.最后, 通过实例验证干扰管理模型和遗传算法的有效性.

2 扰动的分析及恢复策略 2.1 扰动辨识

计划安排K0辆车, 各车辆按照其初始方案设定的任务序列, 对一组垃圾收集点进行服务.车辆kp次收运完成时车辆剩余可用容量为cpk0, 收集点i原定服务时间为ti0, 最晚访问时间为LTi.设在收运过程中, 车辆k在第p次收运因收集点i垃圾量增加Δqi而造成的延迟时间为Δtki, 干扰事件发生后, 车辆k尚未完成服务的收集点的集合为CLk.若车辆k剩余可用容量满足cpk0≥Δqi, 且收集点时间约束满足∀(tj0tki)≤LTj, jCLk, 则垃圾收集点i垃圾量的增加未对垃圾收运系统产生扰动.反之, 则产生扰动.

2.2 扰动度量

干扰管理思想的关键是以原计划为基础快速生成对系统扰动最小的调整方案, 同时保持成本尽量低.在生活垃圾收运车辆调度干扰管理研究中, 系统扰动主要体现在收运路线的偏离上, 成本主要体现在车辆的固定启动费用以及收运费用上.

a. 路线偏离的度量.

(1)

式中:α+, α-分别为与原路线相比, 新路线中新增或减少一条边的惩罚参数; rk+为属于新路线但不属于原路线的线边集合, rk-为属于原路线但不属于新路线的线边集合; rk+, rk-表示集合的数目; K为干扰管理方案收运车辆数目.

b. 收运载重偏离的度量.

(2)

式中:λ为与原路线相比, 新路线增加1 t垃圾量的惩罚参数; qpk为新路线车辆kp次收运装载的垃圾量; qpk0为原路线车辆kp次收运装载的垃圾量; pk为新路线车辆k的收运次数.

c. 收运次数偏离的度量.

(3)

式中:pk为新路线车辆k的收运次数; pk0为原路线车辆k的收运次数.

d. 收运费用偏离的度量.

(4)

式中:C0为初始方案所有垃圾收集点的集合; c1为增派一辆车的固定启动费用; c2为车辆行驶单位距离的收运费用; xijk0为初始方案的决策变量, xijk为干扰管理方案的决策变量, 决策变量为1时表示车辆k从收集点i前往收集点j, 决策变量为0时表示车辆k未从收集点i前往收集点j; dij0为初始方案收集点i, j之间的距离, dij为干扰管理方案收集点i, j之间的距离.

2.3 扰动恢复策略

根据王旭平等[9-10]在物流配送中提出的扰动恢复策略, 本文结合生活垃圾收运车辆的特点, 提出车辆自救策略、邻近救援策略和增派救援策略3种生活垃圾收运车辆的扰动恢复策略.

a. 车辆自救策略:通过微调受扰车辆垃圾收集点的服务顺序保证收运系统正常运行.

b. 邻近救援策略:通过调度在途的其他车辆辅助受扰车辆完成剩余任务.可调度的车辆同时满足两个条件:一是要在受扰任务的时间窗范围内到达受扰任务收集点的位置; 二是施救车辆尚有空间可以利用.

c. 增派救援策略:从车场新派车辆对受扰任务进行救援.增派车辆费用包括两部分:一是增派车辆的行驶费用; 二是启动车辆的固定费用.

3 干扰管理模型的构建 3.1 问题的描述及假设

本文对有垃圾收集点垃圾量变化这一干扰事件进行研究, 在不能改变干扰事件发生的同时, 要求制定出对整个收运系统影响最小的调整方案.本文假设, 在垃圾收运系统中, 各垃圾收集点、车场、中转站位置已知, 初始路线为收运距离最短的最优路线.当干扰事件发生时, 垃圾收运系统能迅速获取所有车辆的位置、行驶时间、装载情况等信息.

3.2 构造虚拟收集点

本文为统一车辆收运状态, 引入虚拟垃圾收集点概念, 从而将所有车辆统一到车场或是中转站.

干扰发生时车辆所处状态共分3种情况, 建立相应情况下的虚拟收集点方法如下:a.车辆正在前往下一收集点途中, 则将车辆前往的收集点设为虚拟收集点; b.车辆正在对收集点进行服务, 则将该收集点设为虚拟收集点; c.车辆在车场, 此时无需设立虚拟收集点.

3.3 数学模型

根据上述描述, 建立垃圾收运车辆干扰管理的数学模型.

目标函数:

(5)

约束条件:

(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13)
(14)
(15)
(16)
(17)

式中:mi表示生活垃圾收集点i的垃圾量; Qk表示车辆k的最大载重; CL表示干扰发生后新建立的收集点的集合; pkmax为车辆k限定的最大收运次数; CM表示虚拟收集点的集合, 且CMCL; [ETi, LTi]为收集点i的服务时间窗; n+1表示车场; NK表示车场可调用车辆数目.

式(6) 和式(7) 保证每个收集点只能被访问一次; 式(8) 对车次的载重进行限制; 式(9) 表示从车场出发和回到车场的车辆数目均为K; 式(10)~(12) 保证车辆从车场出发, 最终回到车场; 式(13) 保证虚拟点第一个得到服务; 式(14) 对车辆收集次数进行约束; 式(15) 为变量整数约束; 式(16) 为收集时间窗约束, 若车辆由收集点i驶向收集点j, 则收集点j的访问时间Tjk=Tik+tij+si, 其中tij为由i行驶至j的时间, si为收集点i的收集时间; 式(17) 表示可使用车辆数目约束.

4 求解算法设计

本节采用遗传算法思想, 设计干扰恢复模型的求解算法, 具体包括:编码与解码设计、种群初始化、适应度函数和遗传操作.

4.1 染色体编码与解码

对于车辆路径问题, 遗传算法染色体的编码形式已有多种表示方法.为了提高算法的效率, 本文在初始最优路径的基础上采用垃圾收集点插入到车辆路径中的方式以更好地得到干扰调度方案.其中, 垃圾收集点用自然数1, 2, 3, …, n表示, 车场、中转站分别用自然数n+1, n+2表示.

初始最优路径:首先, 采用基于垃圾收集点的自然数编码机制, 根据收集点的数目随机生成种群规模为Popsize, 长度为n的初始染色体; 其次, 经过进化N代, 多次实验, 得到最优染色体; 最后采用马慧民等[13]的染色体解码方式, 将最优染色体Rbest根据容量约束得到Rsub, 并将车场和中转站信息加入染色体中, 使之形成完整的收运路径.

干扰管理染色体编码:采用基于车辆收运路径的自然数编码机制, 根据干扰发生时未被服务的收集点数目Num (CL), 随机生成长度为Num (CL), 最大值为pmaxK的初始染色体R.

干扰管理染色体解码:首先将未被服务的垃圾收集点从最优路径Rsub中剔除, 得到Rdissub.其次根据染色体R将未被服务的收集点依次加入到Rdissub中, 如pmax=3, CL=[3 8 7], Rdis=[1 3 5], 则表示将垃圾收集点3插入车辆1的第1次收运中, 垃圾收集点8插入车辆1的第3次收运中, 垃圾收集点7插入车辆2的第2次收运路线中.最后根据车辆的最大收运次数重组染色体, 加入车场和中转站信息, 使之形成完整干扰管理调度方案.

4.2 种群初始化

首先随机生成一个种群规模为Popsize的初始种群.其次为加快寻优速度, 且保证种群的多样性, 本文根据Rsub得出其干扰管理模型的染色体R0, 并将初始种群的1/5替换为R0.

4.3 适应度函数

为保证算法在可行解空间里进行寻优, 建立容量约束惩罚函数及时间约束惩罚函数:

式中:Tpk为车辆kp次收运所消耗的时间; M为无穷大正数.

本文目标函数为最小化问题, 故建立适应度函数:1/(R(k)+Q(k)+P(k)+C(x)+Cl(k)+Ct(k)).

4.4 遗传操作

选择:选择算子的作用是提高种群的平均适应值, 本文采用轮盘赌法与精英个体保留策略相结合的方式.

交叉变异:本文采用文献[14-15]中的自适应的交叉变异算子, 其概率不是固定的0到1的某一值, 而是由每一代种群中最优个体的适应值与其他个体的差额关系所决定的, 交叉概率pc=1/(1+ek(fmin-f)), 变异概率pm=1-1/ek(fmin-f).式中:fmin表示种群中个体最小的适应值; f表示适应值小于平均适应值的所有个体的平均值.

5 实例分析 5.1 具体问题描述

本文以上海市某地区为例, 该地区共有106个生活垃圾收集点, 一个车场, 一个中转站.其中, 生活垃圾收集点编号为自然数1~106, 车场编号为107, 中转站编号为108.实地测得各收集点、车场以及中转站的地理坐标, 采用百度地图开放平台中的Route Matrix API v2.0 Beta测得各收集点之间驾驶模式下的最短距离.该地区生活垃圾收运车辆为单车型, 车辆平均行驶速度为45 km/h, 最大载重为5 t, 垃圾每桶装载耗时30 s, 车辆每日的收运次数不超过3次, 工人工作时间窗为早上6:00至9:30, 本文将时间窗简化为[0, 3.5].该地区生活垃圾收集点垃圾量信息如表 1所示.


表 1 上海市某地区垃圾收集点垃圾量信息 Table 1 Garbage amount information at garbage collection points in one region of Shanghai
5.2 初始最优路线参数设置

为验证模型和算法的可行性, 将算法通过Matlab语言实现, 得出最优调度方案如表 2和下页表 3所示.遗传算法的参数设置如下:种群规模为500, 进化代数为200, 选择概率为0.1, 自适应算子的概率参数为0.002 5.为了保证最优调度方案的合理性, 本文将第i次实验的前10条染色体替换为第i-1次实验的最优染色体, 进行多次实验, 直至实验结果趋于稳定.



表 2 初始最优路线 Table 2 Initial optimal route

表 3 初始最优车辆运输距离及运输垃圾量 Table 3 Initial optimal transport distance and transported garbage amount
5.3 干扰管理优化结果

a. 虚拟收集点.

假设车辆9行驶至垃圾收集点12处时发现该处垃圾量由417.68 kg增加到2 332.00 kg, Δq12=1 914.32 kg, 装载桶数目由原来的15桶变为55桶.由表 3可知, 车辆9第1次收运完成时, 车辆剩余可用容量c1, 90=112.14 kg, 根据剩余可用容量c1, 90 < Δq12可以判定, 此时干扰事件对垃圾收运系统产生扰动, 干扰时刻为0.24.根据本文定义的虚拟收集点, 可以得到干扰发生时刻, 虚拟收集点集合为[58, 60, 8, 100, 98, 55, 105, 27, 12, 53], 已访问的收集点集合为[36, 14, 23, 31, 59, 39, 22].

b. 参数确定.

本文根据实例, 对干扰管理模型目标函数中收运路线偏离与收运总距离偏离惩罚参数之间的关系进行研究, 并确定路线偏离惩罚参数的合理取值范围, 以便于根据不同的实际应用条件灵活取值.

路线偏离的惩罚参数与收运总距离偏离惩罚参数的比值越大, 则表明越注重路线对系统的扰动, 比值越小则表明越注重收运成本对系统的扰动.设路线偏离数目为x, 收运总距离偏离为y, 求解出仅考虑路线偏离时(α+=1, α-=1, c2=1/+∞)的路线偏离数目x1和收运总距离偏离y1.此时方案中x1为最小值, 即x1=xmin, 同时在有效解的范围内, y1为最大值, 即y1=ymax.同理求解出仅考虑收运总距离偏离时(α+=1/+∞, α-=1/+∞, c2=1) 的路线偏离数目x2和收运总距离偏离y2.此时方案中y2为最小值, 即y2=ymin, 同时在有效解的范围内, x2为最大值, 即x2=xmax.

设路线偏离的惩罚参数与收运总距离偏离的惩罚参数的比为β, 路线偏离数目可能的最小值为m, 收运总距离偏离可能的最小值为n.在生活垃圾收运系统干扰管理研究中m=1, n为收运总距离保留的有效位数, β的合理取值范围是[n/(xmax-xmin), (ymax-ymin)/m].

c. 仿真结果.

对本文实例进行求解得xmin=6, ymax=10.5, xmax=14, ymin=4.4, m=1, 收运距离保留一位有效数字, 故n=0.1.因此, β的合理取值范围为[0.125, 6.1].为验证β取值范围的合理性, 本文设定c2=1, 分别选取β为5 000, 100, 50, 10, 5, 2, 1, 0.5, 0.2, 0.1, 0.05, 0共12组数据进行研究, 以变量β为横坐标, 以偏离量为纵坐标, 得到如图 1所示的仿真结果.结果表明, 最优解分别在β取5, 2, 0.2, 0.1, 0.05处发生变化, 且这些取值均在[0.012 5, 6.1]范围内.其中β=0即为重调度方案, 此方案中路线偏离数目为14条, 收运总距离偏离为323.92 km.


图 1 不同惩罚参数下路线偏离与收运总距离偏离的变化 Fig. 1 Change of route deviation and the total distance deviation under different penalty parameters

由求解结果可知当β为5 000, 100, 50, 10, 5, 2, 1, 0.5, 0.2时, 应采取车辆自救策略, 当β为0.1, 0.05, 0时应采取邻近救援策略.根据该地区垃圾收运系统的特点, 干扰管理模型中参数设置如下:α+=1, α-=1, μ=10, λ=0.5, c1=100, c2=1.运用本文所建数学模型对扰动进行恢复, 得到仿真结果, 此时受扰车辆9应采取车辆自救策略, 车辆9收运总距离为39.49 km, 路线偏离数目为8条, 其余车辆按照原计划对垃圾收集点进行服务.受扰车辆干扰管理结果如表 4所示.


表 4 干扰管理方案 Table 4 Disruption management plan

表 4可知, 车辆9较原计划增加1次收运次数, 原计划收运路线由12-13-24-30-79-89-108-20-70-50-108-107变为12-20-108-13-24-30-79-89-70-108-50-108-107, 偏离的路线rk-有12-13, 89-108, 20-70, 70-50, rk+有12-20, 108-13, 89-70, 70-108.

为验证本文所建模型的优越性, 选择以收运总距离最小化为目标进行全局优化调整的重调度方法.干扰管理优化结果与重新调度结果对比如表 5所示.干扰管理方案和重调度方案中总成本为路线偏离、收运载重偏离、收运次数偏离以及收运距离与其相应的惩罚参数的乘积之和.


表 5 干扰管理优化结果与重调度结果对比 Table 5 Comparison of disruption management optimizing results with rescheduling results

干扰管理优化结果在路线偏离、收运载重偏离、收运次数偏离以及收运距离上相对于重调度结果, 优化节省分别为43%, 1.8%, 0%, -0.15%.虽然在收运距离上干扰管理优化结果略低于重调度结果, 但在路线偏离和收运载重偏离上干扰管理结果明显优于重调度.综上所述, 在解决生活垃圾车辆调度问题上, 干扰管理模型效果显著.经过干扰管理优化, 即最大程度降低干扰事件对系统的扰动, 又兼顾成本最小的目标, 得到了有效的新方案.

6 结束语

本文针对生活垃圾收运系统中收集点垃圾量变化干扰事件进行研究.根据收运系统的特点, 设计相应的扰动辨识和扰动度量, 建立了相应的干扰恢复模型.设计了基于车辆收运路径的自然数编码机制.最后通过实例仿真实验并与重调度方法进行比较, 验证干扰管理模型和遗传算法的有效性, 并确定路线偏离惩罚参数的合理取值范围, 以便于根据不同的实际应用条件灵活取值, 为解决生活垃圾收运干扰管理中面对的现实问题进行了有益的探索.

参考文献
[1] YU G, QI X T. Disruption management:framework, models and applications[M]. Singapore, River Edge, NJ: World Scientific Publishing Co.Pte.Ltd, 2004.
[2] CLAUSEN J, HANSEN J, LARSEN J. Disruption management operations research between planning and execution[J]. OR/MS, 2001, 28(5): 40–43.
[3] YU G, ARGVELLO M, SONG M, et al. A new era for crew recovery at continental airlines[J]. Interfaces, 2003, 33(1): 5–22. DOI:10.1287/inte.33.1.5.12720
[4] 王杜娟, 王建军, 刘春来, 等. 具有恶化效应的新工件到达生产调度干扰管理[J]. 系统工程理论与实践, 2015, 35(2): 368–380. DOI:10.12011/1000-6788(2015)2-368
[5] QI X T, BARD J F, YU G. Supply chain coordination with demand disruptions[J]. Omega, 2004, 32(4): 301–312. DOI:10.1016/j.omega.2003.12.002
[6] ZHU G, BARD J F, YU G. Disruption management for resource-constrained project scheduling[J]. Journal of the Operational Research Society, 2005, 56(4): 365–381. DOI:10.1057/palgrave.jors.2601860
[7] 潘逢山, 叶春明, 姚远远. 基于混沌粒子群算法的项目调度干扰问题研究[J]. 计算机应用研究, 2013, 30(9): 2648–2655.
[8] 胡祥培, 孙丽君, 王雅楠. 物流配送系统干扰管理模型研究[J]. 管理科学学报, 2011, 14(1): 50–60.
[9] 王旭坪, 许传磊, 胡祥培. 有顾客时间窗和发货量变化的车辆调度干扰管理研究[J]. 管理科学, 2008, 21(5): 111–120.
[10] 王旭坪, 杨德礼, 许传磊. 有顾客需求变动的车辆调度干扰管理研究[J]. 运筹与管理, 2009, 18(4): 16–24.
[11] 丁秋雷. 客户时间窗变化的物流配送干扰管理模型——基于行为的视角[J]. 中国管理科学, 2015, 23(5): 89–97.
[12] 阮俊虎, 王旭坪. 中转点变化的应急医疗物资联合运送干扰管理研究[J]. 运筹与管理, 2016, 25(4): 114–124.
[13] 马慧民, 罗长见. 城市生活垃圾收运车辆调度干扰管理研究[J]. 工业工程, 2015, 18(3): 92–97.
[14] 刘帆. 基于遗传算法的应急物流车辆路径问题研究[D]. 西安: 西安科技大学, 2012. http://cdmd.cnki.com.cn/Article/CDMD-10704-1012044675.htm
[15] 李欣. 自适应遗传算法的改进与研究[D]. 南京: 南京信息工程大学, 2008. http://cdmd.cnki.com.cn/Article/CDMD-10300-2008092133.htm