论文部分内容阅读
传统的多商品传输网络中,对商品传输所使用的路径数目没有限制,商品可使用任意数目的路径进行流量的传输。然而在实际的传输网络中,商品使用路径数目过多会增加网络传输费用,同时也会增大网络的管理难度。Baier在2002年提出了k-可分流问题,每个商品只能使用有限数目的路径进行流量的传输。本文研究目标为最小拥塞的k-可分流多商品传输问题,网络拥塞在一定程度上反映了网络的整体负载情况,最小拥塞的目的在于将要传输的商品请求量均衡的分布在网络上,避免出现某些边容量使用过度的情形,这样可以更好的保证网络的整体性能,以服务更多的商品。本文主要内容如下: 第二章中,给出了k-可分流多商品传输最小拥塞问题的三个数学模型,分别称为2指标边-路模型(2-Index Arc-Path Model,2-APM),3指标边-路模型(3-Index Arc-Path Model,3-APM)和边-流模型(Arc-Flow Model,AFM)。2-APM和3-APM均假设网络中每个商品的所有可用路径集合已知,从中选出有限数目的路径作为传输路径;而AFM模型将路径看成一个子流,称为路流,模型直接从网络中为商品找到有限数目的路流作为商品传输路径。 第三章中,对k-可分流多商品传输最小拥塞问题的复杂性进行分析,证明了k-可分流多商品传输问题,可行解的存在性为强NP-难问题。当源点数目N≥2作为输入,对于精确一致k-可分流问题,得到拥塞值小于2的近似算法为NP-难问题。单商品且可用路径数目k作为输入情形,得到拥塞值小于√5+1/2的近似算法是NP-难问题。 第四章中,对单源情形k-可分流多商品传输最小拥塞问题设计近似算法。算法假设商品最大请求量不超过网络最小边容量。算法基本思想是将每个商品转化为若干个同源同汇的小商品,小商品的数目不超出原商品可用路径的最大数目。这样将k-可分流问题转化为不可分流问题,调用不可分流相关近似算法,得到满足每个小商品请求量的不可分流,对小商品传输路径流量进行调整以满足原商品请求量。本文推广文献[25]中2-可分流问题最小拥塞算法到一般的k-可分流问题,即商品可用路径数目为任意值,经过分析得到了关于拥塞和费用的近似比为(3/2·1/1-(1/2)kmin,1),其中kmin为商品集中最小的可用路径数目。对于精确一致k-可分流问题,将其转化为不可分流问题后,调用Marten Skutella[20]中关于不可分流近似算法,得到的关于拥塞和费用的近似比为(2+1/k,1)。本章最后研究了k-可分流最小拥塞问题与最少传输次数之间的关系,证明二者之间存在正相关关系,拥塞值越小,传输次数也越少。本文研究的最少传输次数与传统定义不同,我们允许商品请求量分多次传输,但商品使用的总路径数目不超出其路径数目限制,在使用网络次数最少的情况下,传输完所有商品。 第五章中,研究k-可分流多商品传输最小拥塞问题的快速启发式算法。针对带费用和不带费用两种情形分别进行考虑,其中带费用情形,在保证低拥塞的情况下,尽可能使得网络费用最小,将规范化的拥塞和费用的凸组合作为优化目标。本章所设计启发式算法的基本思想是,从一满足所有商品请求量的可行流中,为商品找到不超出路径数目限制的传输路径,或者找到小规模的备用路径集,从备用路径集中为商品二次选路,得到最终传输路径。最后通过仿真实验,对算法进行对比分析。本文所设计的启发式算法,能够快速给出问题的一个可行解,为商品找到最终传输路径,并尽可能使得网络拥塞最小,可适用于高速商品传输网络。 第六章中,研究k-可分流多商品传输最小拥塞问题的精确算法。针对该问题的特点,分析了采用分支定价精确算法的合理性与优势,并给出了基于分支定价精确算法的基本框架以及一些关键问题的解决思路。