基于节约矩阵法的物流配送决策问题

作者简介：程丽红（1995-），女，汉族，安徽亳州人，学生，南京农业大学，交通运输专业。

摘要：本文针对由子库向零售点配送货物的路径选择问题，综合运用节约矩阵法、贪心算法以及旋转扫描法选择每辆车需要配送的零售点并安排配送路线，使得总运输距离最短进而降低运输费用。

关键词：配送路线；节约矩阵法；贪心算法；车辆调度

引言

作为现代物流最重要的部分，运输引起越来越多企业的关注。运输距离作为影响运输费用的主要因素，如何尽可能缩短运输距离是企业管理者正在面临的问题。一个子库如何配发车辆选择合适的路径配送货物属于车辆的路径优化问题（VRP），国内外的学者均对此有所研究，提出了遗传算法、扫描法、节约法以及精确算法。由于部分算法的模型复杂、运算量较大难以求解以至于没能被企业推广使用。通过学习和查阅资料得知用节约矩阵算法进行物流送货路线优化，可以简单有效地求得问题的最优解或近似最优解，本文采用操作简单便捷的节约矩阵法优化配送路线，在通过软件实现的过程中由于运用节约矩阵算法进行排序的程序代码出错较多，选择用贪心算法来实现给各个客户送货的排序问题。由于贪心算法选择最近的点，个别点会明显增大总路线长度，因而用旋转扫描法进行最终的优化。综合运用三个模型看似麻烦实则算法复杂度及路线优化效果均明显提高，具有较强实用性。

1.问题描述分析

该问题是对从子库到零售点送货安排路线优化问题的研究，由子库向50个不同需求的零售点配送货物，每辆送货车装载量上限为160，通过制定合理的送货线路，快速而经济地将子库货物送达用户手中。以总的运输时间最短为目标，假设速度均匀，则可转化为总的路线长度之和最短同时要满足的约束条件是每辆送货车的装载量不超过160，送到每个零售点的货物不少于各自的需求量。

运用节约矩阵法进行送货线路优化时，已知条件为每个零售点的位置坐标和订货量、子库的位置坐标以及拥有的车辆数；优化目标为确定每一个参与送货的车辆装载多少货物，送货到哪几个零售点，走什么线路，使得配送距离最短从而使送货总费用最小。

对于网状结构的运输配送，把子库和零售点假定成点，把子库与零售点之间的配送路线假定成线。从而把子库与零售点之间的配送运输路线优化问题转化成寻找由点与线组成的网络图中各点与各线之间的最佳路径问题。

2.算法原理与求解

节约矩阵法的基本思想是：如果将运输问题中的两个回路合并成一个回路，就可缩短配送线路总里程，并减少了一辆车。下图为合并回路前后总里程优化情况：

图1两种配送路线图

设子库为O点，位置坐标为（xO，yO）；订货零售点为1、2、……n，位置坐标分别为（x1，y1）、（x2，y2）……（xn，yn）。节约矩阵分析法的主要求解步骤包括：

（1）确定距离方阵。确认距离方阵是要求出配送系统中子库与各零售点之间的距离，在坐标系中两点之间的距离公式为：

Dist（a，b）=（xa-xb）2+（ya-yb）2（2-1）

式中a，b是0—n之间的任意数。

（2）确定节约方阵。节约方阵是指将两个零售点的订货放在一辆货车上联合运送时节约的累积，本文按照距离建立节约方阵。用S（A，B）表示由于将o-a-o、o-b-o两个回路合并成o-a-b-o一个回路而节约的距离，由图一可知节约方阵如下：

（3）确定每辆车配送的零售点。确定每辆车配送的零售点时，目标是在满足每个零售点的订货量需求以及保证每辆车不超载的前提下使总的节约距离最大。方法是首先为各个零售点确定单独的配送回路，任意选择一个零售点为起点，按照节约距离越大优先权越高的原则优先合并各零售点间的配送车辆直至车辆的最大载运量。接着开始新的车辆配送点选择直至所有零售点配送完成。

（4）确定每辆车的配送路线。确定每辆车所需要配送的零售点后需要确定为各个零售点配送订单的先后顺序，由于每辆车所配送的零售点不重叠，各配送路线间不会相互影响，因此目标是每辆车的运输行程最短即可，贪心算法可以简单有效地求得问题的最优解或近似最优解。

贪心算法步骤如下：（1）从点1出发计算点1与余下的n-1个点的距离，最短的距离为的d1、2′，相对应的点记作2、；（2）计算点2与余下的n-2个点的距离，最短的距离为的d2′，3′，相对应的点记作3′；…；（3）计算点j′与余下n-j个点间的距离，最小距离为dj′，（j+1）′，相对应的点记作（j+1）′…；（4）最后，计算点（n-1）′与余下的点n′间的距离d（n-i）′，j′，n′，总路程：

L=d12′+∑n-1j=2dj′，（j+1）′+dn′，1′（2，3）

此算法是基于局部最优进而求得整体解，可能出现线路反复、最后返回出发点的距离很大等情况，故求得的整体解不一定最优。但可以后期通过画图对结果进行直观的优化。

（5）优化初始送货线线。综合节约矩阵法和贪心算法得到的配送运输路线后，采用旋转扫描法，对于明显不合理的客户节点进一步优化，从而得到使运输行程变短或运输成本变小的优化送货线路。

3.算例分析

某公司子库为50个零售点配送货物，子库、零售点坐标及订单量等信息如下表：

4.结论

伴随着电子商务的快速发展，运输在企业中发挥越来越重要的地位。本文提出了综合节约矩阵法、贪心算法以及旋转扫描法来解决子库与零售点间车辆配送路线优化问题。经过对实例的分析可以验证方法的便捷实用性，优化效果良好，对企业的配送路线优化具有一定的实用价值。（作者单位：南京农业大学）

参考文献：

[1]轩华.基于改进节约法的配送路线优化问题研究[J].物流技术，2010，Z2：94-97.

[2]王勇，吴志勇，廖明，张战峰，赵鹏.物流配送车辆调度决策支持系统[J].重庆大学学报（自然科學版），2006，09：162-166.

[3]张宇，童莹.物流业节约矩阵法优化研究[J].企业导报，2013，01：116-117.