中南大学现代远程教育课程考试複习题及参考答案

19.在选购主板时应遵循的策略有[ ]

20.字符图形显示错误或花屏主要是由[ ]

共享移动应用程序出现了大幅增長例如共享汽车，食品配送和众包包裹递送共享移动性是指在用户之间共享的传输服务，其中一个核心问题是路线规划给定一组工囚和请求，路线规划为每个工人找到一条路线即一系列用于接收和放下不时到达的乘客/包裹的位置并具有不同的优化目标。以前的研究缺乏实用性因为它们的目标相互冲突，并且在将新请求插入路径时效率低下是一种称为插入的基本操作。在本文中我们提出了一种稱为URPSM的统一路线规划方案。它具有明确定义的参数化目标函数消除了先前研究中的矛盾目标，并为共享移动性的实现提供了灵活的多目標路径规划我们证明该问题是NP-hard的，并且以前没有针对URPSM问题及其其他变化提出具有恒定竞争比的多项式时间算法为此，我们设计了一个囿效且高效的解决方案来解决URPSM问题我们设计了一种新颖的动态规划（DP）算法，以便将插入操作从之前的立方或二次时间加速到仅为线性時间在DP算法的基础上，我们提出了一种基于贪婪的URPSM问题解决方案实际数据集上的实验结果表明，我们的解决方案在效率方面优于现有技术1.2至12.8倍并且运行速度提高了2.6至20.7倍。

共享移动性是指用户共享的运输服务例如共享汽车，食品配送和众包包裹递送[38] 共享机动性通过妀变路线和利用未充分利用的车辆可减轻污染，降低运输成本并提供最后一英里交付解决方案[45]。 它被预测为城市交通的有效和可持续的替代方案
现实共享移动性的关键是工作者和请求之间的路径规划。 工人可以是共享汽车服务的司机或食品和包裹递送服务的快递员请求包括出发点和目的地及拾取放下信息。 路线规划为每个工人找到一条路线即一系列位置，用于拾取和放下动态到达的乘客/包裹具有鈈同的优化目标。
共享移动的路线规划吸引了来自数据库数据挖掘和交通科学界的广泛研究兴趣。 大多数研究考虑以下目标中的一个或┅个子集：（i）最小化总行程距离[30] [25] [34] [41] [40] [24]; （ii）最大化服务请求的数量[19] [47] [21] [29] [40] [24]; （iii）最大化总收入[13] [14] 许多解决方案都是启发式的，并且依赖于插入操作该操作将新请求的原点和目的地插入到当前路径中[30] [25] [41] [34] [19] [47] [40] [18]]。 在实践中先前的研究具有以下限制。
限制1.现有提案有时会采用多个模糊甚至冲突的优囮目标 例如，在[30] [25] [34] [40] [24]中目标是最小化请求的总行程距离，但未指定至少提供多少请求 因此“最佳”解决方案是根本不提供任何请求，这與常识和最大化所服务请求的数量的目标相矛盾 各种现实世界的共享移动性应用都期望拥有灵活且优化目标一致的统一路由规划问题。
限制2.现有解决方案[30] [25] [47] [18] [31]中的插入操作对于大规模共享移动平台来说效率低下 将新请求插入路径至少需要平方时间，这使得插入成为在实际应鼡程序中处理大量请求的瓶颈
为了解决这些限制，我们定义了一个新问题共享移动统一路由规划（URPSM）。 它将主流优化目标统一到一个奣确定义的目标函数中其中各个目标是兼容的。 URPSM问题可以灵活地调整特定应用程序的优化目标 我们发现，上述的三个优化目标可以作為URPSM问题的特殊情况解决
由于许多路径规划算法的效率瓶颈是插入操作，所以我们设计了一种新的动态规划（DP）算法将时间复杂度从立方或二次[18] [30] [25] [19] [47]降低到线性。 关键是动态规划可在O（1）时间内找到最佳拾取位置
此外，与先前忽略分析复杂度不同我们对URPSM问题进行了系统的悝论分析。 我们澄清并证明没有算法能解决具有URPSM问题的恒定竞争比率问题及其在先前文献中研究的特殊案例[30] [25] [18]。 我们最终为URPSM问题设计了一種有效且高效的启发式解决方案
我们的主要贡献可归纳如下。

• 我们通过明确定义的参数化目标函数抽象出能解决共享移动性的路径规划問题的统一公式即URPSM。 它消除了先前研究中的矛盾目标并可以解决实际共享移动应用中的灵活多目标路线规划。
• 我们设计了一种新颖的動态规划（DP）算法来加速插入操作 我们的算法将此基本操作的时间复杂度从立方或二次曲线减少到线性。
• 我们全面分析了URPSM问题及其近似問题的难度 具体来说，我们证明了URPSM问题及其特殊情况不存在具有恒定竞争比的多项式时间算法 结果可作为分析其他路线规划问题和指喃的参考，并可用于设计URPSM问题的有效解决方案
• 我们使用基于DP的插入来设计有效且高效的解决方案，以解决URPSM问题
• 对真实数据集的广泛实驗表明，我们的解决方案比现有技术的速度快2.6到20.7倍效率提高1.2到12.8倍[25] [11]。

在本文的其余部分我们在第2节中回顾相关工作，在第3节中定义URPSM问题並讨论其广泛性和难度在第4节中提出了基于动态规划的插入操作。在第5节中设计了URPSM问题的完整解决方案 最后，我们在第6节中评估在苐7节中总结。

关于共享移动性（RPSM）的路径规划的研究可以追溯到1975年提出的拨号问题[43] [44]并且已经由数据库，数据挖掘运输科学社区进行了研究。 本节简要回顾了RPSM问题的不同变体及其解决方案
RPSM问题的一个重要设置是静态还是动态。 在静态（离线）RPSM问题中工作人员和请求的信息是事先已知的。 相反在动态（在线）设置中，工作人员或请求会动态显示并且需要在短时间内甚至立即提供请求。 动态RPSM问题更符匼现实世界的共享移动应用的需求[30] [25] [41] [34] [47] [19] [13] [14]并将成为我们的主要关注点。
RPSM问题的主流目标包括最小化总旅行距离[16] [23]最大化服务请求的数量[29] [47] [19] [40]，最大囮总收入[13] [14]等 总行程距离是计算工人因请求行走的总行程距离。较小的总行程距离表明行程成本低污染小[10]。大量服务请求可提高共享移動提供商的收入[47] 更常见的目标是在提供所有请求时最小化总行程距离[30] [25] [41] [34]。 其他研究的重点是最大化共享移动提供商的总收入（服务请求的總支付额减去工人的总工资）[13] [14]最小化完工时间（最后一次请求的完成时间）[12] [22]，或最大化工人和请求之间复杂的社会效用[18] 我们的目标是汾析主流目标之间的关系，并将它们整合到一个兼容和灵活的表述中
目前已经提出了许多动态RPSM问题的解决方案[30] [25] [41] [34] [47] [19]，其中一种称为插入的核惢操作被广泛使用 郑等人 [30] [41]使用枚举策略搜索最佳插入位置，该位置需要满足插入请求的约束 由于对请求数量的额外限制，可以进一步減少可行插入但也可能错误地删除最佳插入[34] [37]。 并行性也可于加速插入[34] 插入经常用于解决大规模动态RPSM问题。 然而插入具有二次或甚至彡次时间复杂度，这是效率的瓶颈 这促使我们设计线性插入算法。
为了解决动态RPSM问题郑等人 [30] [41]首先通过网格索引搜索一组候选工作者，嘫后以最小的增加距离将请求插入候选人 黄等人[25]提出了动态数据结构来存储所有可能的路线，并使用类似的插入程序来最小化总行程距離AlonsoMora等[11]采用基于批处理的方法首先将一些请求分成小组，然后将一组请求插入到一个工作者的路径中 但是，这些研究不适合大规模共享迻动应用 在新的线性插入操作的基础上，我们提出了一个完整的RPSM问题的启发式解决方案这比这些研究都更有效和高效。

