The Service station Issue.

Uploaded on:
Category: General / Misc
General Description. Assume you need to go on a street trip over the US. You begin from New York City and might want to drive to San Francisco.You have :roadmapgas station areas and their gas costs Want to:minimize travel cost. Data and Constraints . Information:map of the street: G=(V, E)length of the streets: d: E? R gas costs: c: V? R Constraint: tank limit: UGoal:find a min. cos
Slide 1

The Gas Station Problem Samir Khuller Azarakhsh Malekian Julian Mestre UNIVERSITY OF MARYLAND

Slide 2

General Description Suppose you need to go on a street trip over the US. You begin from New York City and might want to drive to San Francisco. You have : guide service station areas and their gas costs Want to: minimize travel cost

Slide 3

Information and Constraints Information: guide of the street: G=(V, E) length of the streets: d: E  R + gas costs: c : V  R + Constraint: tank limit: U Goal: discover a min. taken a toll answer for go from s to t v 3 v 2 v 1 d(v 2 ,v 3 ) d(v 1 ,v 2 ) Capacity U d(s,v 1 ) d(v 3 ,t) c(v 2 ) c(v 3 ) c(v 1 ) v 4 s t v 5 c(v 4 ) v 6 (NYC) (SF) c(v 5 ) c(v 6 )

Slide 4

Finding gas costs online

Slide 5

Structure of the Optimal Solution Two vertices s & t A settled way Optimal arrangement includes stops at each station! In this manner we allow at most  stops. v 1 v n v 2 v 3 t s 1.00$ 2.99$ 2.98$ 2.97$

Slide 6

The Problem we need to understand Input: Road map G=(V,E) , source s , goal t U : tank limit d : E R + c : VR +  : No. of stops permitted  : The underlying measure of gas at s Goal: Minimize the expense to go from s to t . Yield: The picked way The stops The measure of gas filled at every stop Gas expense is "per mile" and U is the scope of the auto in miles. We can accept we begin with 0 gas at s. c(s\')= 0 s t s\' U - 

Slide 7

Dynamic Programming Assuming all qualities are necessary, we can locate an ideal arrangement in O(n 2 ∆ U 2 ) time. Not firmly polynomial time. The issue could be feebly NP-hard! Least cost to go from x to t in q quits, beginning with g units of gas. Pick [ x , q , g ] =

Slide 8

2 6 2 Start with 7 Tank capacity= 7 3 4 7 3 7 s t Why not Shortest Path? Most brief way is of length 15. Fetched = 37 = 4  7 + 3  3 Cheapest way is of length 16. Fetched = 28 = 4  2 + 2  7 + 2  3 7 3 2 7 2

Slide 9

One more attempt at Shortest Path Let the length of (u,v) be d(u,v) c(u), if d(u,v)  U Shortest way has length 20. Taken a toll = 20 = 2  10. Least expensive way has length 30 . Taken a toll = 5 = 5 1 . 1 0 30 5 6 s t 5 Start with 10 Tank capacity= 10 0 20 2 10

Slide 10

Key Property Suppose the ideal arrangement of stops is u 1 ,u 2 ,… ,u . In the event that c(u i ) < c(u i+1 )  Fill up the entire tank If c(u i ) > c(u i+1 )  Just fill enough to achieve u i+1 . u i+1 u i c(u i ) c(u i+1 )

Slide 11

0 i f c(x) < c(y) U - d(y,x) if c(x)  c(y) Solution Suppose the stop before x was y. The measure of gas we achieve x with is For every x we have to monitor at most n distinctive estimations of g. Least cost to go from x to t in q quits, beginning with g units of gas. Select [ x , q , g ] = At most q stops achieve x with g units of gas y x t d( y, x) 0 U - d(y,x)

Slide 12

achieve 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 expense to go from x to t in q quits, beginning with g units of gas. Select [ x , q , g ] = min v q - 1 more stops

Slide 13

Problem Wrap Up The given DP table can be filled in: O(  n 3 ) time by the direct and innocent arrangement O( n 2 log n) time by a more complex arrangement Faster calculation utilizing an alternate methodology for the "all-sets" form Faster calculation for the settled way with =n with running time O(n log n)

Slide 14

Tour Gas Station issue Would get a kick out of the chance to visit an arrangement of urban communities T . We have admittance to set of corner stores S . Accept gas costs are uniform. The issue is NP-hard even with this limitation. Surmise the scope of costs the ideal arrangement utilizes, pay additional variable in estimation proportion. Manages gas organizations.

Slide 15

Uniform Cost Tour Gas Station There is a set S of corner stores and a set T of urban communities. Need to visit the urban areas with min cost. Gas costs are the same.

Slide 16

Uniform Cost Tour Gas Station Input G = (V,E) d : E R + T, S  V : set of urban communities & corner stores. U : Tank Capacity Goal: Find least expensive visit going to all vertices in T & potentially some vertices in S .

Slide 17

Uniform Cost Tour Gas Station Problem is APX-hard since it sums up TSP. On the off chance that every city has a service station (T  S) the two issues are identical: Let c(x,y) be most limited achievable way from x to y. Triangle disparity holds in c 3 U=5 4 6 3 7 10 3 4 10 4 8

Slide 18

Uniform Cost Tour Gas Station The technique works just when T  S c(x, y) relies on upon the last stop before x . Supposition : Each city has a corner store inside separation at most U/2. U=5 x y 4 2 1 3

Slide 19

A straightforward case For all edges (u,v) in the visit d(u,v)  (1-)U Find the TSP on the urban areas. Begin from g(x 1 ), go to x 1 Continue along the visit until x 2 , most remote city at separation at most (1-)U Go to g(x 2 ), rehash the system from g(x 2 ) Continue until you achieve x 1 . Give g(v) a chance to be closest corner store to v g(x 2 ) x 2 x k  (1-)U x 1 g(x 1 ) g(x k )

Slide 20

Uniform Cost Tour Gas Station In this arrangement |T(x i ,x i+1 )| ≤ (1-)U |T(x i ,x i+2 )| > (1-)U Charge expense of treks to Gas Stations to the visit:  (1-)U X i+1 x i X i+2 > (1-)U |T|+ U k  ( 1 + 2/(1-) ) |T| Round outings to g(x i )

Slide 21

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). Give c(x,y) a chance to be least expensive traversal to go from x to y, with the end goal that we begin at g(x) and end at g(y). g(x) g(y) x c(x,y) y

