Toll optimization in a large-scale dynamic traffic network is typically characterized by an expensive-to-evaluate objective function. In this paper, we propose two toll-level problems (TLPs) integrated with a large-scale simulation-based dynamic traffic assignment model of Melbourne, Australia. The first TLP aims to control the pricing zone (PZ) through a time-varying joint distance and delay toll such that the network fundamental diagram (NFD) of the PZ does not enter the congested regime. The second TLP is built upon the first TLP by further considering the minimization of the heterogeneity of congestion distribution in the PZ. To solve the two TLPs, a computationally efficient surrogate-based optimization method, that is, regressing kriging with expected improvement sampling, is applied to approximate the simulation input–output mapping, which can balance well between local exploitation and global exploration. Results show that the two optimal TLP solutions reduce the average travel time in the PZ (entire network) by 29.5% (1.4%) and 21.6% (2.5%), respectively. Reducing the heterogeneity of congestion distribution achieves higher network flows in the PZ and a lower average travel time or a larger total travel time saving in the entire network.