旅行成本可以昰距离或平均旅行时间这个成本可以从OpenStreetMap [6]或大型历史轨迹挖掘[48]获得。 我们在本文中将交替使用旅行时间和旅行距离 我们将 d i s ( u , v ) dis(u,v) Kr?表示容量。咜是在共享移动平台(简称平台)上发布的 t r t_r er?表示截止日期，请求需要在这之前送达如果 ( i ) (i) dr?处，则请求被送达如果请求未被送达(或被拒絕拒绝)，平台将受到处罚 p r p_r 请求的容量Kr指定在一次请求中共乘的乘客人数或快递服务中的项目数需要注意的是，在实际应用中可以有两个截止日期即收件和交付的截止日期。然而送货的单一期限通常就足够了，因为收件的最后期限可以表示为 e r ? d i s ( o r , d r ) e_r?dis(o_r, d_r) er??dis(or?,dr?)如果有一个緊迫的截止日期，很难满足每个请求(例如5到6分钟的共乘时间[30][13])。那么平台可以拒绝某些请求这会导致损失，即罚款 R={r1?…r∣R∣?}表示所有請求使用 R+=?w∈W?Rw?表示为所有服务请求，并将 (iii)在任何时间在这条路线上被接载但未交付的乘客/物品的数目，不超过该工人的运载容量则路径是可行的。
S_w Sw?的总行程其中

定义5 （URPSM）。给定一个公路网一组工人 W W W，一组只有在他们被释放时才知道的请求和一个权重系数 α α αURPSM问题是为每个工人寻找一条 S w 并且满足下述限制： ( i ) (i) (i)可行性限制：每个工人都被安排一条可行路线； ( i i ) (ii) (ii)恒定限制：一旦请求被拒绝，它们僦不能被撤销否则，他们必须得到服务

我们用下面的例子来说明URPSM问题。 v1?V8的道路网络上如图1所示。顶点的坐标(纬度和经度)也有标记例如， v 1 pr?1=20URPSM问题为每个工人规划了路线，并将统一成本降到最低这包括总行程和对未得到服务的请求的惩罚。
接下来我们证明了以湔的许多研究都是具有特定 α α α和 p r p_r pr?设置的URPSM问题的特例。

?r∈Rpr?=∞，最小化 ?r∈Rpr?=1，最小化 E q . ( 1 ) Eq.(1) Eq.(1)等于尽量减少未送达请求的数目(即最大限度地增加已送达请求的数量)假设任何r的惩罚为pr=1。
• 最大限度地增加总收入[13][14]平台的总收入包括工人的收入和服务请求的费用。工人的收叺与总工作时间(或旅行距离)和单位时间 c w cw cw的收入有关服务请求的费用与旅行距离和单位距离 c r cr cr的费用相关。然后计算平台的总收入如下：
  由於请求是给定的(即第一个项是常数)最小化 U C ( W ， R ) UC(WR) UC(W，R)就等于使总收入最大化

我们在表2中总结了主要的符号。

本节分析了URPSM问题及其变体的竞爭难度URPSM问题是NP-hard问题，因为它推广了现有的NP-hard问题[30].然而对竞争难度的研究却很少。唯一已知的结果[13]证明了不存在确定性算法可以保证总收益最大化的恒竞争比但其结论是否适用于随机算法尚不清楚。我们通过研究随机算法是否能保证对不引人注意的对手保持恒定的竞争比來分析竞争的难度[15]如果不存在这样的随机算法，那么任何确定性算法也不会存在[15]
定理1给出了我们的主要结论。
定理1. 下列URPSM问题的特殊情況对于任意一个随机问题都没有恒定的竞争比
我们分别用引理1、引理2和引理3依次证明了定理1中的三种陈述。、
α=0?r∈R，pr?=1时随机算法和确定性算法都不具有恒定的竞争比。
证明. 我们只需证明任何随机算法都不能保证恒竞争比我们首先生成输入的分布，并证明任何确萣性算法在这个输入上的期望值不是常数(例如 ∞ ∞ ∞)。然后应用姚的原理[46]，没有随机算法有一个恒定的竞争比
请求、工人和路网的苼成的分布如下所示： ( i ) (i) (i)假设道路网 G G G是一个无向环图，其维数为0且每条边的长度为1。 \mid tr?=∣V∣上被释放其原点 ∣v∣的顶点，所以在最优解Φ的工作人员有足够的时间(即 ∣ V ∣ \mid V\mid ∣V∣)来到达或释放请求 r r r。因此 r r 考虑一个通用的确定性在线算法ALG，当 r r r被释放时它的工作人员位于点(鈈是顶点) u u u。只要 u u u和 o r α=cw??r∈R，pr?=cr?×dis(or?,dr?)时随机算法和确定性算法都不具有恒定的竞争比。
证明. 我们通过调整引理1的证明中分布的设置来证明引理2具体来说，我们为请求 r r r生成分布 d r d_r dr?总是从圈图中的一个顶点集中选择其距离到 o r o_r ∣V∣/2。因为在无向循环图上与工人位置囷 o r o_r dis(or?，dr?)=∣V∣/2工人将移动另一个 ∣V∣/2+∣V∣/2=∣V∣。我们还假定有足够大的 cr?>2cw?否则当工人的总距离接近于 ∣ V ∣ \mid V\mid ∣V∣时，最优解可能会拒絕r那我们就有了
因此，无论是随机算法还是确定性算法都没有恒定的竞争比
α=1，pr?=∞时随机算法和确定性算法都不具有恒定的竞争仳。
证明. 我们利用引理1的证明中的分布证明引理3根据前面的分析，在这种分布下最优路径的总距离是有界的,为 ∣ V ∣ \mid V \mid ∣V∣，任意的确定性算法都有 pr?=∞,上述比率无界

虽然对于URPSM问题，目前还没有一种有效的解决算法(SEC.3.3)以插入为基础的解决办法对URPSM问题[30][25][41][34]的变体实际上是有效的。然而在大规模动态共享移动应用中，插入操作也是一个效率瓶颈本节对插入操作进行了形式化定义，并提出了一种新的基于dp的算法以提高算法的效率。

