兼顾成本与风险的渣土车运输路径优化模型

魏森，王永兴，杨绿明，毕军

（北京交通大学交通运输学院，北京 100044）

0 引言

近年来，城市建设过程中产生的建筑垃圾占城市固体废弃物的30%～40%，如何有效处理建筑垃圾已经成为各地政府及企业面临的难题[1]。在建筑垃圾的处理过程中，运输是整个流程的关键环节，其主要目标是通过渣土车将建筑垃圾从产生源运送至消纳场或资源场进行处理。当前的建筑垃圾运输流程首先需要运输单位向政府部门提交包括运输路径信息的申请核准单，经审批部门核实通过后方可执行运输任务。不同于常规车辆，渣土车在实际运输过程中时常伴有超载、超速及抛洒等现象，故政府部门以保障人民群众的生命和财产安全为重，在审核过程中更关注运输路径的安全性，而运输单位则是从经济性的角度出发更倾向于选择成本较低的路径。为此，在规划渣土车运输路径时需要兼顾政府部门和运输单位的需求，确保运输路径同时具备较好的安全性和经济性。

国内外关于建筑垃圾运输方面的研究主要侧重于运输过程监管，如Aleksanin[2]和White[3]分别从节约资源和保护环境的角度出发提出了针对建筑垃圾渣土车的管理策略；王瑾[4]以减少建筑垃圾运输过程中交通事故发生率为目标，设计了一种渣土车动态跟踪与管理系统；张学锋[5]和李宇宏等[6]分别借助无线通信和图像识别等技术建立建筑垃圾运输监管平台，以实现对渣土车的全过程智能化监管。有的学者是从路径优化方面展开研究，如Dantzig等[7]首次基于运筹学理论对车辆路径优化问题进行了深入探讨，随后Gillett等[8]和Schneider[9]进一步对车辆路径优化问题的复杂性进行了研究，分别设计了扫描算法和禁忌搜索算法实现模型求解；刘兰芬等[10]和柴获等[11]分别以运输风险和运输距离为优化目标建立单目标车辆路径优化模型；许冬明[12]进一步考虑实际运输需求，提出同时考虑运输时间和费用的多目标车辆路径优化模型；陈婷婷[13]将时间窗约束融入路径优化问题，建立了以运输距离和风险最小为目标的多目标优化模型。此外，为有效解决多目标优化问题，现有研究在遗传算法的基础上设计了NSGA-Ⅱ算法，并将其广泛应用于解决各类面向车辆路径的组合优化模型，如Liu等[14]和徐慧英等[15]将NSGA-Ⅱ算法应用于车辆路径多目标优化问题，得到权衡了多项优化目标的满意解；Miguel等[16]将NSGA-Ⅱ算法引入带时间窗的物流车辆路径优化问题，研究结果证实NSGA-Ⅱ算法能够有效处理实际场景规模下的多目标车辆路径优化模型。

截至目前，关于车辆路径优化问题的研究主要聚焦于通勤出行和物流配送等常规运输场景，还没有针对渣土车路径优化方面的成果，所提出的方法忽略了渣土车在运输环境和优化目标等方面的特殊性。为解决现阶段渣土车运输路径难以兼顾经济性和安全性的问题，本文在充分考虑建筑垃圾运输特征的基础上，拟提出同时考虑运输成本和风险的渣土车运输路径优化模型，将时间成本、固定成本，以及运输过程中产生的与渣土车流量、道路等级、单双车道相关的风险因素纳入模型的目标函数，并设计NSGA-Ⅱ算法对模型进行求解。最后通过山东省济宁市渣土车实时监测数据设计实例对模型和算法的可行性和有效性进行验证。

1 模型建立

渣土车的主要运输任务是将建筑垃圾从产生源运送至消纳场或资源场，故一般只有起点和终点，不考虑常规车辆路径问题中经常涉及的中途客户点。此外，建筑垃圾运输需要综合考虑运输单位和政府部门的需求，做到兼顾经济性和安全性。基于此，在充分考虑渣土车运输特点的基础上，本文将建立兼顾运输成本和风险的多目标0-1整数规划模型，旨在帮助相关企业和部门规划出能够同时降低运输成本和风险的渣土车运输路径。

1.1 基本假设

考虑渣土车运输的实际情况，对模型作出如下假设：

（1）渣土车的固定成本和时间成本已知。

（2）渣土车运输过程中无抛洒，行驶速度均在限速之下。

