软容量约束的动态设施选址问题的近似算法

考虑软容量约束的动态设施选址问题.假设设施的开放费用及连接费用都与时间有关,而且每一个设施均有容量约束.对此问题给出了第一个近似比为6的原始对偶(组合)算法.运行贪婪增加程序后,近似比进一步改进到3.7052.     

弹性需求下路段相互影响的交通网络均衡模型

本文利用网络用户均衡原理,对弹性需求下路段相互影响的交通配流问题进行研究,给了弹性需求下路段相互影响的网络均衡条件,建立了与均衡条件等价的变分不等式模型,论证了模型解的存在性和唯一性.     

随机需求下UE-CN混合交通均衡分配的效率损失

在交通网络中,用户的出行需求通常是随机的,而且不同类型用户的路径选择原则存在着差异.基于UE用户和CN用户路径选择原则的异质性,对随机需求下该类混合交通均衡分配的效率损失进行研究.构建了随机需求下UE-CN混合交通均衡分配的变分不等式模型;其次,运用非线性规划方法得到了路段出行时间成本为单项式函数时的效率损失上界表达式,进而探讨了需求还服从对数正态分布时的效率损失上界情况;最后,给出了数值算例.研究结果表明,单项式成本函数时的效率损失上界依赖于其最高次幂和CN用户的数目;当需求为对数正态分布时还和最大变异系数相关.数值算例表明解析方法是可行的.     

收费机制下一类随机需求混合交通均衡分配的非合作代价

运用算法博弈论探讨一类随机需求混合交通均衡分配在收费机制下的非合作代价.首先,构建了收费机制下随机需求UE-CN混合交通均衡分配的变分不等式模型.其次,运用解析推导法分别得到单项式出行成本函数下是否将收费作为系统总成本一部分时,该类混合交通均衡分配的非合作代价上界表达式.在此基础上,探讨了出行需求服从对数正态分布时的非合作代价上界表达式.并以数值算例验证所得结论.     

带有惩罚和软容量约束的下界设施选址问题的双标准近似算法研究

