【论文笔记】A Unified Approach to Rout

abstract

共享移动性是指用户之间共享的传输服务，其中一个核心问题是路线规划。本文提出了一个能消除先前研究中的矛盾目标，为共享移动性提供灵活多目标路线规划的参数化对象函数。这个问题被证明是NP-hard,我们提出了一种有效的近似解决方法实现了线性时间

一.introduction

大多数研究在以下几个方面
1）最小化总行程距离
2）最大化服务请求的对象
3）最大化总的收入
许多解决方案都是启发式的并且依赖于将新请求的原点和目的地插入到当前路由中的插入操作。这些方法存在限制：
1）采用多个模糊或者有冲突的优化目标。比如有些文章的目标是最小化总行程距离而不指定应该提供多少被服务的请求
2）在大规模的共享移动平台中，插入操做是低效率的。至少n²时间
共享移动性的统一路由规划（URPSM）将主流优化目标统一到明确定义的目标函数中，其中各个目标是兼容的集成。 URPSM问题还可以灵活地调整特定应用程序的优化目标。 以上三个目标可以减少为URPS问题的特殊情况。

很多路线规划问题的效率瓶颈是插入操作。因此我们提出了一个动态处理算法（DPA）将时间复杂度降为线性。DP可用于在O（1）时间内找到最佳拾取位置。本文还做了一个对URPSM 问题的系统的理论分析。即对于URPSM问题及其先前文献中研究的特殊案例，没有确定性或随机化的算法，具有恒定的竞争比率。

贡献：

1）为共享移动性抽象了路线规划问题的统一表述，消除了矛盾对象，它消除了先前研究中的矛盾目标，并使现实共享移动应用中的灵活多目标路线规划受益
2）设计了一个DP算法去加速插入操作，减少了基本操作的时间复杂度
3）综合分析了URPSM问题近似的难度。证明了URPSM问题及其变量没有具有恒定竞争比的多项式时间算法。
4）使用基于DP的插入来设计有效且高效的解决方案来解决URPSM问题

三.问题申明

3.1概念描述：

1. road network： G=（V,E）dis(u,v)。每条边陡河一个旅程cost（u，v)相关。其中u∈V，v∈V。

2. worker:用w = <ow，Kw>表示，车初始位置ow∈V和容量Kw。 W ={w1 · · · w|W |} t表示所有worker的集合。

3. request:r=r =<o_r, d_r, t_r, e_r, p_r, K_r >请求出事位置o_r ∈ V , 请求目的地 d_r ∈ V ,请求需要服务的数量（如乘车人数）K_r.请求发布时间t_r,截止时间 e_r,I如果请求没有被服务或者被拒绝平台将接受 惩罚 p_r。如果一个请求被服务意味着，乘客r在t_r时间后在地点o_r上车，并且在e_r时间之前在d_r处下车。

4. R = {r1 · · · r|R|}表示所有请求的集合,R_w表示被worker w服务的请求。
   所有被服务的请求表示为：R ⁺ =U_w∈WR_wa。
   所有没有被服务的请求表示为：R=R-R⁺

5. 一个worker w的路线可以表示为：
   

   
   o_w表示为worker w的出事位置，后面的l表示R_w的初始和目的的有序序列。当一个路线是可行的时候：R_w的所有请求r的初始位置和目的地都存在且o_r在d_r之前。 并且w到达d_r的时间不能超过截止时间e_r，并且乘客的数目不能超过worker(车辆的容量）。用D（S_w)表示S_w的总行程距离。

3.2 统一对象和URPSM问题

1. 表示最小化总行程距离：
   设置α = 1，p_r=∞，然后求UC（W,R）的最小值。

2. 最大化服务请求数目：
   设置α =0，p_r=1，然后求UC（W,R）的最小值。其实也就让拒绝的请求最小化，那么服务的订单也就最大化了。

3. 最大化总收入
   平台的总收入由workers的收入和和服务请求的票价组成。worker的工资和工作时长有关，并且单位时间的收入为c_w.而服务的价格和总行程长度有关并且单位距离的价格为c_r。所以平台总的收入为：
   

   
   设置α = c_w ， ∀r ∈ R, p_r = c_r × dis(o_r, d_r):
   那么
   
   而平台收入=从所有请求中能得到的总收入-worker的工资-需要支出的违约款，因此求收入的最大值化为问题化为求UC（W,R)的最小值：
   

3.3.难度分析

