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

[摘要] 应用图论的方法对配送线路进行优化的缺点是，当线路复杂时计算较为烦琐，而应用动态规划的方法能有效解决这个问题。本文从理论上应用动态规划的方法对共同配送线路进行优化，并应用此方法对实际问题进行计算。

[关键词] 动态规则 方法 配送线路

配送中心货物配送的线路直接影响到配送的效率、成本，进而影响到顾客的满意度，因此，如何使配送线路最优即路程最短，一直是理论及企业关心的问题。以前解决此问题的方法主要是应用图论的方法，但该方法的缺点是，当线路复杂时计算较为烦琐，而应用动态规划的方法能有效解决这个问题。

一、模型建立

设n个顶点，每两个项点之间有边连接，现要求从某一个结点出发，经过每一个结点一次且仅一次，最后回到出发时结点，要求路径最短，这就是最优哈密顿回路问题。这个问题用图论语言叙述为：考虑n个顶点无向完全图，为顶点集合，E为边集合，为两结点之间距离。

采用动态规划法计算。考虑顶点1为始点（为了书写方便，把顶点等简化为123）和终点的一条周游路线。每条这样的路线均可表示为形式:对于某个路线包含了一条边和顶点k到1的一条通路，这条通路必须经过V－{1,k}的每个顶点各一次。不难看出，如果以顶点1为始点和终点的某条周游路线是最佳的，那么，这条路径上从顶点k到顶点1的部分路径（经过V－{1－k}的每个顶点各一次），必须是从k到1的一条最短路径。因此，最佳原理是适用的。设(i,S)是从顶点i出发，经过S中除去顶点1之外的其它顶点各一次并回到顶点1的一条最短路径的长。于是g(1,V－{1})就是一条最佳旅游路线的长。根据最佳原理，我们有

一般地，当时，有

.

如果对所有选定的k，已知，则可以求得。各的值可逐步求得。令，这是初始状态。往后，依次对元素个数为1的集合S，求得所有的。然后求和绝对值S=2的所有的等等。当时，对任何必须满足。最后可求得问题的最佳解，我们称这种方法为图论中的动态规划方法。

二、算法实例

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

配送中心采取共同配送方式为各门店配货，共同配送是为了提高物流效率，通过配送中心集中运输货物的一种方式。可以把多种货类集货于一辆车，既提高了车辆的满载率又提高了配送效率。减少了运输自身行为带来的外部不经济如破环生态环境、噪声污染、交通拥挤，即有利于企业经济利润最大化又使整个社会经济的可持续发展。

某配送中心与各连锁店之间的距离用矩阵表示，矩阵中的元素aij表示第i个超市与第 j 个超市之间的距离：

约束条件：为各门店实行配送服务的车辆从配送中心出发最终回到配送中心，各门店的配送业务由一辆货车完成；每个门店都必须有货物需求量，所有门店的货物需求量总和不超过配送车辆的载重量。

要研究的问题是一辆非满载车辆从配送中心出发经过各个门店配货仅一次并且返回配送中心，约束条件是每个配送任务都需要完成而且货物不能超载，要求配送运输路径最短，这是一个最短的哈密顿回路问题。为了找到由0至10的最短线路，可以将该问题成为0―1―2…10 11 个阶段，在每个阶段都需要作出决策，即在0点需决策下一步到哪个门店;同样，若到达第二阶段某个状态，比如1，需决定走向1还是2;依次类推，可以看到：各个阶段的决策不同，由0至10的线路就不同，当从某个阶段的某个状态出发作出一个决策，则这个决策不仅影响到下一个阶段的距离而且直接影响后面阶段的配送线路。所以这类问题要求在各个阶段选择一个恰当的决策，使由这些决策序列所决定的一条路线对应的配送线路最短。

下面用无向图来表示各门店之间的连通情况。说明如下：节点j表示第j个门店，连接两个门店的边上注明的数字表示两个门店之间的距离。显然这个图是有11个节点的完全加权图，此图共有边条边，为了清楚起见我们不画出所有的边。

按照前面图论动态规划方法，找出最短路径的配送方案为：0132546789100

采用动态规划方法计算量比较小，因而节省时间。例如结点系数为n时，一般情况下找出最短哈密顿回路第一个结点到第二个结点n-1种走法，第二个结点到第三个结点有n-2种走法……，共有1/2（n-1）!，不同哈密顿回路为了比较权大小，对每条回路要做n-1次加法，当n较大时，浪费时间是很多的，如果按动态规划算法，设N是未计算g(1，-{1})前需要计算g(i，s)的个数，对于每一个{S}，i有n-1种取法，又包括1和i取大小为k的不同集合个数是，因此，显然计算量要比较其他算法要小的多。

参考文献:

[1]胡运权:运筹学基础及应用[M].哈尔滨工业大学出版社，1998年2月版

[2]李军郭耀煌:物流配送车辆优化调度理论与方法[M]. 中国物资出版社，2001年3月版

[3]毛薇:物流园区规划及运营关键技术研究[D].天津大学.2005年

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。