没有合适的资源?快使用搜索试试~ 我知道了~
在线乘车和配送服务中的最小化延迟
3790在线乘车和配送服务中的最小化延迟 �0Abhimanyu DasGoogle研究abhidas@google.com0Sreenivas GollapudiGoogle研究sgollapu@google.com0Anthony Kim †0斯坦福大学tonyekim@stanford.edu0Debmalya Panigrahi ‡0杜克大学debmalya@cs.duke.edu0Chaitanya Swamy §0滑铁卢大学cswamy@uwaterloo.ca0摘要0受在线乘车和配送服务的普及的推动,我们研究了经典多车辆最小延迟问题的自然变体,其目标是将位于车站的一组车辆路由到度量空间上的请求,以便最小化总延迟。在本文中,我们考虑了带有源-目的地对和发布时间约束的点对点请求,这些约束限制了每个请求的服务时间。点对点请求和发布时间约束模拟了出租车乘车和配送。对于所有考虑的变体,我们展示了基于线性规划框架的常数近似算法。据我们所知,这是对最小延迟问题的上述变体的第一组结果。此外,我们对基于我们的理论算法的启发式方法在真实出租车乘车数据集上进行了实证研究。0CCS概念0• 计算理论 → 路由和网络设计问题;离散优化;0关键词0车辆路径规划;最小延迟问题;在线乘车服务0ACM参考格式:Abhimanyu Das,Sreenivas Gollapudi,AnthonyKim,Debmalya Panigrahi和ChaitanyaSwamy。2018年。在线乘车和配送服务中的最小化延迟。在WWW2018:2018年网络会议上,2018年4月23日至27日,法国里昂。ACM,纽约,纽约,美国,10页。https://doi.org/10.1145/3178876.318610401 引言0近年来,诸如Lyft、Ola和Uber等共乘平台以及DoorDash和GrubHub等在线配送服务变得越来越受欢迎。0� 本文的完整版本可在https://arxiv.org/abs/1802.02744获取。†本工作的一部分是作者在Google公司实习期间完成的。‡部分受NSF资助,编号为CCF-1535972、CCF-1527084和CAREER Award。§部分受NSERC资助,编号为327620-09和NSERC Discovery AcceleratorSupplement奖励。0本文发表在知识共享署名-非商业性-禁止演绎4.0国际(CC BY-NC-ND4.0)许可下。作者保留在个人和公司网站上传播作品的权利,并附上适当的归属。WWW2018,2018年4月23日至27日,法国里昂,© 2018IW3C2(国际万维网会议委员会),根据知识共享CC BY-NC-ND 4.0许可发布。ACMISBN 978-1-4503-5639-8/18/04。https://doi.org/10.1145/3178876.31861040近年来,诸如Lyft、Ola和Uber等共乘平台以及DoorDash和GrubHub等在线配送服务变得越来越受欢迎,并扩展到许多城市和国家。这些在线服务共同面临的一个核心问题是车辆路径问题,即一组车辆被路由到地理区域上的乘车和配送请求。事实上,这个问题也是传统城市出租车服务(如YellowCab)的核心问题,出租车被路由到通过电话或互联网接收的乘车请求。在所有这些设置中,一个请求包括一对源和目的地位置,例如出租车服务中乘客的起始和结束坐标,以及食品配送服务中的餐厅和客户地址。此外,这些“点对点”请求通常具有发布时间约束,即客户指定了请求不能被服务的期望服务时间。车辆路由算法旨在最小化客户的平均延迟,即其请求的服务时间与实际服务时间之间的差异。在本文中,我们正式定义了一个多车辆路径问题,得到了一个基于线性规划框架的算法,并证明了基于这个正式算法的启发式方法在真实的城市出租车乘车数据集上改进了基准贪婪解决方案。大多数当前系统,如上述在线服务和传统服务,采用各种启发式方法来解决这种类型的车辆路径问题。相比之下,算法文献中有关所谓的车辆路径问题(或VRP)的研究历史丰富,涵盖了各种约束下的一个或多个车辆的路由问题。对于这些问题,正式文献包含了一系列复杂的技术,通常基于线性规划形式化,可以得到具有可证明保证的近似算法。虽然我们不知道以前关于我们的具体问题形式的点对点请求和发布时间约束的任何结果,但相关文献提出了一个自然的问题:这些复杂的算法技术能否应用于这个重要的实际问题,即最小化具有发布时间约束的点对点请求的延迟?如果可以,这些算法思想是否也能在实践中提供更好的启发式方法?我们通过设计一个常数近似算法来肯定地回答了这两个问题,该算法还导致了一个优于自然贪婪策略的启发式方法。01请注意,我们使用“在线”一词来指代由基于Web的服务生成的请求,而不是指代以算法意义上的“在线”到达的请求。0Track:社交网络分析和Web上的图算法WWW 2018年4月23日至27日,法国里昂38001.1我们的贡献0我们在第2节中正式定义了最小延迟问题。在第3节中,我们介绍了Post和Swamy[23]提出的线性规划框架,这将是我们算法和分析的核心。我们的理论贡献是为以下问题获得常数近似算法:(1)(第4.1节)最小延迟问题(MLP)和单仓库多车辆最小延迟问题(k-MLP)与点对点请求。(2)(第4.2节)多仓库多车辆最小延迟问题(k-MLP)与点对点请求。(3)(第5节)对于具有点和点对点请求的上述问题的发布时间约束。此外,我们通过将我们的算法与两个真实的出租车数据集上的自然贪婪基准进行比较,对最小延迟问题进行了大规模的实证分析。我们展示了我们的算法在延迟、路径长度和系统中出租车的利用率(活动时间)等不同指标上优于基准。有关我们的理论结果的摘要,请参见表1。据我们所知,这些结果是相应最小延迟问题的第一个多项式时间近似保证。对于多仓库问题,我们通过常数因子约简(比率为3)获得了近似保证。我们相信,通过使用更复杂的结构,可能会获得更好的近似比率,但我们在本文中没有探索这些内容,以使我们的算法在实践中可行。“客户端”与“平台端”目标:请注意,我们在本文中研究的平均延迟目标是“客户端”目标,而车辆行驶的总距离,通常在诸如著名的旅行推销员问题(或TSP)等问题中研究,是“平台端”目标。我们可以将平均延迟解释为客户端的平均等待时间,而将总距离解释为平台的燃料等运营成本。我们的点对点请求的路径问题可以被视为所谓的单位容量车辆拨号问题的“客户端”对应问题,其中车辆像我们的问题一样提供点对点请求,但寻求最小化总行驶距离的“平台端”目标。具有发布时间约束的点请求的延迟最小化问题已经在[32]中提出作为一个开放问题,并且存在于特殊情况下的多项式时间近似方案,例如恒定数量的车辆,或者如果度量空间具有特殊结构,例如欧几里得平面或加权树[30]。我们的结果是对于一般度量空间和任意数量的车辆的第一个结果,并进一步推广到点对点请求。01.2相关工作0我们的问题是车辆路径问题的一个示例,这是一个通用术语,用于描述度量空间上的各种路径问题。与我们的背景特别相关的是最小延迟问题(或MLP),也称为旅行修理工问题或送货员问题,它在磁盘头调度和在网络中搜索信息等方面有应用。0作为世界范围的网络[7,17]。这个问题是我们问题的一个特例,其中请求位于点位置(而不是点对点请求),并且没有发布时间约束。MLP和k-MLP(分别为一个或k辆车)在运筹学和计算机科学社区中长期研究。MLP被证明是NP完全的,然后是一般度量的MAXSNP难问题[8,22,26]。实际上,即使度量是具有{0,1}权重的加权树,它也是NP难的[29],并且被认为比著名的旅行推销员问题更难。20已经有很多研究专注于精确解决MLP/k-MLP及相关问题,尽管不是在多项式时间内。已经提出了许多混合整数形式,并且已经提出了精确方法,如切割平面算法和分支切割定价算法(例如,[1, 18,19])以及各种元启发式方法(例如,[20, 21,28])。最近,已经提出了几种k-MLP的混合整数形式,并在节点数范围为80的路由和调度实例上进行了实验[3]。MLP的第一个常数因子近似算法是在[8]中获得的,随后在一系列工作中将近似因子改进到3.592 [5, 9,15]。类似地,对于多车辆版本的k-MLP,即多仓库和单仓库变体,由于一系列工作[9, 11, 14,23],我们有常数因子近似算法,当前已知的最佳近似因子分别为8.497和7.183。对于几种特殊情况,已知更强的保证。对于带权树和任意有限维度的欧几里德度量,已知准多项式时间近似方案[6],最近,对于带权树和欧几里德平面的MLP和单仓库k-MLP,即常数k(即,常数数量的车辆)已经证明了多项式时间近似方案[30]。MLP/k-MLP还与其他车辆路径问题密切相关,如旅行商问题、定向问题(参见[10])和打车问题(参见[13])。它们还与调度文献中具有最小总(加权)完成时间目标的许多排序问题相关(参见[16,30])。有大量关于车辆路径问题和调度问题的工作超出了本文的范围。有关详细信息,请参阅上述工作和其中的参考文献。最后,我们提到了数据挖掘和人工智能社区在乘车和送货服务的其他方面的许多工作中的几项工作。已经研究了不同的出租车调度策略和路线推荐系统,以最小化乘客的等待时间(在不同的设置中,参见[2,34]),最大化司机的利润(参见[25])并在一组竞争司机中保证公平性(参见[24])。为了解决出租车系统的低效问题,已经设计了几种基于图的模型和算法,以最小化所需出租车的总数并减少出租车司机的总空闲时间(参见[33,35])。还研究了按需到达的动态变体(参见[27])。02旅行商问题在一般度量下是MAXSNP难的,但在带权树度量的情况下可以在多项式时间内解决(通过欧拉回路)。0论文题目:社交网络分析和网络图算法 Track: Social Network Analysis and Graph Algorithms for the Web WWW 2018, April 23-27, 2018, Lyon, FranceWe describe the linear programming framework due to Post andSwamy [23] for single-depot k-MLP and MLP with point requests.Some of our algorithms utilize a directed metric, so we describetheir LP in this general setting. Linear programs for multi-depotk-MLP are also given in [23] and are different, but we primarilyfocus on the linear program for the single-depot case in this paper.Let r denote the single depot for the point-request version.Given a problem instance with point requests, let digraph D =(V,A) with arc-costs {cu,v }u,v ∈V represent the underlying directedmetric. (If we have an undirected metric, we simply bidirect theedges to obtain D, setting cu,v = cv,u = cuv.) We use a to indexthe arcs in A, v to index nodes in V \ {r}, i to index the k vehicles,and t to index time units in [T]. We use variables xiv,t to denoteif node v is visited at time t by the route originating at the root.Directing the vehicles’ routes away from the root in a solution, zia,tindicates if arc a lies on the portion of vehicle i’s route up to time t.Let T be an easily certifiable upper bound on the maximum latencyof a request. Consider the following LP. We will be able to ensurethat either: (a) T is polynomially bounded by scaling and roundingthe metric (e.g., [6]) while losing a (1 + ϵ)-factor, in which case thisLP can be solved efficiently; or (b) log T is polynomially bounded,and use ideas from [23] to obtain a (1 + ϵ)-approximate solution tothis LP.Constraints (1) ensure that every non-root node is visited at sometime, and constraints (2) ensure that each node cannot be visited3810P需求 P2P需求 P需求 w/RTs P2P需求 w/RTs0MLP 3.592 ([9]) 3.592 7.183 7.1830单仓库 k-MLP 7.183 ([23]) 8.978 7.183 8.9780多仓库 k-MLP 8.497 ([23]) 25.488 13.728 41.1840表1:各种最小延迟问题(MLP/k-MLP)的最新近似保证,包括点(P)需求和点对点(P2P)需求,以及是否有释放时间(RTs)。除了第一列之外,常数因子近似比是新的,归功于本文。02 问题形式化0我们将多车辆最小延迟问题(k-MLP)定义为具有点对点需求的问题。让G=(V,E)是具有边上的距离函数c:E→R+的加权完全无向图,形成度量空间。有n个点对点需求,其中每个需求Ri由源节点和目标节点的一对(si,di)给出,并且需求在没有中断的情况下满足,即,车辆通过先到达源节点,然后直接到达目标节点来服务它。有k辆车辆位于各自指定的仓库节点,等效地,根节点r1,...,rk。目标是找到从各个仓库出发服务所有请求的k条路径P1,...,Pk,并最小化总延迟,即请求的延迟之和,其中请求的延迟等于服务它的车辆路径上从仓库到请求目标的距离。0经过适当的缩放和舍入,我们可以假设ce是整数,对于每个根节点ri和请求Rj,creisj + csjdj ≥1。为了方便起见,我们假设距离ce以时间单位给出,并将请求的延迟解释为其完成时间,遵循作业调度文献。因此,所定义的问题是本文要研究的最一般版本,我们将其称为具有点对点请求的多仓库k-MLP。当所有车辆都有一个单一的仓库r0(即r0 = r1 = ∙ ∙ ∙ =rk)时,我们将其称为具有点对点请求的单仓库k-MLP,并且当只有一个车辆(即k =1)时,我们将其称为具有点对点请求的MLP。当请求的源节点和目标节点相同时,我们有经典的k-MLP,并且我们将其称为(多仓库/单仓库)具有点请求的k-MLP(例如,[23]),以区分它们与具有点对点请求的更一般问题。具有释放时间的MLP /k-MLP是具有附加释放时间约束的MLP /k-MLP。每个请求Ri都有释放时间Ti,使得在时间Ti之前不能访问它。可以考虑点和点对点请求与释放时间。当车辆位于请求的源节点时,它可以等待,直到请求在其释放时间可用时。在上下文清楚时,我们使用较短的名称来指代这些问题。0符号。我们使用ri,si和di来表示指定的节点,并使用通用索引变量(如u和v)来表示任意类型的节点。我们使用I来表示输入大小。路径可以从不同的节点开始和结束,而旅行必须从相同的节点开始和结束。我们通过路径/旅行上的节点序列或仅通过按服务顺序的请求序列来表示路径/旅行。例如,如果请求的顺序是R1 ∙ ∙ ∙ Rn,则相应的路径是P =r0s1d1 ∙ ∙ ∙ sndn。03注意总延迟和平均延迟相差n倍,优化这两个目标是等价的。0(假设根节点r0)。对于路径P,让Lat(P,i)是路径上第i个请求的延迟,即从路径的根到请求的目的地的距离,而Lat(P) = �ni=1Lat(P,i)是路径的总延迟。总延迟目标是k辆车辆的路径的延迟之和。注意,如果有一辆车位于根节点r0,并按顺序服务所有请求R1 ∙ ∙ ∙ Rn,则0Lat(P, i) =0�Lat(P, i - 1) + cd(i-1)si + csi(di, i > 1 0,i = 0,0其中d0 =r0。给定一组边Q和距离函数c,令c(Q)为c中边的长度之和;如果P是一条路径,则c(P)是路径的长度。我们经常对路径和旅行进行连接和快捷操作。如果两条路径/旅行在同一个节点相遇,即一条路径以该节点结束,另一条路径以该节点开始,我们可以将它们连接在一起,创建一个更长的路径/旅行。我们可以通过跳过节点来简化路径/旅行,以避免重复访问节点;如果距离满足三角不等式(在度量空间中成立),则这将导致路径/旅行的长度最多为原始长度。03 LP框架0Track:Web WWW 2018的社交网络分析和图算法,2018年4月23日至27日,法国里昂��3820在根节点的距离被覆盖之前。约束(3)-(5)是为了车辆的路线:(3)确保车辆的路线在时间t之前的部分必须访问到时间t之前被该车辆访问的每个节点,(4)确保该路线的长度确实不超过t,最后(5)试图编码路线形成一条路径。(注意,约束(5)显然是有效的,也可以包括约束条件�a∈δout(r),zia,t≤1,对于所有i,t。)0min �0对于所有v,t,i,txiv,t(LP)0s.t. �0对于所有v,t,i,txiv,t≥1(1)0xiv,t=0,对于所有v,t,i(2)�0对于所有t,i,a∈δin(S),zia0对于所有S�V\{r},v∈S,对于所有t,i,t'≤txiv,t'(3)0�0对于所有t,i,aca,zia,t≤t(4)0对于所有t,i,a∈δin(v),zia0对于所有v,t,i,a∈δout(v),zia,t(5)0x,z≥0。(6)0为了将分数解舍入为车辆的一组路线,我们使用了加权有向图和连接图的多项式时间树形装箱结果。以下结果不要求边的成本对称或形成度量,而是适用于任意非负边成本。0定理1([23]中的定理3.1):设D =(U +r,A)是具有非负整数边权重{we}的有向图,其中r∈U是根节点,对于所有u∈U,|δin(u)|≥|δout(u)|。对于任何整数K≥0,可以在多项式时间内找到以r为根的外向树F1,...,Fq和整数γ1,...,γq,使得�qi = 1γi =K,对于所有e∈A,�i:e∈Fiγi≤we,并且对于所有u∈U,�i:u∈Fiγi0连接图是由Goemans和Kleinberg [15]引入的,然后由Archer和Blasiak[4]扩展为一种方便的方法,用于表示从较短路径构建车辆路线的连接过程。与非负数序列w1 =0,...,wn(以0开头)对应的连接图,表示为CG(w1,...,wn),是一个有n个节点和长度为n-i+j的弧(i,j)。02�wj,对于所有i0,我们可以计算出一个(ϵ)近似解。0定理5.对于带有点对点请求的单仓库k-MLP问题,我们可以在多项式时间内计算出一个(0对于任意ϵ>0,我们可以计算出一个(ϵ)近似解。(2.5µ�≈8.978。)0定理6.对于带有点对点请求的多仓库k-MLP问题,我们可以在多项式时间内计算出一个(0对于任意ϵ>0,我们可以计算出一个(ϵ)近似解。04.1 单仓库0定理5的算法在算法1中给出;MLP的改进比例(定理4)是由于一个简单的观察和基本相同的算法和分析。正如前面提到的,我们将给定的无向问题实例转化为有向度量中的点请求实例(参见算法1的第1步),并在第3节中应用线性规划方法。转化为有向度量是无损的,因为在G和G'中的可行解之间存在一一对应关系,并且相应的解具有相同的总延迟。算法1在步骤1-7中使用有向实例G',在步骤7和8中使用给定的无向实例G。分析与[23]中的分析非常相似,但由于请求的“方向性”,所以更加复杂,因为车辆通过从源到目的地而不是相反的方式来服务请求。引理7将第5步中C的下包络曲线f与第2步中的分数最优解的目标值联系起来,就像[23]中一样,因为这只需要非负的边成本。0论文集:社交网络分析和Web图算法WWW 2018,2018年4月23日至27日,法国里昂Proof. This is a modified version of Lemma 6.3 in [23] and hasTrack: Social Network Analysis and Graph Algorithms for the WebWWW 2018, April 23-27, 2018, Lyon, France3830证明。这是[23]中引理6.3的修改版本,其证明基本相同。唯一的区别是我们添加了0引理7.(i)对于任意n个函数f(x)的积分,有∫ n 1 f ( x ) dx ≤ 5 �u ∈ V , t ∈[ T ] tx ′ u , t .(ii)如果ℓ是f的一个拐点,则存在一棵树Q�ℓ和时间t�ℓ满足算法1中第5步中所述的性质。0点|V(Qtℓ)∩S(t)|,3c'(Qtℓ)0k + 2t≤C。根据定理1,E[c'(Qtℓ)] ≤0kt,因此E[3c'(Qtℓ)]0k + 2t≤5t。其余部分遵循相同的0证明和引理得出。□0引理8。如果(ℓ,f(ℓ))是f的一个角点,则每个旅行0k + 2t*ℓ。特别地,每个旅行的第一个和最后一个边缘之外的部分0连接到根节点的长度最多为2c'(Q*ℓ)0k。0证明。当打破循环Zℓ时,断点可以在节点上或边缘上。在前一种情况下,该节点出现在两个连续的段中,在后一种情况下,该边缘被移除。在任一情况下,Q*ℓ的所有节点都将包含在至少一个段中,并且相应的请求将在k个旅行Z1,ℓ,...,Zk,ℓ之一中被覆盖,构造如下。考虑一个段和相应的旅行Zi,ℓ。在循环Zℓ中,我们通过“正确”方向的边缘(即与旅行方向相同)首次访问节点,通过“错误”方向的边缘(即与旅行方向相反)进行后续访问,因此,该段由正确和错误方向的边缘组成。不失一般性,设R1,...,Rq是在给定段中首次访问的顶点对应的请求。然后,Zi,ℓ = r0s1d1...sqdq r0。对于P =d1s2d2...sqdq,我们证明0k。根据c'的定义,G'中的每条弧对应于原始图G中长度为2的路径。我们用形式为di sj dj的路径替换段的边缘。0k,并且将P的节点作为子序列包含在其中,不一定是连续的。我们通过快捷方式来确切地得到P,其中快捷方式涉及直接从di到si+1的路径,对开始或结束进行截断。0对于完成P形成Zi,ℓ的两条路径r0s1d1和dqr0,我们将每条路径的长度上界设为t*ℓ。设G'中的根节点为r0v1,vq∈V'是对应于d1和dq的顶点。由于v1和vq在Q*ℓ∩S(t*ℓ)中,c'rv1 ≤ t*ℓ和c'rvq ≤ t*ℓ。然后,cr0s1 + cs1d1 = c'rv1 ≤t*ℓ和cr0dq ≤ cr0sq + csqdq = c'rvq ≤ t*ℓ。它0由此可得c(Zi,ℓ) = c(P) + cr0s1 + cs1d1 + cr0dq ≤ 2c'(Q*ℓ)0k + 2t*ℓ。□0定理5的证明。我们声称算法1返回的解的总延迟最多是CG(f(1),...,f(n))中PC的长度。根据推论3和引理7的第(i)部分,PC的长度最多为µ*。02个节点v,t之间的延迟为2.5µ * v,i,t tx i v,t。此外,v,i,t txiv,t最多是最优延迟的(1+ϵ)倍,其中(1+ϵ)因子是由于缩放和舍入造成的。我们现在证明这个命题。更具体地说,我们通过归纳证明总延迟最多是CG(f(1),...,f(n))中PC的长度。根据定理2和引理7,对于PC上的每个角点(ℓ,f(ℓ)),存在Q*ℓ和t*ℓ满足第5步中所述的属性。根据引理8,从Q*ℓ创建的路径0k + 2 t � ℓ 以正确的方向,并覆盖与 Q � ℓ的顶点对应的所有请求。特别地,每个游览除了连接到根节点的第一条和最后一条边之外的部分都有0k 以正确的方向。归纳假设,我们已经通过连接到 P C上的节点对应的游览串联的部分解覆盖了至少 o 个请求。假设我们接下来选择一条边 (o , ℓ ) ,并考虑当我们将 Z i ,ℓ 连接到车辆 i的路径时,对总延迟的额外贡献。注意,结果的部分解至少覆盖了 ℓ个请求。在当前连接步骤中覆盖的每个请求产生的额外延迟最多为 f ( ℓ )02 期望值。为了看到这一点,设 L 是游览 Z i ,ℓ 的不包括根节点 r 0 的部分的长度,L ′是被游览覆盖的请求的目的地之前的长度。以概率 304 ,请求产生的额外延迟为 t ℓ + L ′ 。以概率 104 ,额外延迟最多为 t ℓ + 3 ( L − L ′ ),因为在相反方向上的遍历的长度上界是正确方向上对应遍历的长度的三倍(考虑到 s i- d i 部分三倍)。例如,如果 s 1 d 1 . . . s n d n是正确方向上的遍历,那么反向遍历是 s n d n s n d n . . . d 1 s 1 d 1 s 1的简化版本,其长度最多是 s 1 d 1 . . . s n d n的三倍。期望值上,请求产生的额外延迟最多为 302,这是0k 。通过类似的论证,每个在连接之后仍未覆盖的请求在期望中产生的额外延迟最多为f ( ℓ ) 。正确方向上的遍历长度最多为 2 t ℓ + L,相反方向上的遍历长度最多为 2 t ℓ+ 3 L。期望值上,额外延迟最多为 2 t ℓ + 3 L02 ≤ f ( ℓ ) 。有恰好 ℓ 个请求由游览 Z 1 ,ℓ , . . . , Z k ,ℓ覆盖,并且当前连接步骤中至多覆盖 ℓ − o个新请求。每个请求在当前连接步骤中产生的额外延迟最多为 f ( ℓ )02 。最多还有 n − ℓ个请求需要被覆盖,它们每个在期望中产生的额外延迟最多为 f ( ℓ) 。总的增加0延迟最多为 f ( ℓ )02 � 这是�3840算法 1。输入是一个单仓库 k -MLP 实例 G = ( V , E ) ,具有点对点请求和根节点 r 0 。01. 定义一个有向图 G ′ = ( V ′ , A ) ,有 n + 1 个节点对应于根节点/请求和弧 ( v i , v j ) ,其长度为 c ′ v i v j = c d i s j + c s j d j ,对于所有请求 i 和 j 。将根节点 r 0 视为第 0 个请求 ( s 0 , d 0 ) ,其中 r 00ϵ � 失去一个 ( 1 + ϵ ) -因子。2. 计算给定 G ′ 和 { c ′ a } 实例的 (LP) 的最优解 ( x , z ) 。让 x ′ v , t = � i x i v , t , z ′ a , t = � i z i a , t ′ 对于所有 v , a , t。3. 初始化 C ← {( 1 , 0 )} , Q ← � 。令 K 是这样的 Kz ′ a , t 对于所有 a , t 是整数。对于 t ∈ [ T ] ,定义 S ( t ) = { u ∈ V : � t t ′ = 0 x ′ u , t ′ > 0 }。(注意对于所有 t > 0 ,r ∈ S ( t ))。4. 对于所有 t = 1 , . . . , T ,执行以下操作。在带有边权重 { Kz ′ a , t } a ∈ A 和整数 K (以及根节点 r ) 的有向图 D上应用定理 1,以获得一个0k+2t�到C,并将Qtℓ添加到Q。5.对于所有ℓ=1,...,n,计算f(ℓ),其中f:[1,n]→R+是C的下包络曲线。我们在引理7中证明,对于每个角点�ℓ,f(ℓ)�0k+2t*ℓ,并且maxv∈Q*ℓ∩S(t*ℓ)c'rv≤t*ℓ。6.在连接图CG(f(1),...,f(n))中找到最短的1到n路径PC。7.对于PC上的每个节点ℓ>1,执行以下操作。从Q*ℓ上的r开始进行DFS遍历,以获得一个循环Zℓ,以无向方式使用Q*ℓ的每条弧两次。将Zℓ分解为k个段,每个段的长度至多为2c'(Q*ℓ)/k。对于每个段,创建相应的路径Zi,ℓ在G中,从r0开始并以r结束,仅满足在欧拉路径中该段内首次出现的请求,并按照首次出现的顺序。跳过不在S(t*ℓ)中的请求。以概率304,在相反的方向上(满足相同的一组请求但顺序相反)。这产生了一组k个路径Z1,ℓ,...,Zk,ℓ。8.对于每个i =1,...,k,将路径Zi,ℓ连接起来,对应于连接图CG(f(1),...,f(n))上的节点ℓ,以获得车辆i的路径,如果请求已经满足,则进行快捷处理。0等于连接图CG(f(1),...,f(n))中边(o,ℓ)的长度。根据归纳法,总延迟至多为PC的长度。对于运行时间,由于T=poly(I,1/ϵ)0ϵ),我们可以为(3)设计一个分离Oracle,即一个最小割算法,并在poly(I,1/ϵ)的时间内解决(LP)。0ϵ)。□0定理4的证明。我们对算法1进行与上述相同的分析。近似比的改进来自于我们无需在步骤7中将循环Zℓ分解为k个路径,因为我们只有一个车辆。此外,我们注意到Zℓ的遍历长度在任一方向上都不超过2c'(Q*ℓ)。在步骤4中,我们现在添加点� | V(Qtℓ)∩S(t)|,2c'(Qtℓ)�0为了利用这一事实,我们遵循定理5的证明,因此现在获得了一个µ�-近似。□0我们注意到对于单仓库k-MLP问题,我们可以通过利用[23]中提出的更组合的方法来避免近似因子中的可加ϵ。在这种方法中,我们直接获得树林而无需求解LP问题。具体来说,对于每个i =1,...,n,我们的目标是找到至少包含i个请求的最小c'-代价树林(这反过来利用了树林的打包)。然后我们再次使用连接图来选择将被转换为路径的子集,然后将它们连接起来。这更接近我们在实验结果中遵循的方法。04.2多个仓库0对于更一般的多仓库k-MLP问题,我们提供了一个归约,证明了在无向度量上点对点请求版本的α-近似算法可以得到在无向度量上点对点请求版本的3α-近似算法。具体来说,以下结果立即使用[23]中多仓库k-MLP问题中点请求的(8.496+ϵ)-近似算法得到定理6。本节剩余部分的证明推迟到全文[12]中。0引理9.让OPT和OPT'分别表示具有点对点请求的多仓库k-MLP实例和通过在c'边缘成本下进行的减少所得到的具有点请求的多仓库k-MLP实例的最优值。那么OPT ≤ OPT' ≤3∙OPT。因此,对于点请求实例的α近似解可以得到点对点请求实例的3α近似解。0因子-3减少的主要思想是通过源节点识别请求,并以对称方式将请求特定的距离 c s i d i合并到源之间的距离中。我们将根节点视为具有相同源和目标节点的虚拟请求,用于减少。具体而言,G'仅包含根节点和表示请求的节点,G'中的v i 和v j 之间的距离为c'v i v j = c s i s j + c s i d i + c s j dj。很容易看出,(G',c')是一个度量。然后,我们使用点请求的算法解决所得到的问题实例,并将计算出的路径转换为原始问题实例中的路径。通过这种减少,可以观察到在(G',c')实例中的根路径的延迟对应于原始问题实例中的一种特定类型的路径,我们称之为回溯路径,在此路径中,车辆通过从s i 到d i ,然后返回s i,然后移动到下一个请求来满足每个请求i。回溯路径仅用于分析目的,我们通过捷径这些路径以获得车辆的最终路径。显然,请求排序和路径以及回溯路径之间存在双射映射。如果请求的顺序是R 1 ∙ ∙ ∙ R n,等效地对应于路径P,则相应的回溯路径是P b = r 0 s 1 d 1 s 1 s2 d 2 s 2 ∙ ∙ ∙ s n d n 。0如果请求的顺序是R 1 ∙ ∙ ∙ R n ,在车辆从根节点r 0开始的路径P上,相应回溯路径P b 上的第i个请求的延迟确定为0Lat(P b, i) =0Lat(P b, i - 1) + c d i - 1 s i - 1 + c s i - 1 s i + c s id i ,i > 10,i = 0。0Track: Social Network Analysis and Graph Algorithms for the Web WWW 2018,2018年4月23日至27日,法国里昂Lat+(P,i) =max{Lat+(P,i − 1) + cdi−1si ,Ti } + c
下载后可阅读完整内容,剩余1页未读,立即下载
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)