供应链（Supply Chain）中运送线路规划问题研究

１引言

在供应链中，与供应链中运输相关的最重要的运营决策是送货路线的规划和送货日程的安排。管理人员必须决定以哪种运输工具向客户送货，并决定向客户送货的先后顺序。如网上商店和网上送货公司，都向客户提供送货上门服务。它们的运营成功，源于其在确保承诺的送货速度同时，降低运费能力。给定一组客户订单送货，公司的目标就是对送货工具和线路进行规划，对送货日程进行安排，以便在满足承诺要求的同时，尽可能地降低送货成本。进行运输工具安排时，典型的目标通常是以下二者的结合：一是缩短运输工具的行程和运输时间，以减少运费；二是避免出现像送货延误之类的失误。管理人员必须决定：哪辆卡车为哪些客户送货，并设定每辆卡车送货过程中的行驶路线。

本文讨论模式为通过配送中心由多个供应商至一家零售商或一个供应商至多家零售店的运送问题。我们考虑如果每家商店的进货规模较小，配送中心就可以使用送奶路线向零售商送货，送奶路线通过联合小批量运送减少了送货成本。

２通过配送中心的“送奶线路”的线路规划

我们认为送货成本与卡车的总行程高度相关，送奶路线就是将不同客户的送货分配到每辆卡车上去，并为每辆卡车设计行驶路线，以达到减少总运距的目标。

首先必须确定哪些卡车为那些客户送货，然后再设计每辆卡车的行驶路线。考虑到供应链中运送货物的频次很高，为更加容易实现编程，使问题能在计算机帮助下更好的解决，笔者采用改进的节约矩阵分析法来解决此问题。

２．１节约矩阵分析法

节约矩阵分析法的基本思想就是在安排为多个零售商运送货物时，在运输工具允许的范围内，选择一组零售商形成组合，目标是使通过配送中心运送组合内零售商货物时，节约的运送距离最大。

２．１．１确认距离方阵

距离方阵就是运送模型中配送中心以及各个零售商之间的距离。

２．１．２确认节约方阵（略）

２．１．３将客户划归不同运输线路的运输工具

我们力图将客户划归不同的运输线路中使节约最大化。这一划分过程要用到一个重复进行的程序。最初每一客户被划分到各自独立的运输线路中去。如果两条运输线路上的运输总量不超过运输工具的最大载重量，那么二者的合并就是可行的。在任何反复进行的步骤上，总是试图使节约最大的两条线路合并成一条新的可行的线路。这一过程一直持续到不能再合并时为止。

２．１．４排定线路内的送货顺序

改变送货顺序对交通工具的行程有显著影响。排定线路内的送货顺序目标是尽量缩短每一运输工具必需的行程。送货顺序的决定就是：首先得到一个最初的行程安排，然后运用线路改进程序得到一个距离较短的送货顺序，这一过程一直持续到不能再改进为止。

节约矩阵分析法采用的改进程序有二分法，三分法等。为更加容易实现编程，我们对它进行改进。

２．２改进的节约矩阵分析法

改进的节约矩阵分析法前面的步骤同上，我们要改进的是第四步，即改进线路程序。

我们在做这一步工作之前，已经利用节约矩阵对零售商分组，现在我们对每组中的零售商排定顺序，以使在本组内运送时距离最短。

２．２．１哈密尔顿图（略）

３算法举例

有一配送中心要为１３家零售商运送某种货物。

我们不考虑延误，即假设零售商对货物到达时间没有严格限制，只要求当天到达即可。我们选择运输工具为卡车，对该产品卡车的容量为２００。

第一步：确认距离方阵

根据各零售商和配送中心所在的地理坐标，得出距离方阵。

第二步：确认节约方阵并改进节约方阵，利用节约矩阵将零售商分组

第三步：将运输线路排定为为客户送货的顺序。

作者：刘文芳陈永峰