基于延迟接受算法的电动出租车线上派单策略

2024-03-04甘少君赵远洋王燕霞

交通工程 2024年2期

关键词：等待时间出租车订单

甘少君, 赵远洋, 王燕霞

(北京工业大学城市建设学部, 北京 100124)

收稿日期: 2023-12-20.

基金项目: 国家自然科学基金资助项目(62003011).

作者简介: 甘少君(1988—), 男, 副教授, 研究方向为交通大数据分析与人工智能算法. E-mail:s.gan@bjut.edu.cn.

0 引言

随着出租车行业信息化水平的提高,线上派单的模式得到了广泛应用,越来越多的出租车司机利用线上平台开展接单业务. 出租车线上派单流程包括2个步骤:首先用户使用移动应用发起出行服务请求,然后通过派单系统的计算将订单分配给合适的司机. 与以往的路边叫车方式不同,这种方式可让用户在不用离家的情况下叫车,而且可更方便地确定出行价格和出发时间,同时节省了司机等单的时间成本,提高了车辆运营效率. 因此,高效的线上派单策略是提升用户出行体验和司机收益的关键.

在电动出租车线上派单系统中,关于订单分配的相关方法包括:通过对历史订单数据的分析,使用神经网络预测乘客的出行需求,并根据预测的结果进行派单[1-2],Liu等[3]基于图卷积神经网络预测各区域的订单需求,协调各区域内的车辆资源. 也可使用协同过滤算法来分析乘客的出行偏好向用户推荐合适的车辆. 此外,还可结合多种算法来提高出租车线上派单系统的效率[4-5]. 例如,Alisoltani等[6]提出了1种基于滚动视窗的动态优化方法,以最小化乘客等待时间. Hu等[7]提出1种结合整数线性规划和机器学习的实时调度模型,仿真结果表明应用该模型可减少车辆空驶距离.

在设计派单策略时,现有研究大多直接采用接单距离或接单时间作为决策依据,这种做法仅考虑缩短司机空驶距离或乘客等待时间,而未能综合评估订单与司机的匹配程度,从而导致派单结果难以实现全局最优. 此外,电动出租车运营是1个动态转换过程,但是现有研究在构建仿真场景时,往往忽视了车辆和乘客的行为具有动态性. 例如,乘客可能因为等车时间过长而取消订单;司机需要考虑车辆剩余电量,电量过低时将放弃接单而去充电. 因此,设计派单策略和仿真场景时,应该充分考虑车辆与乘客的实际情况和动态变化特征,以提高派单策略的准确性和适用性.

本文构建了1个考虑实际路网情况和电量约束的电动出租车运营仿真场景. 在此基础上,开发了 1个具有全局控制和监控功能的线上派单平台. 我们提出“订单评价值”指标衡量等待时间对司机接单意愿的影响,该指标可反映不同候客时间下订单对司机的吸引力;同时提出“订单期望值”指标评估不同等车时间对乘客满意度的影响. 进而以车辆接单空载里程比和订单评价值为目标建立了电动出租车司机的偏好关系,以订单期望值为目标建立了乘客的偏好关系,采用延迟接受算法求解电动出租车与订单之间的匹配问题. 通过仿真验证所设计的派单策略的有效性.

1 仿真场景设计

1.1 电动出租车运营状态设计

本文从电动出租车运营的角度,将其状态划分为以下5种:巡航状态(车辆处于待命状态,随时准备接受订单)、接单状态(车辆接受乘客订单请求,前往乘客上车地点)、载客状态(车辆正在为乘客提供出行服务)、去充电状态(车辆前往充电站或等待充电机会)和充电状态(车辆正在充电站进行充电). 5种状态及其转移关系如图1所示.

图1 车辆运营状态转换关系

1.2 订单和充电站设计

为了量化乘客与司机之间的等待行为对出行体验和收益的影响,根据乘客发起出行请求的位置,本文将订单划分为2类(如图2所示):

一类是在乘车地约单,如公交站、小区门口和交叉口. 在此类订单中,唯一的等待状态是乘客等待车辆到达.

另一类是在出发地约单,如写字楼、公园和商场内. 在此类订单中,可能存在2种等待状态:乘客等待车辆到达与车辆到达后等待乘客.

图2 2类订单关系图

为每个订单设置最大等待响应时间属性,如果平台长时间没有为订单分配车辆,超过此时间视为订单流失. 此外,本文在场景中设置订单存储池,作为订单动态产生和消耗的载体. 此外,本文在场景中设置订单存储池,作为订单动态产生和消耗的载体.

图3展示了订单池中4类订单状态,其含义如下:

超时订单表示订单产生后在订单池中的停留时间超过乘客最大等待时间,此时视为乘客取消订单;

待分配给车辆的订单表示该订单已经被线上平台明确指定给特定车辆完成;

新产生的订单表示此时研究场景中出现新的订单请求等待平台分配车辆接单;

未超时且未被分配的订单表示在上轮派单过程中没有分配给合适的车辆接单,而订单未被乘客取消,所以可继续参与本轮派单.

图3 订单池设计

