An evolutionary algorithm approach to the share of choices problem in the product line design

In this paper an evolutionary algorithm (EA) approach for solving the share of choices problem in the design of a line of substitute products is presented. Because this problem is NP-hard, we are forced to use heuristic methods, which do not guarantee obtaining the optimal solution. In order to see whether there exists any computational advantage of the EA approach, it is compared to the beam search (BS) heuristic method. An extensive comparative computational study is performed. The solutions found by the EA are close to optimal. Moreover, in most cases the EA obtains a better solution than that found by the BS method. In most problem sizes the BS method is faster than the EA. However, the CPU time needed by the EA is very reasonable. Moreover, the EA can be used as an effective second step to the BS method.