论文部分内容阅读
摘 要：物流配送中心选址问题在物流网络规划中占有十分重要的地位，选址的合理与否直接影响配送企业的效益。文章基于树型动态规划，提出了物流配送中心的最佳选址算法。该算法利用树型结构简化配送网络，降低了选址的复杂性，具有较高的稳定性。实验表明，相较于目前较为普遍的算法，如传统动态规划、层次分析法等，文章所提出的算法在时间上具有明显的优势。
关键词：树型动态规划；物流配送；配送中心选址
中图分类号：F252.14 文献标识码：A
摘 要：物流配送中心选址问题在物流网络规划中占有十分重要的地位，选址的合理与否直接影响配送企业的效益。文章基于树型动态规划，提出了物流配送中心的最佳选址算法。该算法利用树型结构简化配送网络，降低了选址的复杂性，具有较高的稳定性。实验表明，相较于目前较为普遍的算法，如传统动态规划、层次分析法等，文章所提出的算法在时间上具有明显的优势。
关键词：树型动态规划；物流配送；配送中心选址
中图分类号：F252.14 文献标识码：A
Abstract： The problem of logistics distribution center location plays an important role in the logistics network planning. The benefit of enterprises is affected by location selection directly. In this paper， the best location algorithm of logistics distribution center was proposed based on the tree dynamic programming. This algorithm uses the tree structure to simplify the distribution network， and reduces the complexity of location. Moreover， it has higher stability. Experiments show this algorithm has obvious advantage on time， comparing with the convention algorithm， such as traditional dynamic programming and analytic hierarchy process.
Key words： tree dynamic programming； logistics distribution； distribution center location decision
0 引 言
物流企业普遍需要同时确定多个配送地址。因而在已有的客观条件下，如何选择配送中心，使得整个系统费用最低，客户服务效果最好，显得尤为重要。一个良好的物流配送中心的选址方案，不但能有效节约成本，促进生产和消费的协调、配合，同时能保证物流系统的高效和平衡发展，使企业在激烈的市场竞争中处于有利的地位。
物流配送中心的选址，对其功能的发挥和整个物流系统的经济效益影响甚大。因此，该问题也引起不少学者的关注。文献[1]基于传统动态规划，提出了最优化网络销售运营方案；文献[2]采用过滤法求解整数规划数学模型，确定了物流配送中心的最佳地；文献[3]分析了物流中心选址中涉及的众多因素，运用层次分析法进行了实现；文献[4]利用BP神经网络处理数据，建立选址决策的模糊评价矩阵；文献[5]借助运筹学思想，以距离为考虑因素，提出合理解决配送中心选址问题的方法。文献[6]结合聚类蚁群算法与AHP-模糊综合评价法，得出配送中心选址的最佳方案。
上述提及的问题，均与物流中心选址有着高度的相似性。但配送点较多时，往往要耗费大量时间进行求解。本文基于树型动态规划算法，通过分层方法和树型结构，简化物流配送网络，降低选址的复杂度，在时间上具有明显的优势。
1 问题分析
配送中心的选址直接影响了配送环节中各项活动的成本，同时也关系到配送中心的正常运作与发展。因此，配送中心的选址和布局须在充分调查分析的基础上，结合企业自身的经营模式、商品特点及交通状况等综合考虑。
结合配送的相关流程，主要需考虑费用：供货点到配送中心再到用户的运输费用、流经配送中心的产品的管理费用、配送中心的固定投资费用。
2 模型建立
物流配送中心的选址涉及众多的因素和数量关系，因此，在保证模型基本符合现实情况的基础上，作如下假设，以简化模型：
（1）假设配送中心所提供的各项服务收入关于物流量成线形函数；
（2）假设各点间（供货点、配送中心、用户）运送运费为关于路程的线性函数，且同一运送路线费用相同；
（3）假设各点需求量及所在地区的交通情况在一定时间内不出现较大波动；
（4）假设配送中心的固定费用为已知常数。
基于以上假设，仅考虑物流配送过程中产生的运费，将全国的物流配送网络划分为多个区域，每个区域均可确定一个配送中心，且每两点之间均由双向边连接，各边权值即为两端点间的运输成本。分别确定最优点以及最优路径，使得该点到其他各点的费用为最小。具体目标函数如下：
minValue=min■cost■1≤j≤n （1）
其中，cost■表示i点至j点的费用。
3 树型动态规划算法
3.1 符号与定义
3.2 算法求解
普通动态规划均为线性或是建立在图上的。对于线性情况，有两种方向：向前和向后，或称顺推与逆推。树型动态规划以“树”的数据结构为基础，同样有两个方向： （1）根—叶：该方法在实际问题中应用不多，因此无典型实例；
（2）叶—根：根的子节点向根传递有用的信息，再由根通过这些信息求得最优解。
本文所选用的树型动态规划即为后者。由于树型动态规划属于动态规划范畴，因此，它同样具有无后效性、子问题重叠性和最优子结构的性质[7]。因此，树型动态规划建立过程中，只需考虑根节点与子节点间如何进行信息交换即可。
模块1 预处理节点信息
已知：u，v边的权值costuv，标记数组mark；
输入：任意一个点root；
输出：以x节点为根节点的子树所具有的节点数和权值和分别为childx， value1：n；
Step 1 用mark数组标记root；
Step 2 当存在与root节点相连且未在mark中标记的点vi时：
（1）以vi作为进行递归；
（2）childroot+=childvi+1；
（3）valueroot=childvi+1*childrootvi+valuevi。
任意选取一个点作为树的根节点root开始进行第一次树型动态规划扫描，并计算树中每个节点的孩子个数，以及以每个子节点到根的权值和，即求出dpi和childi值。相应目标函数如下：
dpi=dpi+childj*cost■ （2）
childi=childi+childj （3）
其中，j∈Son■，初始值dpi=0，childi=1。
模块2 确定中心点
已知：以x节点为根节点的子树所具有的节点数和权值分别为childx，value1：n，清空mark数组，图中点的个数n；
输入：任意节点root；
输出：以x为根节点的树的总权值和rvaluex；
Step1 用mark数组标记root；
Step2 当存在于root节点相连且未在mark中标记的点vi时：
（1）计算rvaluevi=rvalueroot-childvi+1*costrootvi+n-childvi-1*costrootvi；
（2）以vi作为输入进行递归。
从根节点root出发，利用第一次树型动规中所求得的dpi和childi数组，进行第二次树型动规。此时需采用从根到叶的方式，通过根已有的信息来更新子节点的信息，从而达到求出解的目的。相应目标函数如下：
total_valj=■ （4）
3.3 时间复杂度分析
模块1为处理阶段，对每个节点i求dpi和childi时，其子节点仅在i的转移方程中出现，且只出现一次，因此复杂度为ON。
模块2为决策阶段，通过遍历整棵树，求解每个点到其他点的费用和。由于求当前节点时，只需知道其父亲节点的信息（即父亲节点total_val值），因此复杂度亦为ON。
综合上述分析，总的算法复杂度即为ON。
4 实验结果与分析
为了更好地检验树型动规算法的效率，随机产生了8组数据，同时，通过加权取模的方法，对数据范围作了限定，使其更贴近实际。通过对比，检验树型动态规划的正确性和高效性。本文用于对比的传统算法，采用枚举中心点，求其到其他点的距离和。在所有距离和中，取最小值对应的中心点。
最终得到选址中心确定所需的时间分别为：
对比两种算法可发现：当备选点个数超过一定数量后，树型动态规划的时间效率要远胜于传统算法。且树型动态规划的时间及空间复杂度只和待处理的作业的数量有关。在内存受限，计算时间要求较高的物流配送中心选址问题中，是一种相对理想的算法。
5 总 结
本文以ON的时间复杂度确定了每一区域的最优中心点，大幅度优化了选址效率。但由于配送中心的选址问题还涉及到经济、城市规划等因素，因此算法只能为该问题提供相对较优的参考方案。
本文算法建立在区域划分的基础上，后续将进一步研究区域划分和该算法的结合，并加入影响选址中心的其他因素，提高算法的实用性，使之适用于不同情况，为物流配送中心选址提供更为准确的方案。
参考文献：
[1] 谢云. 基于动态规划的最优运输费用问题探析[J]. 财会通讯，2011（1）：138-139.
[2] 刘晓惠. 物流配送中心选址规划方法研究[J]. 综合运输，2012（3）：30-32.
[3] 李海洋，刘冬敏，张晓磊. 基于AHP层次分析法的物流中心选址研究[J]. 中州大学学报，2012（2）：115-118.
[4] 韩庆兰，梅运先. 基于BP人工神经网络的物流配送中心选址决策[J]. 中国软科学，2004（6）：140-143.
[5] 田昌奇. 物流配送中心合理选址问题的研究[J]. 物流工程与管理，2009（10）：99-100.
[6] 饶良良. 基于聚类蚁群算法的区域物流配送中心选址模型研究[D]. 南昌：江西财经大学（硕士学位论文），2012.
[7] 董军军. 动态规划算法和贪心算法的比较与分析[J]. 软件导刊，2008（2）：129-130.
关键词：树型动态规划；物流配送；配送中心选址
中图分类号：F252.14 文献标识码：A
摘 要：物流配送中心选址问题在物流网络规划中占有十分重要的地位，选址的合理与否直接影响配送企业的效益。文章基于树型动态规划，提出了物流配送中心的最佳选址算法。该算法利用树型结构简化配送网络，降低了选址的复杂性，具有较高的稳定性。实验表明，相较于目前较为普遍的算法，如传统动态规划、层次分析法等，文章所提出的算法在时间上具有明显的优势。
关键词：树型动态规划；物流配送；配送中心选址
中图分类号：F252.14 文献标识码：A
Abstract： The problem of logistics distribution center location plays an important role in the logistics network planning. The benefit of enterprises is affected by location selection directly. In this paper， the best location algorithm of logistics distribution center was proposed based on the tree dynamic programming. This algorithm uses the tree structure to simplify the distribution network， and reduces the complexity of location. Moreover， it has higher stability. Experiments show this algorithm has obvious advantage on time， comparing with the convention algorithm， such as traditional dynamic programming and analytic hierarchy process.
Key words： tree dynamic programming； logistics distribution； distribution center location decision
0 引 言
物流企业普遍需要同时确定多个配送地址。因而在已有的客观条件下，如何选择配送中心，使得整个系统费用最低，客户服务效果最好，显得尤为重要。一个良好的物流配送中心的选址方案，不但能有效节约成本，促进生产和消费的协调、配合，同时能保证物流系统的高效和平衡发展，使企业在激烈的市场竞争中处于有利的地位。
物流配送中心的选址，对其功能的发挥和整个物流系统的经济效益影响甚大。因此，该问题也引起不少学者的关注。文献[1]基于传统动态规划，提出了最优化网络销售运营方案；文献[2]采用过滤法求解整数规划数学模型，确定了物流配送中心的最佳地；文献[3]分析了物流中心选址中涉及的众多因素，运用层次分析法进行了实现；文献[4]利用BP神经网络处理数据，建立选址决策的模糊评价矩阵；文献[5]借助运筹学思想，以距离为考虑因素，提出合理解决配送中心选址问题的方法。文献[6]结合聚类蚁群算法与AHP-模糊综合评价法，得出配送中心选址的最佳方案。
上述提及的问题，均与物流中心选址有着高度的相似性。但配送点较多时，往往要耗费大量时间进行求解。本文基于树型动态规划算法，通过分层方法和树型结构，简化物流配送网络，降低选址的复杂度，在时间上具有明显的优势。
1 问题分析
配送中心的选址直接影响了配送环节中各项活动的成本，同时也关系到配送中心的正常运作与发展。因此，配送中心的选址和布局须在充分调查分析的基础上，结合企业自身的经营模式、商品特点及交通状况等综合考虑。
结合配送的相关流程，主要需考虑费用：供货点到配送中心再到用户的运输费用、流经配送中心的产品的管理费用、配送中心的固定投资费用。
2 模型建立
物流配送中心的选址涉及众多的因素和数量关系，因此，在保证模型基本符合现实情况的基础上，作如下假设，以简化模型：
（1）假设配送中心所提供的各项服务收入关于物流量成线形函数；
（2）假设各点间（供货点、配送中心、用户）运送运费为关于路程的线性函数，且同一运送路线费用相同；
（3）假设各点需求量及所在地区的交通情况在一定时间内不出现较大波动；
（4）假设配送中心的固定费用为已知常数。
基于以上假设，仅考虑物流配送过程中产生的运费，将全国的物流配送网络划分为多个区域，每个区域均可确定一个配送中心，且每两点之间均由双向边连接，各边权值即为两端点间的运输成本。分别确定最优点以及最优路径，使得该点到其他各点的费用为最小。具体目标函数如下：
minValue=min■cost■1≤j≤n （1）
其中，cost■表示i点至j点的费用。
3 树型动态规划算法
3.1 符号与定义
3.2 算法求解
普通动态规划均为线性或是建立在图上的。对于线性情况，有两种方向：向前和向后，或称顺推与逆推。树型动态规划以“树”的数据结构为基础，同样有两个方向： （1）根—叶：该方法在实际问题中应用不多，因此无典型实例；
（2）叶—根：根的子节点向根传递有用的信息，再由根通过这些信息求得最优解。
本文所选用的树型动态规划即为后者。由于树型动态规划属于动态规划范畴，因此，它同样具有无后效性、子问题重叠性和最优子结构的性质[7]。因此，树型动态规划建立过程中，只需考虑根节点与子节点间如何进行信息交换即可。
模块1 预处理节点信息
已知：u，v边的权值costuv，标记数组mark；
输入：任意一个点root；
输出：以x节点为根节点的子树所具有的节点数和权值和分别为childx， value1：n；
Step 1 用mark数组标记root；
Step 2 当存在与root节点相连且未在mark中标记的点vi时：
（1）以vi作为进行递归；
（2）childroot+=childvi+1；
（3）valueroot=childvi+1*childrootvi+valuevi。
任意选取一个点作为树的根节点root开始进行第一次树型动态规划扫描，并计算树中每个节点的孩子个数，以及以每个子节点到根的权值和，即求出dpi和childi值。相应目标函数如下：
dpi=dpi+childj*cost■ （2）
childi=childi+childj （3）
其中，j∈Son■，初始值dpi=0，childi=1。
模块2 确定中心点
已知：以x节点为根节点的子树所具有的节点数和权值分别为childx，value1：n，清空mark数组，图中点的个数n；
输入：任意节点root；
输出：以x为根节点的树的总权值和rvaluex；
Step1 用mark数组标记root；
Step2 当存在于root节点相连且未在mark中标记的点vi时：
（1）计算rvaluevi=rvalueroot-childvi+1*costrootvi+n-childvi-1*costrootvi；
（2）以vi作为输入进行递归。
从根节点root出发，利用第一次树型动规中所求得的dpi和childi数组，进行第二次树型动规。此时需采用从根到叶的方式，通过根已有的信息来更新子节点的信息，从而达到求出解的目的。相应目标函数如下：
total_valj=■ （4）
3.3 时间复杂度分析
模块1为处理阶段，对每个节点i求dpi和childi时，其子节点仅在i的转移方程中出现，且只出现一次，因此复杂度为ON。
模块2为决策阶段，通过遍历整棵树，求解每个点到其他点的费用和。由于求当前节点时，只需知道其父亲节点的信息（即父亲节点total_val值），因此复杂度亦为ON。
综合上述分析，总的算法复杂度即为ON。
4 实验结果与分析
为了更好地检验树型动规算法的效率，随机产生了8组数据，同时，通过加权取模的方法，对数据范围作了限定，使其更贴近实际。通过对比，检验树型动态规划的正确性和高效性。本文用于对比的传统算法，采用枚举中心点，求其到其他点的距离和。在所有距离和中，取最小值对应的中心点。
最终得到选址中心确定所需的时间分别为：
对比两种算法可发现：当备选点个数超过一定数量后，树型动态规划的时间效率要远胜于传统算法。且树型动态规划的时间及空间复杂度只和待处理的作业的数量有关。在内存受限，计算时间要求较高的物流配送中心选址问题中，是一种相对理想的算法。
5 总 结
本文以ON的时间复杂度确定了每一区域的最优中心点，大幅度优化了选址效率。但由于配送中心的选址问题还涉及到经济、城市规划等因素，因此算法只能为该问题提供相对较优的参考方案。
本文算法建立在区域划分的基础上，后续将进一步研究区域划分和该算法的结合，并加入影响选址中心的其他因素，提高算法的实用性，使之适用于不同情况，为物流配送中心选址提供更为准确的方案。
参考文献：
[1] 谢云. 基于动态规划的最优运输费用问题探析[J]. 财会通讯，2011（1）：138-139.
[2] 刘晓惠. 物流配送中心选址规划方法研究[J]. 综合运输，2012（3）：30-32.
[3] 李海洋，刘冬敏，张晓磊. 基于AHP层次分析法的物流中心选址研究[J]. 中州大学学报，2012（2）：115-118.
[4] 韩庆兰，梅运先. 基于BP人工神经网络的物流配送中心选址决策[J]. 中国软科学，2004（6）：140-143.
[5] 田昌奇. 物流配送中心合理选址问题的研究[J]. 物流工程与管理，2009（10）：99-100.
[6] 饶良良. 基于聚类蚁群算法的区域物流配送中心选址模型研究[D]. 南昌：江西财经大学（硕士学位论文），2012.
[7] 董军军. 动态规划算法和贪心算法的比较与分析[J]. 软件导刊，2008（2）：129-130.