Determining appropriate utility specifications for discrete choice models is time-consuming and prone to errors. As the number of possible functions exponentially grows with the variables under consideration, analysts need to spend increasing amounts of time on searching for good specifications through trial-and-error and expert knowledge. This paper proposes a data-driven algorithm that aims at assisting modelers in their search. Our approach translates the task into a multi-objective combinatorial optimization problem and makes use of a variant of the variable neighborhood search algorithm to generate solutions. We apply the algorithm to a real mode choice dataset as a proof of concept. The results demonstrate its ability to generate high-quality specifications in reasonable amounts of time.