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)