（3）从起点到终点过程中，各路段均符合建筑垃圾运输要求，渣土车可正常行驶，不会出现堵塞或无法通过等情况。

（4）路段风险值可叠加，路径的总风险值为各路段风险值之和。

（5）不同路径的相同路段渣土车流量和平均速度相同。

1.2 目标函数

本文模型兼顾运输成本和风险，其中运输成本包括固定行驶成本和时间成本；运输风险主要与所经路段的渣土车流量、道路等级以及单双车道指标有关。

（1）固定成本

渣土车运输过程中产生的固定成本主要包括车辆维护费和司机工资等基本费用，且单次运输的总固定成本受行驶距离的影响，具体计算公式如下：

式（1）中：C11为总运输固定成本（元）；c1为渣土车单位距离行驶成本（元/km），可以从研究区域内建筑垃圾运输单位提供的数据中获取；K为研究区域内的节点集合；i,j为节点，两个节点可构成一条路段ij；dij为路段ij的行驶距离（km），可以从当地城市管理局提供的数据中获取；xij为模型的0-1 决策变量，用以确定车辆是否经过路段ij，若经过则等于1，反之等于0。

（2）时间成本

时间成本主要体现为渣土车完成一次单程运输所消耗的时间。消纳场地点固定的情况下，每天运输的总次数越多，则运输单位盈利越多。每天运输的总次数主要与运输路径长度和平均速度有关。路径总运输时间成本按下式计算：

式（2）中：C12为总运输时间成本（元）；t为渣土车单位时间行驶成本（元/h），可以从研究区域内建筑垃圾运输单位提供的数据中获取；vij为车辆在路段ij的平均行驶速度（km/h），可以从当地城市管理局提供的数据中获取；其他变量含义同前。

（3）运输风险

建筑垃圾渣土车在执行任务时面临的运输风险受多方面因素的影响，其中渣土车流量、道路等级和单双车道是主要影响因素，因此模型中涉及的路段风险值主要考虑这3 个方面。渣土车庞大的体积使得渣土车流量成为建筑垃圾运输过程中造成交通事故的严重隐患，路段上的渣土车数量越多，安全风险就越大；渣土车在较为狭窄的道路上行驶时会增大交通事故发生风险，通常道路越宽阔、路面越平坦，渣土车的运行相对就越安全，而道路等级是反映道路状况的主要因素，道路等级越高则渣土车运输环境越安全；双向单车道由于允许不同车辆在同一条车道上相向而行，故会增加交通事故风险，而双向双车道可将不同方向行驶的车辆分配在不同车道，相对来说更加安全。需要说明的是，本文只考虑双向单双车道，而对单向单车道不作考虑，因为渣土车的行驶环境多以城市的双向车道为主。路段总风险值为渣土车流量、道路等级和单双车道三者风险值之和，计算公式为：

式（3）中：Rij为路段ij的风险值；R1ij为路段ij与渣土车流量相关的风险值；R2ij为路段ij与道路等级相关的风险值；R3ij为路段ij与单双车道相关的风险值。

上述3 项风险值可以先通过实测数据和层次分析法获得初始风险评估值，然后分别结合渣土车流量、道路等级和单双车道指标的百分制评价得分转化而来[17]。

（4）目标函数建立

基于上文提出的固定成本、时间成本和运输风险计算式，建立目标函数。首先，将固定成本和时间成本归为运输成本，以总运输成本最小为目标构建目标函数：

式（4）中：COD为起点到终点的总运输成本（元）；C11和C12的含义同前。

然后，定义路径总风险值为各路段风险值的加权平均，其中将各路段的行驶距离视为权重，建立以总风险值最小为目标的目标函数：

式（5）中：ROD为起点到终点的总运输风险值；其他参数和变量含义同前。

1.3 约束条件

结合建筑垃圾渣土车运输特点，模型考虑约束条件包括路段约束、时间窗约束、节点连续性约束和起终点约束，具体如式（6）～式（9）所示。各式中除新出现的变量外，其余参数和变量含义同前。

（1）路段约束

对于每条路段，要保证渣土车最多只能单程通过一次：

（2）时间窗约束

根据运输单位的要求，渣土车必须在规定的时间内完成运输任务，且只能提前不能延误：

式（7）中：T为渣土车运输时间限制（h）。

（3）节点连续性约束

