LP-Based Approximation Algorithms for Multi-Vehicle Minimum Latency Problems
The research discusses LP-based approximation algorithms for solving Multi-Vehicle Minimum Latency Problems, focusing on minimizing waiting times for vehicles visiting clients starting from a depot. Various cases, including single- and multi-depot scenarios, are explored, and significant improvements in approximation factors are achieved compared to previous works. LP-based techniques are developed, demonstrating the effectiveness of leveraging LP relaxations for such complex routing problems.
Uploaded on Dec 11, 2024 | 0 Views
Download Presentation
![](/assets/img/so-down.gif)
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
LP-based Approximation Algorithms for Multi-Vehicle Minimum Latency Problems Chaitanya Swamy University of Waterloo Joint work with Ian Post University of Waterloo
Minimum-latency problem (MLP) starting root/depot node/client Find a path P that visits all clients starting from depot to:
Minimum-latency problem (MLP) starting root/depot node/client total latency Find a path P that visits all clients starting from depot to: minimize (sum of node/client waiting times = v P cP(v) ) Classical vehicle-routing problem. Also called traveling-repairman problem or delivery-man problem Problem is hard to approximate better than some constant
Multi-vehicle MLP r2, r3 r1 r4 root/depot nodes node/client Given: (multi) set R={r1, ,rk} of not necessarily distinct roots Find paths P1, Pk rooted at r1, ,rk that together visit all nodes, minimize (sum of node waiting times = v Pi cPi(v) )
Multi-vehicle MLP r2, r3 r1 r4 multi-depot k-MLP root/depot nodes node/client Given: (multi) set R={r1, ,rk} of not necessarily distinct roots Find paths P1, Pk rooted at r1, ,rk that together visit all nodes, minimize (sum of node waiting times = v Pi cPi(v) ) Special case r1= =rk: single-depot k-MLP
Our results Design: 8.497-approx. for multi-depot k-MLP 7.183-approx. for single-depot k-MLP First improvements in over a decade; previous best factors: 12 for multi-depot (CK04 + CGRT03) 8.497 for single-depot (FHR03 + CGRT03) Guarantees extend to various generalizations: weighted latency, node-depot service constraints, node service times Develop LP-based techniques Exploit configuration LPs (for 8.5-approx. for multi-depot k-MLP) and bidirected LPs (for 7.183-approx. for single-depot k-MLP) First concrete evidence that LP-relaxations can be effectively leveraged for minimum-latency problems Chakrabarty-S11 proposed some LPs but no improvements via these LPs; our LPs are subtly different, except when k=1
Our results (contd.) Obtain a stronger configuration LP that sheds further light on the power of LPs and why they are promising Integrality gap of LP 3.5912 for multi-depot k-MLP give an efficient rounding procedure OPTLP combinatorial lower bound that generalizes the q-stroll lower bound for MLP Shows (non-constructively) integrality gap 3.03 for MLP (follows from AB10) Do not know how to solve LP in general, but can solve it for k=1 yields LP-relative ( *+ )-approx. for MLP *
Our results (contd.) Use bidirected LP to obtain following prize-collecting result of independent interest:
Our results (contd.) Use bidirected LP to obtain following prize-collecting result of independent interest: given root r, node penalties { v}, can efficiently compute one r-tree T s.t. c(T)+ (V(Tc)) mincollection P of r-paths ( P P c(P) + (V\ UP P V(P))) Substantially generalizes a result of CGRT03, who show the above when P consists of only one r-path Our proof is much simpler: exploit bidirected LPs and arborescence-packing results of BFJ95 (unlike CGRT03, infeasible to guess end-points of paths in P ) Yields a combinatorial 2 *-approx. for single-depot k-MLP
A brief history of MLP-time OPT = minr-paths P(1) P(2) P(n) [c(P(1))+ +c(P(n))] |V(P(q))|=q for all q
Template for approximating MLP (i.e., 1-MLP) OPT = minr-paths P(1) P(2) P(n) [c(P(1))+ +c(P(n))] |V(P(q))|=q for all q minr-paths P(1),P(2), ,P(n) [c(P(1))+ +c(P(n))] |V(P(q))|=q for all q = q=1 n OPTq q-stroll lower bound (CGRT03) min-cost r-path spanning q nodes
Template for approximating MLP q-stroll lower bound (CGRT03) OPT q=1 n OPTq Theorem (BCCPRS94): Given trees T(1), ,T(n) with |V(T(q))|=q for all q, can obtain solution of cost O(1).[c(T(1))+ +c(T(n))] GK96: O(1) = *; Concatenation graph to find best way of combining tours obtained from T(q) s So if each T(q) is an -approx. q-MST, get . *-approx. (2+ ) *-approx.: G96, AK00
Template for approximating MLP q-stroll lower bound (CGRT03) OPT q=1 n OPTq Theorem (BCCPRS94 + GK96): Given r-trees T(1), ,T(n) with |V(T(q))|=q for all q, can obtain solution of cost *.[c(T(1))+ +c(T(n))] So if each T(q) is an -approx. q-MST, get . *-approx. [ALW03]: Let Z(1), ,Z(s) be random r-trees s.t. |V(Z(1))|=1, |V(Z(s))|=n with probability 1. Let f:[1,n] + be lower-envelope curve of Uq=1, ,s Usupport of Z(q) (|V(Z(q))|, c(Z(q))) Can get solution of cost *(f(1)+ +f(n)) c(Z) 2 *-approx.: can get trees T(q) s.t. E[|V(T(q))|] q, E[c(T(q))] 2OPTq-MST *-approx. (CGRT03): can get T(q) s.t. E[|V(T(q))|] q, E[c(T(q))] OPTq n |V(Z)| 1
Template for approximating k-MLP Concatenation theorem (Post-S14): Let (Z1(1), Z2(1), , Zk(1)), (Z1(2), , Zk(2)), , (Z1(s), , Zk(s)) be a sequence of k-tuples where each Zi(q) is a random tree rooted at ri. Suppose |Ui=1, ,k V(Zi(s))|=n with probability 1. Let f:[1,n] + be lower-envelope curve of Uq=1, ,s Usupport of Z(q)(|Ui=1, ,k V(Zi(q))|, maxi=1, ,k c(Zi(q))) bottleneck cost n total coverage 1
Template for approximating k-MLP Concatenation theorem (Post-S14): Let (Z1(1), Z2(1), , Zk(1)), (Z1(2), , Zk(2)), , (Z1(s), , Zk(s)) be a sequence of k-tuples where each Zi(q) is a random tree rooted at ri. Suppose |Ui=1, ,k V(Zi(s))|=n with probability 1. Let f:[1,n] + be lower-envelope curve of Uq=1, ,s Usupport of Z(q)(|Ui=1, ,k V(Zi(q))|, maxi=1, ,k c(Zi(q))) Can get a solution of cost *. 1 bottleneck cost ?? ? ?? n total coverage 1
Template for approximating k-MLP Concatenation theorem (Post-S14): Let Z(1), Z(2), , Z(s) be a suitable sequence of k-tuples of {ri}-trees. Let f:[1,n] + be their lower-envelope curve can get solution of cost *. 1 Key question: How to get good k-tuples of {ri}-trees? For multi-depot k-MLP: CK04 solve a suitable variant of max k-cover: lose various factors Our approach: use configuration LP yields, for each t, {ri}-trees, each of cost t; fall behind LP-coverage by time t, so factor degrades from * to 8.497 ?? ? ??
Configuration LP for k-MLP configurations for vehicle i at time t Let Pi(t)= all ri-paths of length at most t. xiv,t : indicates if node v is visited at time t by vehicle i ziP, t : indicates if path P P i(t) is used to visit clients on vehicle i s route with latency t T : upper bound on node latency; assume poly-bounded (can ensure via scaling + rounding); t indexes {1, ,T} Minimize i, v, t txiv,t subject to, i,t xiv,t 1 P P i(t) ziP, t 1 P P i(t):v P ziP, t t t xiv,t x, z 0. (P) for all v for all i, t for all v, i, t
Configuration LP for k-MLP Let Pi(t)= all ri-paths of length at most t. xiv,t : indicates if node v is visited at time t by vehicle i ziP, t : indicates if path P P i(t) is used to visit clients on vehicle i s route with latency t Minimize i, v, t txiv,t subject to, i,t xiv,t 1 P P i(t) ziP, t 1 P P i(t):v P ziP, t t t xiv,t x, z 0. Theorem: Can efficiently compute (x,z) of value (1+ )OPTP s.t. {zi ,t} is a convex combination of ri-trees of length (1+ )t. Theorem: Can round such an (x, z) losing a factor of 8.497. (P) for all v for all i, t for all v, i, t
Rounding algorithm Let (x, z): solution of value (1+ )OPTP where {zi ,t}: convex combination of ri-trees of length (1+ )t 1. For each time t=tj in a suitable random geometric sequence t0, t1, , and for every vehicle i=1, ,k independently : Sample an ri-tree Q from {zi ,t}: has length (1+ )t. Double and shortcut Q to obtain a cycle; traverse this in a random direction to get tour Zi, j 2. For all i, concatenate tours Zi,0, Zi,1, to get i s route. Analysis: Let pv, j = Pr[v is not covered by end of time-pt. tj] Lemma: pv, j (1 e 1) i t >tj xiv,t + e 1 .pv, j-1 for every v, j. Total extent to which LP does not cover v by time tj
Rounding algorithm Let (x, z): solution of value (1+ )OPTP where {zi ,t}: convex combination of ri-trees of length (1+ )t 1. For each time t=tj in a suitable random geometric sequence t0, t1, , and for every vehicle i=1, ,k independently : Sample an ri-tree Q from {zi ,t}: has length (1+ )t. Double and shortcut Q to obtain a cycle; traverse this in a random direction to get tour Zi, j 2. For all i, concatenate tours Zi,0, Zi,1, to get i s route. Analysis: Let pv, j = Pr[v is not covered by end of time-pt. tj] Lemma: pv, j (1 e 1) i t >tj xiv,t + e 1 .pv, j-1 for every v, j. Using this and choosing the geometric sequence suitably, can show that E[latency of v] 8.497 ( i, t txiv,t) for every v.
Template for approximating k-MLP Concatenation theorem (Post-S14): Let Z(1), Z(2), , Z(s) be a suitable sequence of k-tuples of {ri}-trees. Let f:[1,n] + be their lower-envelope curve can get solution of cost *. 1 Key question: How to get good k-tuples of {ri}-trees? For multi-depot k-MLP: CK04 solve a suitable variant of max k-cover: lose various factors Our approach: use configuration LP to obtain k-tuples of {ri}-trees For single-depot k-MLP: FHR03 obtain an r-tree for each i=1, ,k separately using q-MST as black-box. So do not quite cover q nodes; factor degrades to 8.497. Our approach: use bidirected LP extract, for each t, a random r-tree T s.t. E[|V(T)|] (LP-coverage by time t), E[c(T)] kt (and crv t for all v T) Yields k-tuple of expected bottleneck cost 2t get 2 *-approx. ?? ? ??
Bidirected LP for single-depot k-MLP Bidirect edges to get digraph both (u,v) and (v,u) get cost cuv xv,t : indicates if node v is visited at time t; is 0 if crv>t zt, a : indicates if arc a is on some vehicle s path (rooted away from r) up to time t T : upper bound on node latency; assume poly-bounded (can ensure via scaling + rounding); t indexes {1, ,T} Minimize v, t txv,t subject to, t xv,t 1 a ca zt,a k.t zt( in(v)) zt( out(v)) a into S zt, a t t xv,t x, z 0. looking for paths (P) for all v for all t for all v r, t for all S: r S, v S, t Exploit that we are
Rounding bidirected LP xv,t : indicates if node v is visited at time t; is 0 if crv>t zt, a : indicates if arc a is on some vehicle s path up to time t Minimize v, t txv,t subject to, t xv,t 1 a ca zt,a k.t zt( in(v)) zt( out(v)) a into S zt, a t t xv,t x, z 0. Theorem: Given a solution (x,z) to (P), for all t zt dominates a convex combination of r-rooted out-trees s.t. Pr[v is covered] t t xv,t for all v. Follows essentially from arborescence-packing results of BFJ95 since r v connectivity with arc-capacities {zt, a} is t t xv,t (P) for all v for all t for all v r, t for all S: r S, v S, t
Rounding bidirected LP xv,t : indicates if node v is visited at time t; is 0 if crv>t zt, a : indicates if arc a is on some vehicle s path up to time t Minimize v, t txv,t subject to, t xv,t 1 a ca zt,a k.t zt( in(v)) zt( out(v)) a into S zt, a t t xv,t x, z 0. Theorem: Given a solution (x,z) to (P), for all t zt dominates a convex combination of r-rooted out-trees s.t. Pr[v is covered] t t xv,t for all v. So for all t, can get a random k-tuple of r-trees (Z1(t), ,Zk(t)) s.t. E[maxi=1, k c(Zi(t))] 2t, E[|Ui=1, ,k V(Zi(t))|] v t t xv,t (P) for all v for all t for all v r, t for all S: r S, v S, t Gives a 2 *-approximation using concatenation theorem
Prize-collecting arborescences Goal: Given root r, node penalties { v }, find an r-tree T s.t. c(T)+ (Tc) mincollection P of r-paths ( P P c(P) + (V\ UP P V(P))) Consider following bidirected relaxation for finding best path- collection P. Bidirect edges to get digraph both (u,v) and (v,u) get cost cuv . Minimize a ca za + v v xv subject to, z( in(S)) + xv 1 z( in(v)) z( out(v)) x, z 0. Exploit that we are looking for paths (PCLP) for all S: r S, v S for all v r
Prize-collecting arborescences Goal: Given root r, node penalties { v }, find an r-tree T s.t. c(T)+ (Tc) mincollection P of r-paths ( P P c(P) + (V\ UP P V(P))) Minimize a ca za + v v xv subject to, z( in(S)) + xv 1 z( in(v)) z( out(v)) x, z 0. OPTPCLP mincollection P of r-paths ( P P c(P) + (V\ UP P V(P))) Theorem: Given a (PCLP)-solution (x,z) z dominates a convex combination of r-rooted out-trees s.t. Pr[v is not covered] xv for all v. Follows essentially from arborescence-packing results of BFJ95 since r v connectivity with arc-capacities {za} is 1-xv Best tree T in convex combination satisfies c(T)+ (Tc) OPTPCLP (PCLP) for all S: r S, v S for all v r
Open Questions Improve the approximation factors for k-MLP. Can one match the current best factor, *, for MLP? Separation oracle for stronger configuration LP (with integrality gap *) is multi-vehicle orienteering problem how well can this be approximated? Improve approximation for MLP. LPs seem promising advantage over q-stroll bound is that LP couples the different paths. How to exploit this? How good are (our) LPs for MLP or k-MLP? For 1-MLP, bidirected LP (weakest) also has integrality gap * Other uses of configuration LPs for vehicle-routing? Only aware of Friggstad-S14 as another application.