Construction of optimization algorithms for road-network design problems considering dicrete constraints

道路网络上的交通拥堵可以通过绕行建设和/或扩大道路宽度来减少。然而，优化路网建设/扩建的问题是NP困难的，而且计算上也是困难的。在本研究中，我们解决了以往研究中没有充分考虑的“离散约束”网络设计问题，并构造了优化算法来解决这一问题。我们提出了“寻找最优路网建设/扩建以减少交通拥堵的数学公式”和“寻找最优铁路时刻表以减少交通堵塞的数学公式”。此外，作为本研究的副产品，我们还得到了一个求解具有非凸目标函数的网络设计问题的数学公式。

Traffic jams on a road network can be reduced by bypass construction and/or expanding width of roads. However, problems to obtain optimal construction/expansion are NP-hard, and indeed computationally difficult.In this research, we tackled a network design problem with "discrete constraints," which were insufficiently considered in previous researches, and constructed optimization algorithms to solve the problem.We have developed "mathematical formulation finding optimal network construction/expansion to reduce traffic jams" and "mathematical formulation finding optimal railway timetable to reduce traffic jams." In addition, as a by-product of this research, we also obtained a mathematical formulation to solve a network design problem with a nonconvex objective function.