Convexification of the Traffic Equilibrium Problem with Social Marginal Cost Tolls

In an earlier paper, we have demonstrated that traffic equilibria under social marginal cost tolls can be computed as local optima of a nonconvex optimization problem. The nonconvexity of this problem implies in particular that linearizations, e.g. in the Frank-Wolfe method, do not give underestimates of the optimal value. In this paper we derive the convex hull of nonconvex arc cost functions of BPR type. These convexifications can be used to get underestimates of the optimal value, or to get better search directions in the initial phase of the Frank-Wolfe method. Computational results for the Sioux Falls and Stockholm networks are reported