Solving a Continuous Transit Network Design Problem Using a Gradient-Based Algorithm

The transit network design problem (TNDP) takes the form of bi-level programming and falls into the category of nondeterministic polynomial time-hard (NP-hard) problems that cannot be solved in a practical amount of computing time as the problem size increases. The upper-level objective is to determine the configuration of transit lines, and the lower-level objective is to load traffic demand onto the transit network. The lower-level problem is thus parameterized with respect to the upper-level design variables. The problem can be interpreted as combinatorics wherein the transit assignment problem should be solved to evaluate each design alternative. Many researchers have mobilized metaheuristics to solve the problem and obtained near-optimal solutions. In the present study, a gradient-descent algorithm was devised to solve the TNDP after converting it to a single-level unconstrained optimization problem. First, the Gumbel soft-max function continuously approximates the discrete design variable of the upper-level problem. Second, the line connectivity constraints change to a penalty function to ensure that the upper-level problem takes the unconstrained form. And, third, the Jacobian of the lower-level solution with respect to the upper-level variable, which plays a key role in computing the gradient of the upper-level objective function, is derived using the implicit differentiation for the Karush–Kuhn–Tucker (KKT) conditions of the lower-level transit assignment problem. The computation utilizes the auto-differentiation scheme without resorting to numerical or symbolic differentiation. When applied to determining the optimal line configuration of a newly projected metro line, the proposed gradient-based algorithm outperformed “state-of-the-art” metaheuristics in both accuracy and efficiency