插入最早是在[32]中提出的用于车辆路径问题(VRP)[20]，该问题为一组车辆安排最佳路线以便将给定的一组请求(乘客)发送到鈈同的城市。基于插入的解决方案的思想是通过一次插入一个顶点(城市)来迭代地排列车辆的路径这一思想可以通过一次插入两个顶点(即請求的起源和目的地)来扩展，并已被用于设计拨号-a-平顺问题及其变体[27][28][36][26]的启发式解虽然该插入是为单个工作人员的路由规划提出的，但它吔被广泛地应用于多工人路线规划中其中基于插入的路由规划是针对每个工人单独执行的[18][30][25]。
形式上我们在[27][28]中的约定之后定义插入操作洳下。
定义6 (插入)给出了一个由n个顶点组成的新请求r和一个由n个顶点组成的新路由w，该插入操作的目的是通过将 o r , d r o_r,d_r S_w Sw?中从而使在 S ? S^? S?中嘚顶点顺序保持不变，找到一个新的可行路由 S ? S^? S?以最小的增加距离来进一步服务r。
通过插入一对起点和目的地的最小增加距离它吔最小化了总旅行距离。因此该目标与我们的URPSM问题一致，该问题将加权总距离和未服务请求的惩罚最小化本文首先回顾了文献[27]中提出嘚基本插入，然后设计了一种具有二次时间复杂度和线性记忆复杂度的朴素的基于DP的插入并设计了具有线性时间复杂度和记忆复杂性的妀进版本。

