The Gas Station Problem Samir Khuller Azarakhsh Malekian Julian Mestre UNIVERSITY OF MARYLAND
General Description • Suppose you want to go on a road trip across the US. You start from New York City and would like to drive to San Francisco. • You have : • roadmap • gas station locations and their gas prices • Want to: • minimize travel cost
Information and Constraints • Information: • map of the road: G=(V, E) • length of the roads: d: E R+ • gas prices: c: V R+ • Constraint: • tank capacity: U • Goal: • find a min. cost solution to go from s to t v3 v2 v1 d(v2,v3) d(v1,v2) Capacity U d(s,v1) d(v3,t) c(v2) c(v3) c(v1) v4 s t v5 c(v4) v6 (NYC) (SF) c(v5) c(v6)
Structure of the Optimal Solution • Two vertices s & t • A fixed path • Optimal solution involves stops at every station! • Thus we permit at most stops. v1 vn v2 v3 t s 1.00$ 2.99$ 2.98$ 2.97$
The Problem we want to solve • Input: • Road map G=(V,E), source s, destination t • U: tank capacity • d: ER+ • c: VR+ • : No. of stops allowed • : The initial amount of gas at s • Goal: • Minimize the cost to go from s to t. • Output: • The chosen path • The stops • The amount of gas filled at each stop • Gas cost is “per mile” and U is the range of the car in miles. • We can assume we start with 0 gas at s. c(s’)= 0 s t s’ U -
Dynamic Programming • Assuming all values are integral, we can find an optimal solution in O(n2 ∆ U2) time. • Not strongly polynomial time.The problem could be weakly NP-hard! Minimum cost to go from x to t in q stops, starting with g units of gas. OPT[x,q,g] =
2 6 2 Start with 7 Tank capacity= 7 3 4 7 3 7 s t Why not Shortest Path? • Shortest path is of length 15.Cost = 37 = 47 + 33 • Cheapest path is of length 16.Cost = 28 = 42 + 27 + 23 7 3 2 7 2
One more try at Shortest Path Let the length of (u,v) be d(u,v)c(u), if d(u,v) U • Shortest path has length 20. Cost = 20 = 210. • Cheapest path has length 30.Cost = 5 = 51 . 1 0 30 5 6 s t 5 Start with 10 Tank capacity=10 10 10 0 20 2 10
Key Property Suppose the optimal sequence of stops is u1,u2,…,u. • If c(ui) < c(ui+1) Fill up the whole tank • If c(ui) > c(ui+1) Just fill enough to reach ui+1. ui+1 ui c(ui) c(ui+1)
0 if c(x) < c(y) U - d(y,x) if c(x) c(y) Solution • Suppose the stop before x was y.The amount of gas we reach x with is • For each x we need to keep track of at most n different values of g. Minimum cost to go from x to t in q stops, starting with g units of gas. OPT[x,q,g] = At most q stops reach x with g units of gas y x t d( y, x) 0 U - d(y,x)
reach x with g units of gas t x v d(x,v) Dynamic Program OPT[v,q-1,0] + (d(x,v)-g) c(x) if c(v) c(x) &d(x,v) > g OPT[v,q-1,U-d(x,v)] + (U-g) c(x) if c(v)>c(x) Minimum cost to go from x to t in q stops, starting with g units of gas. OPT[x,q,g] = minv q -1 more stops
Problem Wrap Up • The given DP table can be filled in: • O( n3) time by the direct and naïve solution • O( n2 log n) time by a more intricate solution • Faster algorithm using a different approach for the “all-pairs” version • Faster algorithm for the fixed path with =n with running time O(n log n)
Tour Gas Station problem • Would like to visit a set of cities T. • We have access to set of gas stations S. • Assume gas prices are uniform. • The problem is NP-hard even with this restriction. • Guess the range of prices the optimal solution uses, pay extra factor in approximation ratio. • Deals with gas companies.
Uniform Cost Tour Gas Station • There is a set S of gas stations and a setT of cities. • Want to visit the cities with min cost. • Gas prices are the same.
Uniform Cost Tour Gas Station • Input • G = (V,E) • d : ER+ • T, S V : set of cities & gas stations. • U : Tank Capacity • Goal: • Find cheapest tour visiting all vertices in T & possibly some vertices in S.
Uniform Cost Tour Gas Station • Problem is APX-hard since it generalizes TSP. • If each city has a gas station (TS) the two problems are equivalent: • Let c(x,y) be shortest feasible path from x to y. • Triangle inequality holds in c 3 3 U=5 4 6 3 7 7 10 3 3 4 10 4 8
Uniform Cost Tour Gas Station • The method works only when T S • c(x, y) depends on the last stop before x. • Assumption: • Each city has a gas station within distance at most U/2. U=5 x y 4 2 1 3 3
A simple case For all edges (u,v) in the tourd(u,v) (1- )U Find the TSP on the cities. Start from g(x1), go to x1 Continue along the tour until x2, farthest city at distance at most (1-)U Go to g(x2), repeat the procedure from g(x2) Continue until you reach x1. Let g(v) be nearestgas station to v g(x2) x2 xk (1-)U x1 g(x1) g(xk)
Uniform Cost Tour Gas Station • In this solution • |T(xi,xi+1)| ≤ (1- )U • |T(xi,xi+2)| > (1- )U • Charge cost of trips to Gas Stations to the tour: (1-)U Xi+1 xi Xi+2 > (1- )U |T|+ U k (1 + 2/(1-)) |T| Round trips to g(xi)
Uniform Cost Tour Gas Station • Obtain a bound of (1 +2/(1- )) 1.5 c(OPT). • Note that when =0, then we get 1.5 c(OPT). • Let c(x,y) be cheapest traversal to go from x to y, such that we start at g(x) and end at g(y). g(x) g(y) x c(x,y) y
Main problem • Lack of triangle inequality • Use Christofides method. Combine with previous approach to get a feasible solution. y z x
Single Gas Station Problem • Suppose the salesman lives near a gas station. • He wants to go to a set of cities. • In each trip we can travel a distance of U.
Single Gas Station • We are given G=(V,E) • We want to cover the vertices in V • We have only one gas station • Dist. of the farthest city to the gas station is U/2. • Each cycle has length U u/2 Cycle length less than U
Naïve Solution • Find the TSP on cities & gas station • Chop thetour into parts oflength (1-)U • Connect each segment to the root • This is a 1.5/(1-) approximation • Given by Li et al.  U/2
Improved Method • Group cities based on their distance to the gas station • Solve the problem for each group separately 3U/2 2U/2 1U/2 =(1-i)/(1-i+1)
Finding Segments in Layer i • Guess the Min. No. of cycles:k • Run Kruskal until you have k connected components. (R) • Double subtrees to find cycles • Chop the cycles as needed • Connect the k’ CCs to GS • Cost(C)< 2cost(R)+k’ i+1U • We can show that • k’ (2+ 1) k • # of groups log(1- 1)/(1-) k’=4 Putting everything together we get a O(log 1/(1-))
Conclusion • Incorporate the algorithms as part of a “tool” for path planning. • Solve the tour gas station problem with arbitrary gas prices. • Remove the assumption that every city has a gas station at distance U/2.