绿色车辆路径问题研究

王璐瑶 杨巍 曹竹 汪弘 李雅婷

摘要：现在社会上对各类热点问题格外重视，特别能源危机与环保问题，这两个难题已经成为了焦点。而如今，世界经济发展的态势逐渐向较低的能耗，较低的排放量的增长模式趋近，而这个模式最终目标就是保护环境，使绿色可持续发展。。在日常生活中交通运输业是造成环境问题的主要原因之一，并且随着电子商务的发展，物流配送成为城市经济发展和居民生活消费多样化的重要支柱，其造成的城市污染问题已引起人们的高度关注。

针对该问题，首先我们选定沈阳市物流配送的28个站点进行研究，收集并整理其2018年的全部相关数据，之后采用多目标规划模型，分各个站点进行分析，假设各个站点车辆有效利用台数占各个站点的总运输车辆台数比值不变，分别设置车辆有效利用系数、碳排放量以及车辆运营效率等变量，先把目标和约束函数列出，之后会用到数学建模上的遗传算法，以及运用MATLAB软件对算法进行求解，并最终得到结论。

层次分析法则在遗传算法后使用，对车辆路径选择上有直接影响的各个考量进行加权分析，量化评分其余的预选路径因素。在实际情况中可根据决策者的需求对路径进行评价排序，进而得到最佳车辆行驶路径。

最后，我们根据研究得出结论，得到最优绿色车辆路径。

一、问题背景

由于现在社会上对各类热点问题格外重视，特别能源危机与环保问题，这两个难题已经成为了焦点。而如今，世界经济发展的态势逐渐向低能耗，低排放的增长模式趋近，而这个模式最终目标就是保护环境，使绿色可持续发展。而交通运输业是造成环境问题的其中的一个主要原因，并且电子的商务发展的如此迅速，物流配送成为城市经济发展和居民生活消费多样化的重要支柱，其造成的城市污染问题引起人们的高度关注。所以把经济性当做目标的传统车辆的路径研究的问题已不能很好地应对这个趋势，在降低经济成本的同时如何保护环境已经成为车辆路径优化需要考虑的重要因素，这就是所谓的绿色车辆路径问题。

二、备选较优路径——多目标规划模型的建立

本文求解在确保车辆载重、容积、起点及终点和客户服务要求的前提下，保证碳排放量呈下降趋势以及车辆有效利用率提高到0.6以上的目标。这道题是多目标总体规划问题，因此我们在这里，用到的是多目标规划模型，来解决。

沈阳市2018年车辆有效利用率、碳排放量、总运输车辆台数以及车辆运营效率变量，列出目标和约束函数。而我们假设沈阳各个站点的车辆有效利用台数占其总运输车辆台数比值、各个站点碳排放量占沈阳市总碳排放量的总比值不变，以及可通过查找数据得出。

根据MATLAB编制程序可求得2018年车辆有效利用系数、碳排放量、总运输车辆以及车辆运营效率：

（1）形成相对较优绿色车辆路径

由于模型中有多个目标，同时求解较为困难，所以运用禁忌搜索算法对这个进行求解，形成相对较优绿色车辆路径。

（2）评价较优绿色车辆路径

由于前面得到的相对较优绿色车辆路径包括三个目标的各自较优路径，对其进行评价。

求解方法：

对于上述绿色车辆路径问题中所建立的多目标规划模型，鉴于多目标约束下模型的求解方法比较复杂，因此我们采取禁忌搜索算法来求解考虑到油耗的单个车场多个车型的车辆路径问题。

我们假定一个车场共有L种类型的车辆，设第 种类型车共有 辆（ 足够大），每辆车的容量为 ，油耗费为 。该车场共为N个站点服务，其中第 个站点所需货物重为 。配送车辆从站点装上货物出发为客户送货，要求每个客户只由一辆车配送，车辆将货物运送完畢后停留在最后的站点，每辆车的费用均为其油耗费，目标为使所有被派出的车辆的费用之和最小。

禁忌搜索算法：

（1）禁忌算法中解的表示：由于上述问题为多车型单车场问题，又本文用 MATLAB 实现该禁忌搜索算法，为了便于进行邻域操作，所以采用车型代替车场，例如，假设一车场共有2种类型车辆，为10个站点配送货物，用1，2表示车型，1--10表示10个站点，则1维元胞数组：{[4] ，[1，3，5，7]，[2，2，1，6]，[1，4，19]，[2，8]}表示该问题的一个解，该解中共有4条路径，它们分别为：

（1）禁忌算法中邻域操作：根据车型不同而导致启动费用不同的特殊情况，用一些特殊的邻域操作方法来减少车辆的剩余容量，从而减少车辆的使用数量，以达到减少目标函数的目的。随机从 （其含义与改进的最近邻算法中的 相同）中任取两条路径，再分别从两条路径中任取出两个节点：

①若取出的两个节点均为车型，则检测是否有容量更加适合，若有则更换车型，若无则进入下一步操作。

②若取出两节点中分别为车型和客户点。则将客户点插入在路径车型之后，并将此点在原路径中剔除，若仍然有客户点存在，则将车型替换成容量与此路径中总装载量最近的车型，若无客户点存在，则直接删除此路径。

③若取出的两点均为客户点，则将第二个客户点插在第一个客户点之后，并将此点在原径中剔除，如果仍然有客户点存在，则将车型替换成容量与此路径中总装载量最近的车型，若无客户点存在，则直接删除此路径。

