BA 308B
Dr. Campbell
MULTIPLE FACILITY LOCATION HEURISTIC
Locate two or more facilities to serve demand points at minimum total cost. Heuristic algorithms are simple and usually, but not always, find good locations.
ADD Heuristic
k = number of facilities
1. Start with one facility (k = 1).
2. Find the best single facility location and cost. (Allocate all demand to one facility.)
3. Increase the number of facilities by one (k = k + 1).
4. Find optimal locations for k facilities:
4.1 Select k initial facility locations.
4.2 Allocate each demand point to the least cost (nearest) facility to create k groups of demand points.
4.3 Relocate: Optimally locate one facility in each of the k groups of demand points and determine the total cost.
4.4 Repeat 4.2 and 4.3 until there is no change (in allocation or cost).
5. Repeat steps 3 and 4 as long as the total cost decreases.
6. Select the lowest cost solution.
NOTE: The MULTICOG module in the software does step 4.
DROP Heuristic
Replace steps 1 - 3 in the ADD Heuristic by the following three steps.
1. Start with the number of facilities equal to the number of demand points (k = number of demand points).
2. Locate a facility at each demand point and determine the cost.
3. Decrease the number of facilities by one (k = k - 1).
2
BA 308B
Dr. Campbell
MULTIPLE FACILITY LOCATION EXAMPLE
One or more facilities must be located to serve six demand points. The fixed facility cost is $600/week for each facility and the weekly inventory cost is $300 times the square root of the number of facilities. The locations of the nine demand points are shown below. The volume delivered to each demand point is 1000 cwt per week and the transportation rate to all demand points is $0.1 per cwt per unit distance. Determine the number and locations of facilities to serve the nine demand points at minimum total cost. (Use the Add Heuristic.)
Demand Point / A / B / C / D / E / FLocation / (0,0) / (0,2) / (0,4) / (5,0) / (5,4) / (12,2)
Total cost per week = 100 di + 600 k + 300
k = 1: Results from COG:
Location = (2.50, 2.00)
Transportation Cost = 2480.625
Total Cost = 2481 + 600 + 300 = 3381
k = 2: Results from MULTICOG:
Location 1 = (0.00,2.00) A, B, C allocated to Location 1
Location 2 = (6.155,2.00) D, E, F allocated to Location 2
Transportation Cost = 400.000 + 1046.41 = 1446.41
Total Cost = 1446 + 1200 + 424 = 3070
k = 3: Results from MULTICOG:
Location 1 = (2.50,0.00) A, D allocated to Location 1
Location 2 = (0.00,3.00) B, C allocated to Location 2
Location 3 = (8.50,3.00) E, F allocated to Location 3
Transportation Cost = 500.000 + 200.00 + 728.01 = 1428.01
Total Cost = 1428 + 1800 + 520 = 3728
2
BA 308B
Dr. Campbell
Note that MULTICOG may not find the best solution. It is a heuristic.
For k=3 Consider the following three locations
Location 1 = (0.00,2.00) A, B, C allocated to Location 1
Location 2 = (5.00,2.00) D, E allocated to Location 2
Location 3 = (12.00,2.00) F allocated to Location 3
Transportation Cost = 400.000 + 400.00 + 0.00 = 800.00
Total Cost = 800 + 1800 + 520 = 3120
SUMMARY:
Costk / Locations / Transportation / Facility / Inventory / Total
1 / (2.5,2) / 2481 / 600 / 300 / 3381
2 / (0,2) (6.155,2) / 1446 / 1200 / 424 / 3070
3 / (0,2) (5,2) (12,2) / 800 / 1800 / 520 / 3120
The lowest total cost is with two facilities.
2