节约矩阵法的配送中心送货路线优化问题研究精品

基于节约矩阵法的配送中心送货路线优化问题研究1 引言物流配送是指按照用户订货要求，在配送中心进行分货和配货，然后将货物及时送交收货人，其当前趋势是朝着小批量、多品种、多批次的即时送货方向发展，及时满足客户的个性化需求[1]。

影响物流配送体系的因素众多，其中送货线路的规划是非常重要的运营决策，其对加快配送速度、提高物流服务质量和降低配送成本有重要影响。

然而，由于我国物流业起步晚，发展速度慢、物流行业基础设施不足且技术落后，当前我国物流企业基本处于小、少、弱、散的状况[2]。

此外，目前我国大部分自营物流配送中心的运营现状是：送货业务量小且终端客户多；缺乏合理的送货规划；缺乏送货线路优化软件；物流规划专业人才缺乏等。

由于这些问题的存在，我国物流企业尤其是中小物流企业送货成本较高。

考虑到中小物流企业是构成我国物流行业的主体，且今后较长时间内我国物流业仍将以中小物流企业为主体，因而我国物流行业迫切需要降低送货成本，因而找到一种适合我国物流发展现状而且简单实用的送货线路优化方法具有重要的现实意义。

本文主要关注从物流配送中心调用多辆车满足向各零售点的送货服务，即通过为多辆车分配客户并分别制定各辆车的合理行驶线路的多车辆路径问题VRP ( Vehicle Routing Problem )优化算法的实现，从而快速且经济的将货物送达用户。

关于多车辆路径问题算法的研究，国内外学者提出了很多方法，如遗传算法、禁忌搜索算法、模拟退火算法等[3]。

这些算法能够解决复杂的配送路线优化问题，但存在模型复杂、求解难、运算量大的缺点，由此限制了它们在我国物流企业中的推广应用[4]。

本文提出的节约矩阵法，已知条件较少、操作方法简单、优化效果良好，而且可以很容易的根据送货时间限制和其他限制进行修改。

采用节约矩阵法决定哪些货车为哪些客户送货，以及确定每辆货车的最优送货路线，适用于我国现有的中、小型物流企业[5]。

本文运用节约矩阵法进行送货线路优化时，优化目标为：确定每一个参与送货的车辆该运多少货物，走什么线路，送货到哪几个零售点)，从而使送货总费用最小⑹。

已知条件为：①配送中心的位置坐标以及拥有的车辆数；②每个客户的位置坐标和订货量。

限制条件为：①车辆的载重能力约束；②每个客户点只能被一辆车访问。

实际中可能还存在客户对送货时间的约束，即时间窗问题)，本文暂且不涉及该约束。

2 节约矩阵法由于交通运输是一个网状结构，因此可以把分布于这个网状结构中的配送中心和用户假定成一个个数学上的点，把配送中心与用户以及用户与用户之间的运输线路假定成一条条的线。

那么，送货线路优化问题就可转化为在一个以许多“点”和“线”组成的“图”中寻找各点与点间的最佳路径问题。

设配送中心为 0点，位置坐标为(X o, y o)；订货客户为A、B、 ........ N,位置坐标分别为(X A,y A)、( X B, y s) . ( X N,Y N)。

节约矩阵法主要步骤如下：(1)确认距离方阵[1]确认距离方阵是要确认任何将要经过的两个地点之间的距离。

坐标系中任意两点之间的距离公式，见式1。

2 2Dist(K,M ) =*：(X K -X M) +队-Y M ) (1) 式中，K、M都可以取0和A〜N之间的任意点。

这样，就构造出一个N + 1阶的距离方阵。

由于两点之间距离的对等关系，亦即Dist(K , M)= Dist(M , K)，因而该距离方阵是一个对称阵。

因此可以将其简化为上三角或下三角阵。

(2)确认节约方阵⑴节约方阵是指将两个客户的订货放在一辆货车上联合运送时节约的累积。

节约可以按照距离、时间或者货币来计量，本文按照距离建立节约矩阵。

运输工具的行程依其所经过地点的顺序不同来确认。

0- K- 0这一行程表示始于配送中心，送货给客户后返回到配送中心。

节约S(K, M)表示将两个行程 0-K- 0、 0 - M - 0合成为一个行程0-K - M - 0后而节约的距离，节约距离的计算(其中 K, M的取值范围同式1)公式，见式2,节约方阵表见表1。

SK,M 4Dist0,K Dist 0,M - Dist K, M (2)表1节约方阵表客户A 客户B•- 客户1••- 客户N客户A S(A, A)客户B S(B, A) S(B , B)客户1 S(I, A) S(I , B) S(I, I)客户N S(N, A) S(N, B) S(N, I) •S(N, N)(3)将客户划归不同运输车辆⑴将客户划归到不同运输线路的运输车辆，其目标是在完成送货任务的同时使总的节约最大化。

划分步骤：先把每一客户划分到各自独立的运输线路中，然后不断把已有线路与剩下的某点进行合并。

合并优先权按照两条线路的节约距离大小加以确定，即节约越大，优先权越高。

合并可行性规则是指两条运输线路上的运输总量不超过货车的最大载重量。

每一辆车的合并过程持续到合并不可行为止（即合并运货量超过车辆的最大载重量），然后进行另一辆车的合并，直到所有的客户订货量都被划归到相应的运输车辆中。