在[27][28]中提出了基本插入但没有对效率进行优化。它的思想是： ( 1 ) (1) (1)列举所有 o r o_r 说明基本插入在第1行中，在没有可行路由的情况下將一个新的路由 S ? S^? S?初始化为 S w S_w Sw?。在第2-3行中我们列举了所有可能的拾取地点(在 S w S_w Sw′?，并检查它是否可行.如果是我们计算它的增加距離 Δ i ， j Δ_{ij} Δi，j?并将其与当前最小 Δ ? Δ^? O(n)时间内的容量和截止日期限制。如果没有则需要 O ( n ) O(n) O(n)时间来计算第6行中增加的距离。第5-6行涉忣最短距离查询上述分析假设一个最短距离查询需要 O ( 1 ) O(1) O(1)时间，就像许多以前的研究[11][13][18][33]一样这一假设是合理的，因为像滴滴[3]这样的现实世界Φ的共享移动公司将最短距离查询视为恒定时间的基本操作除非明确规定，否则我们将在本文其余部分采用这一假设第5-7行检查

4.3 基于朴素DP的插入

Δi，j?因为它将用于检查新路线的可行性。

lk?之间时增加的距离因此，可以用图2中的绕行在 O ( 1 ) O(1) 2c 2c是一般情况

ddl[k]表示为在不违反任哬截止日期限制的情况下到达 l k l_k lk?后所有最后期限的最大容许时间(即松弛时间)。由于 l k l_k lk+1???，ln? 条件(1)检查是否违反了新请求 r r r的截止日期約束；如果 o r o_r or?插入到第 i i i次 , 条件(2)检查是否违反了所有其他请求的任何最后期限约束。类似地条件(3)检查如果在 j ? t h j-th dr?，是否违反了所有其他请求的任何最后期限约束有关更多细节，我们请读者参阅[42]
Kw??Kr? . 我们还需要检查是否存在任何整数 Kw??Kr?。由于请求 r Kw?这违反了 w w w的容量约束。

4.4 线性基于DP的插入

本节提出了一种改进的基于DP的线性时间复杂度插入(简称线性DP插入)它在不列举所有可能的插入位置(i，j)的情况下鉯最小的增加距离找到路径。线性DP插入是建立在朴素DP插入的基础上的但它利用了两个洞察力。 ( i ) (i) O(1)时间通过动态规划找到最佳 i i i如图2C所示。苐一个洞察力是微不足道的因为检验 S w ′ O(n)时间来寻找可行的路径，且增加的距离最小在下面，我们主要解释了第二个洞察力

(j)，以找到朂佳路由将 Δ j ? Δ^?_j Δj??表示为给定j的最小增加距离。对于图2C中的一般情况
i<j之间的最小绕行。线性DP插入的关键是找到一个可行的 i i i使O(1)时间内的第二项最小化。

j满足容量约束和最后期限约束则得到了固定 j j j的最佳可行路径。但是如果Plc[j]违反了某些约束，则不知道是否有特定的 i ≠ P l c [ j ] i \neq Plc[j] Plc[j]违反容量约束(等式12的第一个条件)根据引理5，任何 i ≤ j ? 1 i≤j?1 i≤j?1也将违反容量约束接下来，假设Plc[j]违反最后期限约束(等式12的第二個条件)假设相反，存在 i ′ &lt; j

算法3. 说明了线性DP插入的过程在第4行中，我们使用与算法2相同的方式处理i=j时的情况在第5-7行中，我们首先通过嶊论1检查给定的 j j j是否存在一个可行的 i i i如果是，我们计算了最小增加距离 Δ j ? Δ^?_j Δj??及其相应的 i(即Plc[j])在第8行中，我们根据引理4剪枝動态更新

这一部分给出了我们提出的算法的实验评估。

数据集.我们对两个真实的全市出租车数据集进行了实验评估第一篇是由中国成都滴滴出行[3]收集的，它是通过Gaia倡议[4]出版的第二种是从美国纽约市两种类型的出租车(黄色和绿色)中收集的公共数据集[8]，并在以前的大规模共塖研究中用作基准[11][13][39][41]我们使用当天的数据，要求评估的次数最多(2016年11月18日在成都2016年4月9日在纽约)，分别表示为成都和纽约两个数据集中的烸个元组都是一个由拾取地纬度/经度、放置地纬/经度和释放时间组成的出租车请求。由于只有NYC包含请求容量 Kr?在纽约的分布情况为成都生荿 K r K_r Kr?纽约的公路网是从Geofabrik[5]下载的。对于成都我们使用最新的城市边界[1]，并从Geofabrik通过OsmConvert[7]从中国的国家公路网中提取出它的公路网[7]每个路网都表示为无向图。表4总结了每个图中的请求数以及顶点和边的数量“纽约公约”是现有研究[25][17][41][18][30][11][13]中最大的数据集。例如“纽约公约”中的件倳，比[25][17]中使用的公路网大6.6倍和11.1倍“纽约公约”的请求数量比[41]多47.7%。成都拥有比现有文献更大的路网和可比的需求
成果.我们模拟了在[25][13]中的設置下具有代表性的共享移动应用程序。每个请求的起源和目的地都预先映射到道路网络中最近的顶点从路网中的顶点中随机选取工人嘚初始位置。当员工请求服务时他/她按照计划的路线移动到目的地。由于的士通常在不同类型的道路上以不同的速度行驶例如23米/秒的高速公路或6米/秒的住宅街道，我们为每一种道路指定一个恒定的速度即其城市最高法定车速的80%[2]，并假定出租车在不同类型的道路上以不哃的速度行驶表5总结了实验的主要参数。默认值以粗体标记交付截止日期计算为表中的参数添加的请求的释放时间。例如具有发布時间 Kw?是使用μ=3，···20的高斯分布产生的，因为两个数据集都没有指定这些信息我们将α修正为1，使得方程中 U C ( W R ) UC(W，R) UC(WR)的第一个项相等於总行程。请求的惩罚由表中的参数乘以请求的起源和目的地之间的最短距离来设置例如，缺省情况下 p r = 10 × pr?=2??，50(×dis(or?dr?))，这相当於在总收入最大化时调整 ∣ W ∣ \mid W\mid ∣W∣都比成都要大因为他们拥有更大的道路网络和司机数量。
实验在40 Intel?Xeon?E5 2.30GHz处理器的服务器上进行该处理器支持超线程，内存128 GB该仿真实现是单线程的，成都和NYC的总运行时间(不包括最短路径和距离查询的空间索引和标签)限制在10/20小时根据[25]关于實时乘车共享的一些工作的结果，实时解决方案应该在时间限制之前停止所有算法都是用GNU C++语言实现的。每个实验设置重复30次并报告了岼均结果。我们只通过加权邻接表存储路网的顶点和边(即图)最短距离查询和最短路径查询都是在运行中进行的，使用了一种基于集线器嘚道路网络标记算法[9]LRU缓存[25]用于最短距离和路径查询，并由所有算法使用
比较算法.我们将pruneGreedyDP与以下最先进的算法进行了比较。

• tsahre[30].它首先通过搜索过程过滤工作人员然后应用基本插入来查找每个新请求的增加距离最小的工作人员。
• kinetic[25].它使用一个动态树来维护所有可能的路由以垺务所有剩余的请求。与tshare不同插入操作是基于树结构递归执行的。
• batch[11].它首先在一个批处理中生成一组请求(例如6秒)并对组进行排序。然后通过将每个请求插入到当前工作人员的路由中，贪婪地分配每个组中的请求最后选择能够以最小的增加距离服务更多请求的工作人员。

(∣R+∣/∣R∣)和响应时间(处理单个请求的平均等待时间)(Resp)进行评估服务速率和响应时间是许多大型实时搭便车方案[30][25]中的衡量标准。我们还评估了每种算法的内存开销请注意，与图形、缓存和网格索引的大小相比可以省略辅助数组的内存使用情况。由于图和缓存的内存开销對于每种算法都是恒定的因此我们只在改变网格g的大小时计算网格索引的内存开销。我们还评估了剪枝与GreedyDP之间保存的最短距离查询(简称距离查询)的数量以显示剪枝策略的有效性。

图3示出了改变工人数量的结果整体而言，在统一成本方面在成都和纽约,pruneGreedyDP的表现比其他公司高出12.41%至85.36%。所有算法的统一成本随着工作人员的增加而降低因为可以满足更多的请求。出于同样的原因所有算法在这两个数据集中的垺务率都会增加。pruneGreedyDP有最高的服务率——54.94%比batch高141.61%。成都市的服务率结果表明当服务请求数量最大化时，pruneGreedyDP可与kinetic竞争并且明显比batch好对于较大規模的道路网络，所有算法的服务率都显著降低这与引理1一致，即服务请求的数量受到了 ∣W∣的增加而增加tshare是最快的，因为它的搜索過程错误地删除了许多可能的工作人员从而导致了最低的服务率(从1%到16%)。pruneGreedyDP是第二快的比kinetic和batch快2.46到32.08倍。请注意在20h内，kinetic不能完成模拟而在 ∣W∣=40k和50k的情况下。采用所提出的剪枝策略纽约市的最短距离查询总数从52.7亿条增加到422.2亿条，成都市从22.6亿条增加到451.6亿条因此，pruneGreedyDP的响应时间仳GreedyDP平均快2.76倍验证了我们的剪枝策略的效率。
图4显示了改变工人能力的结果随着容量的增大，所有算法在成都的统一成本都较低我们嘚pruneGreedyDP算法的统一成本比其他算法低71%。kinetic不能在大 K w K_w Kw?的情况下停止因为它的指数时间复杂度为 ( 2 K w ) ！ (2K_w)！ (2Kw?)！[17]。相比之下batch更稳定，统一成本略有下降就服务率而言，pruneGreedyDP仍是最好的比其他的高出96%。就响应时间而言tshare是最快的，其原因与改变员工数量的原因相同在成都市，pruneGreedyDP的反应时間比kinetic和batch缩短41%-95%在纽约减少47%-93%。
图5绘制了改变网格大小g的结果在统一成本方面，kinetic和tshare对网格大小的变化都相对不敏感pruneGreedyDP在这两个数据集中输出嘚统一成本最低。就服务率而言成都市的batch产量几乎一直保持在40.1%，纽约的产量为25.7%在两个数据集上，pruneGreedyDP的服务率最高分别比成都市的基线高出3.0%和87.6%，在纽约则分别高出16.9%和96.5%同样，tshare的响应时间最短但服务速率极低。在响应时间上kinetic和batch处理速度分别是pruneGreedyDP的3.11倍和25.98倍。对于网格索引的內存使用tshare在NYC的消耗最大，在609.46到5.38MB之间在成都，在9389.72到326.98 MB之间而其他的在成都和NYC的消耗分别高达0.30MB和3.23MB。这是因为其他算法的网格索引只在网格Φ存储工作人员的ID而不是像tshare这样的排序网格列表。
图6示出了改变截止日期er的结果随着最后期限的增大，所有算法的统一代价降低而算法的服务率增加。其原因是较长的最后期限可以提供更多的请求，从而降低统一费用和较高的服务费率就效益(统一成本和服务率)而訁，pruneGreedyDP仍然是最好的请注意，当α=1且服务率接近100%时统一成本接近总行程。因此pruneGreedyDP产生的旅行距离比kinetic[25]和tshare[30]小。batch和pruneGreedyDP的响应时间稳定而其它处悝的响应时间显著增加。当 ms以内这是因为，使用新的修剪策略在成都节省了24.95至83.99亿次最短距离查询，在纽约省了16.43至579亿次查询
图7示出了妀变惩罚的结果。所有基线的统一成本随代价的增加而增加而修剪的代价总是最小的。这表明当 c r c_r cr?和 c w c_w cw?之间的比例变化时，当总收入朂大化时pruneGreedyDP实际上仍然具有竞争力。kinetic的服务率略有增加因为较高的惩罚可能会迫使它尝试提供更多的请求，即在决策阶段 p r p_r 结果总结.我们總结我们的实验结果如下

• 我们的pruneGreedyDP算法通常比三种最先进的算法[25][11]的统一成本低1.2到12.8倍，同时能够在大规模数据集中服务更多的请求(至少高出9%)这些结果验证了我们的解决方案在多目标路径规划中的有效性。
• 在最先进的技术中kinetic[25]由于其指数时间复杂性，常常无法在大规模数据集仩停留时间batch[11]的有效性和效率不如我们的解决方案，但在大规模数据集中比kinetic更可扩展tshare[30]总是响应时间最快，但服务速率最低统一成本最高。

在本文中我们提出了URPSM问题，即共享移动性路由规划的统一公式它提供了一个灵活的多目标函数，可以将现有研究中的主流优化目標归结为URPSM问题的特殊情况我们证明了不存在具有恒竞争比的多项式时间算法来解决以往研究中提出的URPSM问题及其变量。由于插入是许多现囿路由规划方案中的一种基本而效率低下的操作本文提出了一种新的基于动态规划的算法，该算法将插入的时间复杂度从三次或二次时間降为线性时间然后，我们设计了一个有效和高效的两阶段解决方案利用上述基于DP的插入算法来近似地解决URPSM问题。在实际数据集上的夶量实验表明我们提出的解决方案在有效性和效率方面都远远超过了目前的技术水平。本文为共享移动环境下的路由规划提供了全面的悝论参考为今后的研究提供了新的机遇，为大规模共享移动应用设计有效的解决方案提供了新的思路

共享移动应用程序出现了大幅增長例如共享汽车，食品配送和众包包裹递送共享移动性是指在用户之间共享的传输服务，其中一个核心问题是路线规划给定一组工囚和请求，路线规划为每个工人找到一条路线即一系列用于接收和放下不时到达的乘客/包裹的位置并具有不同的优化目标。以前的研究缺乏实用性因为它们的目标相互冲突，并且在将新请求插入路径时效率低下是一种称为插入的基本操作。在本文中我们提出了一种稱为URPSM的统一路线规划方案。它具有明确定义的参数化目标函数消除了先前研究中的矛盾目标，并为共享移动性的实现提供了灵活的多目標路径规划我们证明该问题是NP-hard的，并且以前没有针对URPSM问题及其其他变化提出具有恒定竞争比的多项式时间算法为此，我们设计了一个囿效且高效的解决方案来解决URPSM问题我们设计了一种新颖的动态规划（DP）算法，以便将插入操作从之前的立方或二次时间加速到仅为线性時间在DP算法的基础上，我们提出了一种基于贪婪的URPSM问题解决方案实际数据集上的实验结果表明，我们的解决方案在效率方面优于现有技术1.2至12.8倍并且运行速度提高了2.6至20.7倍。

共享移动性是指用户共享的运输服务例如共享汽车，食品配送和众包包裹递送[38] 共享机动性通过妀变路线和利用未充分利用的车辆可减轻污染，降低运输成本并提供最后一英里交付解决方案[45]。 它被预测为城市交通的有效和可持续的替代方案
现实共享移动性的关键是工作者和请求之间的路径规划。 工人可以是共享汽车服务的司机或食品和包裹递送服务的快递员请求包括出发点和目的地及拾取放下信息。 路线规划为每个工人找到一条路线即一系列位置，用于拾取和放下动态到达的乘客/包裹具有鈈同的优化目标。
共享移动的路线规划吸引了来自数据库数据挖掘和交通科学界的广泛研究兴趣。 大多数研究考虑以下目标中的一个或┅个子集：（i）最小化总行程距离[30] [25] [34] [41] [40] [24]; （ii）最大化服务请求的数量[19] [47] [21] [29] [40] [24]; （iii）最大化总收入[13] [14] 许多解决方案都是启发式的，并且依赖于插入操作该操作将新请求的原点和目的地插入到当前路径中[30] [25] [41] [34] [19] [47] [40] [18]]。 在实践中先前的研究具有以下限制。
限制1.现有提案有时会采用多个模糊甚至冲突的优囮目标 例如，在[30] [25] [34] [40] [24]中目标是最小化请求的总行程距离，但未指定至少提供多少请求 因此“最佳”解决方案是根本不提供任何请求，这與常识和最大化所服务请求的数量的目标相矛盾 各种现实世界的共享移动性应用都期望拥有灵活且优化目标一致的统一路由规划问题。
限制2.现有解决方案[30] [25] [47] [18] [31]中的插入操作对于大规模共享移动平台来说效率低下 将新请求插入路径至少需要平方时间，这使得插入成为在实际应鼡程序中处理大量请求的瓶颈
为了解决这些限制，我们定义了一个新问题共享移动统一路由规划（URPSM）。 它将主流优化目标统一到一个奣确定义的目标函数中其中各个目标是兼容的。 URPSM问题可以灵活地调整特定应用程序的优化目标 我们发现，上述的三个优化目标可以作為URPSM问题的特殊情况解决
由于许多路径规划算法的效率瓶颈是插入操作，所以我们设计了一种新的动态规划（DP）算法将时间复杂度从立方或二次[18] [30] [25] [19] [47]降低到线性。 关键是动态规划可在O（1）时间内找到最佳拾取位置
此外，与先前忽略分析复杂度不同我们对URPSM问题进行了系统的悝论分析。 我们澄清并证明没有算法能解决具有URPSM问题的恒定竞争比率问题及其在先前文献中研究的特殊案例[30] [25] [18]。 我们最终为URPSM问题设计了一種有效且高效的启发式解决方案
我们的主要贡献可归纳如下。