• 引理1:
  α = 0 and ∀r ∈ R, p_r = 1时，不存在随机或者确定性算法与最优算法相比有一个常量竞争比 最佳的解决方式当然是所有的请求都被服务，并且不被服务的请求数为0. E_χ[OPT] = 0.
  设置d_r = o_r, e_r = t_r + ε,ε > 0 and p_r = K_r = 1.如果当请求r发布的时候worker在点u，o_r和u之间距离的不超过ε，r被服务的概率小于2ε/|V|。而r不被服务的概率为E_χ[ALG] ≥ 1 − 2ε/|V|
  因此有：
  

  

• 引理2：
  当α = cw ， ∀r ∈ R, p_r= c_r × dis(o_r, d_r):
  从worker到请求r的距离不超过|V|/2
  假设存在一个充分大的c_r,例如c_r>2c_w,一个最优解可能会拒绝r当worker的总距离接近|V|的时候。
  

  
  ε足够小的时候
  
  因此也不存在常量的竞争比。

• 引理3：
  设置α = 1，p_r=∞。总的距离的上界是|V|,任何的确定性算法都有1 − 2ε/|V|的概率拒绝r。
  

  
  当p_r=∞ 和ε足够小的时候，竞争比趋于无穷大。

四.DP_based 插入

4.1 insertion的定义

给定worker w,当前有n个节点的路线S_w和一个新的请求r，insertion操作通过将o_r,和d_r都加入S_w来找到一个新的可行路线S*使得加入新的服务r增加的距离最小化并且使得原来S_w中的节点序列顺序保持不变。

4.2.基本插入：

Δ∗当前最短增加距离

枚举所有可能的上车位置和下车位置生成新的路线S',检查新路线是否可行，如果可行记录当前增加的距离Δij，如果Δ_i,j < Δ ^* ，那么更新S*=S'_w .此操作的时间复杂度为：O(n³q)，空间复杂度为O(n）

4.3.naive DP_based insertion**

1. 在插入 o_r 和 d_r时枚举所有可能得地点对
2. 在O(1)时间检查新路线是否可行和计算Δ_i,j

4.3.1 在O(1) 时间内计算Δ_i,j

在l_i 和l_k之间插入l_j 的时候需要绕路的距离为：
det(l_i , l_j , l_k)= dis(l_i , l_j ) + dis(l_j, l_k ) - l_i , l_k
Δ_i,j 的计算有三种情况：

解释：
i=j=n：即为在当前所有已有请求都完成之后再去接新请求r
i=j<n：接到r请求之后接到这个乘客之后先送这个乘客
i<j:接到乘客之后，先送一些之前的乘客然后再去送该乘客。
通过（5）可以在O(1)内计算Δi,j

4.3.2在O(1)时间内检查路线的可行性：

检查路线的可行性需要检查期限约束和容量约束

• i) 检查时间约束**
  ddl[k]表示为在不违反任何期限约束的情况下到达 l_k 的最晚时间。
  
  如果 l_k 是请求r的起点，那么达到 l_k 之前的时间 =请求r的截止时间-请求r需要的服务时间，如果 l_k 是请求r的目的地，那么到达 l_k 的最晚时间就是r的截止时间。
  w到达 l_k 的时间用arr[k]表示
  
  用slack[k]表示l_k 和l_{k +1}绕行的最大可容忍时间（满足lk之后所以的期限约束）。
  
  引理4：期限约束不被违法当且仅当以下条件满足：
  (1) arr[i]+dis(l_i , o_r ) ≤ e_r ; //到达li的时间+从li到请求r的起点位置的时间不大于请求r的最后期限。即检查or插入位置i是否满足期限约束。
  (2) det(l_i , o_r , l_i+1 ) ≤slack[i]; //从li绕到请求的起点在回到li+1的绕道时间不大于li的最大容忍时间（也就是不大于li的预留的时间。）检查当or插入到位置i的时候其他请求的期限约束是否满足
  (3) arr[i] + dis(li, or) + dis(or, dr) ≤ er when i = j(Fig. 2a and Fig. 2b) or arr[j]+det(l_i , o_r , l_i+1 )+dis(lj, dr) ≤er when i < j (Fig. 2c); //达到请求r目的地的时间不大于请求r的最后期限。检查当在第j位插入请求r的目的地dr，请求r的期限约束是否满足
  (4) Δi,j ≤ slack[j].//在li和lj之间增加的总时间不能查过lj的最大容忍时间。检查当在第j位插入请求r的目的地dr时其他请求的期限约束是否被违背。
