需求不确定的有容量限制网络设计问题

摘要

该文研究的是需求不确定的有容量限制网络设计问题.(Capacitated Network Design Problem with Uncertain Demand,简写为CNDPUD).在该网络中,每个结点对每种商品的需求都是不确定的,构成了一个随机规划问题.同时现有的网络图中的任意两点间允许存在多条有向弧,决策者必须从网络中选出一些实际使用的弧来供应需求.同时每条弧上运载的商品数量不得超过其额定的容量限制,在此条件下安排多商品流的运输任务.每选用一条弧就会发生一个相应的固定启用成本.此外,在每个结点上,允许短缺或是过量供应,分别给予相应的短缺或持有成本加以惩罚,目的使得这部分短缺或是多余的需求量尽量小,以降低成本(比如失去客户和过量供应造成的额外仓储成本).问题的目标是使得弧的启用成本、短缺/持有惩罚成本和线性运输成本三者之和达到最小.文中用Benders分解算法求解该随机网络设计问题,通过分支定界方法和延迟约束生成来求解这种大规模有容量限制的网络设计问题.并在微机上测试了一个包含5个结点20条弧的网络问题,形成运算结果.

目录

引言

1.网络设计问题及其应用背景

1.1无容量限制的网络设计问题

1.2有容量限制的网络设计问题

1.3容量扩充问题CEP

1.4网络设计问题的研究现状和本文的主要工作

2.模型和问题的复杂性

2.1问题描述

2.1.1商品的定义

2.1.2需求的不确定性

2.2定义决策变量

2.3模型的构建

2.4问题的复杂性

3.模型的求解

3.1模型转化

3.2 Benders分解算法

3.3合并弧模型

3.3.1两点间多条弧的单位流量成本相同

3.3.2所有商品在同一条弧上的单位流量成本相同

4.延迟约束生成和算法总结

4.1延迟约束生成

4.2算法中的记号和参数

4.3算法思路和步骤

4.3.1算法思路

4.3.2算法步骤

4.4算法对应的框图

5.计算实验

5.1测试问题

5.2运算结果

6.小结

参考文献：

致谢

论文独创性声明及论文使用授权声明