孙金枝

摘要：近年来，环境和能源问题成为人们关注的一个焦点。交通运输业是一个高能耗的行业，该行业实现节能减排是有必要的。文章以降低车辆碳排放为目标进行车辆路径构建和速度优化，从而实现交通运输业的节能减排。在考虑配送节点约束、车辆速度约束、容量约束、时间窗约束的情况下，构建了一个非线性数学模型，并设计了一个两阶段算法：第一阶段假设网络速度相同进行路径优化，第二阶段在已知路径的情况下进行速度优化。最后通过算例验证了算法的可行性和有效性。

关键词：带时间窗的车辆路径问题;速度优化;碳排放

中图分类号：U116.2文献标识码：A

O引言

随着环境污染、能源枯竭问题越来越突出，人们也更加关注环境和能源问题。交通运输业是一个高能耗的行业，《公路水路交通节能中长期规划纲要》、《“十三五”现代综合交通运输体系发展规划》等都指出要降低能源消耗，减少污染气体的排放。除了构建合理的交通运输系统、研发新能源汽车等措施外，交通运输企业可以通过构建合理的车辆行驶路径、车辆行驶速度等措施来降低能源消耗。基于此确定了本文的研究主题——基于碳排放的车辆路径优化和速度优化。

关于路径优化（VRP）的文章很多，研究也相对成熟。本文主要关注了带时间窗的车辆路径问题（VRFTW），该类问题属于典型的NP-hard问题，求解方式包括精确算法和启发式算法。精确算法有分支定界、列生成等，Desrochers等用分支定界算法解决列生成中的子问题，该算法可以求得VRPTW的最优解。Choi等采用列生成算法求解整数规划问题，并针对VRPTW提出了两种动态规划算法。启发式算法有禁忌搜索、蚁群算法等，Pisinger等提出了大规模领域搜索算法框架来解决VRPTW的问题。张金金（2012）设计了两阶段的启发式算法，何小锋，马良（2013）通过将量子计算和蚁群算法相结合提出了量子蚁群算法。

速度优化问题最先出现在航海路径减排问题上。Fagerholt等证明了速度优化问题为非线性凸规化问题。Norstad等提出了一个递归算法来求解固定路径上的速度优化问题，被Hvattum等证明该算法是精确算法。

目前，考虑碳排放的路径优化问题还比较少。BektaS等提出了污染路径问题并建立了一个非线性数学模型，然后通过离散化速度，将非线性模型转化为线性模型进行求解。Fukasawa等构建混合整数规划算法解决PRP问题。Demir等建立了一个ALNP算法解决污染路径问题。李进等以旅行时间、碳排放和油耗的总费用最小化为目标函数，设计了两阶段启发式算法。

本文在配送成本中考虑车辆油耗成本和车辆使用成本，以路径优化和速度优化为决策变量建立了数学模型，并设计了一个两阶段算法来解决该问题，第一阶段假设网络速度相同采用二分法求解可能路径，第二阶段在已知的路径集合中进行速度优化，从而输出最优解。

1问题描述与模型构建

1.1问题描述

根據1.2.1，该目标函数为凸函数，约束式（13）为非线性约束，该问题为非线性凸规划问题，速度决策可以借助MAT-LAB的fmincon命令求解。

2.2算法设计

本算法设计整体思路分为两个阶段，第一阶段是假定网络速度相同的情况下，对网络进行路径优化;第二阶段是在获得路径之后，对路径上的速度进行速度优化。由于给定的网络速度会影响求解结果。本文在第一阶段用二分法求出所有可能路径，之后在第二阶段对所有路径进行速度优化，从而输出最优解。具体算法流程如图1、图2所示。

3算例分析

3.1参数设置

现有一个配送中心和15个客户，所有节点的经纬度、客户需求（单位kg）、需要的服务时间（单位s）如表1所示。此外，配送中心有载重量为3.5t的车辆10辆，采用的油耗成本如1.2.2中所示，车辆最高限速为120km/h，最低限速为20km/h，最优速度υ_opt为63.39km/h。单位里程的油耗成本C₁=7.5，车辆使用成本C₂=100。对于不同的测试实例，生成不同宽度的时间窗。

3.2算法有效性验证

原模型是非线性混合整数规划，不容易求得最优解。为此，需要寻找原问题最优解的下界。假设（x，y）是原问题P1的最优解，问题P2仍然按照该路径和速度行驶，也可以满足所有约束，因此（x，y）也是问题P2的可行解。则P2的最优值小于等于P1的最优值，因此问题P2的最优值可以作为问题P1最优值的下界。

3.3固定速度和本文算法计算结果比较

为了进一步说明对车辆进行速度优化的必要性，将网络速度固定为使单位里程油耗最小的速度υ_opt=63.39km/h，计算了在此情况下的配送成本、车辆使用数量，如表3所示。计算结果表明，对车辆进行速度优化，平均可以节省11.98%的费用，因此对车辆进行速度优化是有必要的。

4结束语

本文以车辆油耗成本和使用成本为目标函数，建立了以路径和速度同为决策变量的数学模型，并针对模型设计了算法，通过算例验证了模型和算法的可行性和有效性。但是本文选用cplex进行路径优化，仅适用于客户规模较小的情况，在后续研究中将针对大规模客户进行研究。