Evacuation Center Location Optimization
In the context of facility location on path networks, the goal is to choose an optimal location for an evacuation center along a highway connecting multiple cities, aiming to minimize evacuation time during emergencies. The uncertainty model entails varying city populations within specific intervals, leading to the need for a regret minimization approach. The objective is to find an evacuation center location that minimizes the maximum regret across different scenarios, optimizing the evacuation process considering uncertainty and population distribution. Noteworthy advancements in algorithmic efficiency have been made in solving this complex location optimization problem.
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.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
Minmax Minmax Regret Uncertain Uncertain Path Networks Regret 1 1- -Facility Location on Facility Location on Path Networks Haitao Wang Utah State University ISAAC 2013
Motivations Motivations A highway P connecting multiple cities Goal: choose a location on P to build an evacuation center such that when an emergency happens evacuate people in all cities to the center minimize the evacuation time a highway P a city an evacuation center
Motivations Motivations The highway P has a capacity, e.g., four driving lanes Cities have different populations 20k 20k 12k 31k
An uncertainty model An uncertainty model The population wiof each city xiis uncertain days, nights, holidays, weekdays, weekends but it is known that wiis in an interval [li, ri] 15k ~ 23k 20k 20k 18k ~ 27k 12k 10k ~ 13k 31k 28k ~ 33k
A scenario A scenario At any moment, called a scenario, each city has a fixed value of population, i.e., wiis a fixed value 15k ~ 23k 20k 20k 18k ~ 27k 12k 10k ~ 13k 31k 28k ~ 33k
Defining the regret Defining the regret Suppose we build an evacuation center at location x For any scenario s T(x,s): the evacuation time xs: the optimal location for s The regret: R(x,s) = T(x,s) T(xs,s) worst-case loss, opportunity loss xs x 12k 20k 20k 31k the highway an evacuation center
The problem objective The problem objective Find a location x for the center, such that Rmax(x), the maximum R(x, s) over all scenarios s, is minimized Difficulty: There are infinitely many scenarios A crucial observation given by Cheng et al. 13 only need to consider at most 2n scenarios, one of which is a worst-case scenario Previous work: O(nlog2n) time and O(nlog n) space, Cheng et al. 13 Our result: O(nlogn) time and O(n) space
The definition of T(x, s) The definition of T(x, s) T(x, s) = max{TL(x, s), TR(x, s)} TL(x,s): the time for evacuating the cities on the left side TR(x,s): the time for the right side Suppose x is in (xk, xk+1] TL(x,s) = max1 i k{ (x-xi) * a + it=1wt } fiL(x,s) = (x-xi)*a + it=1wt a is a positive constant, the time for traversing a unit distance xi x1 x2 x3 xk xk+1 x
T( T(x,s x,s) : a ) : a unimodal unimodal function of x function of x T(x,s) = max{TL(x,s), TR(x,s)} TL(x,s) = max1 i k{ (x-xi)*a + it=1wt } fiL(x,s) = (x-xi)*a + it=1wt T(x,s) TL(x,s) TR(x,s) f iL(x,s) x xs xi
Computing Computing R Rmax max(x) (x) Rmax(x) = maxall scenarios s{R(x,s) = T(x,s) T(xs,s)} Difficulty: There are infinitely many scenarios A crucial observation by Cheng et al. 13 : Only need to consider a set E of 2n scenarios a unimodal function Rmax(x) = maxs ER(x,s) Define E: E = EL ER EL= {sL(i) | 1 i n} sL(i) : r1r2 rili+1li+2 . ln sL(i+1) : r1r2 riri+1ri+2 . ln each city population wiis in [li, ri]
The algorithm The algorithm Goal: find a location x = x* that minimizes Rmax(x) Rmax(x) = maxs ER(x,s) R(x,s) = T(x,s) T(xs,s) The algorithm: Do binary search on x1x2 xnto determine the interval [xi, xi+1] that contains x* The main difficulty: For any x, compute R(x,s) in O(n) time for all 2n scenarios in E Rmax(x) x x* xi+1 xi
Computing R( Computing R(x,s E in O(n) time E in O(n) time x,s) for all scenarios s in ) for all scenarios s in R(x,s) = T(x,s) T(xs,s) Two major procedures: As preprocessing, compute xsand T(xs,s) for all s of E O(nlog n) time in total Given any x, compute T(x,s) for all s of E O(n) time
Computing Computing x xs sand T( and T(x xs s,s ,s) for all s of E ) for all s of E Only discuss EL= {sL(i) | 1 i n} si= sL(i) : r1r2 rili+1li+2 . ln TL(x,si) TR(x,si) x xs
The function T The function TL L(x, s TL(x,s) = max1 i k{ (x-xi)*a + it=1wt } fiL(x,s) = (x-xi)*a + it=1wt si= sL(i) : r1r2 rili+1li+2 . ln si+1 = sL(i+1) : r1r2 riri+1ri+2 . ln (x, si+1 i+1) ) wi+1increases from li+1to ri+1 shift upwards by ri+1 li+1 x xi xi+1
A A monotonicity monotonicity property of property of x xs s From sito si+1 xsmoves to the left if xi+1 xs TR(x,si+1) TL(x,si+1) TL(x,si) TR(x,si) x xs xi xi+1
A data structure A data structure For any x and any scenario siin ELused in our algorithm compute TL(x, si) and TR(x, si) in O(log n) time Preprocessing: O(n) time and space
Computing T( Computing T(x,s x,s) for all s of E ) for all s of E T(x,s) = max{ TL(x,s), TR(x,s)} Only discuss how to compute TL(x,s) for s in EL = {sL(i) | 1 i n} Compute TL(x, s) for the first scenario s = s1 = sL(1)
Observations Observations Suppose x is in (xj-1, xj] and TL(x,s1) = fk(x,s1) Three cases for computing TL(x,si) for si: i is in [2, k] i is in [k+1, j-1] i is in [j, n] TL(x, s1) fk(x,s1) x xk xj-1 xj x
Case 1: Case 1: i i is in [2, k] is in [2, k] s1: r1 l2 l3 . ln s2: r1 r2 l3 . ln TL(x, si) = TL(x,s1) + it=2(rt- lt) TL(x, s2) = TL(x,s1) + (r2 l2) TL(x, s1) fk(x,s1) x xk xj-1 xj x
Case 3: Case 3: i i is in [j, n] is in [j, n] TL(x, si) = TL(x, sj-1) TL(x, s1) fk(x,s1) x xk xj-1 xj x
Case 2: Case 2: i i is in [k+1, j is in [k+1, j- -1] 1] The difficult case After changing from skfrom sk+1 The function ftshifts upwards for t > k, but fkdoes not TL(x, sk+1) = TL(x, sk+2) = max{fk(x,sk), fk+3(x,sk+2)} TL(x, sk+3) = max{fk(x,sk), fk+3(x,sk+3)} TL(x, sk+4) = ? max{fk(x,sk), fk+3(x,sk+1)} the second largest function at x x xj-1 xj xk xk+1 xk+2 xk+3 x
Thank You Thank You
