基于含连通图约束的背包问题的图分割方法

图分割技术(网络分割技术)在互联网研究、交通运输、电网故障诊断和电力系统解列等方面有着重要的意义。首次建立一个新的图分割问题——含连通图约束的背包问题(connected graph constrained knapsack problem,CGKP),并提出其有效近似算法。引入与图连通性相关的4个新节点集合,证明这些新节点集合的性质,并提出这些节点集合的搜索方法;结合新节点集合的性质及搜索算法,通过对含图约束的背包问题近似算法进行扩展,提出求解CGKP的近似算法,并讨论此算法的计算复杂性。算例结果证明了该算法的有效性。因电力系统主动最优解列问题在一定条件下可归结为一个CGKP,该研究成果为电力系统最优主动解列断面搜索问题的求解奠定了理论基础。

基于江海直达运输模式和投资约束的长江干散货运优化模型

引入了江海直达运输模式和投资约束的概念,对已有的长江干散货运输网络进行优化,并比较了江海直达与江海联运2种运输模式的特点。根据中国内河航运成熟性市场的特质和航运企业滚动规划的经营特征,以最小运营成本与最小船舶投资成本为目标函数,建立了集成处理运输模式选择、航线配船和船型更新的模型。简化了模型的时间维度,设计了基于背包问题的拉格朗日松弛算法,并应用A集团数据求解模型。分析结果表明:当以现行模式的航运总成本为基准点,在引入江海联运模式后,航运总成本可下降2%左右;在引入江海直达运输模式后,航运总成本的最大下降幅度超过8%,但财务风险会增大;当资金成本率为7%且不考虑投资约束时,成本节约效应可提高16.2%,但投资净预算将会上升60.1%。从最优航线配置可以看出,在不同航线上,江海直达与江海联运2种运输模式应协同使用。