A model for the optimal location of new facilities in a competitive market is introduced under the hypothesis that customers' behavior can be modeled by random utility functions. It means that the company, that wished to locate, uses a random utility model to forecast the market share of a location. Therefore the company cannot forecast the behavior of every customer in a deterministic fashion, but is able to embed him by a probability distribution. Three formulations are proposed to compute upper bounds of the objective function and compared in a numerical simulation. A branch & bound method is developed and tested on examples with up to 50 potential locations, and a Variable Neighborhood Search heuristic is proposed to solve larger instances.