为应对车辆在充电站可能出现的排队情况,本文将充电站设计为单通道多服务台(多个相同充电功率的快充桩)的充电系统,并规定车辆进入充电站后的充电行为:

1)进入排队队列后,中途不允许有车辆插队;

2)队列遵循先进先出的单向充电顺序;

3)单个充电桩不能同时为多台车辆提供充电服务.

1.3 线上调度平台设计

在仿真场景中,线上调度平台的主要任务包括如下2部分(如图4所示):

任务1:处理乘客发起的出行订单,并指派合适的车辆接单. 平台需要结合车辆状态与订单信息,使用派单策略做出最佳派单决策.

任务2:实时监控系统内各对象的运行状态. 平台需要跟踪车辆位置和电量信息、订单的起终点位置和数量信息以及充电站的空闲桩数量等,全面掌握仿真场景中各要素的动态变化状况.

图4 调度平台的主要任务

1.4 仿真系统设计

系统设计主要围绕电动出租车的充电事件、排队事件和接单事件的处理流程展开说明.

1.4.1 充电

车辆在行驶过程中会不断检查自身的剩余电量,在充电调度策略介入线上调度平台前,车辆使用临界最低电量作为触发巡航状态转移到去充电状态,车辆会前往距离最近的充电站充电.

1.4.2 排队

排队发生在车辆由去充电状态向充电状态转移的过程中,其处理逻辑如图5所示. 已到达充电站的车辆通过检查排队队列的长度,决定是否立即转为充电状态. 如果队列长度为空且有可用充电桩,车辆开始充电,否则车辆进入队列排队.

1.4.3 接单

作为触发车辆从巡航状态转移到接单状态的关键,本文从线上调度平台的角度设计派单逻辑从而实现接单的处理. 具体来说,平台会定期扫描订单存储池内所有未被服务的订单,并根据订单里程、乘客等待时间以及车辆当前位置和状态信息,指派合适的车辆完成接单任务. 在选定目标车辆后,平台会下发指令,要求该车辆前往订单起点接单.

2 派单指标的建立

为反映乘客等车和司机候客对出行服务的影响,本文提出订单期望值和订单评价值2个指标.

图5 排队的处理逻辑图

对乘客而言,适当的等车时间对出行心理的影响还在可接受的范围内. 然而,对出租车司机而言,等待乘客上车会导致有效运营时间的损失. 此外,接单距离也是其他派单平台(如滴滴打车)考虑的重要因素之一.

2.1 出发地预约订单

出发地预约订单对应的订单期望值和评价值参数如表1所示.

如图6黄线部分所示,订单期望值随等待时间的增加而减少,刚发起请求时值为1,表示乘客希望尽快有车辆接单. 随着等待时间超过T5(订单最大等待响应时间),期望值降为0,表示乘客失去耐心取消订单.

如图6蓝线部分所示,订单评价值的计算与乘客等车时间和车辆候客时间有关. 对司机而言,如果车辆过早地到达乘客上车地点,则会得到较低的订单评价值. 这部分对应于评价值曲线的T1区间.

对乘客而言,如果等车时间没有超过乘客可接受的等车时间,订单评价值会保持不变. 但是,一旦超过最大阈值,乘客会变得越来越焦虑,并给接单司机带来负面影响,因此评价值逐渐下降. 这部分对应于曲线的T2和T3区间. 评价值曲线形状为梯形,同类型订单曲线形状相近.

表1 订单期望值与评价值参数表

图6 出发地预约订单的订单期望值与评价值曲线图

按时间顺序对订单期望值和订单评价值曲线进行组合,如图7所示.

序号①代表乘客在出发地发起订单时对应的评价值曲线;

序号②代表乘客在前往乘车地途中的订单评价值曲线;

序号③代表乘客在乘车地等车的订单评价值曲线;

序号④代表乘客已经在乘车地等待一段时间,其可用的评价值曲线最短.

图7 不同时刻出发地预约订单的订单期望值与评价值曲线变化图

2.2 乘车地预约订单

乘客在乘车地预约订单,意味着乘车地点就是出发地点,所以t1和T1值为0,其他参数表示与出发地预约订单相同(如图8所示).

图8 乘车地预约订单的订单期望值与评价值曲线图

与图7表示类似,将图中序号①和序号②排除,则在乘车地预约订单的状态组合(如图9所示),即不包括乘客前往乘车地的行程时间.

图9 不同时刻乘车地预约订单的订单期望值与评价值曲线变化图

3 基于延迟接受算法的派单策略

3.1 延迟接受算法

该算法[8-10]是由David Gale和Lloyd Shapley提出的,旨在解决“婚姻市场”中的一对一双边匹配问题,同时证明了该算法所得匹配结果的稳定性,即一对一双边匹配市场中的集合A与集合B,不存在对象a∈A和对象b∈B相较于当前匹配对象,a更倾向于b,同时b也更倾向于a.该算法被广泛应用于解决双边市场的资源匹配问题.

