Surrogate-based optimization for multi-objective toll design problems

The toll design problem (TDP) provides a quantitative approach to the design of road pricing schemes. Its practical use, however, can be computationally challenging if the formulated TDP requires time-consuming computer models to evaluate candidate designs, especially if such designs must account for multiple objectives. For TDPs to be of practical relevance to the real-world planning of sustainable transportation networks, efficient TDP solution heuristics must be developed. To this end, two surrogate-based solution heuristics for multi-objective TDPs are proposed in this paper. Surrogate-based optimization uses simple approximations to computationally expensive models in order to accelerate the discovery of good solutions. The general search strategy of the proposed heuristics is as follows. In each iteration of the heuristics, a pool of candidate pricing schemes with unique sets of tolling locations and associated tolling levels is generated. From this pool of designs, the heuristics use the surrogate models to screen for solutions that are expected to be nondominated and that meet a specified selection criterion. Then, these promising designs are evaluated by the computationally expensive models, and the outputs obtained from these evaluations are used to update the surrogate models. Both heuristics repeat this general process until a maximum number of iterations are completed, at which point the best TDP solutions are returned.