关键词: 交通规划, 启发式算法, 综述, 离散网络设计问题

Abstract: The rapid development of urbanization and corresponding increase in the number of private vehicles have led to a significant rise in traffic congestion, posing a critical and everyday challenge to urban management. The scientific planning and design of urban transportation networks are crucial in optimizing traffic flow distribution, enhancing road network capacity, and improving transit efficiency, thereby fundamentally alleviating traffic pressure. Nevertheless, the Discrete Network Design Problem (DNDP), a frequently encountered issue in transportation planning, has received relatively little attention due to its complexity as an NP-hard and non-convex optimization problem. This paper provides a comprehensive review of DNDP, outlining its origins, conceptual definitions, classification methods, model construction, and solution strategies to inspire further academic interest and exploration in this field.
This paper systematically classifies DNDP into three types: strategic decision-making similar to continuous network design problems, tactical decision-making involving decisions such as one-way traffic directions, and integrated problems that consider both strategic and tactical decisions. A general bilevel programming model is proposed, where the upper level represents the government's objective to optimize the entire transportation network system, and the lower level represents travelers' objective to pursue the most efficient travel routes. This model combines the concepts of User Equilibrium (UE), Stochastic User Equilibrium (SUE), and System Optimal (SO) for traffic assignment. The paper reviews various algorithms for solving DNDP, including exact methods such as branch-and-bound, heuristic algorithms, and metaheuristic algorithms, highlighting their applications and limitations.
The review reveals that while exact methods can provide optimal solutions at the cost of computational time, heuristic and metaheuristic algorithms offer effective approximations. The paper discusses several case studies where these algorithms have been applied to networks of different scales, demonstrating their effectiveness. It also emphasizes the importance of considering demand elasticity in traffic assignment, which has gained attention in recent years. Furthermore, the paper introduces various objectives used in the upper-level optimization model, such as minimizing total cost or travel time, minimizing total travel distance, and maximizing spare capacity.
The paper acknowledges the challenges faced in the DNDP field, particularly the trade-off between solution quality and computational efficiency. It suggests that future research could benefit from hybrid algorithms that combine the efficiency of metaheuristic algorithms with the accuracy of exact algorithms. Additionally, the emergence of shared mobility and the integration of information and mobile internet technologies present new challenges and research directions for transportation network design. The paper concludes by highlighting the need for further research to address these emerging trends and to develop more sophisticated models and algorithms capable of adapting to the dynamics of urban transportation networks.
In conclusion, this paper provides an extensive review of DNDP, offering an in-depth understanding of its complexity and significance in urban transportation planning. It emphasizes the importance of algorithm development and the need for innovative solutions capable of effectively addressing the complexities of DNDP. The paper also points out the potential for integrating emerging technologies into transportation network design, paving the way for future research in this crucial area.

Key words: traffic planning, heuristic algorithm, review, discrete network design problems