渣土车在选择路段时需保证其连续性，即到达某节点后，必须从该节点出发前往下一节点，其中不包含起终点：

式（8）中：n为集合K中的节点总数；p为集合K中除起点和终点外的任意节点。

（4）起终点约束

通过构成路段节点之间的关系来判断节点是否为运输路径的起终点，主要判断依据为：若某节点为路径起点，则该点在构成路段时只能作为出发点；若某节点为路径终点，则该点在构成路段时只能作为到达点；若某节点不是路径的起终点，则该点在构成路段时既可以作为出发点也可以作为到达点。基于此，建立终点约束表达式如下：

2 求解算法设计

本文建立的渣土车运输路径优化模型是多目标0-1 整数规划模型且两个优化目标之间存在矛盾冲突，通常难以求得两者均为最优的解。一种有效解决此类问题的方法是同时对多个目标函数进行求解，得到Pareto 最优解集，其特点为优化其中一个目标函数时无法同时对其他所有目标函数优化[18]。NSGA-Ⅱ是一种基于遗传算法改进得到的启发式算法，同时也是一种用于解决多目标组合优化问题的有效算法，能够准确得到多目标优化问题的Pareto 最优解集，具有较好的求解性能[19]。本文将采用NSGA-Ⅱ算法对渣土车的双目标路径优化模型进行求解。针对渣土车路径优化模型，NSGA-Ⅱ的算法流程如图1所示。

根据图1，NSGA-Ⅱ算法流程具体如下：

步骤1：首先对生成的种群P0进行初始化，并设进化代数Gen=1；

步骤2：判断是否生成新一代子种群，若生成则令进化代数Gen=2，否则对当前种群中个体进行非支配分层排序，并依次通过选择、交叉和变异等遗传算子操作形成第一代子种群P1，并取进化代数Gen=2；

步骤3：将父代种群P0和生成的子代种群P1合并成新种群P2；

步骤4：对新种群P2中的个体进行快速非支配排序，并计算每个Pareto等级中的个体拥挤度，根据精英保留策略选择出优胜个体并组成下一代种群P3；

步骤5：对步骤4产生的新的进化种群P3再次经选择、交叉和变异操作产生新一代子种群，并判断是否达到算法收敛准则，如果达到则停止迭代，否则令Gen=Gen+1，回到步骤3，继续循环。

3 实例分析

3.1 实例数据

现基于山东省济宁市建筑垃圾管控实践进行实例分析。实验数据从城市建筑垃圾智慧监管平台获取，该平台可以通过车载终端设备对渣土车的实时位置及速度进行监控，并收集相关数据。本文选取济宁市的孟子大道、济邹路和崇文大道所在区域为研究对象，对渣土车运输路径进行规划。该区域为济宁市高新技术开发区，也是渣土车的重点活动区域。同时该区域道路网复杂，工业园区众多，还有不少学校与居民区，因此渣土车运输势必会给周边居民带来诸多影响，选定该区域为研究对象具有一定的现实意义。

为采用NSGA-Ⅱ算法实现模型求解，对各路段节点按自然数顺序编码，其中将运输起点路段节点编号设为1，终点为德源路与济邹路交叉口。编码所用地图采用中国行政区划地图，可显示区域内道路网信息，有利于对道路交叉口进行编码操作。由于起终点呈现出近似矩形对角线分布，因此仅在以起终点连线为对角线的矩形路网范围内进行编码。研究区域的完整路网结构如图2所示。

在图2 展示的实例研究区域中共包含56 个路段节点和90条路段，路段在图中以各节点之间的连线表示，根据连线的颜色区分道路等级，其中橙色（如路段16-17）、浅黄色（如路段16-19）、白色（如路段17-34）依次表示道路等级较高、居中、较低。部分路段长度信息如表1所示。

表1 实例研究区域内部分路段长度

由表1可知，在实例研究区域的所有路段中，最短路段长度为0.36km（路段13-14），而最长路段长度为3.6km（路段5-18）。由模型可知，路段长度直接关乎固定成本、时间成本和运输风险，因此是运输路径优化的关键指标之一。

实例研究区域内，部分路段的车辆平均速度如表2所示。

表2 实例研究区域内部分路段平均速度

城市交通路网的各路段行驶速度通常被限制在一定范围内，且不同路段间的行驶速度差异不大。由表2 可知，最小路段平均速度为30km/h（路段2-4），而最大路段平均速度为51km/h（路段41-42 和路段42-47）。由模型可知，路段行驶速度主要对时间成本有显著影响。

