管理论文动态规划方法在配送线路优化中的应用研究

《管理论文动态规划方法在配送线路优化中的应用研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、动态规划方法在配送线路优化中的应用研究 动态规划方法在配送线路优化中的应用研究是小柯论文网通过网络搜集，并由本站工作人员整理后发布的，动态规划方法在配送线路优化中的应用研究是篇质量较高的学术论文，供本站访问者学习和学术交流参考之用，不可用于其他商业目的，动态规划方法在配送线路优化中的应用研究的论文版权归原作者所有，因网络整理，有些文章作者不详，敬请谅解，如需转摘，请注明出处小柯论文网，如果此论文无法满足您的论文要求，您可以申请本站帮您代写论文，以下是正文。 　　[摘要]应用图论的方法对配送线路进行优化的缺点是，当线路复杂时计算较为烦琐，而应用动态规划的方法能有效解决这个问

2、题。本文从理论上应用动态规划的方法对共同配送线路进行优化，并应用此方法对实际问题进行计算。 　　[关键词]动态规则方法配送线路 　　 　　配送中心货物配送的线路直接影响到配送的效率、成本，进而影响到顾客的满意度，因此，如何使配送线路最优即路程最短，一直是理论及企业关心的问题。以前解决此问题的方法主要是应用图论的方法，但该方法的缺点是，当线路复杂时计算较为烦琐，而应用动态规划的方法能有效解决这个问题。 　　 　　一、模型建立 　　 　　设n个顶点，每两个项点之间有边连接，现要求从某一个结点出发，经过每一个结点一次且仅一次，最后回到出发时结点，要求路径最短，这就是最优哈密顿回路问题。这个问题用

3、图论语言叙述为：考虑n个顶点无向完全图，为顶点集合，E为边集合，为两结点之间距离。 　　采用动态规划法计算。考虑顶点1为始点（为了书写方便，把顶点等简化为123）和终点的一条周游路线。每条这样的路线均可表示为形式:对于某个路线包含了一条边和顶点k到1的一条通路，这条通路必须经过V－{1,k}的每个顶点各一次。不难看出，如果以顶点1为始点和终点的某条周游路线是最佳的，那么，这条路径上从顶点k到顶点1的部分路径（经过V－{1－k}的每个顶点各一次），必须是从k到1的一条最短路径。因此，最佳原理是适用的。设(i,S)是从顶点i出发，经过S中除去顶点1之外的其它顶点各一次并回到顶点1的一条最短路径

4、的长。于是g(1,V－{1})就是一条最佳旅游路线的长。根据最佳原理，我们有 　　 　　一般地，当时，有 　　. 　　如果对所有选定的k，已知，则可以求得。各的值可逐步求得。令，这是初始状态。往后，依次对元素个数为1的集合S，求得所有的。然后求和绝对值S=2的所有的等等。当时，对任何必须满足。最后可求得问题的最佳解，我们称这种方法为图论中的动态规划方法。 　　 　　二、算法实例 　　 　　集中存储统一配送是现代化连锁经营的典型物流模式。以一个配送中心为10家门店进行配送服务的业务流程为例进行线路优化设计，连锁经营集团在门店不设有仓储设施，由各供应商集货到配送中心，由配送中心统一配货和保管。

5、配送中心以技术为支撑，它是各门店供货枢纽，配送中心建立了有效的信息处理系统如POS系统通过运输车队按照各门店的需求进行配送，门店由于没有设置仓储设施增加了营业面积，降低了各门店仓储人力资源成本。对各门店配送路线的优化选择是典型的最短路径求解方法。由POS系统把各门店的全部需求信息后反馈给配送中心，由配送中心根据商品需求信息制定配送计划并对配送路线做出最佳选择，对各门店进行多品种、小批次、多频率的配送，路线优化设计从配送中心开始，车辆经过10家门店且只经过一次，最终完成配送任务返回配送中心使总路程最短。 　　配送中心采取共同配送方式为各门店配货，共同配送是为了提高物流效率，通过配送中心集中运

6、输货物的一种方式。可以把多种货类集货于一辆车，既提高了车辆的满载率又提高了配送效率。减少了运输自身行为带来的外部不经济如破环生态环境、噪声污染、交通拥挤，即有利于企业经济利润最大化又使整个社会经济的可持续发展。 　　某配送中心与各连锁店之间的距离用矩阵表示，矩阵中的元素aij表示第i个超市与第j个超市之间的距离： 　　约束条件：为各门店实行配送服务的车辆从配送中心出发最终回到配送中心，各门店的配送业务由一辆货车完成；每个门店都必须有货物需求量，所有门店的货物需求量总和不超过配送车辆的载重量。 　　要研究的问题是一辆非满载车辆从配送中心出发经过各个门店配货仅一次并且返回配送中心，约束条件是每

7、个配送任务都需要完成而且货物不能超载，要求配送运输路径最短，这是一个最短的哈密顿回路问题。为了找到由0至10的最短线路，可以将该问题成为0—1—2…1011个阶段，在每个阶段都需要作出决策，即在0点需决策下一步到哪个门店;同样，若到达第二阶段某个状态，比如1，需决定走向1还是2;依次类推，可以看到：各个阶段的决策不同，由0至10的线路就不同，当从某个阶段的某个状态出发作出一个决策，则这个决策不仅影响到下一个阶段的距离而且