低碳导向的网约车合乘动态匹配算法研究

Dynamic matching algorithm for ridesplitting under low carbon target

针对网约车合乘减排效益未能充分发挥的问题,提出一种低碳导向的网约车合乘动态匹配算法,可在保证网约车合乘经济效益的同时优化合乘的减排效益。首先根据合乘规则构建可合乘网络,然后基于图优化理论将可合乘网络转换为带权无向图,同时基于COPERT模型计算潜在合乘订单的碳减排量作为无向图的权重,最后利用改进的最大权重匹配方法对其进行求解,进而得到碳减排效益最大化的合乘匹配方案。以成都市网约车订单数据为分析实例,对该算法与传统匹配算法进行对比评估。结果表明,当乘客最大允许延误为10 min时,该算法下的可合乘出行比例达86%,碳减排总量相比传统匹配算法可提高122%,单次合乘行程的减排效率平均提高128%。因此,该算法能够在不影响平台经济效益的情况下,显著提升合乘减排效益。

In order to address the problem that the emission reduction benefits of ridesplitting are not fully utilized,this paper proposed a dynamic matching algorithm for ridesplitting under low carbon target.The proposed algorithm could optimize the emission reduction benefits of ridesplitting while ensuring its economic benefits.Firstly,it constructed a shareability network to the ridesplitting rules,then transformed the shareability network into a weighted undirected graph based on graph optimization theory,and calculated the carbon emission reduction of potential ridesplitting orders as the weights of the undirected graph based on the COPERT model,and finally solved it by using an improved maximum weight matching algorithm to obtain a ridesplitting matching scheme that maximized the carbon emission reduction benefit.This paper evaluated the proposed algorithm in comparison with the traditional matching algorithm,using the data of online ride-hailing orders in Chengdu as case study.The results show that when the passenger’s acceptable delay is 10 minutes,the proportion of ridesplitting trips under the proposed algorithm is as high as 86%,and it can increase the total carbon emission reduction by 122%compared with the traditional matching algorithm.Further more,it can improve the carbon emission reduction efficiency of a single ridesplitting trip by 128%.Therefore,the proposed algorithm can significantly improve the ridesplitting emission reduction efficiency without affecting the economic benefits of the platform.