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

收稿日期：；修回日期：基金项目：国家自然科学基金资助项目（）；上海市晨光计划资助项目（）；上海市科技创新行动计划资助项目（）作者简介：于天翔（），男，上海人，硕士研究生，主要研究方向为低碳交通、共享交通；李文翔（），男（通信作者），江西赣州人，副教授，硕导，博士，主要研究方向为低碳交通规划、共享交通管理、时空大数据挖掘（）；张玉梁（），男，山西忻州人，博士，主要研究方向为智能交通、交通大数据分析；陈豪（），男，浙江温州人，高级工程师，硕士，主要研究方向为交通大数据分析；董洁霜（），女，浙江温州人，副教授，博士，主要研究方向为土地利用与交通规划低碳导向的网约车合乘动态匹配算法研究于天翔，李文翔，张玉梁，陈豪，董洁霜（上海理工大学 管理学院，上海 ；浙大城市学院，杭州 ；温州理工学院，浙江 温州 ）摘要：针对网约车合乘减排效益未能充分发挥的问题，提出一种低碳导向的网约车合乘动态匹配算法，可在保证网约车合乘经济效益的同时优化合乘的减排效益。首先根据合乘规则构建可合乘网络，然后基于图优化理论将可合乘网络转换为带权无向图，同时基于 模型计算潜在合乘订单的碳减排量作为无向图的权重，最后利用改进的最大权重匹配方法对其进行求解，进而得到碳减排效益最大化的合乘匹配方案。以成都市网约车订单数据为分析实例，对该算法与传统匹配算法进行对比评估。结果表明，当乘客最大允许延误为 时，该算法下的可合乘出行比例达 ，碳减排总量相比传统匹配算法可提高 ，单次合乘行程的减排效率平均提高 。因此，该算法能够在不影响平台经济效益的情况下，显著提升合乘减排效益。关键词：城市交通；网约车合乘；低碳；共享网络；图匹配中图分类号：文献标志码：文章编号：（）：，（，；，；，）：，：；引言网约车由于其高效、便捷等特点，已经成为许多人日常出行的首选交通方式，然而随着大量网约车辆的投放，城市道路的拥堵和交通污染问题也日益加剧。为解决上述问题，各大网约车企业和城市逐步推出了网约车合乘业务。理论上来说，合乘出行相比常规网约车出行，能够提高车辆利用率，减少行驶距离以及交通碳排放量 ，然而实际上，由于现有的合乘匹配算法主要是以企业利润最大为目标，导致部分合乘订单路线重叠率不高、绕路距离较远，其碳排放甚至超过常规网约车行程 ，使得合乘出行的减排效益并未充分发挥。因此，急需对现有网约车合乘匹配算法作进一步改进与优化。目前关于网约车合乘匹配算法的相关研究大多基于优化模型，已有较为成熟的理论体系。例如，等人 设计了基于贪婪分配算法的合乘匹配方法，实现了对大量网约车订单的实时合乘分配功能。吴癑琳等人 以车辆数最小与总里程最短为目标，设计两阶段算法求解合乘匹配方案及路径问题。王志建等人 以车辆的总行驶距离最短以及总信任度值最高为目标，对合乘轨迹线路进行优化。等人 提出了利用可合乘网络对网约车合乘进行建模的方法，并以合乘比例作为优化目标挖掘潜在的合乘方案。在此之后，许多学者采用以可合乘网络为主的聚类方法对网约车合乘出行进行建模，并利用不同的合乘匹配算法计算不同目标下的最优合乘匹配方案，充分挖掘网约车合乘出行的潜力。等人 选择了合乘数量、节省时间以及节省费用三种不同的匹配目标进行合乘匹第 卷第 期 年 月计 算 机 应 用 研 究 配，结果表明潜在的合乘比例高达 ，且最大化节省费用相比于其他两个目标的平均延误更低。等人 提出了基于需求的合乘出行匹配算法，利用效用函数替代时间窗口等约束条件，并以节省费用为目标对共享网络进行优化。等人 提出了基于运营车辆的合乘网络模型，并利用最小车队数量作为目标函数对其进行优化。、等人 ，均以车辆总行驶里程作为合乘模型的优化目标。而 等人 优化了合乘出行的定价策略，并以企业的合乘收益作为优化目标。可见，已有关于合乘匹配的研究大多以合乘匹配数量、总里程、总时间、总费用、车队规模等为优化目标，但却忽视了对网约车合乘减排效益的优化。针对上述研究不足，本文提出了一种低碳导向的网约车合乘动态匹配算法，在具有时间约束的可合乘网络基础上，以潜在合乘订单碳减排量为优化目标，保证了网约车合乘经济效益的同时还可充分挖掘合乘的减排潜力，以实现更高效、更低碳的合乘出行。研究方法 问题描述当用户发起网约车合乘需求后，网约车企业需要在尽可能短的时间内为用户寻找到满足一系列条件的合乘订单并发布。而当企业将环境效益作为合乘行程的主要指标后，合乘行程的碳减排量就成为了订单筛选时的主要目标。由此可见，低碳导向的网约车合乘匹配问题实际上可以分为两个问题，首先是考虑时间约束的合乘订单筛选，其次是碳减排总量最大化的优化。图 展示了当有两位合乘用户时，两种基本合乘方式，考虑到合乘的舒适性、安全性等诸多因素，网约车企业只允许司机同时接受两个合乘订单，当其中一个订单结束后，司机可接受第三个合乘订单，但此种情况的比例很低，因此本文暂且不考虑。其中，表示订单 的起点，表示订单 的终点；和 分别表示合乘后实际的起终点；表示合乘后的上车时间；表示在非合乘时订单的到达时间；表示乘客预期上车时间，由于合乘会产生绕路导致延误，所以第二位乘客的实际上车时间会晚于预期上车时间，如图 （）中，订单 是合乘订单中的首个订单，因此其预期上车时间等于实际上车时间，即 ，而订单 受到合乘的影响，其预期上车时间晚于实际上车时间，即 。表示时间窗口约束，为了减少用户发起订单后的等待时间，只有在时间窗口内的订单才会进行匹配，若时间窗口内不存在订单，则发布非合乘行程。表示乘客允许延误，由于合乘行程会造成时间延误，所以仅当两位乘客的出发、到达时间都在其可允许的延误之内时，该合乘订单才可行；表示合乘行程中每一段的行程时间，由各路段的行程时间累计而成。图 合乘行程示例图 可合乘网络模型建立如前文所述，首先需要解决的是考虑时间约束的合乘订单筛选问题。传统的方法是对订单数据集进行遍历筛选，但这种方法耗时较大，能够处理的数据量有限，无法应对海量的网约车订单数据集。因此，为了实现网约车合乘的高效匹配，本文引入了由 等人 提出的可合乘网络模型（），该模型较为成熟，求解效率高 ，。设 （，）为可合乘网络 ，其中包含端点集 以及连接两个端点的边集 。网约车订单数据集中的每一个订单 ，都与可合乘网络中的一个端点 一一对应，因此订单数据集也在网络中转换为端点集 ；当两个端点 与 所代表的订单 、满足式（）中的合乘时间约束条件时，则这两个订单可以进行合乘，即存在边 ，连接 与，即为所有可行边的集合。在可合乘网络模型中，当且仅当两个订单满足一系列预先设定的时间窗口约束时，这两个订单才具有合乘的可能。必须满足的约束条件如下所示。（）（）（）（）其中：式（）表示两订单预期上车时间不得超过时间窗口约束；式（）表示车辆接到第一位乘客后到达第二位乘客上车地点的时刻可以早于第二位乘客的实际上车时间（即车辆等待乘客），但不能晚于第二位乘客的最晚预期上车时间（即预期上车时间 加乘客允许延误 ）；式（）（）分别表示车辆到达第一、二位乘客下车地点时刻不得晚于最晚到达时间（即预计到达时间 加乘客允许延误 ）。传统可合乘网络求解目标多为合乘比例最大化、企业收益最大化等，难以体现合乘出行的减排效益，因此，本文以减排效益最大作为优化目标对可合乘网络进行求解，基于该优化目标，本文所构建的可合乘网络求解模型如下所示。，（）式（）（）（），（）其中：，表示订单 和 合乘后的碳减排量（）；表示网约车合乘订单集。合乘碳减排量由订单 、在非合乘时的碳排放量、减去两个订单合乘后产生的碳排放量 ，计算得到。对于所有满足时空约束的网约车合乘订单，可以绘制成一张可合乘网络图，由定义可知，可以与订单 进行合乘的订单 并不唯一，即与订单 通过边 ，相连的 并不唯一。如图（）所示，订单 、互相可以合乘，订单 可与订单 、合乘，而订单 只能与订单 进行合乘。根据不同的筛选条件，一张可合乘网络图可以得到多种合乘匹配方案如图 （）（）两种情况。可以使用合乘匹配算法对可合乘网络进行优化，得到一个无重复的合乘方案集，通过调整最优化目标函数，便可以修改筛选条件，得到满足条件的合乘方案。图 可合乘网络示意图 低碳导向的网约车合乘动态匹配算法当可合乘网络构建完成后，需要对所有可能的合乘方案进行筛选，得到满足目标的合乘方案集。根据本文目标，在这里需要考虑的是碳减排总量最大的优化问题，因此筛选的依据就是合乘行程的碳减排量。在可合乘网络中，每一条边 ，代表第 期于天翔，等：低碳导向的网约车合乘动态匹配算法研究着一个可行的合乘方案，因此可以计算该合乘方案的碳减排量，并将碳减排量作为权重 赋值到边 ，上。因为可合乘网络图中的每一条边都不具有方向性，而每条边上都有权重，所以此时的可合乘网络图等价为带权无向图。而碳减排总量最大化的问题此时就转变为在带权无向图中寻找一组边的集合，要求每条边不能相连，而且所有边的权重加和为最大。这实质上是一个带权无向图的匹配问题。因此，本文将可合乘网络图转换为带权无向图，利用最大权重匹配方法对其进行求解，所得结果即为碳减排总量最大的合乘方案集。首先将共享网络转换为无向图 （，），其中 为顶点集，表示所有的订单；为边集，表示所有的合乘方案，（，）表示连接 与 两顶点的边 ，的权重，如图 所示。其中每条边的粗细不同代表着这条边的权重大小不同，当每条边都被赋予权重值后，的总权重就可表示为（）（，）。（，），（）图 带权无向图 经过上述操作后，可合乘网络图转换成了带权无向图，此时可利用最大权重匹配法进行匹配。对于一张无向图 ，设是它的一个匹配，则 中所有的边都不相邻。若不存在另一个匹配，使得（）（），则认为 是 的最大权重匹配。本文采用线性时间近似的最大权重匹配算法，该方法基于带花树算法进行优化，比使用原始对偶的近似匹配方法效率更高 。该算法输入项为带有权重的无向图，输出项为使得 权重最大的边集合，计算时间为 （），其中 表示顶点的数量，算法伪代码如下所示。算法 合乘匹配算法输入：转换为带权无向图 的可合乘网络。输出：合乘集合 ，以及每组合乘的碳减排量。），。初始化）偶数集 匹配 中的自由边，奇数集为空，树集为空，保证边集 偶数集 奇数集。）从偶数集中取一条边，若不存在，则输出 。）若该边不在树集中，则成功匹配，将该边加入匹配集。）若该边在偶数集中，且与树相连则进行开花运算；返回 ）。）若该边在偶数集中，且未连接，则存在增广路径，更新 并返回 ）。）当没有更多条件满足时，结束并返回匹配集合 以及各权重。合乘出行碳减排量计算机动车排放模型通过计算机动车运行时的排放系数、平均速度、燃油消耗以及交通量等参数，得出各类污染物的排放水平。一般来说，机动车排放模型按计算复杂程度可以分为基于宏观交通量的模型、基于平均速度模型以及行驶工况的模型 。本研究采用 模型来计算排放量，该模型属于基于平均速度的排放计算模型 ，虽然该模型是为符合欧洲排放标准的机动车辆设计，但经过学者研究，该模型同样适用于我国机动车排放计算 。由于本文将道路交叉口作为路段节点并以此进行路径规划，所以本文以两个交叉口之间的路段作为计算单位进行碳排放计算，路段示意图如图 所示。路段碳排放的基本公式由距离和排放因子构成，如式（）所示。（）其中：表示路段 上污染物的排放量，单位为 ；表示机动车在路段 上的行驶距离，单位为 ；表示路段 上污染物的排放因子，通常为 ，计算方式如式（）所示。（）其中：是机动车在路段 上的平均速度（）；、是由车辆类型、排放标准、燃料类型、发动机类型等因素决定的模型参数，模型已根据有关实验对这些参数进行了标定 ，本研究所选用的网约车数据大部分符合中国第四阶段排放标准（国 ）限值的汽油车。图 路段示意图 在获得车辆经过路段的排放后，将其经过的所有路段的排放量进行累加，就获得了订单 运营期间的总排放量。（）实例数据分析 研究范围与数据描述本次研究区域以成都市主城区为范围，共包含 个下辖区，研究范围内道路通过 提供的开源地图数据获得，路网数据中包括了路段编号、道路名称、车道数、单双向形式、路段限速等字段。接着，本文以交叉口为节点、道路为连接线的形式进行处理，得到精简后的道路网络图如图 所示，包括了 个节点以及 条连接线。图 研究区域及路网 本文使用的网约车订单数据由滴滴公司推出的滴滴盖亚数据开放计划提供，数据集包含成都市 年 月 日的滴滴专车和滴滴快车订单数据，共包含 万个订单，数据字段如表 所示。数据处理流程在获得简化路网后，根据成都市实际道路情况，对各等级道路设置了不同的平均行驶速度并加载至路网属性中，随后利用平均速度以及路段长度属性，计算各路段的行程时间并添加计 算 机 应 用 研 究 第 卷至属性中。随后将订单中的起、终点位置分别与实际路网中距离该点最近的路口相匹配，利用路口的坐标代替订单中的实际位置从而减少后续匹配的计算复杂程度，考虑到经过上述处理后的道路网络十分密集，信息较为详细，因此可以认为该处理方法对于结果的影响较小。在获得更新后的订单起终点坐标点位后，利用最短路算法结合路段行程时间属性，计算网约车订单的行驶轨迹、行程时间、平均速度等数据，为后续排放计算提供支持。具体处理过程如图 所示。表 网约车订单数据样本 订单编号订单起始时间订单结束时间起点经度起点维度终点经度终点纬度 图 数据处理流程图 网约车出行时空特征分析对经过筛选后的数据进行初步分析。以行政区域为边界对网约车订单的上车地点和下车地点进行集计，得到网约车订单空间分布如图 所示。由该图可以看出，网约车订单主要分布在城市的中心区域，有较明显的空间集聚现象。这说明网约车主要服务于功能密集、出行需求量大而均出行距离较短的区域，即城市 区域，而该区域由于上述特点，存在大量的潜在合乘出行需求可供挖掘。图 网约车出行空间分布 进一步分析网约车订单一天内的时间分布如图 所示，可以发现网约车订单在上午 点、下午 点以及晚间 点都存在比较明显的高峰时刻，说明网约车除了满足一定的通勤需求，同样可以满足众多休憩、娱乐的出行需求。另一方面，由于网约车出行高峰时期也与通勤高峰时期存在重叠，所以也会进一步加剧高峰时期的车辆拥堵状况，从而造成尾气污染排放的增加。图 网约车出行时间分布 结果与讨论本文引入传统网约车合乘匹配算法与本文提出的新算法进行对比。传统匹配算法主要考虑网约车企业的运营效益，其优化目标是使匹配成功的合乘订单数量最大化。通过将可合乘网络中各条边的权重设为 ，便可以通过最大权重匹配算法实现目标。因为此时边（即合乘方案）的数量等同于权重，而当图的总权重最大时，就代表合乘方案数量最大。根据 等人 的研究，传统网约车业务与网约车合乘业务的高峰期存在显著差异，网约车合乘高峰期主要出现在下午一点至三点这个时间段内，故下文选择该时段内的数据进行重点分析。利用低碳匹配算法和传统匹配算法两种不同方式对研究数据进行合乘匹配计算，考虑不同的乘客最大允许延误 对可合乘订单比例所造成的影响如图所示。随着 不断增加，两种方法的可合乘比例都呈逐渐上升的趋势，在 时可合乘比例迅速上升，由 快速上升至 ；而在 的范围内，可合乘比例上升趋势减缓，低碳匹配算法的可合乘比例上升至 ，而传统匹配算法的可合乘比例上升至 ；在 内，两种匹配方式的可合乘比例都趋于稳定，分别达到 和 。分析认为该现象是由乘客对出行时间的敏感程度决定的，一般来说，相比于选择公共交通出行的乘客，选择网约车出行的乘客对于时效性的要求更高，所以一旦选择合乘出行所带来的延误过大超出了出行者的接受范围，这部分出行者就不会选择该方案，从而导致当 较大时，可合乘比例难以上升的现象。另一方面，从图中可以看出两种匹配算法得出的可合乘比例差距较小，表明本文所提出的合乘匹配算法虽然以合乘出行的减排效益为优化目标，但同样也能保证网约车平台的经济效益。图 展示了在不同 水平下，两种匹配方式对碳减排总量带来的影响。传统匹配算法的碳减排总量在 时达到 的最大值，随后呈缓慢下降的趋势，并在 后趋于稳定，保持在 左右。结合前文可以发现，在传统匹配算法中，虽然总合乘比例是上升的，但碳减排总量却在下降。分析认为，由于碳减排量较大的合乘行程往往具有重叠率高、目的地接近等特征，而拥有这些特征的订单多处于网约车出行需求密集地区，所以也有更多的合乘备选方案可供算法选择，所以当 增加时，为了满足最大合乘数量的优化目标，算法会选择相对数量更多而碳减排量较小的合乘行程，而不是碳减排量较大但数量较少的行程，从而导致碳减排总量持续减少。相反地，在低碳匹配算法中，由于算法会优先匹配碳减排量较大的合乘行程，该方法下碳减排总量持续增加且能达到较高水平，当 时，低碳匹配算法下的合乘出行碳减排总量达到 ，相比传统匹配算法提升了 。第 期于天翔，等：低碳导向的网约车合乘动态匹配算法研究图 不同匹配算法中可合乘订单比例 图 不同匹配算法中合乘出行碳减排总量（）（）图 分别表示在不同 下，每次合乘行程的平均碳减排量与每公里平均碳减排量的变化情况。在传统匹配算法下，随着 的增加，合乘行程可允许的绕路也就越长，而车辆的碳排放与车辆行驶里程具有显著关联，因此可以很直观地看出随着增加，平均碳减排量以及每公里减排都在逐渐减少，即碳排放逐渐增加。而在低碳匹配算法中，可以看到当 时，平均碳减排量及每公里减排均呈下降趋势。经过分析认为，该现象是由于当 较小时，各合乘行程的重叠率高、绕路比例极小，所以碳减排量相对较大，而这些约束较为严格，可选的合乘方案数量较少，导致平均减排偏高。而当 放宽后，增加了大量碳减排量适中的合乘行程，碳减排量分布更为均匀，因此平均碳减排量有所下降。而在 的部分，虽然 不断变大，但合乘行程的平均碳减排量和每公里碳减排量都在缓慢提升，并在 后逐渐趋于稳定，对比两条不同曲线可以看出，本算法可极大提升网约车的减排效益。以 时为例，相比传统算法，利用本文提出的算法后合乘行程的平均碳减排量由 （行程）升高至 （行程），减排效率提高 ；而合乘行程的每公里碳减排量由 （）增长至 （），减排效率提高 。综上可以看出，基于本研究提出的低碳导向的网约车合乘动态匹配算法，即使在 较大的情况下，依旧能有效提升合乘出行的减排能力。（）平均每次合乘行程碳减排量（行程）（）平均每公里合乘行程的碳减排量（）图 不同匹配算法中合乘出行平均减排强度 根据以上结果可知，若将本文所提出的低碳导向网约车合乘动态匹配算法应用于成都市网约车派单平台，相比传统算法每年可预计减少 二氧化碳排放。按目前的碳市场价格（元 吨）计算，网约车平台可增加约 万元的碳交易收益。可见，本文算法可在大幅提升网约车合乘出行减排效益的同时，有效增加网约车企业的经济效益，且随着未来碳市场价格不断提高，碳交易收益也会随之增加。因此，本文算法具有良好的应用前景和应用价值。结束语本文基于成都市中心城区的网约车订单数据，建立可合乘网络模型识别了潜在的合乘订单，并基于 机动车排放模型计算了网约车合乘行程的碳减排量，然后以潜在的合乘订单碳减排量为优化目标，提出低碳导向的网约车合乘动态匹配算法，并分别对可合乘比例、碳减排总量、碳减排强度等指标与传统合乘出行匹配算法进行了对比评估。具体结论如下：）建立的可合乘网络模型能够高效地在大规模网约车订单数据集中筛选出所有满足条件的合乘出行订单，可以帮助网约车平台充分挖掘合乘出行的潜力。）相比于排放系数或平均排放量等计算方式，利用 机动车排放计算模型可以得到路段级别的机动车碳排放量，所得结果更精准且符合现实情况，能够为低碳导向合乘匹配奠定良好基础。）相比传统网约车合乘匹配算法，提出的低碳导向的网约车合乘动态匹配算法能够在保证网约车企业经济效益的同时，显著提升了合乘出行的减排效益。当乘客最大允许延误为 时，本算法实现的可合乘订单比例达 ，合乘订单总碳减排量达 ，相比传统算法提高 ，单次合乘行程的平均碳减排量达 ，相比传统算法提高 ，单位公里合乘行程的平均碳减排量为 ，相比传统算法提高 。本文主要研究内容为燃油车辆在网约车合乘中的减排效益。然而随着机动车辆的快速电动化，网约车车队中电动车辆的占比逐渐上升。因此，在后续研究中有必要考虑电动车辆对网约车合乘减排效益的影响。参考文献：，：，（）：，：，（）：，（）：吴癑琳，袁振洲，陈秋芳，等考虑轨迹相似度的综合客运枢纽出租车合乘方法研究 交通运输系统工程与信息，（）：（，（）：）王志建，郭健，张强考虑乘客信任程度的营运车辆合乘线路规划 计算机应用研究，（）：（，（）：），（）：，：，：，（）：，：，（）：，：，：（下转第 页）计 算 机 应 用 研 究 第 卷 、等算法，不仅显著提高了机器人 定位的精度，而且相比常规语义分割动态 算法在运行实时性上取得了明显的改善，提升了 系统的精度、鲁棒性和实时性。表 和 平均跟踪时间对比 序列 结束语针对复杂动态环境下视觉 定位精度低、鲁棒性差的问题，本文提出基于场景动态分级的自适应多策略同时定位与建图算法 。首先根据对极几何约束实时判断运行环境为高动态和低动态场景，在高动态场景语义分割协同极线约束剔除动态目标上大量动态特征点和少量异常噪声点，在低动态场景引入极线约束剔除少量的动态外点，更新维护地图点的累积运动概率，消除了动态特征和地图点对相机位姿估计的影响。在公开数据集 上对算法进行了验证，实验结果表明本文算法在未知动态环境下的定位精度和鲁棒性有显著提升，且相比仅语义分割的 算法，算法的实时性得到了改善。下一步工作，将进行复杂动态环境下的高精度地图构建和维护。参考文献：，：，（）：，：，：，：，：，：，：，：，（）：，（）：，：，（）：林凯，梁新武，蔡纪源基于重投影深度差累积图与静态概率的动态 算法 浙江大学学报：工学版，（）：（，：，（）：）魏彤，李绪动态环境下基于动态区域剔除的双目视觉 算法 机器人，（）：（，（）：）何召兰，何乃超，张庆洋，等基于实例分割的视觉 算法 计算机工程与设计，（）：（，（）：），：，：，：，：，：，：，：，：，：，：，（）：，：，（）：，：，：，：，：，：，：，（）：，：，（）：，：，：（上接第 页），（）：，（）：，（）：，？，：，：，：，（）：（）：，：，：，：计 算 机 应 用 研 究 第 卷