| This dissertation studies numerical aspects of large-scale toll pricing problems, where tolls are used to encourage drivers to choose less congested routes and thereby reduce traffic congestion. A toll pricing problem is an optimization problem for deter mining prices and locations at which to toll transportation networks. The constraints of a toll pricing problem are defined by a system of linear equalities and inequalities describing the toll set, i.e., a set of toll vectors that would encourage drivers to choose routes that lead to the minimum total travel delay. From all the toll vectors in this toll set, an optimal toll vector with respect to a desired objective is selected by solving the corresponding toll pricing problem.; One focus of the dissertation is on developing numerical schemes to obtain nonempty toll sets for practical networks. We consider traffic assignment problems in both fixed and elastic demand cases, and provide sufficient and necessary conditions under which a toll set is nonempty for the two cases. When a toll set is empty, we develop a procedure to relax one or more conditions defining the toll set so that the relaxed toll set is nonempty. Furthermore, we present sensitivity results to validate the proposed relaxation technique.; The other focus of the dissertation is on developing efficient algorithms to address large instances of two toll pricing problems. The first problem is a linear program minimizing the financial burden of tolls on travelers, or from another perspective, minimizing the toll revenue to be collected. We develop a Dantzig-Wolfe decomposition for the problem; and establish the duality relationship between variant, of the Dantzig-Wolfe decomposition and an existing cutting plane method. Furthermore, we identify a variant of the Dantzig-Wolfe decomposition that is the most reliable for practical implementation.; The second problem is a mixed integer program minimizing the number of required toll booths. We show that the problem is NP-complete and develop a heuristic based on the dynamic slope scaling procedure. We also propose a modified slope up dating scheme. Moreover, two meta-heuristics using first improvement local search and simulated annealing, respectively, are explored. |
