Two new methods are proposed for solving the step-tolled bottleneck model with general heterogeneity.

The semi-analytical method transforms the problem into a traffic assignment problem with side constraints.

Existence and uniqueness results are obtained by analyzing a variational inequality problem.

The exact method locates the equilibrium solution by enumerating all combinations of user departure orders, with a simple heuristic to reduce the number of solutions to be enumerated.

Results confirm that ignoring user heterogeneity may lead to sub-optimal design of step tolls.