葛显龙1,2，苗国庆1，谭柏川1
(1.重庆交通大学 管理学院，重庆，400074;
2.重庆邮电大学 经济管理学院，重庆，400065)
摘要：针对当前雾霾严重与节能减排问题，在分析能耗与碳排放相互关系的基础上，提出物流配送问题的碳排放计算方法，建立带有载重与工作时间约束的开放式污染路径问题的数学模型，同时设计改进的自适应遗传算法求解该问题。算法结合扫描算法优化初始种群，设置自适应的交叉与变异操作，并加入进化逆转算子修正误差，提高了算法的求解性能。最后，结合算例对模型和算法的有效性进行验证，并从多维视角分析开放式污染路径问题中影响节能减排的因素，找寻经济成本和环保要求之间的均衡。
关键词：开放式；污染路径问题；遗传算法
中图分类号：F274 文献标志码：A
Research on Optimization Modeling and Algorithm for Open Pollution Routing Problem
GE Xianlong1,2，MIAO Guoqing1，TAN Baichuan1
(1.School of Management , Chongqing Jiaotong University, Chongqing, 400074;
2. University of posts and telecommunications，Chongqing 400064)
Abstract:In view of the current severe haze and energy saving and emission reduction issues, by analyzing the relationship between energy consumption and carbon emission in logistics distribution, which proposed the calculation method of carbon emissions, researched on Open Pollution Routing Problem with load and work time constraints, the integer programming model was established. At the same time, we designed the improved adaptive genetic algorithm to solve this problem. Algorithm combines scanning algorithm to optimize the initial population, setting adaptive crossover and mutation operation, and joining the evolutionary reversal operator to correct error, improved the solution performance of the algorithm. Finally, combined with examples to verify the validity of the model and algorithm, and analyze on the factors of energy
saving, to find a balance between economic costs and environmental requirements.
Keywords: Open , Pollution Routing Problem, Genetic Algorithm
1 引言
现代经济社会中，能源枯竭及温室效应等问题日益凸显，能源与环境问题已成为全球关注的议题。特别是2013年以来，我国频繁发生的空气污染事件以及各地出现的持续雾霾天气，严重威胁着自然生态系统和人们的身心健康，引起了社会的广泛关注。大量的温室气体排放是气候变化和极端天气出现的主要原因，而温室气体主要来源于人类活动导致的二氧化碳（CO2）的排放，如工业生产、物流运输活动中化石燃料的燃烧等[1]。
而物流运输行业是能源消耗较大的产业，更是碳排放大户，据世界资源学院的统计，交通运输行业的二氧化碳排量占全球总排量的18%。因此，实施低碳运输已经成为减少物流领域碳排放的必然趋势[2]。“绿色物流”、“低碳物流”也成为了国内外理论研究的新热点[3]。正是在这样的背景下，Tolga Bektas等[4]在2011年提出了污染路径问题（Pollution Vehicle Routing Problem, PRP），在车辆路径问题中同时考虑经济因素和环境因素，将燃料消耗和二氧化碳排放纳入到现有的车辆路径规划方法中，寻求一条经济环保的车辆路径。之后，Emrah Demira等[5]设计了一种自适应大邻域搜索算法解决PRP，使包括油耗、碳排放和司机成本在内的目标函数最小；Emrah Demira等[6]研究了双目标PRP，一个目标是使包含当量二氧化碳排放量的油耗最少，另一个是使行驶时间最少，为路径决策中减少碳排放成本提供了依据；Anna Franceschettia等[7]研究了时间依赖性PRP，在路径确定时，规划车辆的出发时间和速度，使得整个路径的碳排放量最少。近年来，国内对于此类问题的研究也日益增多，如唐加福[8]、吕品[9]、于雷[10]等人从构建模型或算法设计方面对低碳车辆路径问题进行了研究。然而，这些研究均是针对闭环车辆路径问题（Vehicle Routing Problem, VRP）展开的研究。而现实中愈来愈多的企业开始物流外包，此时车辆的行驶路径是开放的[11]。由于开放式车辆路径问题（Open Vehicle Routing Problem, OVRP）的特殊性，车辆行驶的过程中较闭环VRP将产生更多的碳排放。但是，国内外对OVRP的研究[12-14]尚未考虑到日益增加的碳排放的影响。因此，在考虑碳排放的情况下研究OVRP，对节能减排来说显得十分必要。
基于上述分析，本文提出了开放式污染路径问题（Open Pollution Routing Problem, OPRP），通过分析物流配送中能耗与碳排放的相互关系，提出碳排放的计算方法，建立带有载重与时间约束的开放式污染路径问题优化模型，并设计改进自适应遗传算法对模型进行求解。最后，结合算例对算法和模型进行验证分析。
2 问题描述与假设
OVRP中通常认为租车的费用往往与租用的车辆数和车辆负载时的行驶距离成正比，因此，OVRP中对其车辆行驶路线进行优化时，往往将所租用的车辆数最少和车辆总行驶距离最短作为优化目标[15]。这就会造成车辆的载重率较高，而车辆的碳排量与车辆载重等因素息息相关[4]，载重率高最终会导致车辆的油耗和碳排量的增加。基于以上分析，开放式污染路径问题可以描述为：某公司物流外包，现要对客户进行物流配送，在考虑使用车辆数尽可能少的情况下对该物流配送网络进行优化设计，对网络中配送量的分配问题以及配送路径的选择问题进行综合决策，使总路径的碳排放量尽可能的少，以及行驶距离尽可能的短。
基金项目：国家自然科学基金项目资助（71502021）；电子商务与现代物流重庆高校市级重点实验室开放基金项目资助（ECML201408）；教育部人文社会科学基金项目资助（2014YJC630038）；重庆市教委自然科学基金项目资助项目（KJ400311）.
作者简介：葛显龙(1984-)，男，河南信阳人，副教授，博士，研究方向为网络配送与路径优化；苗国庆（1991-），男，河南开封人，硕士研究生，主要研究方向为物流配送，Email：miaoguoqing1991@126.com；谭柏川，男，汉族，四川巴中人，硕士研究生，主要研究方向为物流配送。