Optimally Locating Facilities on a Network A Second Application of Transportation Network Analysis There Are Three Things Important When Buying a House: zLocation zLocation zLocation Examples: z Libraries z Ambulances z Warehouses z Factories z Restaurants z Banks z Telephone centers z Military facilities Let’s Consider Objective Functions: z Minimize average travel time or distance z Minimize worst case (maximum) travel time or distance z Minimize fraction of population greater than 10 minutes from a facility z Maximize minimum travel time Classic Location Problems z Median Problems – Minimize average travel distance (time) – Sometimes called Minisum z Center Problems – Minimize maximum distance to (from) a facility z Requirements Problems – Allocate to achieve some objective Median Problem z Nodal weights h j , representing fraction of customers from node j z Sum of h j 's equals one. z We have an undirected network G(N,A) z Objective: locate k facilities on G such that mean travel distance to a closest facility is minimized G(N,A), | N |= n h j ≥ 0 h j j=1 n ∑ =1 X k = {x 1 ,x 2 ,...,x k }; x j ∈G d(X k ,j)≡ min. distance between any one o points x i ∈X k and the node j∈N. d(X k ,j)≡ MIN x i ∈X k d(x i ,j) J(X k ) ≡ h j d(X k j=1 n ∑ ,j) = mean travel time to (from) closest facility Find X k * ∈G such that for all X k ∈G, J(X k * ) ≤ J(X k ) X k * is a k - median of G(N,A) with a given h = (h 1 ,h 2 ,...,h n ) Theorem z At least one k-median exists solely on the nodes of G. Proof by contradiction for k=1 pq d(x,p) d(x,q) P Q Proof z Start with 2 node problem, w p > w q . J(x) = w p x + (1 ? w p )(1? x) = 2w p x + 1? x ? w p = x(2w p ?1) +1 ? w p Proof - con't. z Draw this graphically z Add general multi-node network z Add breakpoints 1 2 3 4 5 2 2 2 2 1 1 1 2 3 4 5 2 2 2 2 1 1 h 1 =0.1 h 2 =0.1 h 3 =0.0 h 4 =0.4 h 5 =0.4 1 2 3 4 5 2 2 2 2 1 1 h 1 =0.1 h 2 =0.1 h 3 =0.0 h 4 =0.4 h 5 =0.4 1 2 3 4 5 2 2 2 2 1 1 h 1 =0.1 h 2 =0.1 h 3 =0.0 h 4 =0.4 h 5 =0.4 Summary for 1-Median z Step 1: Find travel distance matrix D z Step 2: Find (h j ,d(i,j)) z Step 3: Find row sums of (h j ,d(i,j)) – Take the minimum Center Problems G(N,A), undirected Locate one facility so as to minimize maximum distance to a node 1 2 3 4 5 2 2 2 2 1 1 h 1 =0.1 h 2 =0.1 h 3 =0.0 h 4 =0.4 h 5 =0.4 Recall: 0 2 3 2 4 2 0 2 3 3 D= 3 2 0 1 1 2 3 1 0 2 4 3 1 2 0 Nodes 2, 3 and 4 all vertex centers Center Problem z No nodal solution in general for the absolute center, only for the vertex center Let x ∈G(N,A) Define the "maximum distance function": m(x) ≡ MAX j ∈N d(x, j) [] Objective for the absolute center : Find x * ∈G such that m(x * ) ≤ m(x) for all x ∈G. Single Absolute Center Algorithm: z 1. Find all local centers (one for each link) z 2. Choose a local center with smallest m(x l ). That is an absolute center x* of G.