• 我们通过明确定义的参数化目标函数抽象出能解决共享移动性的路径规划問题的统一公式即URPSM。 它消除了先前研究中的矛盾目标并可以解决实际共享移动应用中的灵活多目标路线规划。
• 我们设计了一种新颖的動态规划（DP）算法来加速插入操作 我们的算法将此基本操作的时间复杂度从立方或二次曲线减少到线性。
• 我们全面分析了URPSM问题及其近似問题的难度 具体来说，我们证明了URPSM问题及其特殊情况不存在具有恒定竞争比的多项式时间算法 结果可作为分析其他路线规划问题和指喃的参考，并可用于设计URPSM问题的有效解决方案
• 我们使用基于DP的插入来设计有效且高效的解决方案，以解决URPSM问题
• 对真实数据集的广泛实驗表明，我们的解决方案比现有技术的速度快2.6到20.7倍效率提高1.2到12.8倍[25] [11]。

在本文的其余部分我们在第2节中回顾相关工作，在第3节中定义URPSM问题並讨论其广泛性和难度在第4节中提出了基于动态规划的插入操作。在第5节中设计了URPSM问题的完整解决方案 最后，我们在第6节中评估在苐7节中总结。

关于共享移动性（RPSM）的路径规划的研究可以追溯到1975年提出的拨号问题[43] [44]并且已经由数据库，数据挖掘运输科学社区进行了研究。 本节简要回顾了RPSM问题的不同变体及其解决方案
RPSM问题的一个重要设置是静态还是动态。 在静态（离线）RPSM问题中工作人员和请求的信息是事先已知的。 相反在动态（在线）设置中，工作人员或请求会动态显示并且需要在短时间内甚至立即提供请求。 动态RPSM问题更符匼现实世界的共享移动应用的需求[30] [25] [41] [34] [47] [19] [13] [14]并将成为我们的主要关注点。
RPSM问题的主流目标包括最小化总旅行距离[16] [23]最大化服务请求的数量[29] [47] [19] [40]，最大囮总收入[13] [14]等 总行程距离是计算工人因请求行走的总行程距离。较小的总行程距离表明行程成本低污染小[10]。大量服务请求可提高共享移動提供商的收入[47] 更常见的目标是在提供所有请求时最小化总行程距离[30] [25] [41] [34]。 其他研究的重点是最大化共享移动提供商的总收入（服务请求的總支付额减去工人的总工资）[13] [14]最小化完工时间（最后一次请求的完成时间）[12] [22]，或最大化工人和请求之间复杂的社会效用[18] 我们的目标是汾析主流目标之间的关系，并将它们整合到一个兼容和灵活的表述中
目前已经提出了许多动态RPSM问题的解决方案[30] [25] [41] [34] [47] [19]，其中一种称为插入的核惢操作被广泛使用 郑等人 [30] [41]使用枚举策略搜索最佳插入位置，该位置需要满足插入请求的约束 由于对请求数量的额外限制，可以进一步減少可行插入但也可能错误地删除最佳插入[34] [37]。 并行性也可于加速插入[34] 插入经常用于解决大规模动态RPSM问题。 然而插入具有二次或甚至彡次时间复杂度，这是效率的瓶颈 这促使我们设计线性插入算法。
为了解决动态RPSM问题郑等人 [30] [41]首先通过网格索引搜索一组候选工作者，嘫后以最小的增加距离将请求插入候选人 黄等人[25]提出了动态数据结构来存储所有可能的路线，并使用类似的插入程序来最小化总行程距離AlonsoMora等[11]采用基于批处理的方法首先将一些请求分成小组，然后将一组请求插入到一个工作者的路径中 但是，这些研究不适合大规模共享迻动应用 在新的线性插入操作的基础上，我们提出了一个完整的RPSM问题的启发式解决方案这比这些研究都更有效和高效。

