An Optimal Location Problem with an Obstruction

Friday, 13 February 2015
Exhibit Hall (San Jose Convention Center)
Richard Huang, Beavercreek, OH
In the problem studied, Corporation A needs to visit the facilities P1, P2, P3 with k1, k2, k3 trips every week, respectively. An obstacle, such as a river, runs across the area from east to west. P1 and P2 are north of the river while P3 is south of the river. There exists only a bridge connecting the regions north and south of the river. The streets in the area run east-west or north-south. The problem posed is to find an office location for Corporation A such that the total distance it travels every week to these three facilities is minimal. The hypothesis is that the optimal location should heavily depend on k1+k2 (trips north) and k3 (trips south). The problem was solved by converting it into a mathematical problem of finding the minimum of a somewhat complicated distance function. By the nature of this problem, the distance travelled from point (x1, y1) to point (x2, y2) is not given by the typical Euclidean distance, but by |x2-x1|+|y2-y1| if both points are on the same side of the river and by |x1|+|y1|+|x2|+|y2| if both points are on opposite sides of the river. The mathematical formulas for the optimal locations were derived and confirmed the hypothesis precisely: if k1+k2 > k3, the optimal location is on the same side as P1 and P2; if k1+k2 < k3, P3 is the optimal location; if k1+k2=k3, a suitable portion of the vertical street through the bridge can be selected for the optimal location. The optimal location minimizes the usage of fuel and manpower for Corporation A.