The assortment planning problem involves choosing an optimal product line, as defined by a set of products with specific attributes, to offer consumers. Under a locational choice model in which products are differentiated both horizontally (by variety attributes) and vertically (by quality attributes), an optimal assortment, whose attributes have only been partially characterized, may consist of multiple quality levels. Using previous analytical results, we approximate the optimal assortment for make-to-order and static substitution environments. We test the appropriateness and compare the performance of three metaheuristic methods. These metaheuristics can easily be modified to accommodate different consumer preference distribution assumptions. (C) 2010 Elsevier Ltd. All rights reserved.