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

摘要： 在有效缓解城市交通拥堵的诸多措施中,城市交通网络的科学规划与设计显得尤为关键。通过合理规划,可以优化交通流的分布,提升道路网络的承载力和通行效率,从而在根本上减轻交通压力。而城市交通网络设计领域中的离散网络设计问题通常较为棘手,且研究相对较少,原因在于这类问题属于NP-hard问题,并且是非凸优化问题。然而,离散网络设计问题在当前的交通规划实践中却是一个反复出现的主题。本文通过深入研究国内外相关文献,对离散网络设计问题的起源、概念界定、分类方法、模型构建以及求解策略进行了详尽的梳理和总结。同时,文章还深入分析了该领域目前面临的主要挑战和未来可能的研究方向,旨在为读者提供一个全面而深入的视角,以期激发更多学者对这一领域的兴趣和进一步的探索。

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