This site showcases a method of solving what is commonly referred to as the P-median problem, the problem of locating P "facilities" relative to a set of "customers" such that the sum of the shortest demand weighted distance between "customers" and "facilities" is minimized.
Solving this problem, is non-trivial. To see this, consider that the number of possible solutions to any given instance of a P-Median problem is:
where N is the number of "customers" and P is the number of facilities to be located. As an example, for N = 20, and P = 5, the resulting number of possibilities is 15,504. For N = 50, and P = 10, a problem that is not large by most standards, the resulting number of possibilities is 10E10!
As a result, a number of heuristic approaches have been developed to solve this problem. This site features a java applet that uses one such approach called Lagrangian Relaxation to solve the P-Median problem (or at the very least determine a reasonably good solution). With this applet, users may specify a graph of arbitrary complexity which possesses less than 100 nodes and watch as the algorithm systematically updates the screen as it determines the lowest upper-bound (estimate of worst case objective) as well as the highest lower-bound (estimate of best case objective).
To get started immedietely, see the section titled "Instructions." Further details about how algorithm works can be found in the section titled "How it Works." Finally, the applet can be found in the section titled "P-Median Solver."
This project was submitted as a semester project for IEOR 251, "Facilities Design and Logistics," a course taught at the University of California atBerkeley during the Spring 1998 term when it was taught by Professor Phil Kaminsky. He can be reached at kaminsky@ieor.berkeley.edu for more information.
Unfortunately, the applet only works properly with the newest 4.0 browsers even though the applet was written to be compliant with Java JDK 1.0. The applet has been successfully tested on Windows and Linux platforms and was developed using a Linux System and Java JDK 1.1.5. Questions, concerns, or comments may be directed to viper@hyuan.com