Slide 22

Main issue Lack of triangle imbalance Use Christofides strategy. Join with past way to deal with get a practical arrangement. y z x

Slide 23

Single Gas Station Problem Suppose the businessperson lives almost a corner store. He needs to go to an arrangement of urban communities. In every excursion we can travel a separation of U .

Slide 24

Single Gas Station We are given G=(V,E) We need to cover the vertices in V We have stand out corner store Dist. of the most distant city to the corner store is U/2 . Every cycle has length  U u/2 Cycle length not as much as U

Slide 25

Naïve Solution Find the TSP on urban communities & service station Chop the visit into parts of length (1-)U Connect every portion to the root This is a 1.5/(1-) guess Given by Li et al. [1991] U/2

Slide 26

Improved Method Group urban communities in view of their separation to the corner store Solve the issue for every gathering independently  3 U/2  2 U/2  1 U/2  =(1- i )/(1- i+1 )

Slide 27

Finding Segments in Layer i Guess the Min. No. of cycles: k Run Kruskal until you have k associated segments. ( R ) Double subtrees to discover cycles Chop the cycles as required Connect the k\' CCs to GS Cost(C)< 2cost(R)+k\'  i+1 U We can demonstrate that k\'  (2+ 1) k # of gatherings  log(1- 1 )/(1-) k\'=4 Putting everything together we get an O(log 1/(1-))

Slide 28

Summary of The Results

Slide 29

Conclusion Incorporate the calculations as a feature of an "apparatus" for way arranging. Take care of the visit service station issue with discretionary gas costs. Expel the suspicion that each city has a service station at separation U/2.

Slide 30

Thanks for your consideration

View more...