（3）计算禁忌算法中的评价值：为了扩大算法的搜索范围，防止局部最优解的生成，在每次迭代中，本算法允许不可行解产生邻居，但由于不可行解的违反目标约束的特点，对不可行解加以惩罚，设惩罚因子为 ，且令 若解x中总共有 条路不可行，设x对应的目标函数值为 ，则解x的评价值为 。

（4）禁忌对象及禁忌长度：将每次迭代得到的局部最好解（评价值最小）作为禁忌对象放入禁忌表中;取禁忌长度为一个常数，其值根据问题的规模来确定;将从当前解的邻域中随机选择N个邻居作为候选集合;采用迭代指定步数T的终止准则。

三、评价预选较好路径——运用层次分析法确立层次分析模型

根据不同的实际情形，我们分析了各项原因，并对其进行了加权，这一步用到了层次分析法。为挑选出最佳车辆路径，我们采取各项指标权重系数与实际数据相结合的评分制度，以此定量评价各备选路径。

（一）建立影响车辆路径选择的指标体系

由上一模型的建立我们已知路径选择主要有成本、路程和污染三大目标，而各个目标又由多种指标决定，分别有总运输车辆台数、车辆有效利用率、行驶里程、行驶时间、耗油量、碳排放量六项指标。而这六项基准方便于根据执行者的需要明确权重。

（二）确定各项指标的权重并建立矩阵

运用层次分析法，简称为AHP，加权定量分析各项指标，这个指标是指可以决定路径选择的。

第一步先将指标构造一个成对比较阵，两两对比比较这个方案里面的所有因素，用成对比较矩阵A，B表示出所有的比较成果。

矩阵A、B是一致阵，权向量就是取对应于最大根的归一化的向量表示对上层原因的权重。下一步将各层权重结果进行乘法和加法的运算，得到的结果就是各个目标的权重值。

（三）一致性检验

再接着下一步就是一致性检验，将一致性指标，这里简称为CI，随机一致性指标，这里简称为RI，这两个指标引入算法中。一致性比例是需要根据随机一致性指标给定的数值表来计算的。 若CR均小于0.1，则通过一致性检验。

（四）计算各路径得分

根据各权重计算各备选路径得分并进行排名。

分数越高者，越满足决策者的要求。

四、挑选最佳路径——依据不同需求挑选

根据实际情况，依据不同决策者的需求，可以调整各指标的权重，以挑选出适合不同情况的最佳车辆路径。

参考文献：

[1] 唐修柏.财务风险跟踪评价方法初探[J].科技视界，2016（01）：278.

[2] 陶大俊. 基于小波与层次分析法的电子银行风险评价与研究[D].西安电子科技大学，2009.

[3] 赵志学，李夏苗，周鲜成.考虑拥堵区域的多车型绿色车辆路径问题优化研究[J/OL].计算机应用：1-11[2019-11-21].

[4] 高飞. 不确定因素下配送路径优化问题研究[D].北京交通大学，2019.

[5] 李英，李惠，成琪.基于文献计量和知识图谱的国际绿色车辆路径问题研究发展分析[J].中国管理科学，2016，24（S1）：206-216.

[6] C.H.Lin，K.L.Choy，G.T.S.Ho，S.H.Chung，H.Y.Lam. Survey of green vehicle routing problem，past and future trends[J]. Expert Systems with Applications，2014，41：1118–1138.

[7] 陈玉光，陈志祥. 基于准时送货和最小耗油的配送车辆路径问题研究[J]. 中国管理科学，2015，23：156-164.

[8] 饶卫振，金淳，王新华等. 考虑道路坡度因素的低碳 VRP 问题模型与求解策略[J]. 系统工程理论与实践，2014，34（8）：2092-2105.

[9] Küçükoğlu，S. Ene，A. Aksoy et al. A memory structure adapted simulated annealing algorithm for a green vehicle routing problem[J]. Environmental Science & Pollution Research，2015，22 （5）：3279-3297.

[10] 葛显龙，黄钰，谭柏川. 基于油耗的带时间窗变速车辆路径问题研究[J]. 物流技术，2015，34（8）：127-149.

[11] 李进，张江华. 基于碳排放与速度优化的带时间窗车辆路径问题[J]. 系统工程理论与实践，2014，34（12）：3063-3072.

[12] J. Zhang，Y. Zhao，W. Xue et al. Vehicle routing problem with fuel consumption and carbon emission [J]. International Journal of Production Economics，2015，170：234-242.

[13] 李进，傅培华，李修琳等.低碳环境下的车辆路径问题及禁忌搜索算法研究[J].中国管理科学，2015，23（10）：98-106.

[14] 康凯，韩杰，马艳芳等. 基于碳排放的模糊约定时间车辆路径问题研究 [J]. 工业工程与管理，2017，22（4）：17-22.

[15] T. Bektas，G. Laporte. The Pollution-Routing Problem[J]. Transportation Research Part B，2011，45：1232-1250.

[16] R. Kramer，A. Subramanian，T. Vidal et al. A matheuristic approach for the Pollution-Routing Problem[J]. European Journal of Operational Research，2015，243 （2）：523-539 .

[17] 左秋玲，李景山.AHP-模糊数学模型在高层工业建筑火灾风险评估中的应用[J].城市建筑，2017（11）：25-27.

[18] 肖晓伟，肖迪，林锦国，肖玉峰. 多目标优化问题的研究概述[J]. 计算机应用研究，2011，28（ 3）：805-808

[19] 潘斌斌.多目标路径规划问题的算法综述[J].重庆工商大学学报（自然科学版），2012，29（05）：78-84.

[20] 滕立春. 電器连锁零售企业的供应商评价研究[D].西北工业大学，2005.

（作者单位：沈阳师范大学）