英语原文共 15 页，剩余内容已隐藏，支付完成后下载完整资料
预约和按需请求的动态行程车辆调度
Taoan Huang1, Bohui Fang2, Xiaohui Bei3, Fei Fang4
1清华大学，2上海交通大学
3南洋理工大学，4卡耐基梅隆大学
摘要：向骑车人派遣司机和车辆的交通服务提供商开始支持实时发布的按需乘车请求和提前预定的乘车，这带来了新的挑战，据我们所知，现有工程尚未解决这些挑战。为了填补这一空白，我们设计了新颖的出行车辆调度算法来处理这两种类型的请求，同时考虑了按需请求的估计请求分布。该算法的核心是新提出的约束时空值函数(CST函数)，它是多项式时间可计算的，表示车辆在给定时间到达特定位置所需的约束条件下可以获得的期望值。在CST函数的基础上，我们设计了一个随机的最适合调度请求的算法和一个在线的按需请求规划算法。我们通过在线打车平台的真实数据集上的大量实验来评估这些算法。
1.简介
位置跟踪技术的发展、智能手机的普及以及移动网络通信成本的降低导致了移动性的革命和按需交通系统的普遍使用，对个人移动性、污染和拥堵产生了巨大的积极社会影响。最近，越来越多的交通服务提供商开始支持实时发布的按需乘车请求和提前预定的乘坐，为乘客提供更加灵活可靠的服务。例如，Uber等叫车平台根据乘客的要求实时匹配司机或车辆(我们将交替使用司机和车辆)和乘客，还允许乘客提前安排乘车时间。2018年，嘉宝、神州准车、康惠德格罗和SU珀舒特尔等公司改变了传统的打车、司机用车和班车服务，以满足这两种需求。
计划请求和按需请求的出现给服务提供商的出行车辆调度任务带来了新的挑战。接受预定的请求是一把双刃剑:一方面，这种请求减少了需求的不确定性，给服务提供商更多的时间来准备和优化这些行程；另一方面，某些预定的请求可能导致在服务它们的途中浪费时间，或者阻止分配的车辆服务更有价值的按需请求。有些系统，如优步，在提货时间到期时，只将计划请求视为常规按需请求，并直接对按需请求应用现有调度算法。然而，这种做法忽略了预定请求和按需请求之间的根本区别:一旦他们的预定请求被接受，骑车人就必须准时接车，也就是说，这是平台必须履行的承诺。许多预定的请求是为了重要的目的，比如去机场赶飞机或者参加一个重要的会议。未能提供这些服务可能会损害服务提供商的信誉及其长期可持续性。就我们所知，没有任何现有的工作可以应对这些挑战。
在本文中，我们填补了空白，并提供了第一个研究行程车辆调度的计划和按需请求。我们考虑两阶段决策过程。在第一阶段(阶段1)，系统被呈现一系列预定的请求，系统需要选择接受哪些请求，并决定如何以在线方式向接受的请求派遣车辆；在第二阶段(阶段2)，系统需要根据实时接收的按需乘坐请求调度车辆，或者建议空车辆的重新定位，同时确保阶段1中接受的预定请求得到满足。对于说明性的请求，我们假设预定的请求在所有点播请求之前收到。然而，我们的分析和解决方法适用于更一般的环境。尽管大多数关于旅行车辆调度的工作经常忽略需求中的不确定性。我们还采用数据感知的观点，并假设平台知道按需请求的时空分布，这实际上可以从历史数据中估计出来。
我们为这两个阶段提出了新的算法来处理这两种类型的请求。在这些算法的设计中，我们引入了约束时空值函数的新概念。CST函数由我们提供的多项式时间算法构造而成。我们证明了CST函数代表了车辆在最优调度策略下所能获得的期望值，其约束条件是车辆需要在未来某个给定时间到达某个特定地点。在CST函数的基础上，我们为阶段1设计了一个随机化的最佳匹配算法，以决定是否接受预先在线安排的请求。当阶段2中没有需要考虑的按需请求时，我们也给出了阶段1算法的补偿比的理论界限。此外，我们为阶段2构建了一个在线规划算法，以便在给定已接受的计划请求作为约束的情况下，根据按需乘坐请求实时调度车辆。该在线算法在多项式时间内运行，保证了单车辆情况下的最优性。当存在多辆车时，该算法依次更新CST函数以逐个调度车辆。通过在线打车平台的真实数据集上的大量实验，证明了算法的有效性。
2.相关工作
出行车辆调度已经得到了广泛的研究，但现有的工作只考虑实时按需请求或预定请求。只有预定的任务，这个问题是众所周知的拨号骑行问题(DARP)。对于仅按需请求，调度算法使用不同的方法，例如贪婪匹配、协同调度、规划与学习框架、后悔控制方法等。我们的工作是首先考虑这两种类型的请求，这导致了两个阶段的决策过程。虽然我们的阶段2问题与仅按需请求的调度问题有相似之处，但阶段1中接受的计划请求带来了难以处理的困难。现有算法的简单扩展到我们的设置并没有实现良好的性能，如我们的实验所示。
我们的第一阶段问题与在线包装/覆盖问题密切相关：在线斯坦纳树、在线二分图匹配和在线流量控制包装。尽管有相似之处，但由于问题中的时空限制，这些结果或技术都不能直接应用到我们的环境中。
其他相关工作包括2014年最后一英里运输的努力、协调调度和定价等研究重点不同。
3.建模
我们考虑一个离散时间、离散位置模型，其中有单容量车辆和不耐烦的乘客。我们在第6节讨论假设的放宽。
[T] = {1，hellip;，T}是一组时间步长，代表离散化的时间范围。[N] = {1，..，N}是不同位置或区域的集合，我们用delta;(u，v)，u，v isin; [N]表示从u到v的最短旅行时间，D表示车辆集合。每个车辆c isin; D与时间-位置对(tc，oc)和(tcrsquo;，ocrsquo;)相关联，其中tcisin;[T]表示可以调度c的最早时间，ocisin;[N]表示其初始位置。类似地，(tcrsquo;，ocrsquo;)被定义为时间-位置对，表示c何时何地结束其服务。
我们采用两阶段模型来处理计划请求和按需请求。在第1阶段，系统接收一系列预定的请求。调度请求r由元组(or，dr，t r，vr)描述，表示从起点或目的地dr请求的需要在时间tr开始的旅程，vr表示平台将接收到的用于服务该请求的值。我们假设当提出请求时，虚拟信号被给予系统，例如，由附加者或外部定价方案提供。当预定的请求到达时，平台应该接受并将其分配给特定的驱动程序，或者拒绝它，需要在下一个请求到达之前立即做出决定。我们假设某一天的预定请求都将在当天开始前完成。我们将在第6节讨论这个假设的放宽。假设Rc表示在阶段1结束时分配给c isin; D的一组已接受的计划请求，并定义R=cup;Rc。Omega;. l. o. g.，我们假设车辆总是通过在Rc中服务计划请求来结束其服务。如果不是，则可以将请求时间和来源对应于(tcrsquo;，ocrsquo;)的虚拟计划请求添加到Rc.。
在阶段2中，系统开始接受由元组(or，dr，t r，vr)描述的实时按需请求，与计划请求相同。我们将按需请求的类型定义为(or，dr，t r)，并让Omega;为所有可能类型的集合。我们假设类型omega; = (o，d，t)的按需请求具有相同的值Vomega;(或Vo,d,t),并且Vomega; forall;omega; isin; Omega;是系统预先知道的。这是一个合理的假设，例如，omega;型旅行的价值变化很小，可以从历史数据中估算出来。注意，这些请求是实时接收的，即请求r将在时间t r出现。当在时间t收到一组按需请求Rt时，平台需要立即为每个请求做出决定(1)将请求发送到当前位置的可用车辆c，或者在这种情况下，车辆c将开始服务请求，并在时间tr delta;(or，dr)，(2)的位置dr再次可用或者拒绝该请求。在处理这些按需请求的过程中，平台还需要确保之前接受的所有预定请求必须在各自的预定时间由各自的驱动程序提供服务。在第二阶段，我们还允许在没有请求的情况下调度车辆时将车辆重新定位到位置d。在这种情况下，车辆将以它正在接受目的地为d且值为0的虚拟请求的方式运行。
该系统的目标是最大化所有已接受请求的总价值，包括计划请求和按需请求。由于计划请求的不规则性，我们不假设计划请求分布的任何先验知识，但是我们假设实时按需请求的分布是已知的或者可以从历史数据中估计。让独立随机变量Xomega;表示。
系统在第2阶段接收的omega; isin; Omega;类型。对于所有omega; isin; Omega;和i isin; N，按需请求分布被描述为Pr[Xomega; ge; i]。
4.解决方法
系统需要为出行车辆调度部署两个算法，每个阶段一个。至关重要的是，第一阶段接受的预定请求将作为第二阶段的限制。考虑只有一辆车的最简单的设置。如果系统已经接受了预定请求r，则在阶段2中，当系统在r的开始时间之前接收到按需请求rrsquo;时，系统是否应该调度车辆来服务r取决于(i)车辆在完成r的行程之后是否仍然可以服务rrsquo;，(ii)如果服务r它可以获得多少，(iii)如果它不服务于r，它可以获得多少。事后看来，系统是否应该接受预定请求r取决于阶段2中的预期增益，是否对r作约束。
基于这种约束，在这一节中，我们将首先引入一个新的概念CST函数，它代表了在第二阶段中系统中唯一的运载工具在被承诺服务于预定任务时的预期增益。然后，我们将介绍阶段2的算法，接着是阶段1的算法，两者都基于CST函数。
4.1 CST-功能
当系统中只有一辆车时，第二阶段的系统决策问题可以建模为马尔可夫决策过程(MDP)。让c成为系统中唯一的载体。系统面临由(S，A，P，V)定义的MDP，其中S是状态集，A是动作集，P是状态转移概率矩阵，V是奖励函数。被接受的调度请求Rc集合应该被可靠地服务，并且我们在服务和服务的定义约束S和A。
状态s isin; S由(t，l，Rt，l)定义，其中tle;t crsquo;是时间，l是等待调度的车辆的位置，而Rt、l是当前接收的点播请求的集合，该请求可能由车辆提供服务，同时确保为调度的请求提供可靠的服务。给定一个请求r，将D(t，l|r) := {d : d isin; [N]，delta;(l，d) delta;(d，or)le;tr-t }定义为车辆可以从l出发的一组位置，以便他在到达该位置后能够到达(or , tr)。然后给定Rt和Rcrsquo;，有Rt，l = {r : r isin;Rt，或0 = l，dr isin; D(t，l | Rcrsquo;)，tr = t}其中rcrsquo; isin;Rc是对c的最早调度请求，其提取时间在时间t或之后。
设A(s)是状态s = (t,l,Rt,l)下的一组可用动作。如果请求的接收时间为t，则s处唯一可用的操作是将车辆分配给rcrsquo;，否则，A(s)由两种类型的操作组成:将c标记为请求rrsquo;isin;Rt,l，或将c重新定位为位置lrsquo; isin; D(t，l | rtc)。状态转移概率P ass = Pr[Stau; 1 = srsquo; |Stau; = s，Atau; = a]不为零，仅当车辆在s处采取行动a后在s的(trsquo;，lrsquo;)处再次可用，并且P ass= Pi;omega;isin;w Pr[Xomega; = Xs，omega;]，其中Xsrsquo;，omega;是在Rt，Rsrsquo;,lrsquo;状态srsquo;中的omega;型请求的数量。如果响应调度c到预定或按需请求r，则立即奖励V a s为vr，并且策略pi;下的状态值函数和状态动作值函数分别用vpi;(s)和qpi;(s，a)表示。MDP的总收益被认为是总价值的总和，不应用因子。
给定(t，l)处的车辆，r (tr ge; t)是要求其服务的下一个请求，我们通过算法定义CST函数CST(t，l|r)，以计算它，如算法1所示。我们将首先展示CST函数的一个重要性质，而不是通过算法。
引理1.如果Rc只包含一个(真实或虚拟)请求r，则由算法1计算的CST()满足：
CST(t，l|r) = ERt，l [vpi;(t，l，Rt，l)]
其中pi;是最佳策略，并遵循：
qpi;(s，a) = V a s CST(ta，la|r)，
其中(ta 剩余内容已隐藏，支付完成后下载完整资料
资料编号：[234942]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
