论文部分内容阅读
摘 要：现代物流管理的关键在于决策，决策正确与否直接决定着物流企业能否生存、发展。目前我国的大多数物流企业在库存决策方面还处于初级阶段，尤其是配送中心选址、库存仓储决策等方面仅依赖于传统的经验分析方法，物流库存管理效率低下，急需科学的库存决策支持系统对领导者进行决策支持。针对这两个问题，提出了基于智能的库存决策支持算法，并集成应用到现代物流企业的库存决策支持系统中。实验结果验证了算法的实用性和有效性。
关键词：库存决策支持系统；配送中心选址；库存仓储决策；遗传算法；C4.5决策树算法；
0引言
随着经济飞速发展，现代物流作为集现代运输、仓储管 理、产品流通、加工、配送、客户服务以及信息网络于一体的综合服务业务，在国民经济和社会发展中发挥着重要作用。目前我国的大多数物流企业在库存决策方面还处于初级阶段，尤其是配送中心选址、库存仓储决策等方面的决策仅依赖于传统的经验分析方法，物流库存管理效率低下，急需科学的库存决策支持系统对领导者进行决策支持。因此笔者主要研究物流企业库存决策中的两个重要核心算法，并在此基础上构建一个库存决策支持系统，为行业管理、企业生产提供支持信息。
配送中心选址算法和库存仓储决策算法是笔者讨论的内容。配送中心选址是一种特殊的仓库设计，目的在于加快货物流动速度、方便客户并减少不必要的配送成本，配送中心选址问题属于最小成本问题，即求解使运输成本，变动处理成本和固定成本等之和最小的最优化问题，它包括单一配送中心选址和多个配送中心选址。笔者研究的是多个配送中心选址问题，它是指从一些己知的被选点中选出一定数目的地点，用于设置物流配送中心，使形成物流网络的总费用最少，其中总费用包括基本投资费用、可变费用以及不可变费用等。
遗传算法(GA：GeneticAgorithms)是基于对生物进化机制的模仿而产生的一种优化计算方法，具有并行性和全局搜索特性。笔者采用遗传算法解决配送中心选址优化问题，并通过实验证明其有效性。
库存仓储决策是实现货物对库存仓储模型的选择，它由企业的订货驱动因素决定，选择适合的库存仓储模型对物流业中的仓储管理尤为重要，它将直接影响企业的经济效益。通过数据收集，我们可以得到许多成功的仓储决策历史案例。库存仓储决策的目的是利用这些历史案例，构建决策模型，利用该决策模型对任意给定的输入决策变量，给出最优的仓储决策方案，即采用上述哪种模型作为库存仓储模型。
决策树是预测模型算法，通过将大量数据有目的分类，从中找到潜在有用的信息。C4.5决策树算法，是目前最流行的决策树算法之一，它是对ID3决策树算法的改进。笔者采用C4.5决策树算法解决库存仓储决策问题，并通过实验证明其有效性。
1、库存配送中心选址问题模型及优化算法
1.1问题描述
对选址模型作了如下的假设:
1)仅在一定的被选范围内选出新的配送中心；
2)不考虑库存配送中心的扩建问题；
3)只考虑一种产品的配送，即本系统模型属于单产品多配送中心选址问题；
4)系统各点间采用同样的运输手段；
5)系统中包含二级运输，即包括从供货点到配送中心的运输以及从配送中心到用户的运输；
6)一个配送中心可由多个供货点供货，一个用户的需求也可由多个配送中心提供；
7)运输费用与运输量成正比；
8)配送中心的容量能够满足用户的要求；
9)用户的需求量为已知常量；
10)供货点与各配送中心、配送中心与各用户间的单位运输费用及各配送中心的单位管理费用为己知常量。
目标函数是从候选地点集中选出一定数量的点作为最佳配送中心，使包括从供货点到配送中心的运输费用、配送中心到用户的运输费用、流经配送中心的产品的管理费用以及配送中心的固定投资费用在内的总费用最少。目标函数共包含14个量：E表示总费用；l表示供货点的个数；m表示被选的配送中心的个数；n表示用户的个数；Wki表示从供货点k到配送中心i的运输量；Xij表示从配送中心i到用户j的运输量；Fi表示配送中心i的固定投资费用；Cki表示从供货点k到配送中心i的单位运输费用；hij表示从配送中心i到用户j的单位运输费用；gi表示配送中心i流转产品的单位管理费用；Zi表示配送中心i是否被选中；Ak表示供货点k的供货能力；Mi表示被选配送中心i的建设容量；Dj表示用户j的需求量。
选址问题数学模型:
1.2改进遗传算法求解问题模型
配送中心选址问题属于NP难问题，本文借助改进后的遗传算法来求解。下面通过一个具体的实例来说明。某物流企业有2个供货工厂，6个配送中心备选地，8个用户。
(1)编码方案
采用混合并行编码。决策变量zi，采用二进制编码。决策变量Wki、Xij采用浮点数编码。
(2)解除约束与适应度函数
根据约束条件，分别令：
改进遗传算法的罚函数法：
penaltyf(x)表示罚函数，t表示遗传代数，表示初始系数，这里取3。
设适应度函数为F(x)，Cmax为一个相对较大的数,：
预置的最大值Cmax=10000。
(3)遗传操作
1)选择操作
采用“轮赌法”复制个体进入下一代，设群体大小为M，个体i的适应度为Fi，则个体i被选中的概率pi为：
2)交叉操作
对决策变量zi进行单点交叉，随机选两个个体，再随机选择交叉切点进行交叉。决策变量Wki、Xij也采用与决策变量zi相同的单点交叉法，但交叉点受变量zi的影响。若zi交叉时所选择切点左边的编码串长度为x，则Wki的变量交叉时切点选择在编码串左边的2x处，Xij的变量交叉时切点在编码串左边的8x处。交叉率为相对遗传代数余弦下降的自适应交叉率。
3)变异操作
不对逻辑型决策变量zi进行变异操作。只对被选中的逻辑变量zi所对应的决策变量Wki、Xij进行非均匀变异操作。
(4)参数确定
群体规模M=60，终止代数T=400，自适应交叉率，最大交叉率Pcmax=1.0，最小交叉率Pcmin=0.75；变异率Pm=0.4。
2、库存仓储决策问题模型及算法
2.1问题描述
设D为训练样本集，A为D的一个属性，属性A有n个互不重合的取值{vl，v2，v3，…，vn}。根据D中训练样本在属性A上的取值，D将被分为n个子集Dl,D2,D3,…,Dn。C4.5算法的执行过程如下：
(1)信息熵的计算
信息熵的计算公式为：
P(ui)表示类别为ui的样本所占总样本的比例。
(2)属性A的条件熵计算
条件熵的计算公式为：
P(vj)表示属性A取值为vj的样本所占总样本的比例，P(ui/vj)表示属性A取值为vj时，类别ui的条件概率。
(3)属性A的互信息计算
属性A的互信息Gain(A)的计算公式为：
，V为属性A的所有输出状态集。
(4)属性A的信息增益率计算
属性A的信息增益率GainRatio(A)的计算公式为：
|Di|表示属性A取值为vj的样本个数。
(5)建立决策树的根节点和分枝
检验所有决策属性，选择信息增益率最大的决策属性作为根节点，由该属性的不同取值建立分枝。
(6)递归调用
对各分枝的训练样本子集用递归方法建立决策树节点和分枝，直到满足下面三个条件之一。
条件一:子集中所有元组都属于同一类。
条件二:该子集是遍历了所有决策属性得到的。
条件三:子集中的所有剩余测定属性取值完全相同,但分类属性并不相同,已不能根据这些决策属性进一步进行子集划分。
2.2C4.5决策树算法求解问题模型
下面给出简单的实例，类1表示采用定期订购模型、类2表示采用定量订购模型，由于篇幅有限，还有两种模型未给出。
二、分析过程:
上面的数据集T，有14个样本，9个样本属于类1，5个样本属于类2，区分前的信息熵为:
三个属性都是连续的数值型属性，所以要把所有的值分区成两个区间。C4.5算法选择中间点{vi，vi+1}中的最小值作为阈值。
属性1的集合是{35，50，55，60，65，75，80，85，90，100}，则vi=65，vi+1=75，阈值是65。
同理求属性2和属性3的增益率。
对每个子节点都重复上面的过程。最终形成如下决策树:
3、实验结果
3.1配送中心选址实验结果
实验采用上面给出的实例数据进行测试。将改进后遗传算法与基本遗传算法的输出结果进行了实验计算。群体进化的最大代数为T=500，Pc=0.8，Pm=0.3。分别用改进遗传算法和基本遗传算法重复计算120次。
从实验计算结果看出，当问题规模较小时，用基本遗传算法在可以接受的代数和时间范围内可以获得满意解，但随着物流配送优化规模的进一步扩大，其编码也将变长，采用改进遗传算法的优势将越加明显，说明了该算法的有效性。
3.2库存仓储决策实验结果
实验数据来源于某物流公司2000年到2008年间，收集的库存仓储决策的成功案例。随机抽取预处理后数据集的三分之二作为训练数据集，用这个数据集对C4.5算法进行训练，得出一棵库存仓储决策树模型。再用余下的三分之一数据作为测试数据，对决策树模型进行了测试。
从实验结果看出，用C4.5算法进行库存仓储决策时，正确率达到88.25%。可见对库存仓储决策问题而言，C4.5决策树算法是一个有效的决策方法。
参考文献：
[1]陈文伟.决策支持系统教程[M].清华大学出版社，2004年.
[2]王小平，曹立明.遗传算法理论、应用与软件实现[M].西安交通大学出版社，2002年.
[3]朱玉全，杨鹤标，孙蕾.数据挖掘技术[M].东南大学出版社.
[4]刘海燕，李宗平.物流配送中心选址模型[J].西南交通大学学报(自然科学版)，
2000，35(3):293-296.
[5]王忠，柴贺军，刘浩吾.关于进化遗传算法的几点改进[J].电子科技大学学报.2002,31(1):76-79.
[6]黄晓芳.数据挖掘中决策树算法及其应用[J].兵工自动化.2005，24(2):5-36.
“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文”
关键词：库存决策支持系统；配送中心选址；库存仓储决策；遗传算法；C4.5决策树算法；
0引言
随着经济飞速发展，现代物流作为集现代运输、仓储管 理、产品流通、加工、配送、客户服务以及信息网络于一体的综合服务业务，在国民经济和社会发展中发挥着重要作用。目前我国的大多数物流企业在库存决策方面还处于初级阶段，尤其是配送中心选址、库存仓储决策等方面的决策仅依赖于传统的经验分析方法，物流库存管理效率低下，急需科学的库存决策支持系统对领导者进行决策支持。因此笔者主要研究物流企业库存决策中的两个重要核心算法，并在此基础上构建一个库存决策支持系统，为行业管理、企业生产提供支持信息。
配送中心选址算法和库存仓储决策算法是笔者讨论的内容。配送中心选址是一种特殊的仓库设计，目的在于加快货物流动速度、方便客户并减少不必要的配送成本，配送中心选址问题属于最小成本问题，即求解使运输成本，变动处理成本和固定成本等之和最小的最优化问题，它包括单一配送中心选址和多个配送中心选址。笔者研究的是多个配送中心选址问题，它是指从一些己知的被选点中选出一定数目的地点，用于设置物流配送中心，使形成物流网络的总费用最少，其中总费用包括基本投资费用、可变费用以及不可变费用等。
遗传算法(GA：GeneticAgorithms)是基于对生物进化机制的模仿而产生的一种优化计算方法，具有并行性和全局搜索特性。笔者采用遗传算法解决配送中心选址优化问题，并通过实验证明其有效性。
库存仓储决策是实现货物对库存仓储模型的选择，它由企业的订货驱动因素决定，选择适合的库存仓储模型对物流业中的仓储管理尤为重要，它将直接影响企业的经济效益。通过数据收集，我们可以得到许多成功的仓储决策历史案例。库存仓储决策的目的是利用这些历史案例，构建决策模型，利用该决策模型对任意给定的输入决策变量，给出最优的仓储决策方案，即采用上述哪种模型作为库存仓储模型。
决策树是预测模型算法，通过将大量数据有目的分类，从中找到潜在有用的信息。C4.5决策树算法，是目前最流行的决策树算法之一，它是对ID3决策树算法的改进。笔者采用C4.5决策树算法解决库存仓储决策问题，并通过实验证明其有效性。
1、库存配送中心选址问题模型及优化算法
1.1问题描述
对选址模型作了如下的假设:
1)仅在一定的被选范围内选出新的配送中心；
2)不考虑库存配送中心的扩建问题；
3)只考虑一种产品的配送，即本系统模型属于单产品多配送中心选址问题；
4)系统各点间采用同样的运输手段；
5)系统中包含二级运输，即包括从供货点到配送中心的运输以及从配送中心到用户的运输；
6)一个配送中心可由多个供货点供货，一个用户的需求也可由多个配送中心提供；
7)运输费用与运输量成正比；
8)配送中心的容量能够满足用户的要求；
9)用户的需求量为已知常量；
10)供货点与各配送中心、配送中心与各用户间的单位运输费用及各配送中心的单位管理费用为己知常量。
目标函数是从候选地点集中选出一定数量的点作为最佳配送中心，使包括从供货点到配送中心的运输费用、配送中心到用户的运输费用、流经配送中心的产品的管理费用以及配送中心的固定投资费用在内的总费用最少。目标函数共包含14个量：E表示总费用；l表示供货点的个数；m表示被选的配送中心的个数；n表示用户的个数；Wki表示从供货点k到配送中心i的运输量；Xij表示从配送中心i到用户j的运输量；Fi表示配送中心i的固定投资费用；Cki表示从供货点k到配送中心i的单位运输费用；hij表示从配送中心i到用户j的单位运输费用；gi表示配送中心i流转产品的单位管理费用；Zi表示配送中心i是否被选中；Ak表示供货点k的供货能力；Mi表示被选配送中心i的建设容量；Dj表示用户j的需求量。
选址问题数学模型:
1.2改进遗传算法求解问题模型
配送中心选址问题属于NP难问题，本文借助改进后的遗传算法来求解。下面通过一个具体的实例来说明。某物流企业有2个供货工厂，6个配送中心备选地，8个用户。
(1)编码方案
采用混合并行编码。决策变量zi，采用二进制编码。决策变量Wki、Xij采用浮点数编码。
(2)解除约束与适应度函数
根据约束条件，分别令：
改进遗传算法的罚函数法：
penaltyf(x)表示罚函数，t表示遗传代数，表示初始系数，这里取3。
设适应度函数为F(x)，Cmax为一个相对较大的数,：
预置的最大值Cmax=10000。
(3)遗传操作
1)选择操作
采用“轮赌法”复制个体进入下一代，设群体大小为M，个体i的适应度为Fi，则个体i被选中的概率pi为：
2)交叉操作
对决策变量zi进行单点交叉，随机选两个个体，再随机选择交叉切点进行交叉。决策变量Wki、Xij也采用与决策变量zi相同的单点交叉法，但交叉点受变量zi的影响。若zi交叉时所选择切点左边的编码串长度为x，则Wki的变量交叉时切点选择在编码串左边的2x处，Xij的变量交叉时切点在编码串左边的8x处。交叉率为相对遗传代数余弦下降的自适应交叉率。
3)变异操作
不对逻辑型决策变量zi进行变异操作。只对被选中的逻辑变量zi所对应的决策变量Wki、Xij进行非均匀变异操作。
(4)参数确定
群体规模M=60，终止代数T=400，自适应交叉率，最大交叉率Pcmax=1.0，最小交叉率Pcmin=0.75；变异率Pm=0.4。
2、库存仓储决策问题模型及算法
2.1问题描述
设D为训练样本集，A为D的一个属性，属性A有n个互不重合的取值{vl，v2，v3，…，vn}。根据D中训练样本在属性A上的取值，D将被分为n个子集Dl,D2,D3,…,Dn。C4.5算法的执行过程如下：
(1)信息熵的计算
信息熵的计算公式为：
P(ui)表示类别为ui的样本所占总样本的比例。
(2)属性A的条件熵计算
条件熵的计算公式为：
P(vj)表示属性A取值为vj的样本所占总样本的比例，P(ui/vj)表示属性A取值为vj时，类别ui的条件概率。
(3)属性A的互信息计算
属性A的互信息Gain(A)的计算公式为：
，V为属性A的所有输出状态集。
(4)属性A的信息增益率计算
属性A的信息增益率GainRatio(A)的计算公式为：
|Di|表示属性A取值为vj的样本个数。
(5)建立决策树的根节点和分枝
检验所有决策属性，选择信息增益率最大的决策属性作为根节点，由该属性的不同取值建立分枝。
(6)递归调用
对各分枝的训练样本子集用递归方法建立决策树节点和分枝，直到满足下面三个条件之一。
条件一:子集中所有元组都属于同一类。
条件二:该子集是遍历了所有决策属性得到的。
条件三:子集中的所有剩余测定属性取值完全相同,但分类属性并不相同,已不能根据这些决策属性进一步进行子集划分。
2.2C4.5决策树算法求解问题模型
下面给出简单的实例，类1表示采用定期订购模型、类2表示采用定量订购模型，由于篇幅有限，还有两种模型未给出。
二、分析过程:
上面的数据集T，有14个样本，9个样本属于类1，5个样本属于类2，区分前的信息熵为:
三个属性都是连续的数值型属性，所以要把所有的值分区成两个区间。C4.5算法选择中间点{vi，vi+1}中的最小值作为阈值。
属性1的集合是{35，50，55，60，65，75，80，85，90，100}，则vi=65，vi+1=75，阈值是65。
同理求属性2和属性3的增益率。
对每个子节点都重复上面的过程。最终形成如下决策树:
3、实验结果
3.1配送中心选址实验结果
实验采用上面给出的实例数据进行测试。将改进后遗传算法与基本遗传算法的输出结果进行了实验计算。群体进化的最大代数为T=500，Pc=0.8，Pm=0.3。分别用改进遗传算法和基本遗传算法重复计算120次。
从实验计算结果看出，当问题规模较小时，用基本遗传算法在可以接受的代数和时间范围内可以获得满意解，但随着物流配送优化规模的进一步扩大，其编码也将变长，采用改进遗传算法的优势将越加明显，说明了该算法的有效性。
3.2库存仓储决策实验结果
实验数据来源于某物流公司2000年到2008年间，收集的库存仓储决策的成功案例。随机抽取预处理后数据集的三分之二作为训练数据集，用这个数据集对C4.5算法进行训练，得出一棵库存仓储决策树模型。再用余下的三分之一数据作为测试数据，对决策树模型进行了测试。
从实验结果看出，用C4.5算法进行库存仓储决策时，正确率达到88.25%。可见对库存仓储决策问题而言，C4.5决策树算法是一个有效的决策方法。
参考文献：
[1]陈文伟.决策支持系统教程[M].清华大学出版社，2004年.
[2]王小平，曹立明.遗传算法理论、应用与软件实现[M].西安交通大学出版社，2002年.
[3]朱玉全，杨鹤标，孙蕾.数据挖掘技术[M].东南大学出版社.
[4]刘海燕，李宗平.物流配送中心选址模型[J].西南交通大学学报(自然科学版)，
2000，35(3):293-296.
[5]王忠，柴贺军，刘浩吾.关于进化遗传算法的几点改进[J].电子科技大学学报.2002,31(1):76-79.
[6]黄晓芳.数据挖掘中决策树算法及其应用[J].兵工自动化.2005，24(2):5-36.
“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文”