In this paper we present a new point of view on choice set generation for route choice models. When modeling route choice behavior using random utility models choice sets of paths need to be defined. Existing approaches generate paths and assume that actual choice sets are found. On the contrary, we assume that actual choice sets are the sets of all paths connecting each origindestination pair. These sets are however unknown and we propose a stochastic path generation algorithm that corresponds to an importance sampling approach. The path utilities should then be corrected according to the used sampling protocol in order to obtain unbiased parameter estimates. We derive such a sampling correction for the proposed algorithm. We present numerical results based on synthetic data. The results show that the model including sampling correction yields unbiased coefficient estimates but we also make important observations concerning the Path Size attribute. Namely, it biases the estimation results if it is not computed based on the true correlation structure. These results suggest that the Path Size attribute should be computed based on as many alternatives as possible, more than in the generated choice sets.