• ii）检查容量约束
  
  引理5:
  容量约束被满足当且仅当：
  (1) picked[i] ≤ K_w - K_r , 在位置i的已有容量要小于总容量-请求容量
  (2)∀k, i < k ≤ j, picked[k] ≤ K_w - K_r .在请求r服务开始（i）到结束(j）之间的容量都要不大于总容量-请求容量
• 伪代码
  时间复杂度为：O(n²q)
  

4.4.linear DP-based Insertion

在naive DP_based insertion的基础上，但是加入了两个新的思想
1)当i=j的时候，O(n)去找到最佳路线。并且也只需要O(1)的时间去计算Δ∗
2）在一般化的情况下，固定一个j通过动态程序只需要O(1)时间去找到最佳的i

4.4.1枚举交货地点(目的地)

linear DP_based Insertion 仅仅只通过枚举delivery 地点（j）来找到最佳路线，而不是枚举所有的（i,j）对。第一部分的绕道是固定j，插入在插入j之后的绕道，第二部分是最小化所有i<j之间的绕道。因此本算法的核心是在O(1)时间内找到一个可行的i来最小化第二部分的绕道。

4.4.2.在O（1）时间找到最佳的上车位置

Dio[j]:给定j的i <j中插入_r 的最小绕行。Dio[j] =min i<j det(l_i ，o_r , l_i+1 ).

Plc[j]是关于Dio[j]的or插入位置：

引理6 如果Plc[j]违反了确切的限制，那么其他i≠ Plc[j] 也会违反这些限制。.
因为plc[j]表示的已经是在给定j的情况下插入o_r的最小绕道的位置了,如果最小绕道的位置都违反了时间约束，那么其他的肯定也会违背时间限制。
推论1：
给定一个j，如果存在一个可行的i插入o_r，当且仅当：
(1) picked[j] ≤ K_w - K_r ,
(2) arr[j] + Dio[j] + dis(l_j，d_r ) ≤ e_r
(3) Dio[j] +det(l_j，d_r , l_j+1 )) ≤ slack[j].

4.4.3伪代码：

O(nq).

5.基于插入的解决办法：

该部分展现pruneGreedyDP，分为两部分：一部分为决策阶段，即决定是否接单，第二部分为计划阶段：规划路线。

5.1决策阶段

当拒绝一个请求的惩罚小于服务增加的距离的时候，我们就可以去拒绝这个请求。因此本文提出将最小增加距离的下限作为决定是否提供为新请求提供 服务的度量

5.1.1计算Δ ^* 的下边界

1. 采用计算Δ_i，j的欧氏距离来计算Δ∗的下界
   

   

2. LBΔi,j表示Δ_i，j的下界：其中L = dis(or, dr).
   

   

3. 表示最短欧式绕道：

   
   

4. Dio _euc表示对应的欧氏距离的Dio[.]值，
   

   

5. 所以对应的插入增加距离为

   
   

5.1.2 算法框架

利用 linear DPinsertion算法计算得到最小的插入增加距离，如果p_r<增加的距离那么j就拒绝该请求r
时间复杂度：O(|W | + |R| + q)

5.2：规划阶段

5.2.1修剪候选workers

因为在决策阶段计算了增加的下界，所以可以借助下界来修剪workers
引理8 ：假设workers已经在决策阶段计算LB中的LB_Δ∗时排序了，如果w_a排在w_b的前面并且w_a的Δ∗小于wb的LB_Δ∗，那么就可以忽略所以排在w_a后面的workers

5.2.2找到最佳worker

在修剪之后 ，我们就需要找到worker的最短增加距离。
引理9 使用辅助阵列arr [·]，线性DP插入仅需要2n + 1个最短距离查询。

5.3:算法框架

1. 先过滤候选worker,
2. 决定是否接单，.如果接单，选择最佳worker并规划出最佳的路线，并更新该用户的路线Sw和每个地点的到达时间arr，如果拒绝接单，那么将其加入拒绝的接单的集合中
3. 计算出统一花费UC。

想法：

这篇文章算法给我的总体感觉就是，为共享移动性问题提出了一个统一的函数进行描述，解决了插入操作的瓶颈问题。计算出每个用户的路线图中的每个点到达的要求到达的最晚时间，即给出每个点的冗余度，这一点和之前学软件工程这个课程的时候工程的最晚完成时间是一样。在选选择上车和下车点的时候，先固定下车点，计算下车点之前可能的绕道。在计算绕道的时候充分利用之前遍历的得到的结果和初始化的值。
这篇文章主要研究在已有路线中加入新节点的方式。但是这个算法是否可以加入一个时间段和地段的考虑，这样会使得修剪的更快更好。
参考：
A Unified Approach to Route Planning for Shared Mobility Yongxin Tong， Yuxiang Zeng ，Zimu Zhou ， Lei Chen ，Jieping Ye ， Ke Xu