与伴侣匹配过程类似,派单过程也需要从司机和乘客双方的角度考虑.具体来说,假设有1个包括n辆电动出租车的集合ET={et1,et2,et3,…,etn}和1个包括m个订单的集合O={o1,o2,o3,…,om}.对于电动出租车et∈ET,都存在1个关于订单集合O的偏好关系>et,o1>eto2表示在偏好排序上,et更偏向于选择o1而非o2.如果对于订单o∈O有偏好关系o>etet,则表示对电动出租车et来说,订单o是可接受的,否则我们称订单o对电动出租车et是不可接受的.同样,每个订单o也存在1个关于电动出租车et的偏好关系.

3.2 偏好关系的定义

在订单和车辆之间的偏好关系计算中,本文有如下定义:

车辆对订单的偏好值使用cevaluation+cratio,其中cevaluation是订单评价值,cratio是订单的有效里程比(衡量每个订单载客里程所占比重,值越高说明每订单空载里程越少),车辆优先选择cevaluation+cratio值高的订单.

订单对车辆的偏好值使用cexp,其中,cexp表示订单期望值,订单优先选择订单期望值高的车辆.

另外,构建偏好值序列,必须遵循如下2个约束条件:首先,车辆在完成订单后的剩余电量应大于其临界最低电量,以确保车辆正常运营.其次,订单的有效里程比必须大于0.5,以防止因接受超远距离订单而造成的亏损.这些约束条件可使我们的匹配策略更加准确地反映车辆与订单之间的关系.

3.3 算法执行

步骤1:比较订单数量m和车辆数量n,以确定请求者和接受者,如果m>n,则将车辆作为请求者;否则,将订单作为请求者.以下使用车辆作为请求者进行说明.

步骤2:计算双方的偏好值,将不满足约束条件的偏好值设为不可接受.然后依据偏好值对订单进行排序,每辆车选择偏好值最高的订单作为请求对象.

步骤k≥3:每辆车向其偏好值最高的订单发出请求,每一个订单都拒绝接受任何车辆的请求,收到一次以上请求的订单会拒绝除其偏好值最高的请求外的所有请求,如果在此步骤中没有拒绝车辆,则算法停止.否则,转到步骤k+1.

4 实例分析

本实例构建的仿真场景选取上海市黄浦区作为背景参照(如图10所示),场景中包括200辆电动出租车,19个公共充电站和121个快充桩.

图10 研究区域图

从上海市出租车全天GPS数据中提取出行订单的时空分布特征,订单数量在时间上的分布如下图11所示,出租车订单的数量随时间呈现出明显的高峰和低谷特征.

图11 出租车订单数量变化图

考虑到实际出租车全天平均接单量为30单,平均载客距离10 km,平均载客时间30 min,本实例对仿真场景中相关参数进行了调整,具体信息如表 2所示.

为了使仿真场景更加贴近实际运营状况,本实例选取16:00—22:00作为仿真时段,总时长360 min. 仿真开始前,所有车辆状态均处于巡航状态. 车辆具体位置信息和位置点间距离均使用百度地图导航数据.

通过设置更高的日均接单量(90单)和更短的平均订单距离(3.6 km)增加车辆运营强度与复杂性,可验证调度策略在复杂场景下的适用性. 此外,导航数据的应用提高了位置信息和订单距离的准确度,使仿真场景更加真实.

从车辆运营的角度进行分析,表3的结果可看出,与就近派单策略相比,本文提出的派单策略使车辆总巡航时间减少了719 min,而载客时间增加了1 794 min,这说明该策略优化了车辆运营状态,使更多车辆处于载客状态,减少了浪费在巡航状态的时间. 此外,接单时间减少了942 min,排队时间减少了171 min,这从侧面说明本文提出的派单策略加快了车辆运营状态转换的速度,在一定程度上分散了充电需求. 其他运营状态时间的变化均在10%以内,说明在释放运力的同时,本文提出的派单策略并未对车辆整体运营状态产生显著影响.

表2 实例场景参数设计

表3 车辆不同运营状态累计时间分布表 (16:00—22:00) min

表4记录了在不同派单策略下,乘客与司机之间的等待时间差异. 使用就近派单策略实现了将车辆及时派往乘客上车地点的目的,但同时增加了司机在现场候客的时间. 而在使用本文提出的派单策略后,将司机候客时间显著减少了1 725 min,同时也减少了乘客等待车辆到达的时间532 min. 这说明本文提出的派单策略在保证服务响应速度的同时,也平衡了乘客和司机的等待时间,有效减少了系统运营过程中的无效等待时间,提高了运营效率.

表4 乘客-司机总等待时间(16:00—22:00) min

为验证所设计的派单策略能有效减少订单高峰时段乘客等车时间和司机候客时间,我们选择09:00—15:00作为仿真时段. 相较于16:00—22:00,该时段内的订单量更大,系统运力更紧张,相应的车辆接单数增加. 因此,与表4的结果相比,表5中乘客等车和司机候客时间均有不同程度的增加. 但是在应用本文提出的派单策略后,乘客等车时间减少了 1 532 min,司机候客时间减少了2 509 min. 这表明该派单算法在订单高峰时段同样可起到减少系统内无效等待时间的作用.