Optimally Locating Facilities on a Network A Second Application of Transportation Network Analysis
Optimally Locating Facilities Optimally Locating Facilities on a Network on a Network A Second Application of Transportation Network Analysis
There Are Three Things Important When Buying a House oLocation oLocation oLocation
There Are There Are Three Things Important When Buying a House: Important When Buying a House: zLocation zLocation zLocation
Examples e Libraries ● Ambulances Warehouses ● Factories Restaurants e Banks Telephone centers Military facilities
Examples: Examples: z Libraries z Ambulances z Warehouses z Factories z Restaurants z Banks z Telephone centers z Military facilities
Let' s Consider Objective Functions: o Minimize average travel time or distance o Minimize worst case(maximum) travel time or distance o Minimize fraction of population greater than 10 minutes from a facilit o Maximize minimum travel time
Let’s Consider Objective Let’s Consider Objective Functions: 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 o Median problems Minimize average travel distance(time) Sometimes called minisum ● Center problems Minimize maximum distance to( from)a facility ● Requirements problems Allocate to achieve some objective
Classic Location Problems 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 o Nodal weights h;, representing fraction of customers from node j ● Sum of h; s equals one o We have an undirected network G(N, A) o Objective: locate k facilities onG such that mean travel distance to a closest facility is minimized
Median Problem Median Problem z Nodal weights hj, representing fraction of customers from node j z Sum of hj'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
h.≥0 Xk={x1,x2,…,xk};x∈G d (x,D=min distance between any one pointseX and the noge∈N MIN d(X=.(x,j) x∈X
G(N, A), | N |= n hj ≥ 0 hj j =1 n ∑ =1 Xk = {x1, x2 ,..., xk}; x j ∈G d(Xk, j)≡min. distance between any one o points xi ∈Xk and the node j∈N. d(Xk, j)≡ MIN xi ∈Xk d(xi, j)
Y(X =2h d(X j )=mean travel time to(from)closest facility Find X∈ G such that for all X∈G, V(X)≤J(X) k is a k-median ofG(N, a )with a given h=(h,h , .,h,)
J(Xk ) ≡ hjd(Xk j =1 n ∑ , j) = mean travel time to (from) closest facility Find Xk* ∈G such that for all Xk ∈G, J(Xk* ) ≤ J(Xk ) Xk * is a k - median of G(N, A) with a given h = (h1,h2,...,hn)
Theorem At least one k-median exists solely on the nodes of g
Theorem Theorem z At least one k-median exists solely on the nodes of G
Proof by contradiction for k=1 P -d(x,p)+ d(x, q)
Proof by contradiction for Proof by contradiction for k=1 p q d(x,p) d(x,q) P Q
