随机型流量网络中若干问题的模型及其算法的研究

发布时间：2020-09-02 07:46

　　网络流理论是图论的一个重要分支,是研究网络上相关优化问题的理论和方法。1956年,L.R.福特和D.R.富尔克森等人给出了解决在给定的网络上寻求两点间最大运输量这类问题的算法,从而奠定了网络流理论的基础。网络流理论发展至今,已普遍应用于通讯、运输、电力、工程规划、任务分派等众多领域。为了更好的解决现实中的问题,网络流理论也在不断发展中,先后出现了具有增益的流、分派与匹配、网络优化的拉格朗日松弛法、多商品流、网络流的分解与合并等新的理论和方法。但以上研究都是在网络参数和拓扑结构固定的网络上进行的优化,而实际环境中的网络系统受多种因素影响往往会表现出随机性,所以传统网络流理论在具体应用时与实际情况会有一定的偏差,如果能在随机环境下对网络流进行优化,对提高网络流理论的实用性和针对性均有重要意义,这个问题已越来越引起关注。目前主要从3个方面将随机因素引入网络流理论:1.令网络的权值为随机变量;2.假设网络的拓扑结构为随机的;3.假设网络中各边的容量为随机变量,提出了随机型流量网络(Stochastic Flow Network)的概念。随机型流量网络上的网络流理论的研究目前处于起步阶段,研究主要集中在:设计算法寻找网络流在网络容量状态X下的最大流V(X)能满足接收端需求d的网络容量状态的临界点d-MCs或d-MPs,并根据这些点计算随机型流量网络的可靠性。但当随机型流量网络的容量处于非临界状态时,对网络流进行分配优化的研究还较少见,论文中将针对不同问题选取特定优化目标,研究网络流不处于最大流状态V(X)时的优化问题。论文主要研究了以下几方面的内容: 1.以目前使用较多的两种随机型流量网络模型(网络节点可靠,单商品流,多发送端,多接收端的网络模型和网络节点不可靠,多商品流,多发送端,多接收端的网络模型)为基础,研究当网络流不处于最大流状态V(X)时如何对网络流流量进行分配优化。选定满足接收端需求的网络流可靠性为目标,建立整数随机规划模型。针对模型的特点,设计相应的算子,采用遗传算法对优化模型进行求解,并与使用Lingo软件方法求解得到的结果进行比较,分析两种求解方法的优缺点及其适用的问题。 2.文中将网络流传输时间和成本从约束条件转化为整体优化目标,并结合网络流可靠性这一主要目标,研究随机型流量网络上网络流的多目标优化问题。为求解建立的多目标优化模型,对NSGA-II方法做出如下改进:改进2-联赛选择算子的比较规则,将模拟2进制交叉算子改进为单点复合交叉算子,改进精英保留策略,使用改进后的算法对模型进行求解,经过测试,得到的结果从多方面优于原NSGA-II算法。 3.已有的随机型流量网络可靠性的算法,由于涉及到最大流最小割原理和Ford-Fulkerson算法等传统网络流理论,故不得不假设随机型流量网络中的所有变量为离散型变量。本文中由于采用了单目标/多目标遗传算法对网络流进行优化,故不受上面的限制。因此文中扩展随机型流量网络的容量为连续型随机变量,各条边上分配的网络流量为连续实数,建立连续型的多目标网络流优化模型,为了处理包含连续型变量的等式约束,对等式约束增加逼近参数,将等式约束分解为两条不等式约束以逼近方式处理。采用改进后的NSGA-II对处理后的优化模型进行求解。通过测试,可快速求出连续型多目标优化模型的Pareto前沿。 4.论文对网络中各节点包含随机需求的网络流多目标优化问题进行了研究。针对这种复杂随机情况下的网络流优化问题建立了机会约束多目标随机规划模型。对建立的随机规划模型进行预处理,将部分以置信度表示的约束条件转化为对应的确定性等价约束。采用随机模拟方法对优化模型的其余部分进行处理。结合前面提到的改进后的多目标遗传算法,提出一个基于随机模拟的多目标遗传算法对机会约束随机规划模型进行求解。通过算例测试,可以求得优化问题的Pareto解集。
【学位单位】：山东师范大学
【学位级别】：博士
【学位年份】：2008
【中图分类】：N945.15
【部分图文】：

流量网络,节点,接收点

图 2.1.1 节点可靠的随机型流量网络通过一个实际的例子来测试提出的遗传算法，假设有如图节点可靠的随机型流量网络，有两个发点 s1、s2，两个接收运输一种资源到接收点并要求满足接收点的需求。网络中各概率分布可以通过一些统计方法得到，本例中假设其概率分最大容量向量 M = (6,5,5,7,3,5,7,6,8,3,4,4,6,8)。假设发点2 分别服从均匀分布 U(5,25)、U(5,29)，收点的资源需求量d分布 N(8,0.72)、N(11,1.52)。本例中的 MPs 共 11 条，如下 5 , a},1,1,2 2 7 9MPs = {a , a , a},1,1,3 1 6 MPs = {a , a , a 6 14 , a , a},1,2,2 2 7 14MPs = {a , a , a},2,1,1 3 7 MPs = {a , a 4 8 13 9 , a , a , a},2,2,1 3 7 14MPs = {a , a , a},2,2,2 4 8 1MPs = {a , a , a

代时,进化过程,遗传算法,物流运输

2.1.2 遗传算法进化 500 代时的 3 次进化过程（从第 6 代到 450 代7 小结节以一个跨国公司物流运输调度问题为例，研究了在多个收点、节点可靠的随机型流量网络上的网络流优化问题。采用了最小路集，使模型的复杂度降低，并将原始问题转化为在各条最小路上进行并提出一个遗传算法求解建立的优化模型。相关决策者可以利用本立模型并求解，然后根据情况来指导物流运输的调度。

均匀分布,流量网络,接收点,资源需求量

图 2.2.1 两个发点两个收点的随机型流量网络.1 所示的一个随机型流量网络，按要求从两个发到接收点 t1、t2,并满足接收点的需求。网络中各布可以通过一些统计方法得到，本例中为便于eCp 取最大值eM 的概率为 0.9，取其它值的概率均M=(12,10,10,14,8,10,14,12,16,8,10,10,12,16,14,1源供给量1,1r 、1,2r 、2,1r 、2,2r 服从均匀分布 U(10,2，收点的资源需求量1,1d 、1,2d 、2,1d 、2,2d 分别服、N(8,1)、N(8,2.5)。本例中的 MPs 共 11 条，5a},1,1,2 1 15 6 18 9MPs = {a , a , a , a , a},1,1,3 2 MPs = {a , 6 18 14a , a , a},1,2,2 2 16 7 18MPs = {a , a , a , a a , a , a},MPs = {a , a , a , a , a ,

【参考文献】