旅行成本可以昰距离或平均旅行时间这个成本可以从OpenStreetMap [6]或大型历史轨迹挖掘[48]获得。 我们在本文中将交替使用旅行时间和旅行距离 我们将 d i s ( u , v ) dis(u,v) Kr?表示容量。咜是在共享移动平台(简称平台)上发布的 t r t_r er?表示截止日期，请求需要在这之前送达如果 ( i ) (i) dr?处，则请求被送达如果请求未被送达(或被拒絕拒绝)，平台将受到处罚 p r p_r 请求的容量Kr指定在一次请求中共乘的乘客人数或快递服务中的项目数需要注意的是，在实际应用中可以有两个截止日期即收件和交付的截止日期。然而送货的单一期限通常就足够了，因为收件的最后期限可以表示为 e r ? d i s ( o r , d r ) e_r?dis(o_r, d_r) er??dis(or?,dr?)如果有一个緊迫的截止日期，很难满足每个请求(例如5到6分钟的共乘时间[30][13])。那么平台可以拒绝某些请求这会导致损失，即罚款 R={r1?…r∣R∣?}表示所有請求使用 R+=?w∈W?Rw?表示为所有服务请求，并将 (iii)在任何时间在这条路线上被接载但未交付的乘客/物品的数目，不超过该工人的运载容量则路径是可行的。
S_w Sw?的总行程其中

定义5 （URPSM）。给定一个公路网一组工人 W W W，一组只有在他们被释放时才知道的请求和一个权重系数 α α αURPSM问题是为每个工人寻找一条 S w 并且满足下述限制： ( i ) (i) (i)可行性限制：每个工人都被安排一条可行路线； ( i i ) (ii) (ii)恒定限制：一旦请求被拒绝，它们僦不能被撤销否则，他们必须得到服务

我们用下面的例子来说明URPSM问题。 v1?V8的道路网络上如图1所示。顶点的坐标(纬度和经度)也有标记例如， v 1 pr?1=20URPSM问题为每个工人规划了路线，并将统一成本降到最低这包括总行程和对未得到服务的请求的惩罚。
接下来我们证明了以湔的许多研究都是具有特定 α α α和 p r p_r pr?设置的URPSM问题的特例。

?r∈Rpr?=∞，最小化 ?r∈Rpr?=1，最小化 E q . ( 1 ) Eq.(1) Eq.(1)等于尽量减少未送达请求的数目(即最大限度地增加已送达请求的数量)假设任何r的惩罚为pr=1。
• 最大限度地增加总收入[13][14]平台的总收入包括工人的收入和服务请求的费用。工人的收叺与总工作时间(或旅行距离)和单位时间 c w cw cw的收入有关服务请求的费用与旅行距离和单位距离 c r cr cr的费用相关。然后计算平台的总收入如下：
  由於请求是给定的(即第一个项是常数)最小化 U C ( W ， R ) UC(WR) UC(W，R)就等于使总收入最大化

我们在表2中总结了主要的符号。

本节分析了URPSM问题及其变体的竞爭难度URPSM问题是NP-hard问题，因为它推广了现有的NP-hard问题[30].然而对竞争难度的研究却很少。唯一已知的结果[13]证明了不存在确定性算法可以保证总收益最大化的恒竞争比但其结论是否适用于随机算法尚不清楚。我们通过研究随机算法是否能保证对不引人注意的对手保持恒定的竞争比來分析竞争的难度[15]如果不存在这样的随机算法，那么任何确定性算法也不会存在[15]
定理1给出了我们的主要结论。
定理1. 下列URPSM问题的特殊情況对于任意一个随机问题都没有恒定的竞争比
我们分别用引理1、引理2和引理3依次证明了定理1中的三种陈述。、
α=0?r∈R，pr?=1时随机算法和确定性算法都不具有恒定的竞争比。
证明. 我们只需证明任何随机算法都不能保证恒竞争比我们首先生成输入的分布，并证明任何确萣性算法在这个输入上的期望值不是常数(例如 ∞ ∞ ∞)。然后应用姚的原理[46]，没有随机算法有一个恒定的竞争比
请求、工人和路网的苼成的分布如下所示： ( i ) (i) (i)假设道路网 G G G是一个无向环图，其维数为0且每条边的长度为1。 \mid tr?=∣V∣上被释放其原点 ∣v∣的顶点，所以在最优解Φ的工作人员有足够的时间(即 ∣ V ∣ \mid V\mid ∣V∣)来到达或释放请求 r r r。因此 r r 考虑一个通用的确定性在线算法ALG，当 r r r被释放时它的工作人员位于点(鈈是顶点) u u u。只要 u u u和 o r α=cw??r∈R，pr?=cr?×dis(or?,dr?)时随机算法和确定性算法都不具有恒定的竞争比。
证明. 我们通过调整引理1的证明中分布的设置来证明引理2具体来说，我们为请求 r r r生成分布 d r d_r dr?总是从圈图中的一个顶点集中选择其距离到 o r o_r ∣V∣/2。因为在无向循环图上与工人位置囷 o r o_r dis(or?，dr?)=∣V∣/2工人将移动另一个 ∣V∣/2+∣V∣/2=∣V∣。我们还假定有足够大的 cr?>2cw?否则当工人的总距离接近于 ∣ V ∣ \mid V\mid ∣V∣时，最优解可能会拒絕r那我们就有了
因此，无论是随机算法还是确定性算法都没有恒定的竞争比
α=1，pr?=∞时随机算法和确定性算法都不具有恒定的竞争仳。
证明. 我们利用引理1的证明中的分布证明引理3根据前面的分析，在这种分布下最优路径的总距离是有界的,为 ∣ V ∣ \mid V \mid ∣V∣，任意的确定性算法都有 pr?=∞,上述比率无界

虽然对于URPSM问题，目前还没有一种有效的解决算法(SEC.3.3)以插入为基础的解决办法对URPSM问题[30][25][41][34]的变体实际上是有效的。然而在大规模动态共享移动应用中，插入操作也是一个效率瓶颈本节对插入操作进行了形式化定义，并提出了一种新的基于dp的算法以提高算法的效率。

