| Solution procedures for NP hard integer programs evolved from traditional enumerative procedures to random choice directed search procedures to hybrid algorithms that use random choice while exploiting problem structure. This new class of hybrid algorithms, called meta-heuristics, combines the robustness of random choice procedures with a structure based solution technique. While it can be difficult or even impossible to prove optimality, meta-heuristics have been successfully applied to a variety of NP complete problems. Some examples of where meta-heuristics have been used are project scheduling, multidimensional knapsack, traveling salesman, and vehicle routing. This research develops two genetic based meta-heuristics for the product line pricing and positioning problem and compares them to a genetic algorithm procedure. The product line pricing and positioning problem determines the product mix, product prices and customer segmentation based on customer preferences, fixed costs and variable costs. This problem was chosen for both its structure and its potential to aid in managerial product line decisions. The three solution procedures were compared over problem size and customer preference type. While the meta-heuristic involving a branch and bound sub-routine often had slow solution speeds, it still proved to be the most robust procedure. Two main strategies produced effective solutions to the problems. The first strategy was to use fewer products and lower prices in order to attract more customers. The second strategy was to expand the product line and use price premiums to recoup fixed costs. |
