交通网络设计中的双层优化模型算法研究.pdf

摘 要 双层优化问题作为多层优化模型中应用最为广泛的一类问题，从其被提出 之日起就受到了极大的关注。传统的单层优化方法在解决规模较大、结构较复 杂的优化问题时，常常显示出其效率上的不足，双层优化模型即是在解决这些 问题的要求上提出的。近年来，随着其在工业、经济、金融和军事等诸多领域 获得广泛的应用，有关双层优化模型的研究正在逐步升温。特别是进入20世纪 90年代以后，由于双层优化方法较之传统单层优化方法具有显而易见的优势， 其在大规模系统的分解技术、生产控制领域的分级规划方法、多目标规划、平 衡规划、博弈论、控制论以及交通运输规划等方面都得到了更大的发展，各领 域专家学者也纷纷发表文献，双层优化已逐渐成为最优化理论与算法研究领域 中最具发展前景的热点问题之一，并成为运筹学领域的新分支。 双层优化模型的一般形式通常包含两层规划问题，决策变量分为上层决策 者和下层决策者，并通过两层决策者的博弈达成最终的决策。而将其应用到交 通网络设计的领域中，恰能将上层决策者与下层网络用户的优化过程完美的呈 现出来。具体的含义是：下层网络用户的路径选择行为能直接影响到上层决策 者对总体交通网络设计的优化决策；而通过上层决策者与下层网络用户的博弈， 可以达到对交通网络中交通系统性能函数优化的均衡状态。 交通网络设计的问题，就是在交通网络规划整体布局的基础上（如：城市 中的各商业网点、火车站、飞机场、港口码头等），利用预测到的资源分布情况， 对整个交通网络进行规划处理，以期达到某项整体性能的最优化（如总费用最 低、总时间最少等），以此适应交通网络整体性的优化需求。但由于交通网络设 计中某项整体性能最优化的问题本身就是一个非线性的多目标规划问题，因而 在实际情形中比较难解决。 双层优化方法较之传统单层优化方法最明显的优势就在于：双层优化问题 可以同时分析决策过程中两个不同的、相互矛盾的目标；其多价值准则的决策 方法更接近实际情况；其分层的模型形式更利于明确表示上层决策部门和下层 公众的相互作用。而在实际的交通网络设计问题中又确实涉及到两种具有明显 不同目标函数的决策者：上层决策者和下层用户，因而对于交通网络设计问题 采用双层优化模型来描述是较为适宜的模型之一。对于交通网络设计中双层优 化问题的求解算法的研究，已经取得了较为丰硕的成果，前人对求解这一问题 提出了多种较为有效的算法，例如罚函数算法、下降算法、信赖域算法、禁忌 有哪些信誉好的足球投注网站算法、遗传算法、模拟退火算法等算法，都在一定意义上获取了较为成功 的求解结果。但由于这一问题结构的复杂性及双层优化模型本身所具有的非光 滑性与非凸性，使得在求解这一问题的实际过程中存在相当大的难度。 本文在对国内外有关交通网络设计及非线性双层优化问题研究的基础上， 通过对现有的求解交通网络设计中非线性双层规划问题的理论与算法进行分类 汇总，综合应用线性规划方法、二次规划方法、非线性规划方法、交通网络设 计、城市规划、程序设计等相关领域的理论知识和技术，对有关求解交通网络 设计中非线性双层规划问题的研究成果、求解难点、需求状况等各方面进行深 入分析，旨在讨论交通网络设计中双层优化问题的创新算法。首先，整理及归 纳双层规划问题、交通网络设计问题的相关文献，并对问题的定义与特性进行 详细介绍；其次，以序列二次规划算法（SQP算法）与积极集算法为基础来求解 交通网络设计中的双层规划问题：通过编程的方法对中小规模交通网络设计双 层优化问题进行数值实验，并与前人所提出的其他算法的结果作比较，分析新 算法与前人所提出算法的优劣，进一步验证本文所建立算法对与求解中小规模 双层规划问题的正确性与有效性。文章共分四章，具体的篇章安排如下： 在本文的导言中，主要介绍了本文的背景知识及现实意义，并对本文的研 究内容、研究方法和创新意义进行阐释；在第一章的文献综述中，简单的介绍 了双层优化问题、交通网络设计问题及交通网络设计中的双层优化问题等领域 的研究成果，客观地分析其他文献在本文所研究领域的发展水平；第二章和第 三章则较为具体的介绍了双层优化模型的理论与算法，以及交通网络设计中双 层优化模型的基本知识，其中第二章主要介绍了双层优化问题的相关知识，对 双层规划模型的一般形式、分类情况进行简单介绍，并介绍求解非线性规划的 序列二次规划算法、求解二次规划的积极集算法等相关算法；而第三章则主要 对交通网络设计问题的提出和发展、用户均衡问题的性质以及交通网络设计中 双层优化的形式及分类进行阐述；在本文最为核心的第