Near optimal solutions for product line design and selection: Beam search heuristics

Many practical product line design problems have large numbers of attributes and levels. In this case, if most attribute level combinations define feasible products, constructing product lines directly from part-worths data is necessary. For three typical formulations of this important problem, Kohli and Sukumar present state-of-the-art heuristics to find good solutions. In this paper, the authors develop improved heuristics based on a beam search approach for solving these problems. In the computations for 435 simulated problems, significant improvements occur in five important performance measures used. The present heuristic solutions are closer to the optimal, have smaller standard deviation over replicates, take less computation time, obtain optimal solutions more often and identify a number of ‘good’ product lines explicitly. Computation times for these problems are no more than 22 seconds on a PC, small enough for adequate sensitivity analysis. The authors also apply the heuristics to a real data set and clarify computational steps by giving a detailed example.