多约束条件下城市道路环卫车优化配置与路径规划

聂庆慧，龙秀江，梁程，夏井新，欧吉顺*

(1.扬州大学，建筑科学与工程学院，江苏扬州 225127；2.东南大学，智能运输系统研究中心，南京 211189）

0 引言

随着城市化建设进程不断加快，传统人工作业方式已经难以满足日益增长的城市环卫需求。相较于人工作业，机械化作业具有更加安全和高效的优点，已经成为我国大中型城市的主流环卫作业方式。然而，针对机械化环卫车辆的配置与调度，大部分城市仍主要依赖于市政管理人员的主观经验，缺乏科学客观的规划与管理决策，从而造成车辆资源闲置或作业时行走路径非最优等突出问题。随着“智慧城市”试点工作的不断深化，环卫领域亦迎来了“智能化”革命。由此，研究如何对环卫车辆进行科学合理的配置与路径规划，使得“车尽其用和路径最优”，成为交通工程领域一项热点研究课题。

车辆配置与路径规划问题可以从数学角度建模为以节点为研究对象的车辆路径问题(Vehicle Routing Problem,VRP)[1]和以弧为研究对象的弧路径问题(Arc Routing Problem,ARP)[2]。本文研究的环卫车配置与路径规划问题属于ARP。标准的ARP可以表述为：某车队中的车辆从路网中某起始节点(交叉口或路网边界出入口)出发，对所有有服务需求的弧(路段)进行遍历作业1 次，对无服务需求的弧(路段)可以空驶通过多次，待所有作业完成后返回出发节点，最终建模目标是为所有指派车辆分配能够满足路网作业需求且成本最小或利益最大的行驶路径。ARP在环卫领域有着广泛应用，包括：道路维护[3]、冬季道路除雪[4]及城市垃圾回收[5]等。尽管如此，现实中大多数应用问题由于作业任务的复杂性以及存在诸多现实约束条件，通常难以用标准的ARP 进行描述。为此，一些学者针对考虑不同现实约束条件的扩展ARP 展开了深入研究。

HUANG等[6]构建了以周期性和中转补给为约束条件的城市道路洒水ARP，并设计基于蚁群算法的启发式求解策略，以在合理时间内获得一组近似最优解；CHEN 等[7]提出一种鲁棒优化方法解决道路日常维护时服务时间不确定性的ARP，并运用分支平面切割算法进行求解；RIQUELME等[8]研究了含周期性约束和车辆行驶速度约束的道路洒水ARP，并通过设计一种精确数学优化求解算法在小规模路网上获得了令人满意的车辆路径规划方案；MOFID 等[9]提出一种自适应搜索与鲸鱼优化相结合的算法搜寻城市固体垃圾收集的最佳路线；陈博晓等[10]综合考虑服务水平约束和养护车辆工作时长限制，建立养护服务区域规划模型，实现对养护区域作业时间的准确计算，为养护资源合理配置提供决策依据；考虑带时间窗的甩挂运输路径优化问题，边展等[11]建立了以行驶时间最短为目标的优化模型，并开发两阶段混合启发式算法求解最优车辆路径组合；JIN 等[12]研究带枢纽港靠泊时间选择约束的船舶路线规划与转运协调问题，并设计了分支定价精确式和列生成启发式两类算法对其进行求解。

综上，国内外学者从不同工程应用角度探索了带各类现实约束条件的ARP[13]。本文涉及的环卫车优化配置与路径规划问题属于带以下现实约束条件的ARP，包括：①作业时限约束，即对于每一作业路段要求车辆在给定时段内完成作业任务；②不同道路功能等级下的服务次数约束，即要求车辆在不同功能等级路段上完成特定次数的作业任务(不同于仅需在给定路段上完成1次作业的标准ARP，本文的ARP 在部分路段上需要完成多次作业)；③车辆行驶速度约束，即需要考虑作业和非作业两类情形下的速度限制；④路网流量平衡约束，即驶入某节点的车辆总数应该等于驶出该节点的车辆总数；⑤车辆退出约束，即车辆可以在用户指定的路网中任一节点自由退出(包括起始节点)。本文ARP 的优化目标是使车辆配置成本与车辆出行成本最小。由以上描述可知，该ARP 属于典型的非确定多项式时间难题(Non-deterministic Polynomial-time Hardness,NP-hard)，具有较高的模型求解复杂度。考虑到实际工程应用主要以节约环卫运营成本为首要考量因素，且所设计的环卫车调度方案允许以离线方式生成，而分支定价算法通过分支定界和列生成策略能够显著降低求解问题的复杂度，本文基于分支定价算法优化求解所构建的模型。利用苏州工业园区19个真实区域路网综合评估所提出的方法，并从经济成本、作业效率和环保效益这3 方面验证所提方法的可行性和有效性。

1 问题描述与解决思路

本文模型构建过程中涉及的数学变量符号含义说明如表1所示。

表1 本文模型构建过程中涉及的数学变量符号含义说明Table 1 Description of mathematical symbols associated with model development in this study

本文环卫车优化配置与路径规划问题描述为：给定城市道路网络拓扑G=(L,I)，其中，L为路段(弧)集合，I为交叉口(节点)集合，L=L′⋃L″，其中，L′为作业路段集合，L″为非作业路段集合。对于给定任务的b辆环卫车，规划其行驶路径，使车辆从路网内给定节点出发，遍历所有作业路段L′完成作业任务，然后经由用户指定的路网中的任意节点退出。建模优化目标是使环卫运营成本最低。本文的环卫运营成本包括车辆配置成本和车辆出行成本。车辆配置成本由车辆固有成本和配置车辆数目决定，车辆出行成本通过车辆在路网上的行驶时间进行量化评估。考虑的约束条件包括：①作业时限约束；②不同道路功能等级下服务次数约束；③车辆行驶速度约束；④路网流量平衡约束；⑤车辆退出约束。考虑到城市道路环卫作业在工作时通常会避开早晚高峰时段，本文在建模时忽略了高峰期不稳定交通状况对环卫车作业的影响。路网中道路功能等级与其需求服务次数紧密相关，以保洁和清洗作业任务为例，路网中含有中央分隔带和机非隔离带的单向路段需作业2次，不含中央隔离带的单向支路路段仅需作业1次。此外，在标准ARP中，车辆完成作业后通常会返回开始节点，而在本文所要解决的ARP 中，车辆需要根据用户要求从路网中任一指定节点自由退出(包括起始节点)，这在增加工程应用灵活性的同时，也为建模带来了挑战性。根据上述需求分析，给出的解决思路如图1所示。

图1 城市道路环卫车优化配置与路径规划问题的解决思路Fig.1 Solutions to problem of optimal allocation and routing of sanitation vehicles on urban roads

2 城市道路环卫车优化配置与路径规划建模

2.1 时空网络建模

本文研究的ARP 需要实现在多个现实约束下运营成本最小，其中，配置成本由调度的车辆数量决定，出行成本由车辆在路网上的行驶时间决定。行驶时间通过路段长度与车辆在该路段上的平均行驶速度计算获得。环卫车的平均行驶速度分为作业模式下的平均行驶速度和非作业模式下的平均行驶速度，其中，前者由环卫机械化作业标准确定，后者设置为对应功能等级的道路限速。

为方便描述车辆在路网上的时空行驶轨迹，将道路物理网络拓展为时空网络。具体而言，将交叉口节点i扩展为时空点(i,j)，将路段(i,j)扩展为时空弧(i,j,t,s)，表示车辆由t时刻进入路段(i,j)，并在s时刻驶出，s-t为路段行驶时间。通过构建时空网络，将原始问题转化为带路段服务次数约束的网络流问题。

为保证起始节点和终点节点流量守恒，本文构建1 个虚拟起始时空节点和1 个终点时空节点，即所有车辆均由虚拟出发节点驶出，并在虚拟退出节点结束作业。由此，路网上所有起始时空节点和终点时空节点均为满足流量守恒的普通节点，从而简化了建模复杂度。同时，上述设置也可以保证环卫车可由路网任一节点进入或退出。

环卫车在实际行驶过程中包括两种模式，即作业模式和非作业模式。为完整描述车辆行驶轨迹，并保证车辆在时空网络上的流量守恒，分别构建作业时空弧A′和非作业时空弧A″。对于作业时空弧(i,j,t,s) ∈A′，s-t为车辆处于作业模式下通过路段(i,j)所需时间；对于非作业时空弧(i,j,t,s)∈A″，s-t为车辆处于非作业模式下通过路段(i,j)所需时间。

假设1个含3个节点的示例物理网络及其拓展的时空网络。节点1到节点2的作业时间为1个时间单位，节点2 到节点3 的作业时间为2 个时间单位。环卫车从节点1到节点2的允许作业时间范围为[2,4]。在规定时间范围内完成作业的时空弧表示为有效时空弧；否则，表示为无效时空弧。等待弧表示环卫车到达作业路段的时间早于路段服务最早时间的情形。在构建时空网络时，通过删除处于规定作业时间范围外的无效时空弧有效刻画环卫车在作业路段上的作业时限约束。物理网络及其拓展的时空描述示例如图2所示。

图2 物理网络及其拓展时空网络描述示例Fig.2 Description example of physical network and its corresponding time-space network

1 辆车的时空行驶轨迹描述示例如图3所示，加粗实线表示车辆处于作业模式下的行驶路段，虚线表示车辆处于非作业模式下的行驶路段。车辆由0 时刻从起始节点1 出发，经过3 个时间单位作业至节点2，然后，经过6个时间单位作业至节点3，之后，按照非作业速度行驶2 个时间单位至节点5，最后，经过4 个时间单位作业至节点6 完成环卫作业任务。上述车辆时空行驶轨迹可以描述为(1,2,0,3)→(2,3,3,9)→(3,5,9,11)→(5,6,11,15)。

图3 车辆时空行驶轨迹描述示例Fig.3 Description example of a vehicle spatiotemporal travel trajectory

2.2 优化模型构建

令O为所有车辆的虚拟出发节点，并建立非作业时空弧(O,j,0,0)∈A″与路网时空节点(j,0)相连。需要注意的是，时空弧(O,j,0,0)表示由0 时刻从虚拟节点O出发，并在0 时刻到达节点j，该建模方式用以描述车辆可由路网任一节点开始作业。定义D为所有车辆的虚拟退出节点，并建立作业时空弧(i,D,t,t)∈A′与路网时空节点(i,t)相连，用以描述车辆可在任意时刻由路网任一节点结束作业。城市道路环卫车辆配置及路径优化模型建立如下。

目标函数为

流量平衡约束为

服务约束为

决策变量为

式(1)由两部分组成，其中，第1 部分表示环卫车辆的配置成本(固定使用成本)，第2 部分表示所有环卫车完成作业任务的总行驶时间；式(2)为路网流量守恒约束，对于非虚拟节点O和D路网中的其他时空节点需保持流量守恒，即进出任意一时空节点的车辆数相等；式(3)表示从虚拟节点O驶出的所有车辆数量应该和最后从虚拟节点D退出的车辆数量保持一致；式(4)保证了对于所有需要服务路段(i,j)∈L′，满足车辆在作业模式下驶过该路段的次数大于等于最少作业服务次数。

在目标函数中，当yO,j,0,0=1时，表示有1辆车从虚拟节点O驶出进入节点j开始作业，对所有的yO,j,0,0求和，可得到进行环卫作业的总车辆数。上述环卫车辆最优配置与路径规划问题本质上属于双目标规划问题，可构建双层规划模型进行求解。然而，考虑到双层规划问题求解复杂度较高，本文通过线性加权法将第1部分的目标函数乘以1个大常数M，让模型在车辆数最少的情形下有效优化目标函数中第2 部分的目标函数，将双目标规划问题转化为单目标规划问题，有效简化建模复杂度。

3 求解算法设计

考虑到实际应用中主要以节约环卫运营成本为首要考量因素，且分支定价算法是一种适用于大规模问题的精确式求解算法，本文基于分支定价算法求解模型。该算法的基本思想是通过设计列生成算法与分支定界算法求解整数规划问题的松弛问题。首先，基于Dantzing-Wolfe分解技术(D-W分解技术)将原始问题的数学模型分解为环卫车运营总成本最小的主问题和含有多条件约束最短路径的子问题；其次，利用列生成算法求解主问题的松弛问题，求得的初始解生成部分可行列，形成受限主问题(Restricted Master Problem，RMP)；然后，求解RMP 得到对偶变量，再将其带入子问题中重新定价，通过求解子问题检验数小于0 的列添加到RMP 中再次迭代，直到求得最优整数解。分支定价算法的主要工作流程如图4所示。

图4 分支定价算法的主要工作流程Fig.4 Main workflow of branch-and-price algorithm

3.1 Dantzing-Wolfe分解

考虑到本文ARP 模型的变量和约束条件数量较多，利用Dantzig-Wolfe 分解算法提升求解速度，基本思想是将原始问题分解为若干个规模较小的子问题，通过求解子问题进而得到原问题的最优解。为获得高质量的线性规划问题松弛值，设计路径决策变量构建模型，并对其进行Dantizg-Wolfe分解。假定所有满足约束条件的可行路径集为R，即R为环卫车从虚拟节点出发，完成作业任务后生成的所有可行路径集合，则所求解的问题可转化为从R中选择若干条路径组成1 个可行解，使模型的目标函数值最小。

3.1.1 主问题建模

模型分解过程涉及的参数变量定义如表2所示。令ci,j,t,s=croad·di,j,t,s，则车辆在路径r上的总成本cr为

表2 模型分解过程涉及的符号说明Tabel 2 Symbol description associated with model decomposition

通过上述定义，构建主问题模型如下。

目标函数为

服务约束为

决策变量为

式(7)为目标函数；式(8)表示车辆在作业模式下驶过该路段的次数大于等于其最少服务次数。由于无法枚举主问题模型的所有可行路径，需要利用列生成算法迭代的过程转化为求解主问题的松弛问题。

3.1.2 子问题建模

依据上述主问题的松弛问题得到其对偶模型为

设zi,j,t,s为对偶问题最优解，则主问题对偶模型检验数为

子问题模型可构建为

式(14)中，子问题目标函数与检验数表达式相同，本质是尽可能寻找使得检验数小于0 的列，并将该列带入到主模型中迭代，优化当前最优解。在初始状态下，主问题需要通过初始解求得对偶值，对子问题进行定价。然后，将子问题求得的路径集作为新的列加入到原始路径集中，并对主问题求解，得到新的解zi,j,t,s，对子问题重新定价，并继续寻找有效路径集合。通过不断迭代，直至无法找到有效路径为止。上述过程描述如下：

Step 1 初始化主问题，生成主问题所需的初始路径集合R。

Step 2 求解主问题，得到子问题模型所需的解zi,j,t,s，并重新定价。

Step 3 求解子问题，搜索满足条件的最短路径集合。

Step 4 若集合为非空集，则将集合中所有的路径加入到R中，并且在主问题模型中生成对应新的列，转Step2；否则，转Step5。

Step 5 用分支策略求解主问题的整数解。

3.2 分支策略设计

由上述描述可知，从包含部分列的主问题出发，求得使子问题目标函数值(对偶模型的检验数)小于0 的解，并将其作为新列带入主问题求解过程，可为主问题的松弛问题提供更近的下界。当子问题的目标函数无法产生小于0的解时，可以获得主问题线性松弛问题的最优解。在此基础上，利用基于弧的分支策略求得最优整数解。

本文设计的基于弧的分支策略为：首先，将基于路径的浮点数解转化为与其对应弧的浮点数值。当存在浮点数解时，可以找到两条路径r1和r2，满足路径r1经过弧(i,j)访问j点，路经r2经过弧(m,j)访问j点(i≠m)；然后，对弧的浮点数值取整，优先选择值改变较大的弧。假设选择弧(i,j)，则存在两个分支，即最优解中是否包含该弧。当最优解中存在弧(i,j)时，将其他所有到达j点的弧的成本和其他所有离开i点的弧的成本设为足够大的值，并重新计算；反之，只需设弧(i,j)的成本为足够大的值，并且在已有的路径集中删除包含弧(i,j)的路径，再重新计算。具体步骤如下：

Step 1 初始化主问题分支定界树的根节点，生成初始路径集合R。

Step 2 通过初始解得到部分可行列集合，从而构建RMP。

Step 3 求解RMP，传递对偶变量，重新定价子问题。

Step 4 判断检验数-dr是否小于0，若小于0，将小于0的检验树对应的列加入RMP中，并转Step 3；否则，转Step 5。

Step 5 求解主问题模型，若解为整数解，则转Step 6；否则，转Step 7。

Step 6 与当前的上界进行比较，若小于上界，则更新上界值，并且根据新的上界值，对分支定界树进行剪支，转Step 8。

Step 7 若浮点数解小于当前的上界，则根据上述分支策略选择1 条弧进行分支，删除当前节点，将分支节点加入路径集合中；否则，无需进行分支操作。

Step 8 若路径集合为非空集合，则转Step 2；否则，转Step 9。

Step 9 当前上界的值即为最优整数解。

4 实验结果与分析

本文以苏州工业园区19个真实道路网络的环卫车优化配置与路径规划问题为例，评估所提出的方法。依据路段数量和节点数量将19个路网划分为中小规模路网和大规模路网。19 个实例路网的车辆作业任务特征描述如表3所示。其中，路段数小于70 且节点数小于50 的为中小规模路网，共10个，在表中标记为S1～S10；路段数大于70且节点数大于50 的为大规模路网，共9 个，在表中标记为L1～L9。

表3 待评估路网的作业任务特征Tabel 3 Task characteristics of evaluated road networks

4.1 路网拓扑构建

为提取道路网络拓扑，首先，从OpenStreetMap网站下载苏州工业园区城市路网地理信息数据文件；然后，对数据文件进行解析、信息提取和预处理，生成结构化的路网节点和路段关联数据；最后，基于QGIS(Quantum Geographic Information System，QGIS)软件对生成的路网节点和路段数据进行路网拓扑构建与可视化。根据苏州市市政管理要求和环卫作业任务，从苏州工业园区路网提取19 个相互独立的环卫作业路网为本文研究路网。19个环卫作业路网的道路网络拓扑如图5所示。

图5 苏州工业园区19个环卫作业路网拓扑Fig.5 Network topologies of 19 local area networks in Suzhou Industrial Park

4.2 实验结果分析

4.2.1 评估指标

本文从经济成本、作业效率和环保效益这3个方面评估所提出方法的可行性和有效性。其中，经济成本用运营成本指标进行评估；作业效率用车辆路径有效率指标进行评估；环保效益用环卫车作业过程中产生的碳排放量指标进行评估。

(1)运营成本

在运营成本中，车辆配置成本计算为所有环卫车的采购成本，车辆出行成本计算为所有环卫车在路网上行驶的总公里数与每公里作业单价乘积的累计总和。令路网环卫作业运营总成本为C，定义为

式中：B为路网上配置的环卫车的总数量；cveh为环卫车的采购成本；为路网上第b辆环卫车行驶通过的第k条路段的长度。

(2)车辆路径有效率

路径有效率E定义为配置的所有环卫车在路网作业状态下的行驶总里程L1与其完成指定作业任务所需的总行驶里程L2的比值，计算式为

式中：为路网上第b辆环卫车在作业模式下，第k条路段的长度。路径有效率E越接近100%，表明路网上环卫车的作业效率越高，相应的路径规划也更合理。

(3)车辆碳排放量

车辆燃油能耗与其碳排放具有紧密关联关系。首先，利用BARTH 等[16]提出的综合排放模型测算所配置环卫车的能耗；然后，基于燃油能耗与碳排放转换关系估算路网上配置的环卫车的总碳排放量。计算过程为

式中：为环卫车在作业模式下的平均行驶速度；为环卫车在非作业模式下的平均行驶速度；为路网上第b辆环卫车在非作业模式下的第k条路段的长度；ξ为燃料和空气的质量比值；κ为柴油燃料热值；ψ为能源从g·s-1到L·s-1的转化因子；ω为环卫车发动机的摩擦系数；α为环卫车发动机转速；φ为环卫车的排量；η′为车辆转动系统效率；η为柴油发动机效率参数；β为空气的阻力系数；γ为车辆前方表面积；ρ为空气密度；为路网上第b辆环卫车在作业模式下的第k条路段上的燃油能耗量；为路网上第b辆环卫车在非作业模式下的第k条路段上的燃油能耗量；δ为燃料对应的排放因子；Q为路网上环卫车完成作业任务的碳排总量。本文ξ、κ、ψ、ω、α、φ、η′、η、β、γ和ρ这11 个参数依据文献[17]提供的柴油环卫车动力系数表进行取值，δ的设置则参考文献[18]提供的IPCC2006修订标准，取值为2.73 CO2kg·L-1。

4.2.2 算例分析

本文车辆配置数量B是3 个评估指标的关键参数。19 个实例路网优化前后的配置车辆数量对比结果如表4所示。

表4 车辆配置数量优化前后对比结果Tabel 4 Comparison results of number of allocated vehicles before and after optimization

由表4可知，对于中小规模路网而言，优化后车辆配置数量平均下降31.95%，尤其是在路网S3、S5 和S6 上优化效果较为显著，分别下降50.00%、36.36%和45.45%；对于大规模路网而言，优化后的车辆配置数量平均下降19.61%，在路网L7 上优化效果最为显著，下降了27.27%。由对比分析可知，所提出方法相较人工经验配置方法具有显著优势。

(1)营运成本优化对比分析

本文中，保洁车、洒水车和清洗车的采购单价分别设置为18 万，15 万，25 万元·辆-1，平均行驶单价分别设置为18.7，23.43，39.37 元·km-1。19 个实例路网的运营成本优化前后对比结果如图6所示。

图6 不同路网上环卫车运营成本优化前后对比结果Fig.6 Comparison results of operation cost of sanitation vehicles on different road networks before and after optimization

由图6中可知，优化后各个路网的配置成本和出行成本均显著下降。对于中小规模路网而言，优化后的总运营成本下降约871万元，尤其是在路网S2、S8和S9上，对应的运营成本分别下降18.20%、21.43%和19.77%；对于大规模路网而言，其总运营成本下降约854万元，下降比例较为显著的两个路网为L3和L7，分别下降了20.28%和18.87%。由对比结果可知，所提出的方法能够显著节约运营成本，产生显著的经济效益。

(2)车辆路径有效率优化对比分析

由式(18)可知，路径有效率E值越接近100%，规划路径中车辆行驶的非作业里程数越少，环卫车路径有效利用率越高。10 个中小规模实例路网上优化后的车辆路径有效率如表5所示。

表5 中小规模实例路网上优化后的车辆路径有效率Tabel 5 Routing efficiency of sanitation vehicles on medium-size road networks after optimization

由表5可知，中小规模路网上，优化后车辆的平均路径有效率可以达到97.40%。10个路网中有6 个路网在优化后车辆路径有效率达到了99%以上，其中，路网S3、S4和S6甚至可以达到100%。

9个大规模实例路网上优化后的车辆路径有效率如表6所示。

表6 大规模实例路网下车辆路径有效率Tabel 6 Routing efficiency of sanitation vehicles on large-size networks after optimization

由表6可知，该规模路网上的平均车辆路径有效率达到91.89%，其中，有7 个路网的路径有效率到达90%以上，最高路径有效率达到98%。对比结果表明，所提出方法能够有效避免路段重复作业问题，有效提升环卫车的作业效率。随着路网规模不断增加，路径有效率有所下滑，但其平均路径有效率仍高于90%，表明所提出方法在不同规模路网上均具有较好的适用性。

(3)碳排放优化对比分析

从环保效益角度对所提出方法进行评估分析。优化前后的碳排放对比结果如图7所示。

由图7可知，在中小规模路网上，优化后的平均碳排放量下降了19.07%，其中，以S2、S7 和S10碳排放量下降效果最为显著，分别下降了26.21%、21.04%和24.00%；在大规模路网上，优化后平均碳排放量下降了21.47%，在路网L2、L4、L6和L7上碳排放量分别下降了23.68%、23.28%、23.09%和24.39%。综合而言，无论是中小规模路网，还是大规模路网，优化后碳排放量都有较为显著的下降，表明，所提出方法能够显著降低环卫车辆尾气排放量，产生有效的城市环保效益。

4.3 车辆规划路径可视化

所构建的优化模型可与GIS相结合，用于辅助开发城市道路环卫车智慧调度系统。以实例路网L9为例，模型输出的环卫车最优规划路径在GIS上的可视化表征如图8所示。

图8 路网L9上环卫车最优路径规划GIS表征Fig.8 GIS representations of optimal routing paths of sanitation vehicles on road network L9

结合路径可视化结果，市政管理人员可通过自定义环卫车在作业路网中的进入节点和退出节点，实现对环卫车辆的科学快速调度，有效提升环卫运营与管理效益。

5 结论

本文通过综合考虑环卫车作业时限、服务次数、行驶速度和车辆退出节点等多约束条件，构建了以车辆配置与出行总成本最小为优化目标的环卫车优化配置与路径规划模型，并基于分支定价算法精确求解所构建模型。从经济成本、作业效率和环保效益这3 方面综合评估所提出方法。结果表明，同人工经验方法相比，所提出的方法在中小规模路网上，环卫车配置数量下降31.95%，总运营成本下降约871 万元，平均车辆路径有效率达到97.40%，碳排放量降低19.07%；在大规模路网上，环卫车配置数量下降19.61%，总运营成本下降约854 万元，平均车辆路径有效率达到91.89%，碳排放量降低21.47%。

尽管所提出方法考虑了多类现实约束条件，且能够被有效应用于保洁、洒水、清洗等多类城市道路环卫作业任务。然而，在现实应用中，环卫车辆的调度仍会受到其他一些复杂约束条件的影响，例如，车辆容量限制、动态交通环境及作业周期性排班等，使得建模与求解过程仍充满了挑战性。