Regret-Bounded Vehicle Routing Approximation Algorithms
Regret-bounded vehicle routing problems aim to minimize client delays by considering client-centric views and bounded client regret measures. This involves measuring waiting times relative to shortest-path distances from the starting depot. Additive and multiplicative regret measures are used to address the fundamental challenges in regret-bounded VRPs, with algorithms developed for both types of regret. An O(1)-approximation algorithm for additive regret-bounded VRP has been devised based on LP-rounding techniques.
Download Presentation
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
Approximation Algorithms for Regret-Bounded Vehicle Routing and Applications Chaitanya Swamy University of Waterloo Joint work with Zachary Friggstad University of Alberta
Vehicle routing problems (VRPs) Metric space starting depot r client Typical setup: visit all clients via route(s) starting from depot so as to minimize client delays: e.g., max client delay (TSP) But this does not differentiate between clients close to the depot and those far away from it Nearer clients may face more delay than further-away clients source of dissatisfaction
Regret-bounded VRP Metric space starting depot r client Adopt a more client-centric view: seek bounded client regret client regret measure of waiting time of a client relative to its shortest-path distance from depot
Regret-bounded VRP cP(v) Metric space r starting depot P client v Dv cP(v) = time to reach v along P Adopt more client-centric view: ensure bounded client regret client regret measure of waiting time of a client relative to its shortest-path distance from depot Dv (min. possible waiting time of v) Two natural ways to measure regret: additive regret of v = cP(v) Dv multiplicative regret of v = cP(v)/Dv
Regret-bounded VRP cP(v) Metric space r starting depot P client v Dv Two natural ways to measure regret: additive regret of v = cP(v) Dv multiplicative regret of v = cP(v)/Dv Two problems: Given regret bound R, find minimum no. of paths rooted at r that cover all clients such that: 1. additive regret of each node R 2. multiplicative regret of each node R multiplicative RVRP additive RVRP
Both additive- and multiplicative- RVRP are NP-hard to approximate to a factor better than 2. Additive RVRP turns out to be more fundamental. (RECALL: Cover all nodes with the minimum no. of rooted paths such that additive regret of each node v R.) cP(v) Dv (where v lies on path P) Algorithms and techniques developed for additive RVRP also yield algorithms for: multiplicative RVRP and other regret-based VRPs other classical vehicle routing problems In the rest of the talk: regret additive regret, regret-related VRP VRP under additive regret RVRP additive-RVRP
Main result 30 We devise an O(1)-approx. algorithm for (additive) RVRP. Our algorithm is based on LP-rounding: contrasts with our limited understanding of LPs for VRPs (with TSP being the exception) We write a set-cover style configuration LP (with path variables): Previously only O(log n)-approximation and integrality gap was known follows easily from set-cover analysis + orienteering Our main contribution: we show how to exploit LP-structure and round an LP-solution losing only a constant factor One of the few results showing how to leverage configuration LPs (other such results are known for bin-packing, Santa Claus problem, min-makespan scheduling, combinatorial auctions) Near-optimal LP solution can be efficiently obtained: orienteering yields approximate separation oracle for dual LP
Other results Using our algorithm for RVRP and/or our techniques, we obtain: O(log(R/(R-1))-approx. for multiplicative-RVRP O(min{log D/log log D,OPTLP, log n})-approx. for distance-constrained VRP: cover all nodes with minimum no. of rooted paths s.t. waiting time cP(v) of each node v is D; improves upon the previous-best O(min{log D, log n})-guarantee (Nagarajan-Ravi) O(k2)-approx. for k-RVRP: use k paths to cover nodes and minimize max-regret; previous guarantees were only for k=1 via min-excess path (Blum et al.) also show that integrality gap of configuration LP is k
Other results (contd.) Also consider directed graphs. Observe that one can replace regret (in objective or constraint) by cost (in a different asymmetric metric) Hence, known results give: (a) O(log n)-approx. for RVRP; (b) O(k2 log n)-approx. for k-RVRP c-approx. for RVRP 2c-approx. for ATSP
Related work Additive-RVRP proposed in Operations Research literature under the generic name schoolbus problem Bock et al. studied RVRP and k-RVRP, and design: an O(log n)-approximation using set cover + orienteering a 3-approximation algorithm in tree metrics a 12.5-approximation for k-RVRP in tree metrics Additive regret also studied by Blum et al., who used excess to denote regret. They used the min-excess path problem to approximate orienteering. Nagarajan-Ravi studied distance-constrained VRP: give an O(min{log D, log n})-approx. (D=distance bound) 2-approximation in tree metrics
A useful transformation Define cregu,v := Du + cuv Dv for all u, v. creg is an asymmetric metric call this the regret metric cregr,v = 0 for all v For any path P and any v P, cregP(v) = cP(v) Dv = regret of v along P So RVRP minimize no. of rooted paths of creg-length at most R that cover all nodes distance-constrained VRP in asymmetric creg-metric c-length and creg-length of any cycle are equal
Building some intuition Suppose that all nodes were at the same distance from r V = nodes other than r r
Building some intuition Suppose that all nodes were at the same distance from r V = nodes other than r r V can be grouped into k paths, each of creg-cost = c-cost R can partition V into k components of total cost kR
Building some intuition Suppose that all nodes were at the same distance from r V = nodes other than r r V can be grouped into k paths, each of creg-cost = c-cost R can partition V into k components of total cost kR by doubling + shortcutting, get k paths of total cost 2kR Attach each path to r (pick an end-node v, add rv edge) to get a rooted path. Total creg-length of resulting paths 2kR
Building some intuition Suppose that all nodes were at the same distance from r V = nodes other than r r V can be grouped into k paths, each of creg-cost = c-cost R can partition V into k components of total cost kR by doubling + shortcutting, get k paths of total cost 2kR Attach each path to r (pick an end-node v, add rv edge) to get a rooted path. Total creg-length of resulting paths 2kR Break each resulting rooted path into segments of creg-length R and attach each segment to r (this does not increase regret) This gives 3k rooted paths covering V, each of creg-length R.
Lemma: Given at most ak paths of total creg-cost at most bkR, we can efficiently find at most (a+b)k paths, each of creg-cost R.
Lemma: Given at most ak paths of total creg-cost at most bkR, we can efficiently find at most (a+b)k paths, each of creg-cost R. So, suffices to find O(OPT) paths of total creg-length O(R.OPT). path P Dv Lemma (Blum et al.): total c-cost of red edges on P 1.5creg(P).
Configuration LP Let C(R) = {rooted paths P: cregP(v) = cP(v) Dv R for all v P} Minimize P C(R) xP s.t. P C(R): v P xP 1 v V, x 0 Dual separation problem is an orienteering problem There is a (2+ )-approximation for orienteering (Chekuri et al.) This yields an approximate separation oracle, so a (2+ )-approx. solution x* to the configuration LP can be computed efficiently. Let k* = P C(R) x*P .
Rounding the LP solution x* Easy case: suppose that directing edges of all paths P such that x*P>0 away from r gives an acyclic graph Then x* is (the path-decomposition of) an acyclic flow of value k* and creg-cost k*R that covers every node Integrality of flows + acyclicity can find k* paths of total creg-cost k*R that cover all nodes
Rounding the LP solution x* Of course, x* need not yield an acyclic flow. Form a set W of witness nodes, partition V\W into components: 1. Suitably shortcutting paths P with x*P>0 yields an acyclic flow that covers every node in W to an extent of at least 0.5 has value at most k* and creg-cost at most k*R can obtain O(k*) paths covering W of total creg-cost O(k*R) 2. The total (c-)cost of all components is O(k*R), and every component contains r or some witness node we can attach the V\W to the paths found in step 1 incurring O(k*R) total additional regret (and cost) So overall, obtain O(k*) paths with total regret O(k*R)
Rounding the LP solution x* Of course, x* need not yield an acyclic flow. Form a set W of witness nodes, partition V\W into components: 1. Shortcutting paths P with x*P>0 yields a suitable acyclic flow that covers each node in W to an extent of at least 0.5 2. The total (c-)cost of all components is O(k*R), and every component contains r or some witness node Form components whose cost can be charged to the red edges of the paths in the support of x* Can be done cleanly by setting up a network design problem with a downwards-monotone cut-requirement function Also ensures that each component contains a node with large incoming flow on blue edges, which becomes a witness node
Rounding the LP solution x* Of course, x* need not yield an acyclic flow. Form a set W of witness nodes, partition V\W into components: 1. Shortcutting paths P with x*P>0 yields a suitable acyclic flow that covers each node in W to an extent of at least 0.5 2. The total (c-)cost of all components is O(k*R), and every component contains r or some witness node Form components whose cost can be charged to the red edges of the paths in the support of x* Idea: pick edges to cover all sets S s.t. P: red(P) (S) x*P 0.5 (x* fractional solution of cost O(k*R) that covers all such S) Do not know how to do this
Rounding the LP solution x* Of course, x* need not yield an acyclic flow. Form a set W of witness nodes, partition V\W into components: 1. Shortcutting paths P with x*P>0 yields a suitable acyclic flow that covers each node in W to an extent of at least 0.5 2. The total (c-)cost of all components is O(k*R), and every component contains r or some witness node Form components whose cost can be charged to the red edges of the paths in the support of x* Idea: pick edges to cover all sets S s.t. P: red(P) (S) x*P 0.5 Settle for: cover all sets S s.t. v S, P: red(P, v) (S) x*P 0.5 Can be done cleanly by setting up a network design problem with a downwards-monotone cut-requirement function Also ensures that each component contains a node with large incoming flow on blue edges, which becomes a witness node
Application to DVRP RECALL Distance-constrained VRP (DVRP): Cover all nodes with min no. of rooted paths s.t. waiting time of each node v D. cP(v)(where v lies on path P) Simple O(log D)-approximation using RVRP Dv D
Application to DVRP RECALL Distance-constrained VRP (DVRP): Cover all nodes with min no. of rooted paths s.t. waiting time of each node v D. cP(v)(where v lies on path P) Simple O(log D)-approximation using RVRP -7 -1 Dv -3 D 0 -2i -2i-1 -D/2 Nodes v with Dv (D-2i, D-2i-1] have regret <2i under OPT can cover these using O(OPT) paths, each of regret 2i-1 waiting time of each such v D O(log D) intervals O(log D)-approximation
Application to DVRP log D Improved O()-approximation using RVRP log log D These paths cover Si = {v: Dv >D-2i} (#) Let N*i = no. of paths of OPT having regret < 2i Fi = no. of (feasible) paths we use to cover Si Si -7 -1 Dv -3 D 0 -2i -2i-1 -D/2 For any k<i, can cover Si using Fk + O(N*k+2i-k(N*i N*k)) paths So Fi min0 k<i [Fk+ O(N*k+2i-k(N*i N*k))] Base case F0 N*0 recurrence solves to give Fi = O(i/log i) N*i i goes up to log D get O(log D/log log D)-approximation
Conclusions and open questions We systematically study regret-bounded VRPs devise a constant-approx. for additive-RVRP novel rounding method for the configuration LP; new ideas to deal with regret this yields bounds for various other RVRPs, as well as distance-constrained VRP (DVRP) Is there an O(1)-approx. for DVRP? our work is a promising step: improves upon the usual log- guarantee given by set cover, but we use additive-RVRP as a black box; better way of leveraging underlying ideas Improve upon the O(k2)-approximation for k-RVRP. What about other regret-based objectives: e.g., minimizing sum of regrets (much stronger than minimizing latency)?