研究区域内，部分路段的渣土车流量风险值如表3所示。

表3 实例研究区域部分路段渣土车流量风险值

本文根据实际监测数据，将实例研究区域内路段的渣土车流量风险值设定在48～79之间。由模型可知，渣土车流量风险值是构成路段风险值的重要组成部分。

研究区域内，部分路段的道路等级风险值如表4所示。

表4 实例研究区域部分路段道路等级风险值

基于实际路网数据，本文根据路段的道路等级属性，将实例研究区域的道路等级风险值设为20,40及60。道路等级越高，相应的风险值越小。

研究区域内，部分路段的单双车道风险值如表5所示。

表5 实例研究区域部分路段单双车道风险值

基于实际路网数据，本文根据路段的单双车道属性，确定各路段的单双车道风险值分别为40和0。

此外，在运营成本参数方面，设单位里程产生的行驶成本c1=10元/km，单位时间成本t=10元/h，运输时间限制为1h。为保证实验的运行效率，本文采用JavaScript编写NSGA-Ⅱ算法程序。

3.2 结果分析

将3.1 节中的实例数据代入渣土车路径优化模型，并用NSGA-Ⅱ算法对模型进行求解。NSGA-Ⅱ算法参数设置如下：取初始种群规模大小为30，交叉概率为0.6，变异概率为0.1，迭代次数为150。算法求解结果如图3所示。

算法迭代过程在图3 中主要表现为以运输成本最小为目标和以运输风险最小为目标的目标函数值依次从右上角到左下角收敛，即越靠近坐标原点的个体其两个目标函数值越小。统计所得优胜个体的运输成本、运输风险、对应路径路段组成情况如表6所示。

表6 实例求解结果

图4进一步给出了渣土车路径优化问题的Pareto 最优解集。相比于当前采用的运输路径（即1-2-5-18-37-35-31-29-28-25-26-53-55-56，运输成本值为168，运输风险值为129 8），最优运输路径的运输成本值分别减少了17.8%,15.4%,8.9%和19.6%，运输风险值分别减少了16.1%,18.3%,24.6%和14.3%，均达到了最小化目标函数值的效果。

根据实例求解得到的4 条最优运输路径映射在地图上，如图5 所示，分别为：1-2-5-7-10-12-13-14-23-24-54-56,1-3-6-9-10-12-13-14-23-24-54-56,1-2-5-18-17-16-14-23-24-54-56,1-3-6-9-11-12-13-14-23-24-54-56。

观察结果可知，优化后的运输路径整体上更偏向于选择道路等级较高及双车道的路段。此外，虽然渣土车流量的增大会带来路径运输风险值的提升，但是选择道路等级较高的双车道路段依旧可以使总运输风险值降低。运输成本方面，模型得到的最优路径更偏向于选择平均速度较大且行驶距离较短的路段，从而有效降低固定成本和时间成本。

综上分析，本文提出的多目标优化模型得到的最优路径均达到了较好的优化效果，可为运输单位提供多条不同的运输优化路径，具体运输路径的选择则可结合实际路况及司机经验等因素来综合决策。

4 结语

针对建筑垃圾渣土车运输路径优化问题，本文提出了一种多目标0-1 整数规划模型，其中目标函数涉及的因素包括固定成本、时间成本，以及关于渣土车流量、道路等级、单双车道的风险值，并设计NSGA-Ⅱ算法进行求解。将所建模型和算法应用于山东省济宁市渣土车运输问题实例，结果表明NSGA-Ⅱ算法适合求解本文提出的渣土车路径优化模型。通过对模型求解可以得到最优运输路径的Pareto 解集，且所得路径的运输成本和风险相较原路径均明显降低，其中运输成本最多可以降低19.6%，运输风险最多可以降低24.6%。实验结果证明本文提出的渣土车路径优化模型和求解算法是可行和有效的，可供决策者结合不同目标之间的权衡和实际路况制定多种不同运输方案。

本文提出的路径评价和优化模型及其求解算法主要侧重于寻找最优运输路径，但忽略了模型与渣土车运输监管平台的融合。未来将进一步完善模型和算法，并与渣土车运输监管平台进行集成，实现运输路径一键评价，通过设定运输起点与终点自动生成多条最优运输路径以供运输单位选择。同时，在使用中也可不断对该运输路径优化体系做适当调整，使其更加符合实际需要。