ADD-heuristics' starting procedures for capacitated plant location models (Q1068688)

The authors consider modifications of heuristics for capacitated plant location (CPL) models based on priority starting procedures. Many of the heuristics for p-median and uncapacitated location problems have been extended for CPL. Some of these perform effectively only when the capacities at each of the plants are the same. Specifically, ADD heuristics are a class of greedy heuristics that start with no open plant and then, according to some priority or sort rule, choose a plant to open that gives the smallest increment (or greatest reduction) to the current cost. This is determined by solving a transportation problem. When capacities differ, these algorithms can be generalized but add locations according to decreasing capacities. This often leads to poor solutions. The authors suggest three other priority rules for adding new plants while not violating capacities. Several problems were solved using these procedures and the results compared with optimal or near-optimal solutions. They show without a significant CPU-time increase over the basic ADD priority rule it may be possible to achieve significantly better solution quality. It is also demonstrated that the proper choice of priority rule leads to solutions that compare favorably with the optimal or near-optimal solution with a great savings in CPU-time.