交通规划中的广义纳什均衡问题的理论与算法研究

Generalized Nash equilibrium problem is one of the most popular research topics in the field of optimization. It originates from economics. Now it is used as a model which has many applications in various fields such as transportation, environment, communication, computer science, etc. But the researches on theories and numerical methods are still in its infancy. In this project, we will study on the theories and numerical methods for generalized Nash equilibrium problems in transportation. Based on the efficient algorithms in optimization and the special structure of the generalized Nash equilibrium problems, we plan to make the following researches. First, by using smooth exact penalty function, we transform the generalized Nash equilibrium problems into Nash equilibrium problems. Then we develop efficient algorithm solving the generated problem. Under some assumptions, we will prove the convergence of the algorithm. To solve the hub location problems in traffic area, we introduce the generalized Nash equilibrium problem with 0-1 variables. All the variables will be divided into two parts:the continuous ones and the integer ones. Applying alternative direction methods, we want to develop effective algorithms solving this kind of difficult problems. Finally we plan to use generalized Nash equilibrium problems as models which can solve the problems of routing choice, resource allocation arising from the traffic area. The study which combines the special generalized Nash equilibrium problems with numerical optimization will inspire more research on the problems in other area.

广义纳什均衡问题是优化领域近年研究的一个热点问题．该问题来源于经济学，目前作为模型广泛地用于交通、环境科学、通讯、计算机科学等领域．然而针对该问题的理论和数值方法研究仍处于初始阶段．本项目拟根据广义纳什均衡问题自身的特殊结构，以优化算法为基础，对交通领域出现的几类问题进行理论和算法研究．首先，通过引入光滑的精确罚函数，将广义纳什均衡问题转化为纳什均衡问题,再对纳什均衡问题设计高效算法，在适当的条件下证明算法的收敛性． 针对交通领域中出现的选址等问题，我们引入带0-1变量的广义纳什均衡这一特殊的问题，对于这类复杂的问题，我们将对连续变量与整数变量进行合理的分解，应用交替方向法设计有效的数值求解方法． 最后我们还将广义纳什均衡问题作为模型，解决路径选择、公共资源合理分配等交通问题．这些研究结果将特定的广义纳什均衡问题与数值优化相结合，对其它领域的广义纳什均衡问题的研究将有重要的启示作用．

本项目主要研究交通规划问题中的广义纳什均衡问题的算法及应用，研究了在交通高峰时段随机因素导致的拥堵对出行的影响；研究了用交替方向法求解带有耦合项的凸规划问题；研究了一类特殊的带有整数约束的二次规划问题的求解；构造了一类光滑的罚函数求解广义纳什均衡问题；研究了带有不等式约束的可分离的凸规划问题的求解，用于解决交通规划问题中带容量约束及交通流量分配等问题。首先研究了交通规划中的高峰时段随机因素导致的拥堵问题对出行的影响，这个结果可以为高峰时段出行者提供一个出行时间的参考。我们研究了带二次耦合项的凸规划问题的算法，该算法能够有效地求解特殊的广义纳什均衡问题；突破了交替方向法适用于求解可分离结构的优化问题这一限制。非线性整数规划问题是非常难的一类问题，我们研究了带一类特殊的整数约束的二次规划问题，给出了最优解的必要条件，并以此设计了一个算法。 我们考虑了广义纳什均衡问题的罚函数算法，构造了一类光滑的精确罚函数，理论上能够保证算法产生的点列收敛到解，以往文献中求解广义纳什均衡问题的罚函数方法一般采用非光滑精确罚函数，在具体计算时需要先进行光滑化处理， 我们的数值实验表明该方法求解一些广义纳什均衡问题优于非光滑精确罚函数。 另外还考虑了带不等式约束的可分离优化问题， 这类问题通常的解决方法是引入新的变量，将不等式约束变成等式约束，这样增加了问题的规模，降低了计算效率， 我们将乘子进行投影，利用问题的特殊结构，引入的变量具有显式表达形式，直接求解带有线性不等式的可分离问题，并将算法用于求解交通规划中的流量配置问题及带有容量约束等问题。