物流配送问题中贪心算法与动态规划法的分析与应用

徐西啸

摘要计算机的应用触及到了生活的各个方面，它的优点之一就在于强大的计算处理能力上，这也正是物流领域配送路线的问题所需要的。如何选择最佳路线，如何节约物流运输成本，即选择配送的最短路线，我们可以通过贪心算法和动态规划算法来做决定。本文对于中国现今发展蓬勃的电子商务的线下运输问题提出了见解，以一个简化的模型介绍了贪心算法以及动态规划法的应用，为线下运输问题提出了解决方案，有着十分重要的现实意义。

关键词物流问题；最短路径；最小时间；贪心算法；动态规划

计算机自诞生以来，发展迅速，在社会中的各个领域都得到了广泛的应用。使用计算机快速处理问题成为当今社会发展的需要。笔者运用计算机知识为现实问题提供一些意见和建议。笔者在今年“双十一”期间亲身经历了爆仓问题，发现物体配送效率低下，“双十一”期间物流速度极慢，形式十分严峻。据官方所提供的数据，买家每秒创建订单数额达到17.5万笔，有些货物甚至预计需要1个月左右的时间才能配送完毕。

对于现今的物流配送，人们大多选择第三方物流。当货物运送到某地区时，物流公司的将货物囤积在一处，再通过快递员将快递送往千家万户。笔者在此希望对快递员的派送路线进行合理化选择，以最短路程，最小时间完成货物的配送。

以城市中的快递配送为例，现简化模型如下：快递员在某地区配送快递，快递公司（货物囤积地）位于0点，快递员需要派送6份快递，分别送往A，B，C，D，E，F六个地点，每两个地点之间的距离已标出，快递员如何快速规划路线，以最短路径、最小时间完成快递的配送，这不仅可以节约劳动力提高工作效率，也会使网购用户收货速度更快。

在具体代码实现中配送需求地映射为编号：0-0，A-1，B-2，C-3，D-4，E-5，F-6：

城市之间的距离用二维数组来表示，记为D[i][j]，如：D[0][1]表示0与A之间的距离，于是D[0][1]=6；设置flag[][]，初始为0，表示此变量未被访问（配送需求地未到达过），若被访问（已到达过配送完毕）则修改为1。

本文中笔者选择贪心算法、动态规划法来解决这一实际问题。

1贪心算法

贪心算法（Greedy algorithm）是一种对某些动态规划中求优秀解的简单、迅速的算法，以当前情况为基础根据某个标准作最优选择，而不考虑整体情况，省去大量时间。

贪心算法在解决问题的策略上缺点是目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心算法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。这种局部最优选择并不总能获得整体最优解，但通常能获得近似最优解。但由于其处理问题简单高效、节省空间，非常适合实际问题的解决。

现在我们通过来解决这一问题，采用最近邻点策略：从某地点（初始为快递公司，即0点）出发，每次在没有到过的中选择距离当前所在地中最近的一个，直到经过了所有的配送需求地，完成了所有配送任务，最后回到快递公司，即0点。

贪心算法具体求解流程如下：1）了解要求送达地点的的数量与各地点之间的距离。2）重复以下两步直至已全部送达：（1）循环遍历找到与当前出发地点最近的未到达过的配送需求地；（2）以当前找到的（最近一次找到的）送达地点为出发地点，重复步骤（1）。3）回到出发地点。

在本题中贪心算法选择路线经过如下：快递员从0点选择较近的A点作为目的地。到达后选择距离当前出发点A较近的点，0点当前已访问，选择B点。而后依次按照此规则选择配送需求点，当所有快递配送完毕返回0点，即快递公司所在地。路线为0->AV>B->C->D>E->F->0。路程为44。

从本例中也可以看出，贪心算法简单便捷，对于问题的解决有很大的帮助。同时我们清楚地看出，使用贪心算法只能考虑当前的选择，当面对复杂的整体问题时，贪心算法未必能给出最优解只求出了近似最优解。

2动态规划算法

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。如本问题的简化模型有许多可以把货物送达的可行解，但我们希望找到能实现最短路程最小时间的最优解。

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。

如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。

在利用动态规划求解的过程中值得注意的就是是否包含最优子结构，简单来讲就是一个问题的最优解是不是包含着子问题的最优解。利用求解子问题的最优解最后得到整个问题的最优解，这是利用动态规划求解问题的基本前提。

动态规划的求解过程主要分为如下的四步：1）描述最优解的结构；2）递归定义最优解的值；3）按白底向上的方式计算最优解的值；4）由计算出的结果构造一个最优解。

在本快递配送问题的简单模型中求解过程具体如下：假设从顶点0出发，令stM表示从顶点0出发经过图中各个顶点，即配送需求地一次且仅一次最后回到出发点的最短路径长度。

2.1描述最优解的结构

要使得从0（以0表示出发处0节点）点出发配送完毕回到0（以7表示返回处0节点，D[7][k]=D[0][k]）点的路程最短，令f（i）为到第i个节点的最短距离，则f（7）=min{D[7][1]，D17][5]，D[7][6]），用同样的方法可以求得f（1），f（5），f（6）等。

2.2递归定义最优解的值

f（i）=min（f（j）+D[i][j]），其中j表示与i边有连接的节点。

2.3按自底向上的方式计算每个节点的最优值

此时我们就得利用递归公式分别求解f（0），f（1），f（2）…f（7），这样最终便能得到最终的解。

2.4由计算出的结果构造一个最优解

本模型最终解为路线为0-（0）>A（1）->B（2）->c（3）->D（4）->E（5）->F（6）->0（7）。路程為44。

动态规划算法关键在于解决了重复计算的问题，大大提高了代码运行效率。总体来说，动态规划算法就是一系列以空间换取时间的算法。

3结论

中国电商业发展十分迅速，但长期以来，线下运输物流配送速度为人所诟病，笔者认为应该有着更高效的配送方式。本文主要利用贪心算法和动态规划算法来进行求解，快速而准确地得出流配送的近似最佳或最佳路线选择，节约物流运输成本，提高消费者满意度，对快递公司派发快递的路线考虑有很强的现实参考意义。endprint