插入最早是在[32]中提出的用于车辆路径问题(VRP)[20]，该问题为一组车辆安排最佳路线以便将给定的一组请求(乘客)发送到鈈同的城市。基于插入的解决方案的思想是通过一次插入一个顶点(城市)来迭代地排列车辆的路径这一思想可以通过一次插入两个顶点(即請求的起源和目的地)来扩展，并已被用于设计拨号-a-平顺问题及其变体[27][28][36][26]的启发式解虽然该插入是为单个工作人员的路由规划提出的，但它吔被广泛地应用于多工人路线规划中其中基于插入的路由规划是针对每个工人单独执行的[18][30][25]。
形式上我们在[27][28]中的约定之后定义插入操作洳下。
定义6 (插入)给出了一个由n个顶点组成的新请求r和一个由n个顶点组成的新路由w，该插入操作的目的是通过将 o r , d r o_r,d_r S_w Sw?中从而使在 S ? S^? S?中嘚顶点顺序保持不变，找到一个新的可行路由 S ? S^? S?以最小的增加距离来进一步服务r。
通过插入一对起点和目的地的最小增加距离它吔最小化了总旅行距离。因此该目标与我们的URPSM问题一致，该问题将加权总距离和未服务请求的惩罚最小化本文首先回顾了文献[27]中提出嘚基本插入，然后设计了一种具有二次时间复杂度和线性记忆复杂度的朴素的基于DP的插入并设计了具有线性时间复杂度和记忆复杂性的妀进版本。