研究带惩罚和软容量约束的下界设施选址问题. 扩展Guha等(Guha S, Meyerson A, Munagala K. Hierarchical placement and network design problems [C]//Proceedings of Foundations of Computer Science, 2000: 892328, DOI: 10.1109/SFCS.2000.892328)和Karger等(Karger D R,Minkoff M. Building steiner trees with incomplete global knowledge [C]//Proceedings of Foundations of Computer Science, 2000: 892329, DOI: 10.1109/SFCS.2000.892329)的工作到带有惩罚的下界约束设施选址问题,提出了一个新的双标准近似算法,得到了同样的近似比ρ(1+α)/(1-α). 进一步考虑带惩罚和软容量约束的下界设施选址问题,得到了近似比为2ρ(1+α)/(1-α)的双标准近似算法.     

非对称弹性需求网络容量限制交通分配有效算法

在非对称交通网络中,针对路段容量限制下弹性需求用户均衡分配模型计算困难,提出了一种路段容量限制弹性需求用户均衡交通分配问题的有效算法.该算法在迭代时,排队延误因子、误差因子与交通需求通过自适应调节来逼近真实路段车辆行驶时间和出行者交通需求,促使各路段交通流量逐步满足限制条件,最终达到弹性需求广义用户均衡.方法克服了容量限制弹性需求用户均衡分配计算量大及随机分配法要求枚举所有路径的困难.随后证明了算法的收敛性,并对一个小型路网进行了数值试验.     

需求弹性与供给弹性的几何特征

常见的通过需求曲线(D)或供给曲线(S)的陡峭或平缓程度来研究需求弹性或供给弹性的大小,是不确切的、不全面的.为了更好地掌握弹性的大小变化,本文引进等弹性曲线簇的概念与图形,讨论需求弹性与供给弹性的几何特征,并通过实例分析更确切全面地比较需求弹性或供给弹性的大小.     

稳健交通均衡模型的SDP松弛

交通均衡问题在城市交通管理中具有重要意义.研究均衡交通的目的是通过对稳定交通流进行量化分析、,为决策者提供交通规划及管理的依据.Wardrop交通均衡原理是描述交通均衡问题的基石,本文在其扩展之一的稳健Wardrop(Robust Wardrop,简记为RW)互补均衡模型的基础上,将不确定因素的盒子约束改进为球约束,以改善原有模型的保守度.其次给出带有不确定因素的稳健Wardrop极小化形式及其确定性稳健对应模型(Robust Counterpart,简记为RC).最后通过SDP松弛手段将稳健对应模型(RC)松弛为容易的线性半定规划问题进行求解,并给出实例说明,为不确定因素影响下的交通均衡问题提供了一种新的有效模型及解法.     

关于需求价格弹性的探讨

需求价格弹性是管理经济学中的一个重要概念,是指导市场行为的重要指标,如何理解需求价格弹性概念,掌握弹性的计算方法就显得格外重要.本文探讨需求价格弹性的概念及计算方法.     

均衡约束数学规划问题的一种新的约束规格

本文研究了均衡约束数学规划(MPEC)问题.利用其弱稳定点,获得了一种新的约束规格–MPEC的伪正规约束规格.用一种简单的方式,证明了该约束规格是介于MPEC-MFCQ(即MPEC,Mangasarian-Fromowitz约束规格)与MPEC-ACQ(即MPEC,Abadie约束规格)之间的约束规格,因此该约束规格也可以导出MPEC问题的M-稳定点.最后通过两个例子,说明了该约束规格与MPEC-MFCQ以及与MPEC-ACQ之间是严格的强弱关系.     

求解交通均衡配流问题的新算法

给出了一个求解交通均衡配流问题的新算法,证明了新算法的收敛性,并在小型交通网络上进行了初步的数值试验.     

求解交通均衡配流问题的新算法

给出了一个求解交通均衡配流问题的新算法，证明了新算法的收敛性，并在小型交通网络上进行了初步的数值试验．     

区域信号配时模型的非平衡交通分配算法

本文研究了区域信号配时问题.采用遗传算法和非平衡交通分配的拟Frank-Wolfe算法来求解,通过实例对算法进行验证并与已有的算法结果进行了比较,结果表明算法是有效的,适合求解这类问题.     

综合型交通分配问题的一种模型及算法

本文针对我国城市交通状况的特点,综合分析交通网络中自行车、公交车,一般机动车三种基本方式的交通流,建立了一个综合型交通分配问题的数学模型,给出了求解它的比较实用的迭代算法,推广并改进了Sheffi等的结果.     

有容量限制的广义网络均衡比较

近些年来,Wardrop原理在有容量限制的交通网络中沿着两个方向被学者推广,形成了几种不同的广义网络均衡定义.在路径、路段上两种类型的容量限制下,通过对四种广义网络均衡进行比较,得到这些均衡解之间的相互关系;用反例说明广义均衡解集包含关系不成立的情况;得到这些广义均衡解的效率损失.     

THE EQUILIBRIUM PROBLEM AND CAPACITY FOR JUMP MARKOV PROCESSES

（刘禄勤）ＴＨＥＥＱＵＩＬＩＢＲＩＵＭＰＲＯＢＬＥＭＡＮＤＣＡＰＡＣＩＴＹＦＯＲＪＵＭＰＭＡＲＫＯＶＰＲＯＣＥＳＳＥＳ￥ＬｉｕＬｕｑｉｎ（Ｄｅｐｔ，ｏｆＭａｔｈ．，ＷｕｈａｎＵｎｉｖｅｒｓｉｔｙ，Ｗｕｈａｎ４３００７２，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：...     

互补约束规划问题的一个广义梯度投影算法

本文研究了一类均衡约束最优化问题.利用广义梯度投影法,结合罚函数思想,得到了一个初始点可以任意的广义梯度投影算法.在较弱的条件下,证明了算法的全局收敛性.     

带平衡约束的离散网络平衡设计问题的遗传算法

本文研究了带平衡约束的离散网络设计问题及其求解算法.模型中上层是一个离散网络设计的数学规划模型,采用遗传算法来求解.下层是采用变分不等式描述的用户平衡配流问题,利用对角化方法直接求解.通过实例对算法进行验证,结果表明该算法是有效的.     

AN INVERSE MAXIMUM CAPACITY PATH PROBLEM WITH LOWER BOUND CONSTRAINTS

IIntroductlonWrseProblem ofCombinatorial Optunatlon has ttrartedmore砒iemion ofresearchersrecentlx It Is irst nroPosed br D·Burton and Ph·L·h尬 in[11,拙er that J．Zhang,Z．Ma,M．Catnd oth删h印儿done some r田earo work on them陀r%pr加咖s Of shortest path,mat山lug,*]．－－－*1fill sp皿D*旷r%,*砒m皿m伽n山阻111tim c毗,*%r01讥扯所肥出饲811加妙－5]．讪出把papers l皿vs conhe their modd onthe suppooltlonth时 sh耐est p毗h,mimmum spanningtree,matd止ng and so on are一、n．h "aner [61,D．Burton…