A factory consisting of four departments (A, B, C, D) is being designed. Estimates for the annual material flows between departments are as follows:

All material is transported in standard crates by forklift (one crate = one load = one move). The transportation costs for a load are $0.50 per metre. The distances between locations in the proposed factory are as follows:
  

The following constraints must also be taken into account:

• only locations 1, 2, and 4 have outside doors
• departments A and B must have outside doors
• department D must not adjoin either A or B

Find the optimal assignment of departments to locations, such that it 

(1) meets the above conditions, and

(2) minimizes annual material handling costs.

Interdepartmental Flow (number of moves per year) Department A A B C D B C D 100 400 300 200 0 500