基于低碳排放的多车型车辆路径优化问题研究

王恒 王俊超 刘文美 王振锋 王银河 徐亚星

摘要：针对物流配送过程中，如何合理安排配送路线，提高配送效率、降低配送成本和碳排放量的问题，分析了车辆载重量、行驶速度、行车距离、交通状态等因素对车辆油耗的影响，建立了以最小化配送成本和碳排放量为优化目标的多车型车辆配送路径模型。同时，结合蚁群算法对该优化问题进行求解。仿真结果验证了算法能够有效的降低配送成本和碳排放量。

Abstract： In the urban logistics distribution， reasonable distribution of distribution routes can effectively improve the efficiency of distribution， reduce the cost of distribution and carbon emissions. The influence of vehicle load， speed， distance and traffic condition on vehicle fuel consumption is analyzed. At the same time， an optimization model of heterogeneous vehicle distribution routes is constructed based on minimizing the cost of distribution and carbon emissions. Finally， an colony optimization algorithm is used to solve this problem. Finally， the feasibility and effectiveness of the constructed model and the proposed algorithm are verified by simulation experiments.

關键词：车辆路径优化;多车型;碳排放;蚁群算法

Key words： vehicle routing optimization;heterogeneous fleet vehicle;carbon emissions;ant colony optimization algorithm

中图分类号：F259.23                                     文献标识码：A                                  文章编号：1006-4311（2019）12-0080-03

0  引言

如何减少配送过程中的油耗成本一直是各个物流企业关注的问题之一。其原因主要有以下两个方面：一、企业希望通过降低配送过程中的车辆油耗进一步压缩成本，增加企业利润;二、企业通过控制油耗，从而降低配送过程中的碳排放量，承担节约资源、保护环境的社会责任。因此，如何从低碳角度安排配送路线，是物流企业在配送环节中面临的重要问题之一。

目前，国内外学者围绕车辆路径优化问题进行了大量的研究工作。李莹[1]等综合考虑了配送距离、车辆固定成本等多种因素，建立了带有软时间窗的循环取货多车型车辆路径问题;殷亚[2]等以车载量和硬时间窗为约束条件，建立了最小发车量和最小行驶距离为目标的数学模型，并提出了混合蝙蝠法对模型进行求解;陈呈频[3]等以多车场、多车型车辆为研究背景，建立了配送车辆路径优化问题的整数规划模型，提出了多染色体遗传算法。张传琪[4]等以配送成本最小为目标函数，构建了考虑服务途中动态拥挤的多车型车辆路径模型，设计了求解该模型的改进遗传算法。刘丽姣[5]等提出了单循环结构的细菌觅食优化算法与改进的综合学习粒子群算法相结合的混合求解算法。可见，考虑碳排放的车辆路径问题成为现阶段研究的热点。

鉴于此，本文分析了车速、载重，距离等因素对车辆油耗的影响。以最小化配送成本和碳排放为优化目标，构建了多车型车辆配送路径优化模型。最后，提出了一种改进的蚁群算法对该优化问题进行求解。

1  模型建立

1.1 问题描述

本文研究的多车型车辆路径优化问题具体描述如下：配送中心拥有若干不同额定载重的配送车辆，配送中心根据各个配送点需求，安排车辆进行配送。车辆从配送中心出发，按照拟定的行车路线进行逐一配送，完成配送任务后，返回配送中心。在此配送过程中，每个配送点由一辆车配送，配送线路上各个配送点的需求量总量不超过单车的最大装载量。

3.2 仿真结果与分析

通过仿真得到，ACO算法的最优配送方案为：额定载重15吨的配送车辆路径为：0-18-19-11-23-25-26-14-16-28-6-30-4-2-17-29-0;0-13-5-20-9-24-27-10-15-3-8-1-0;额定载重5吨的配送车辆路径为：0-21-22-12-7-0。ABC算法的最优配送方案为：额定载重15吨的配送车辆路径为：0-28-8-13-10-26-7-6-16-9-5-1-17-0;0-19-22-12-2-14-21-30-18-11-24-3-20-29-0;额定载重5吨的配送车辆路径为：0-15-4-27-25-23-0。GA算法的最优配送方案为：额定载重15吨的配送车辆路径为：0-15-29-24-1-25-4-11-10-27-13-23-20-0;0-9-5-21-19-14-22-12-7-0;0-3-17-28-6-16-8-2-26-30-18-0。在算法运行过程中，ACO算法收敛速度较快，搜索得到的最优解较为理想。ABC算法收敛速度较慢，GA算法大约在第300次迭代后不在进行寻优，出现了早熟收敛现象，如图2所示。

表3给出了不同算法得到的配送成本和碳排放量。显然，ACO算法的运行结果优于对比算法。在配送成本方面，ACO算法的配送路线所需的配送成本为1268.92元，碳排放为198.21千克。與ABC和GA算法相比，分别能够节省3.8%，11.4%的配送成本，减少2.1%和9.1%;显然，依照ACO算法得到的配送路线进行配送，具有较低的配送成本和碳排放量。在运行时间方面，三个算法运行时间差别不大。通过以上实验仿真可以看出，ACO算法具有理想的寻优效果，能够在配送路径优化过程中寻找到使配送成本和碳排放最小的配送方案。

4  总结

本文针对多车型车辆路径优化问题进行了研究。首先，本文分析了车速、载重、距离等因素对车辆油耗的影响。然后，以最小化配送成本和碳排放为优化目标，构建了多车型车辆配送路径优化模型。最后，通过蚁群算法对该优化问题进行求解。通过仿真验证模型和算法的有效性，结果表明本文构建的模型可以有效的减少配送成本和碳排放，所提出的算法也取得了良好的效果。

参考文献：

[1]李莹.带软时间窗的循环取货多车型车辆路径问题研究[D].长安大学，2016.

[2]殷亚，张惠珍.求解带硬时间窗的多目标车辆路径问题的多种混合蝙蝠算法[J].计算机应用研究，2017（12）：118-122.

[3]陈呈频，韩胜军，鲁建厦，等.多车场与多车型车辆路径问题的多染色体遗传算法[J].中国机械工程，2018，29（482）：96-101.

[4]张传琪，张杨.动态路网下多车型车辆路径问题研究[J].交通运输工程与信息学报，2017，2（15）：112-118.

[5]刘丽姣.考虑碳排放的多车场多车型VRP模型及算法研究[D].深圳大学，2017.

[6]王恒，徐亚星，王振锋，等.基于道路状况的生鲜农产品配送路径优化[J].系统仿真学报，2019，31（1）：126-135.

[7]Bekta■ T， Laporte G. The Pollution-Routing Problem [J]. Transportation Research Part B Methodological， 2011， 45（8）： 1232-1250.

[8]Mao W W， Yu S P. Ant Colony Algorithm for VRP with Time Windows [J]. Energy Procedia， 2011， 13： 2168-2173.

[9]蔡浩原，潘郁.基于人工蜂群算法的鲜活农产品冷链物流配送路径优化[J].江苏农业科学，2017，45（15）：318-321.

[10]Michalewicz Z， Janikow C Z， Krawczyk J B. A modified genetic algorithm for optimal control problems [J]. Computers & Mathematics with Applications （S0898-1221）， 1992， 23（12）： 83-94.