交通网络设计和物流管理中的双层优化.pdf

摘要 双层优化是运筹学中的一种优化方法，在实际生活中应用极其广泛，吸引了 许多专家、学者的眼光。近年来有不少关于双层优化的文献，进行了算法上的研 究和创新。这种学术热潮还在继续，双层规划理论正在逐步形成运筹学中新的理 论分支。 双层规划问题（BLPP ）和带均衡约束的数学问题（MPEC ）是双层优化的两 个模型。BLPP 模型是以上下两层规划的形式表示双层优化，上下层均有自己的 目标函数和约束条件。MPEC 模型表示的双层优化，是把下层优化以变分不等式 的约束出现在上层优化中。这两个模型可以应用于经济、国防、市场和工程等各 种领域中。但是因为 BLPP 和 MPEC 的非光滑性和非凸性，吸引了无数学者研究 其算法。即使它们是线性的，也是很强的 NP-hard 问题，这就给求解带来了难度。 在交通网络设计中，带用户均衡约束的交通网络优化问题（TNO-UEC ），是 双层优化，含义是在上层决策者进行交通网络优化的同时，考虑到下层用户的路 径选择行为。BLPP 和 MPEC 这两个模型可以很好的表示 TNO-UEC 问题。BLPP 可以表示一类的 TNO-UEC 问题，这里需要找到最优的决策变量来优化不同的交 通系统性能函数，同时考虑到网络用户的选择路径的行为方式。MPEC 可以表示 更加广泛的 TNO-UEC 问题。因为 TNO-UEC 的框架很特殊，许多研究成果不能 直接应用于 BLPP 和 MPEC 中。相比较，MPEC 模型比 BLPP 模型更难于求解。 值函数的应用是交通网络优化的巨大进步。值函数有许多优良的性质，如连 续可微性。应用值函数能把下层优化转化成等式约束，从而使双层优化 TNO-UEC 问题转变成单层连续可微的规划。本文就是考虑一般TNO-UEC 问题的统一MPEC 模型，先把 MPEC 模型转化成 BLPP 模型，再利用值函数把原规划转变成单层连 续可微的规划。本文的创新在于构造了一个间隙函数，它是两个值函数之差。因 为引入了间隙函数，就可以省略去用户均衡问题的约束条件，那么原规划只有一 1 个等式约束。这时再利用罚函数算法，就等价于求无约束的极值问题，这就极大 的简单了求解过程。于是本文分别设计了简单罚函数算法和增广拉格朗日罚函数 算法。 本文的第二部分，描述了物流管理中的双层优化。对于一个工厂来说，优化 产品运输成本是最重要的，其次还需要考虑运输时间或者运输距离。在物流管理 的双层优化模型中，优化上层运输时间或运输距离的同时，需要考虑下层运输成 本的优化。对于单层的运输问题，闭回路算法是非常有效的。本文在此基础上， 针对双层运输模型提出了新的算法——双费用闭回路算法，并通过算例证明了算 法的优越性。 通过交通网络管理和物流管理这两个方面对双层优化的论述，我们明确了双 层优化的概念，了解了双层优化的应用，并掌握了一些相关的算法。 关键词: 双层优化、交通网络设计、值函数、物流管理 2 ABSTRACT Bilevel programming is an optimization algorithm in Operations Research. It has been widely used in real applications, and attracts many scientists’ interests. In the recent years, many papers presents excellent algorithms about bilevel programming, this upsurge of exploring bilevel programming will continue in the near future, and will gradually form a new theory in Operational Rese