Discrete choice models in general and random utility models in particular may be intractable when the number of alternatives is large. In the transportation context, it typically happens for route choice and destination choice models. In the specific case of the widely used multinomial logit model, it has been shown that the model could be estimated as if the choice was made among a subset of the alternatives. In this paper, we propose to design the sampling of alternatives based on a Principal Component Analysis and a Cluster Analysis of the actual data set, in order to increase the efficiency of the estimates. We present a case study of a destination choice model to empirically illustrate the added value of our approach.