Global optimization methods for urban road network design problems

• Main Author: Liu, Haoxiang
• Other Authors: Gao Ziyou
• Format: Theses and Dissertations
• Language: English
• Published: 2016
• Subjects: DRNTU::Engineering::Civil engineering::Transportation
• Online Access: https://hdl.handle.net/10356/67035
• Institution: Nanyang Technological University

Adequate infrastructure is required to alleviate the traffic congestion with the sustained growth in demand of passenger and freight transportation. The main study area in this thesis is the related transportation network design problem (NDP), which involves the optimal decision on the expansion of the existing links and/or on the addition of new links within a given budget aiming to achieve the best network performance. Since this class of problem can also be generalized to handle other transport management problem, like road pricing and signal control, or even be applied on other transportation modes, like public transport and shipping, hence, NDP deserves more attention and further studies on its modeling and solution algorithm development issues. In the literature, NDP problem is often formulated as bi-level programming, which is nonconvex and nonlinear in nature. The solution of nonlinear and nonconvex problem is well recognized to be extremely hard. In the literature, many researchers focused on developing various algorithmic methods for solving NDP, ranging from classic solution algorithms to widely used meta-heuristic methods. However, though a lot of efforts have been made, challenges still exist mainly in two aspects. First, solution accuracy should be enhanced. Due to nonconvex property of the NDP problems, most algorithms developed in previous studies can only find local optimal solution, rather than global optimization solution. Although these solution algorithms are efficient and fast to obtain a “good” solution, the solution quality is compromised, being a local optimal, rather than the globally best. Other than the local optimization method, a class of stochastic global optimization method, including Genetic Algorithm (GA) and simulated annealing (SA), is applied to solve NDP. However, due to the inherent characteristic of stochastic optimization method, global solution cannot be guaranteed. Second, computational efficiency in terms of calculation time should be improved. NDP problems with real-size network or a large size of candidate projects remain far from being tractable. The thesis contributes to the NDP problems in two main aspects: firstly, to develop more realistic mathematical programming model for urban transportation network design problems; secondly, to propose efficient global optimization solution algorithms for network design problems and ensure the true optimal transportation planning. Firstly, a continuous network design problem (CNDP) that aims to optimize the network performance via road capacity expansion is considered in the thesis. Road users are assumed to follow the traffic assignment principle of stochastic user equilibrium, specifically, the logit route choice model, which is a more general model and includes deterministic user equilibrium flow pattern as an extreme case. To obtain the exact global optimal solution of the problem, a global optimal solution algorithm is proposed based on a tight linear programming relaxation. The developed model, which is bi-level and inherently nonlinear and nonconvex, is firstly transformed into a nonlinear programming with only logarithmic functions as nonlinear terms. Then, the tight linear programming relaxation is derived by applying an outer-approximation technique and embedded within a global optimization solution algorithm, which is proved to converge to a global optimum of the target problem. This thesis also applies range reduction technique in the presented algorithm to improve the computational efficiency. This thesis fills the research gap that no global optimal solution method was developed for CNDP with SUE and guarantees exact global optimal solution of the problem to be solved. The thesis then addresses a discrete network design problem (DNDP) with stochastic user equilibrium constraint that aims to optimize the network performance via new link construction. In order to obtain the global optimal solution of the developed discrete network design problem with stochastic user equilibrium model, which is inherently nonconvex, the original problem is relaxed to a convex mixed-integer nonlinear problem, whose solution provides a lower bound of the original problem. Two iterative global optimization solution methods with the embedded relaxed problem are then proposed to obtain its global optimal solution: one is based on the branch-and-bound method and the other adds extra constraints in each iteration to update the iterative process when searching and approaching the global optimal solution. The main contribution of the algorithm is a tight lower-bound problem is formulated for the original problem via various linearization and convexification techniques without introducing any additional binary variables. Efficiency of the proposed algorithms are illustrated in the numerical studies. Classical discrete network design problem assumes the capacities of the candidate links are given and only link addition is optimized. This thesis considers a novel discrete network design problem that aims to determine both the link addition decision (0 or 1) and the optimal link capacity (the optimal link capacity could be either continuous or at discrete levels) simultaneously, which was not addressed in previous studies or otherwise considered separately. A global optimization method employing linearization, outer approximation and range reduction techniques is developed to solve the formulated model. The computational results are consistent with the theoretical analysis, that is, the solution of the proposed model may provide a network design plan, which is generally better than plan from the sequential two-step method. Finally, this thesis proposes a model to address an urban transport planning problem involving combined network design and signal setting in a saturated network. The mutual interaction between network capacity expansion and signal setting is considered so that best transport network performance can be guaranteed. A bi-level programming model is formulated and a global optimization solution method is designed based on mixed-integer linearization approach to solve the problem, which is inherently non-linear non-convex. Numerical example shows the proposed model provides a better result than ENSS and CNDP.