This study describes the use of a Direct Search (DS) metaheuristic algorithm for solving the fixed and variable toll design problem, in terms of finding (adequately near-)optimum toll level(s), in roads operated by private, profitmaximizing firms. The problem is formulated as a nonconvex, bilevel nonlinear mathematical program, which seeks to maximize toll revenues while taking into account the travel responses of network users, through a multi-class stochastic user equilibrium traffic assignment model with elastic demand. The algorithm is implemented onto a real-life urban sub-network which includes a private highway. The results of the case study show the ability of the DS algorithm to relatively quickly converge to a solution and signify its potential to provide a competitive alternative to the currently used genetic algorithm (GA) approach for solving such types of nonconvex bilevel programs in the sector of road transport services.