英语原文共 11 页，剩余内容已隐藏，支付完成后下载完整资料
基于随机网络设计的模型与算法
Anthony Chen, Juyoung Kim, Seungjae Lee, Jaisung Choi
摘要
网络设计问题(NDP)是运输领域中最困难和最具挑战性的问题之一。传统的NDP模型被当做是确定性的双层方案,所有的相关输入都是确定已知的。这篇文章为带有不确定性需求的运输网络设计提出了三种随机模型。这三种随机NDP模型可以阐述为双层规划准则下的期望值模型、机会约束模型、相关机会模型，使用了多种尺度来对冲需求的不确定性。基于运输分配算法，遗传算法，以及蒙特卡洛仿真的解决策略被运用于求解这些随机NDP模型。双层规划的非线性和非凸性由遗传算法及运输分配算法处理，而随机性则由仿真来处理。数值实验被用来评估随机NDP模型及相关解决策略的适用性。三个实验的结果表明对于不同的参数设定，这些解决策略都是非常鲁棒的。
关键词：使用者均衡;运输分配;网络设计;双层规划;随机规划
引言
网络设计问题是对于重视全系统目标同时考虑网络使用者的路线选择行为的运输网络改善的优化之一[1]。它已经广泛地被工程师、数学家、运筹学家以及规划师所研究。它被认为是运输领域中最困难和最具有挑战性的问题之一（参见Boyce[2],Magnanti and Wong[3], Friesz[4], and Yang and Bell[5] 关于这个话题的模型、算法发展以及应用的概要）。网络设计问题根据设计变量可以分为三种类型。
- 离散型网络设计问题:添加新连接，可以选择单向和双向道路，以及连接方式和便利位置。
- 连续型网络设计问题:提高容量，道路定价，信号定时，匝道控制。
- 混合型网络设计问题:联合土地使用网络设计问题，同步定位网络设计问题,离散和连续网络中基于封锁网络的高峰行车收费。
文献中的大多数NDP模型，都是以确定性的形式提出，其中所有的相关输入都被假定为确定已知的。例如，交通需求经常被假定为未来是精确已知的，但是由于不确定性，并不能保证交通需求的预测将会精确实现。因为交通需求预测受许多因素的影响，比如经济增长，土地使用模式，社会经济学特征，所有这些因素都不能被精确测量，而只能大概估计。不考虑需求不确定性的对于网络优劣的评估，将可能潜在地导致投资决策的偏向性。为了解释需求不确定性，最近的一些研究已经将NDP扩展，通过假定未来可能发生的一系列情形来考虑未来交通需求的不确定性。这包括系统预期表现的优化，优化系统的均值与方差表现，最大化达到系统表现预定义阈值的概率，优化系统表现的alpha;分位数。本文针对带有不确定性需求的网络设计问题给出三种随机模型。这三种随机NDP模型为双层规划框架下的期望值模型，机会约束模型，相关机会模型，使用了不同的标准来处理需求不确定性。这种随机模型可以被看做是不确定规划的一个子集,不确定规划已经广泛应用于许多领域，包括拓扑优化,产能的位置分配,冗余优化,项目进度安排以及路径搜索等。本文着眼于系统容量的提升,通过采用不同的标准来研究三种随机模型和基于仿真的遗传算法进而求解随机NDP模型。
1 符号和模型
本节描述了带有不确定需求的针对系统容量优化的随机网络设计问题。
1.1 符号
A: 网络中连接的集合
:网络中系统容量连接的集合
: 起讫点对的集合
起讫点对之间路径的集合,
:起讫点对之间路径上的流量, ,
下层子问题中路径流的向量,
:连接中的连接流量,
:下层子问题中连接流的向量,
:连接的系统容量,
:连接中系统容量的上界,
:上层子问题中连接系统容量向量,
:连接中的行程时间, ,为和的函数
:起讫点对路径行程时间,
:起讫点对之间最小行程时间,
:起讫点对之间的随机需求,
:的实现
:随机变量组成的向量
:组成的向量
:连接扩充容量花费,
:如果起讫点对w的路径r使用了连接取1,其他情况取0
:一个固定提高预算
:机会约束模型中的置信度
TTTB:机会约束模型中所有行程时间预算
TTTR:相关机会模型中总的行程时间要求
1.2 随机双层数学规划
NDP 通常被表述为双层优化问题，其用来反映网络使用者和规划者的不同的目标。网络使用者可以自由选择自己的路线，使得个人行程开销最小化，而规划者的目标是充分利用有限的资源使得网络状况最优（例如减少堵塞,最小化对环境的影响,使得流量最大化）,还需要考虑到使用者的路线选择行为。通常的随机双层数学规划模型表述如下:
(1)
(2)
其中由下式定义:
(3)
(4)
其中F是目标函数,u是上层子程序(UP)的设计向量,G是UP的限制集合,f是目标函数, 是下层子程序的决策变量组成的向量,是设计向量和随机向量的函数,g是LP的限制集合。上层子程序描述了领导者或者规划者问题，而下层子程序则代表了顾客或者使用者行为问题。
本文考虑了连续的NDP问题,其连接的系统容量被看做是连续的设计变量u。在系统容量网络设计问题中，通过对带有不确定需求Q的系统范围目标的优化，上层子程序决定了运输网络中的最优系统容量u。而下层子程序对于一个给定的带有不确定需求的系统容量，决定了网络使用者的路线选择行为。系统的目标函数是最小化整个行程时间（也就是减少拥堵）,目标函数定义如下:
(5)
其中和是关于设计向量u和随机需求向量Q的行程时间和连接上的流量。因此性能指标是一个随机变量。
令是定义在概率空间的随机需求向量, 是所有随机试验结果的集合(非空集合), 被称为代数, 为概率测度。对于每一个,是随机需求向量的一个实现。在随后将要描述的三种随机模型中,下层子程序的建模方式是作为标准用户均衡交通分配问题。对于一个给定的设计向量,其中u由上层子程序决定,还包括随机需求向量q的每一个实现，下层子程序解决如下的交通分配问题:
(6)
(7)
(8)
(9)
其中方程(6)是标准用户均衡交通分配问题的目标函数(也就是对连接消费函数积分的求和),方程(7)是流量守恒约束,方程(8)代表了连接路径流量的关系,方程(9)确保了路径流量的非负性。该问题的最优解满足如下的用户均衡条件:
(10)
其中 是起讫点对之间路径的行程时间, ,是起讫点对之间的最短行程时间, 。当路径r的行程时间大于等于最短行程时间时,该条路径上的流量为0或者该条路径未被使用。当路径r的行程时间等于最短时间时,该路径的流量大于0或者该条路径被使用。为了简单起见,本文中广泛使用的UE模型将作为下层子程序对使用者的路径选择行为进行建模。随机双层数学规划框架也可以容纳其他路径选择模型(比如随机用户均衡模型(SUE),扩展逻辑SUE模型,广义用户均衡模型,基于可靠性的用户均衡模型等等)。
1.3 期望值模型
期望值模型(EVM)大概是解决网络设计问题中需求不确定情况下最广泛使用的方法了。其主要的思想是最优化线性(或附加)全局目标函数的期望值,使得满足预算限制还有决策变量的约束限制。
(11)
(12)
(13)
在期望值网络设计模型中,方程(11)中的目标函数是用来最小化网络中的期望总行程时间,方程(12)确保了系统容量的选择连接不会超过可供预算,方程(13)设定了可能的连接系统容量的上界和下界。
期望值模型仅仅考虑了平均的总行程时间,然而它的可变性却被完全忽略了。在此模型下,规划者(网络设计者)将会考虑两个具有相同期望总行程时间的系统容量方案,而不是不同的总行程时间可变性达到相同。该模型所确认的系统容量方案可能是有风险的,因为它可能选择了一个具有更高总行程时间可变性的方案。这样一个方案对于关心总行程时间可靠性的计划者来说是次优的。
1.4 机会约束模型
机会约束模型,最早由Charnes 和 Cooper所提出,建模在随机决策系统的基础上,其假设约束至少保持次,其中是由决策者所决定的作为大概安全边界的置信水平。它的重点是系统的能力满足机会约束（风险措施）在不确定性下具有一定的可靠性。Charnes 和 Cooper建议三种不同类型的目标函数:
- 最优化目标函数期望值的函数(E模型)
- 最小化目标函数的广义平方平均的函数(V模型)
- 目标函数的期望水平满足概率最大化的函数(P模型)
最初的机会约束模型要求使用者同时指定阈值和置信水平。然而有时很难去提前决定大概的阈值。因此,由Liu提出的一种机会约束模型的变形形式被用来确定最小的阈值,需要满足在置信水平下的机会约束。修改后的机会约束模型表述如下:
(14)
(15)
还有(12)和(13)的约束条件
其中TTTB是需要满足机会约束至少次的情况下的总行程时间预算。方程(14)中的目标函数最小化TTTB,满足方程(15)中的机会约束确保了总行程时间小于TTTB的概率要大于等于预定义的置信水平,还需要满足方程(12)下的预算限制,方程(13)中在连接系统容量集合下的限制约束。在修改后的机会约束模型中TTTB是一个变量。规划者只需要确定置信水平。一个想规避风险的规划者可以指定一个更高的值来控制风险。
1.5 相关机会模型
相关机会模型,最早由Liu提出,在不确定的环境中最大化一些事件的机会函数。在网络设计问题中,规划者指定一个要达到的目标(即拥堵水平或道路状况),而相关机会模型的内在逻辑是要挑选出能够有最大机会满足指定目标的最优设计。
(16)
方程(12),方程(13)
其中TTTR是规划者所给定的总的行程时间。方程(16)的目标函数确定了一个系统容量连接的向量(即设计变量),将会最大化总行程时间的可靠性,该可靠性由总的行程时间小于TTTR(一个预定义的阈值)的概率来定义。该相关机会模型的解可以被当做在给定总行程时间要求的情况下最可靠的NDP。它的限制条件和期望值模型一样(即预算限制和在系统容量连接上的限制约束)。
2 基于遗传算法的模拟
随机双层规划通常很难通过传统的微积分优化方法解决。这些需求不确定的网络设计模型是通过由交通分配算法、遗传算法、蒙特卡洛模拟组成的解决程序来求解,旨在处理本文中涉及解决随机网络设计模型的不同复杂性。需求的不确定性通过随机模拟来解决。双层规划的非线性和非凸性由遗传算法来处理。双层数学规划通常是很难解的,因为上层目标函数的评价需要解下层子程序。这里我们使用一个标准的交通分配算法(熟知的Frank-Wolfe算法)来解下层子程序。
2.1 计算不确定函数
随机（或蒙特卡罗）模拟是对随机系统模型进行抽样实验的重要工具。模拟基于
从概率分布中抽取随机变量以计算不确定函数。在随机NDP模型中使用的不确定函数假设一系列设计(即系统容量)已经通过遗传算法步骤确定。要计算的三种不确定函数分别是期望值函数、机会约束函数以及概率函数。
2.1.1 期望值函数
期望值模型的目标函数最小化:
(17)
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[138123]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
