An algorithm to solve explicitly the path enumeration problem is proposed. This algorithm is based on the branch-and-bound technique and belongs to the class of deterministic methods along with existing approaches that combine heuristic or randomization procedures with shortest-path search. The branch-and-bound algorithm is formulated, and a methodology is designed for the application of deterministic approaches to a real case study. Path sets generated with different methods are compared for behavioral consistency, namely, the ability to reproduce actual routes chosen by individuals driving habitually from home to work. Choice set compositions for modeling purposes are determined for the consistency of the path generation process with the observed behavior. Further, model estimates and performance for different route choice specifications are examined for both path set compositions. Results suggest that the proposed branch-and-bound algorithm generates realistic and heterogeneous routes, reproduces better the observed behavior of the interviewed drivers, and produces a good choice set for route choice model estimation and performance comparison.