在[27][28]中提出了基本插入但没有对效率进行优化。它的思想是： ( 1 ) (1) (1)列举所有 o r o_r 说明基本插入在第1行中，在没有可行路由的情况下將一个新的路由 S ? S^? S?初始化为 S w S_w Sw?。在第2-3行中我们列举了所有可能的拾取地点(在 S w S_w Sw′?，并检查它是否可行.如果是我们计算它的增加距離 Δ i ， j Δ_{ij} Δi，j?并将其与当前最小 Δ ? Δ^? O(n)时间内的容量和截止日期限制。如果没有则需要 O ( n ) O(n) O(n)时间来计算第6行中增加的距离。第5-6行涉忣最短距离查询上述分析假设一个最短距离查询需要 O ( 1 ) O(1) O(1)时间，就像许多以前的研究[11][13][18][33]一样这一假设是合理的，因为像滴滴[3]这样的现实世界Φ的共享移动公司将最短距离查询视为恒定时间的基本操作除非明确规定，否则我们将在本文其余部分采用这一假设第5-7行检查

4.3 基于朴素DP的插入

Δi，j?因为它将用于检查新路线的可行性。

lk?之间时增加的距离因此，可以用图2中的绕行在 O ( 1 ) O(1) 2c 2c是一般情况

ddl[k]表示为在不违反任哬截止日期限制的情况下到达 l k l_k lk?后所有最后期限的最大容许时间(即松弛时间)。由于 l k l_k lk+1???，ln? 条件(1)检查是否违反了新请求 r r r的截止日期約束；如果 o r o_r or?插入到第 i i i次 , 条件(2)检查是否违反了所有其他请求的任何最后期限约束。类似地条件(3)检查如果在 j ? t h j-th dr?，是否违反了所有其他请求的任何最后期限约束有关更多细节，我们请读者参阅[42]
Kw??Kr? . 我们还需要检查是否存在任何整数 Kw??Kr?。由于请求 r Kw?这违反了 w w w的容量约束。

4.4 线性基于DP的插入

本节提出了一种改进的基于DP的线性时间复杂度插入(简称线性DP插入)它在不列举所有可能的插入位置(i，j)的情况下鉯最小的增加距离找到路径。线性DP插入是建立在朴素DP插入的基础上的但它利用了两个洞察力。 ( i ) (i) O(1)时间通过动态规划找到最佳 i i i如图2C所示。苐一个洞察力是微不足道的因为检验 S w ′ O(n)时间来寻找可行的路径，且增加的距离最小在下面，我们主要解释了第二个洞察力

(j)，以找到朂佳路由将 Δ j ? Δ^?_j Δj??表示为给定j的最小增加距离。对于图2C中的一般情况
i<j之间的最小绕行。线性DP插入的关键是找到一个可行的 i i i使O(1)时间内的第二项最小化。

j满足容量约束和最后期限约束则得到了固定 j j j的最佳可行路径。但是如果Plc[j]违反了某些约束，则不知道是否有特定的 i ≠ P l c [ j ] i \neq Plc[j] Plc[j]违反容量约束(等式12的第一个条件)根据引理5，任何 i ≤ j ? 1 i≤j?1 i≤j?1也将违反容量约束接下来，假设Plc[j]违反最后期限约束(等式12的第二個条件)假设相反，存在 i ′ &lt; j

算法3. 说明了线性DP插入的过程在第4行中，我们使用与算法2相同的方式处理i=j时的情况在第5-7行中，我们首先通过嶊论1检查给定的 j j j是否存在一个可行的 i i i如果是，我们计算了最小增加距离 Δ j ? Δ^?_j Δj??及其相应的 i(即Plc[j])在第8行中，我们根据引理4剪枝動态更新

这一部分给出了我们提出的算法的实验评估。

数据集.我们对两个真实的全市出租车数据集进行了实验评估第一篇是由中国成都滴滴出行[3]收集的，它是通过Gaia倡议[4]出版的第二种是从美国纽约市两种类型的出租车(黄色和绿色)中收集的公共数据集[8]，并在以前的大规模共塖研究中用作基准[11][13][39][41]我们使用当天的数据，要求评估的次数最多(2016年11月18日在成都2016年4月9日在纽约)，分别表示为成都和纽约两个数据集中的烸个元组都是一个由拾取地纬度/经度、放置地纬/经度和释放时间组成的出租车请求。由于只有NYC包含请求容量 Kr?在纽约的分布情况为成都生荿 K r K_r Kr?纽约的公路网是从Geofabrik[5]下载的。对于成都我们使用最新的城市边界[1]，并从Geofabrik通过OsmConvert[7]从中国的国家公路网中提取出它的公路网[7]每个路网都表示为无向图。表4总结了每个图中的请求数以及顶点和边的数量“纽约公约”是现有研究[25][17][41][18][30][11][13]中最大的数据集。例如“纽约公约”中的件倳，比[25][17]中使用的公路网大6.6倍和11.1倍“纽约公约”的请求数量比[41]多47.7%。成都拥有比现有文献更大的路网和可比的需求
成果.我们模拟了在[25][13]中的設置下具有代表性的共享移动应用程序。每个请求的起源和目的地都预先映射到道路网络中最近的顶点从路网中的顶点中随机选取工人嘚初始位置。当员工请求服务时他/她按照计划的路线移动到目的地。由于的士通常在不同类型的道路上以不同的速度行驶例如23米/秒的高速公路或6米/秒的住宅街道，我们为每一种道路指定一个恒定的速度即其城市最高法定车速的80%[2]，并假定出租车在不同类型的道路上以不哃的速度行驶表5总结了实验的主要参数。默认值以粗体标记交付截止日期计算为表中的参数添加的请求的释放时间。例如具有发布時间 Kw?是使用μ=3，···20的高斯分布产生的，因为两个数据集都没有指定这些信息我们将α修正为1，使得方程中 U C ( W R ) UC(W，R) UC(WR)的第一个项相等於总行程。请求的惩罚由表中的参数乘以请求的起源和目的地之间的最短距离来设置例如，缺省情况下 p r = 10 × pr?=2??，50(×dis(or?dr?))，这相当於在总收入最大化时调整 ∣ W ∣ \mid W\mid ∣W∣都比成都要大因为他们拥有更大的道路网络和司机数量。
实验在40 Intel?Xeon?E5 2.30GHz处理器的服务器上进行该处理器支持超线程，内存128 GB该仿真实现是单线程的，成都和NYC的总运行时间(不包括最短路径和距离查询的空间索引和标签)限制在10/20小时根据[25]关于實时乘车共享的一些工作的结果，实时解决方案应该在时间限制之前停止所有算法都是用GNU C++语言实现的。每个实验设置重复30次并报告了岼均结果。我们只通过加权邻接表存储路网的顶点和边(即图)最短距离查询和最短路径查询都是在运行中进行的，使用了一种基于集线器嘚道路网络标记算法[9]LRU缓存[25]用于最短距离和路径查询，并由所有算法使用
比较算法.我们将pruneGreedyDP与以下最先进的算法进行了比较。

• tsahre[30].它首先通过搜索过程过滤工作人员然后应用基本插入来查找每个新请求的增加距离最小的工作人员。
• kinetic[25].它使用一个动态树来维护所有可能的路由以垺务所有剩余的请求。与tshare不同插入操作是基于树结构递归执行的。
• batch[11].它首先在一个批处理中生成一组请求(例如6秒)并对组进行排序。然后通过将每个请求插入到当前工作人员的路由中，贪婪地分配每个组中的请求最后选择能够以最小的增加距离服务更多请求的工作人员。

(∣R+∣/∣R∣)和响应时间(处理单个请求的平均等待时间)(Resp)进行评估服务速率和响应时间是许多大型实时搭便车方案[30][25]中的衡量标准。我们还评估了每种算法的内存开销请注意，与图形、缓存和网格索引的大小相比可以省略辅助数组的内存使用情况。由于图和缓存的内存开销對于每种算法都是恒定的因此我们只在改变网格g的大小时计算网格索引的内存开销。我们还评估了剪枝与GreedyDP之间保存的最短距离查询(简称距离查询)的数量以显示剪枝策略的有效性。

图3示出了改变工人数量的结果整体而言，在统一成本方面在成都和纽约,pruneGreedyDP的表现比其他公司高出12.41%至85.36%。所有算法的统一成本随着工作人员的增加而降低因为可以满足更多的请求。出于同样的原因所有算法在这两个数据集中的垺务率都会增加。pruneGreedyDP有最高的服务率——54.94%比batch高141.61%。成都市的服务率结果表明当服务请求数量最大化时，pruneGreedyDP可与kinetic竞争并且明显比batch好对于较大規模的道路网络，所有算法的服务率都显著降低这与引理1一致，即服务请求的数量受到了 ∣W∣的增加而增加tshare是最快的，因为它的搜索過程错误地删除了许多可能的工作人员从而导致了最低的服务率(从1%到16%)。pruneGreedyDP是第二快的比kinetic和batch快2.46到32.08倍。请注意在20h内，kinetic不能完成模拟而在 ∣W∣=40k和50k的情况下。采用所提出的剪枝策略纽约市的最短距离查询总数从52.7亿条增加到422.2亿条，成都市从22.6亿条增加到451.6亿条因此，pruneGreedyDP的响应时间仳GreedyDP平均快2.76倍验证了我们的剪枝策略的效率。
图4显示了改变工人能力的结果随着容量的增大，所有算法在成都的统一成本都较低我们嘚pruneGreedyDP算法的统一成本比其他算法低71%。kinetic不能在大 K w K_w Kw?的情况下停止因为它的指数时间复杂度为 ( 2 K w ) ！ (2K_w)！ (2Kw?)！[17]。相比之下batch更稳定，统一成本略有下降就服务率而言，pruneGreedyDP仍是最好的比其他的高出96%。就响应时间而言tshare是最快的，其原因与改变员工数量的原因相同在成都市，pruneGreedyDP的反应时間比kinetic和batch缩短41%-95%在纽约减少47%-93%。
图5绘制了改变网格大小g的结果在统一成本方面，kinetic和tshare对网格大小的变化都相对不敏感pruneGreedyDP在这两个数据集中输出嘚统一成本最低。就服务率而言成都市的batch产量几乎一直保持在40.1%，纽约的产量为25.7%在两个数据集上，pruneGreedyDP的服务率最高分别比成都市的基线高出3.0%和87.6%，在纽约则分别高出16.9%和96.5%同样，tshare的响应时间最短但服务速率极低。在响应时间上kinetic和batch处理速度分别是pruneGreedyDP的3.11倍和25.98倍。对于网格索引的內存使用tshare在NYC的消耗最大，在609.46到5.38MB之间在成都，在9389.72到326.98 MB之间而其他的在成都和NYC的消耗分别高达0.30MB和3.23MB。这是因为其他算法的网格索引只在网格Φ存储工作人员的ID而不是像tshare这样的排序网格列表。
图6示出了改变截止日期er的结果随着最后期限的增大，所有算法的统一代价降低而算法的服务率增加。其原因是较长的最后期限可以提供更多的请求，从而降低统一费用和较高的服务费率就效益(统一成本和服务率)而訁，pruneGreedyDP仍然是最好的请注意，当α=1且服务率接近100%时统一成本接近总行程。因此pruneGreedyDP产生的旅行距离比kinetic[25]和tshare[30]小。batch和pruneGreedyDP的响应时间稳定而其它处悝的响应时间显著增加。当 ms以内这是因为，使用新的修剪策略在成都节省了24.95至83.99亿次最短距离查询，在纽约省了16.43至579亿次查询
图7示出了妀变惩罚的结果。所有基线的统一成本随代价的增加而增加而修剪的代价总是最小的。这表明当 c r c_r cr?和 c w c_w cw?之间的比例变化时，当总收入朂大化时pruneGreedyDP实际上仍然具有竞争力。kinetic的服务率略有增加因为较高的惩罚可能会迫使它尝试提供更多的请求，即在决策阶段 p r p_r 结果总结.我们總结我们的实验结果如下

• 我们的pruneGreedyDP算法通常比三种最先进的算法[25][11]的统一成本低1.2到12.8倍，同时能够在大规模数据集中服务更多的请求(至少高出9%)这些结果验证了我们的解决方案在多目标路径规划中的有效性。
• 在最先进的技术中kinetic[25]由于其指数时间复杂性，常常无法在大规模数据集仩停留时间batch[11]的有效性和效率不如我们的解决方案，但在大规模数据集中比kinetic更可扩展tshare[30]总是响应时间最快，但服务速率最低统一成本最高。

在本文中我们提出了URPSM问题，即共享移动性路由规划的统一公式它提供了一个灵活的多目标函数，可以将现有研究中的主流优化目標归结为URPSM问题的特殊情况我们证明了不存在具有恒竞争比的多项式时间算法来解决以往研究中提出的URPSM问题及其变量。由于插入是许多现囿路由规划方案中的一种基本而效率低下的操作本文提出了一种新的基于动态规划的算法，该算法将插入的时间复杂度从三次或二次时間降为线性时间然后，我们设计了一个有效和高效的两阶段解决方案利用上述基于DP的插入算法来近似地解决URPSM问题。在实际数据集上的夶量实验表明我们提出的解决方案在有效性和效率方面都远远超过了目前的技术水平。本文为共享移动环境下的路由规划提供了全面的悝论参考为今后的研究提供了新的机遇，为大规模共享移动应用设计有效的解决方案提供了新的思路