Location Theory II Logistical and Transportation Planning Methods Single Tree Center Problem G is a tree. e i , i=1,2,...,m are the end vertices. Single Tree Center Problem e N Step 1: Choose any and find the end vertex, say e N , farthest from x. x ∈G G is a tree. e i , i=1,2,...,m are the end vertices. x Single Tree Center Problem e N Step 1: Choose any and find the end vertex, say e N , farthest from x. x ∈G G is a tree. e i , i=1,2,...,m are the end vertices. Step 2: Find the end vertex, say e S , farthest from e N . x e S Single Tree Center Problem e N x Step 2: Find the end vertex, say e S , farthest from e N . Step 3: The absolute center of G is the midpoint of the path from e N to e S . The vertex center is the vertex closest to that midpoint. Step 1: Choose any and find the end vertex, say e N , farthest from x. x ∈G G is a tree. e i , i=1,2,...,m are the end vertices. e S Single Tree Center Problem e N x Step 2: Find the end vertex, say e S , farthest from e N . Step 3: The absolute center of G is the midpoint of the path from e N to e S . The vertex center is the vertex closest to that midpoint. Absolute center Vertex Center Step 1: Choose any and find the end vertex, say e N , farthest from x. x ∈G G is a tree. e i , i=1,2,...,m are the end vertices. e S Minimum Manhattan Distance Paths in the Presence of Barriers Larson, Li, Networks One of n Q O-D points One of n B polygonal barriers One of n Q O-D points One of n B polygonal barriers Communication: The name of the game! ? Two points having coordinates (x, y) and (u, v) COMMUNICATE if there exists at least one feasible staircase path between them. ? Such a staircase path has minimum possible Manhattan length: ? For example, any 2 adjacent vertices of a barrier communicate L[(x,y),(u,v)] =| x ? u | + | y ? v | Vertex Seeking Tree This tree is from a O-D point +∞ Vertex Seeking Tree This tree is from a barrier vertex +∞ Vertex Seeking Tree This tree is from a barrier vertex +∞ Vertex Seeking Tree This tree is from a barrier vertex +∞ Vertex Seeking Tree This tree is from a barrier vertex Vertex Seeking Tree This tree is from a barrier vertex 2 Nodes Communicating Simply if ? They are adjacent vertices of a barrier ? One is the root and the other is a terminal node of a vertex-seeking tree ? If they they have x and y probes that share at least one common non-nodal point b. Theorem 1 ? Suppose 2 points communicate but not simply. Then there exists at least one feasible staircase path between them containing a sequence of simply communicating nodes. ? Use 'path push and amalgamation' for proof. Theorem 2 ? Suppose 2 points do not communicate. Then there exists at least one minimal distance path between them containing a sequence of simply communicating vertices. ? All this implies that we have reduced the problem to a finite network problem and can use Dijkstra, etc. for analysis. Median Facility Locations with Barriers and Manhattan Metric Median Facility Locations with Barriers and Manhattan Metric 1/5 1/5 1/5 1/51/5 Median Facility Locations with Barriers and Manhattan Metric 1/5 1/5 1/5 1/51/5 1-median Stochastic Queue Median Stochastic Loss Median Motivation ? Standard Hakimi deterministic median ? Lack of effects of uncertainty in time and duration of service request ? Lack of queueing effects or lost customers ? Queueing delay can be far greater than travel time The Model Single server queue garaged at λh i = Poisson rate of service requests from node i Travel time = travel distance/speed = d/v Time required to travel a fraction α of link (i,j) is (α)d ij /v (d ij = length of link) S i (x)=service time associated with node i x ∈G S i (x)=service time associated with node i S i (x) = βd(x,i)/ v + R i + W i R i (β-1)d(x,i)/v W i Travel time to the customer On-scene service time Follow-up travel time Off-scene service time Time d(x,i)/v Potential Location of a Service Facility x a b x l ab -x Model 1: Stochastic Loss Median ? When a customer requests service: – Assign server to customer, if server is available – Or, assign customer to a back-up system (i.e., customer is lost) Model 2: Stochastic Queue Median ? Assume infinite capacity queue ? When a customer requests service – Assign server to customer, if server is available – Otherwise enter thhe customer into a FCFS queue Model 1: Stochastic Loss Median ρ(x)=server utilization factor, when server is garaged at x Expected cost of travel for a random service request is J(x) = (1 ? ρ(x)) h i i=1 n ∑ d(x,i)/v + ρ(x)γ h i = fraction of service requests from node i γ = cost of rejection > 0 Problem: Stochastic Loss Median Find such that x* ∈G J(x*) ≤ J(x) for all x ∈G Lemma: There exists at least one node of G that is a stochastic loss median and that node corresponds to the Hakimi median. Proof requires that we show that is monotonically increasing with mean travel time (or distance) J(x) Model 2: Stochastic Queue Median T R (x) ≡ expected response time = W q (x) + t(x) where W q (x) = mean in - queue delay t(x) = mean travel time Stochastic Queue Median: Find x* ∈[a,b], [a,b] ∈L,such that T R (x*) ≤ T R (x) for all x ∈(a',b'), (a',b')∈L. Problem: we have breakpoints within links, as we have already discussed in class. A breakpoint is a point that is equidistant paths to a node, exiting the link on either end. It is the point at which an optimal path to that node changes. Algorithm ? Can prove convexity of the objective function between breakpoints ? Implies finite step algorithm for finding x* x*(λ): Trajectory of the Optimal Location as a Function of λ ? When λ = 0+, x* is an Hakimi median of G ? When λ approaches λ max -, then x* is again an Hakimi median of G ? What happens in between extreme values of λ?