Using a new gap function recently proposed by Facchinei and Soares [Facchinei, F., Soares, J., 1995. Testing a new class of algorithms for nonlinear complementarity problems. In: Giannessi, F., Maugeri, A. (Eds.), Variational Inequalities and Network Equilibrium Problems. Plenum Press, New York], we convert the nonlinear complementarity problem (NCP) formulation for the traffic equilibrium problem to an equivalent unconstrained optimization. This equivalent formulation uses both route flows and the minimum origin–destination travel costs as the decision variables. Two unique features of this formulation are that: (i) it can model the traffic assignment problem with a general route cost structure; (ii) it is smooth, unconstrained, and that every stationary point of the minimization corresponds to a global minimum. These properties permit a number of efficient algorithms for its solution. Two solution approaches are developed to solve the proposed formulation. Numerical results using a route-specific cost structure are provided and compared with the classic traffic equilibrium problem, which assumes an additive route cost function.