论文摘要
交通分配问题是现代交通规划和管理中的基本问题,它所确定的交通流分布,可以为交通规划方案的设计和评价等提供理论依据.目前,交通管理部门主要通过交通网络设计、信号优化配时、网络拥挤收费等策略来缓解交通拥堵,而交通分配问题就是作为评价上层方案优劣的下层模型.因此,交通分配问题必须要准确的刻画实际的交通流分布,并且能高效的求解.经典的交通分配理论假定网络中各路段的行驶费用仅与该路段自身的交通量有关,而与其它路段上的交通量无关,此时路段行驶费用函数的Jacobi矩阵是对角阵.但是实际的交通系统中存在一些更复杂的情形,导致路段行驶费用函数的Jacobi矩阵非对称,而与之对应的问题被称为非对称交通分配问题.此时,若仍采用经典的交通分配模型来刻画交通流分布,必然会导致其严重失真,从而导致上层决策失误.非对称交通分配问题目前只能用变分不等式和互补问题来建模,由于求解比较困难,目前实用的高性能算法还比较缺乏,限制了它们的实际应用.本文基于上述背景,研究非对称交通分配问题的有效求解算法.幂罚函数法是最近提出的求解互补问题的新算法,该算法简单有效.我们对幂罚函数法的有关结果予以了改进,并把它拓展到求解带有线性约束的变分不等式问题,然后以幂罚函数法为基础,设计求解非对称交通分配问题的若干有效算法.幂罚函数法将互补问题用带惩罚项的非光滑方程组来近似,其最大的优势是在函数连续及ζ单调条件下,方程组的解将以指数速率O(1/λ/k/ζ)收敛到互补问题的解,其中λ>1和k≥1分别为惩罚项中的罚参数和幂参数.本文在幂罚函数算法的理论方面,主要得到如下结果：1.对非线性互补问题和混合互补问题的幂罚函数法,在函数连续及ζ单调条件下,给出了与指数收敛速率相关的常数的一个新的上界,该上界与罚参数完全无关,而主要与互补问题的解相关.接着证明了幂罚函数算法也适用于单调问题,并给出一个充分性条件保证互补问题和幂罚方程有解，该条件要弱于函数ζ单调.2.对一类带特殊线性约束的变分不等式问题，通过KKT条件,将其转化为混合互补问题,再设计相应的幂罚函数法.在函数连续及ζ单调条件下,尽管该混合互补问题不满足ζ单调条件,但我们仍证明了算法具有指数收敛速率.同时给出了一个充分性条件以保证所涉及的几个问题均有解,该条件要弱于函数ζ单调.接着对带一般线性约束的变分不等式问题也相应的设计了幂罚函数法并证明了算法的收敛性.在函数连续及单调条件下,与线性约束的变分不等式问题对应的混合互补问题也满足单调性,因此幂罚函数法也适用于单调变分不等式问题.3.利用强单调条件下幂罚函数法和牛顿法都有很好的收敛性,将邻近点算法和幂罚函数法相结合,构建了求解单调互补问题和单调变分不等式问题的一种新算法.本文将幂罚函数法用于求解四类交通分配问题,分别为固定需求非对称交通分配问题、弹性需求非对称交通分配问题、非可加交通分配问题和随机网络下的交通分配问题.详细分析了非对称交通分配模型的三类基本的算法框架,即单纯形分解算法、列生成算法和非集计单纯形分解算法.本文主要得到如下结果：1.对于固定需求非对称平衡交通分配问题,针对以路段流量为变量的变分不等式模型,在单纯形分解算法框架下,利用本文提出的幂罚函数法求解有限主问题,得到了一种实用高效的求解算法.同时针对以路径流量为变量的变分不等式模型,在列生成算法框架下,同样采用幂罚函数法求解有限主问题,得到另一种新的有效求解算法.数值实验证明了这两种新的算法是有效的,而且还显示新算法对幂罚函数法的参数选取不敏感.2.将邻近点算法用于单纯形分解算法和非集计单纯形分解算法的有限主问题,构建了求解固定需求问题的新的算法框架.邻近点算法将单调的有限主问题转化为一系列强单调问题,进而利用幂罚函数法高效的求解.数值实验表明,在有限主问题中应用邻近点算法可以提高算法的整体效率.3.对弹性需求非对称平衡交通分配问题的非线性互补模型,在列生成算法框架中,仍使用幂罚函数法求解有限主问题,数值实验也表明这种新的算法是有效的,并且算法对幂罚函数法的参数选取不敏感.4.对非可加平衡交通分配问题的变分不等式和互补模型,提出了基于K最短路和幂罚函数法的列生成算法,数值实验分别考虑了固定需求和弹性需求情形,实验结果证明了算法的有效性.5.最后,还研究了因交通需求量随机变化而导致的路段行驶时间及信号交叉口延误不确定所形成的随机网络,建立了基于可靠性的平衡交通分配模型.对此非可加交通分配模型,采用本文提出的相应算法进行了数值计算实验.
论文目录
相关论文文献
标签：非对称交通分配论文; 变分不等式论文; 互补问题论文; 幂罚函数法论文; 单纯形分解算法论文; 列生成算法论文; 邻近点算法论文;