（4）排定车辆的初始送货线路⑴排定送货线路就是确定每一辆车为客户送货的先后顺序，使车辆的以运输行程代表的运输成本最小化，排定车辆的初始送货线路方法主要有三种：最远插入法、最近插入法和最近邻居法。

本文采用最远插入法，其基本原理为：以配送中心为运输线路初始点，以规划到同一车辆的尚未纳入运输线路的客户点为集合，分别测算出集合中的每一点插入到已有线路的任何位置（起始点除外）后得到的线路长度的增加值，从中选出最小值，即求得该点插入后对已有线路原有长度的最小增加值；然后把集合里所有点的最小增加值进行比较，选取其中的最大值，并将该值对应的客户点纳入已有线路，得到一个新的行程。

重复进行这一过程，直到所有属于该线路的客户点全部被纳入为止。

因为距离当前线路最远的客户被一一纳入，因此这种方法被称为最远插入法。

（5）优化初始送货线路在运用最远插入法、最近插入法或最近邻居法得到某种初始送货线路后，可以运用二分法或三分法对其进行改进，从而使运输行程变短，即运输成本变小。

实际上，使用最远插入法和最近插入法（与最远插入法相反，总是把距离当前线路最近的客户纳入）得到的初始送货线路无需再进行路线改进，因为采用这两种方法得到的送货路线已经是最优路线[1]。

但是，如果采用最近邻居法，则需要采用二分法或三分法改进得到最优送货路线。

3实例某公司配送中心（DC）于某天上午收到来自12个不同客户的订单。

配送中心及每个客户的位置坐标和订货量，见表2。

该中心共有4辆卡车，每辆卡车的最大载重量是225单位（1单位=0.1吨），采用节约矩阵法确定每辆卡车的送货客户及送货线路。

表2 客户坐标及订货量X坐标Y坐标订货量配送中心-12 0 74顾客1 -5 6 55顾客2 -15 7 68顾客3 -12 9 109顾客4 -3 15 81顾客5 0 20 41顾客6 2 17 74顾客7 4 7 52顾客8 6 1 80顾客9 6 15 40顾客10 7 20 103顾客11 9 7 75顾客12 -12 0 74 解：①运用式1确定的距离方阵，见表 3。

表3距离方阵DC 1 2 3 4 5 6 7 8 9 10 11 12 DC 01 12 02 8 9 03 17 8 10 04 15 9 8 4 05 15 17 9 14 11 06 20 23 15 20 16 6 07 17 22 13 20 16 5 4 08 8 17 9 19 16 11 14 10 09 6 18 12 22 20 17 20 16 6 010 16 23 14 22 19 9 8 4 8 14 011 21 28 18 26 22 11 7 6 13 19 5 012 11 22 14 24 21 14 16 12 5 7 9 13 0②运用式2确定的节约方阵，见表 4。

表4节约方阵1 2 3 4 5 6 7 8 9 10 11 121 02 11 03 21 15 04 18 15 28 05 10 14 18 19 06 9 13 17 19 29 07 7 12 14 16 27 33 08 3 7 6 12 12 14 15 09 0 2 1 1 4 6 7 8 010 5 10 11 12 21 28 29 16 8 011 5 11 12 14 25 34 32 16 8 33 012 1 5 4 5 12 15 16 14 10 18 19 0③将客户划归不同运输车辆。

由表 4 可知，最大的节约来自客户 6 和 11，节约量为 34，两者总运量为 144，小于 225，因此将 6 和 11 合并。

与 6 或 11 相关的下一个最大的节约是 6 和 7，节约量为 33，三者总运量为 218，小于货车的最大载重量 225，因此将 11、7、6 合并。

与 11、7、6 相关的最大节约为 10 和 11，节约量为 33，四者总运量为 287，大于 225 ，合并不可行，停止本次合并，从而将客户 6、 7和 11划归到第一条线路。

排除客户 11、 6、 7。

接下来最大的节约来自 3和 4，节约量为 28，两者总运量为 177，小于货车的最大载重量225，因此将 3 和 4 合并。

与 3 和 4 相关的最大节约来自 3 和 1，节约量为 21，三者总运量为 251，大于 225，合并不可行。

与 3 和 4 相关的最大节约来自 4 和 5，节约量为 19 ，三者总运量为 258，大于 225，合并不可行。

与 3 和4 相关的最大节约来自 2 和 3，节约量为 15，三者总运量为 232，大于 225，合并不可行。

与 3 和 4 相关的最大节约来自 4 和 10，节约量为 12，三者总运量为 246，大于 225，合并不可行。

与3和 4相关的最大节约来自 4和 8，节约量为 12，三者总运量为 229，大于 225，合并不可行，从而将客户 3 和 7 划归到第二条线路。

排除客户 3、4。

接下来最大的节约来自 5和 10，节约量为 21，两者总运量为 150，小于货车的最大载重量225，因此 5和 10合并。

与 5和 10相关的最大节约来自 10和12，节约量为 18，三者总运量为 225，恰好为货车的最大载重量，合并可行，从而将客户5、10和 12划归到第三条线路。

排除客户 5、10 和 12。

接下来最大的节约来自 1 和 2，节约量为 11，两者总运量为 129，小于货车的最大载重量 225，因此 1 和 2 合并。

剩下客户 8 和 9，加入客户 8，三者总运量为 181，合并可行。

加入客户 9，四者总运量为 221，合并可行，从而将客户 1、2、8和 9 划归到第四条线路。