物流业节约矩阵法优化研究

当前我国物流企业基本处于小、少、弱、散的状况，迫切需要对物流配送中心送货线路合理规划。本文选择适合我国物流业当前现状的节约矩阵法，并将其用于解决一个现实问题，结果表明它能简明有效的优化我国物流企业送货线路。

一、引言

现代物流配送的趋势是朝着小批量、多品种、多批次的即时送货方向发展，及时满足客户个性化需求。影响物流配送体系因素众多，其中送货线路的规划是非常重要的决策因素。然而，由于我国物流业起步晚，发展速度慢，基本处于小、少、弱、散的状况，使得我国物流企业尤其是中小物流企业送货成本较高。因而我国物流行业迫切需要找到合适的送货线路优化方法来降低送货成本。

物流配送中心送货线路优化问题属于多车辆路径问题，主要关注通过为多辆运输工具分配客户并制定合理行驶线路，快速经济的将货物送达用户。

国内外学者提出了很多优化算法，如遗传算法、禁忌搜索算法、模拟退火算法等。这些算法存在模型复杂、求解难、运算量大的缺点，限制了其在我国物流业的推广应用。本文提出的节约矩阵法，已知条件较少、操作方法简单、优化效果良好，且对多重限制的问题同样适用。节约矩阵法的优化目标为：确定每一个参与送货的车辆该送货到哪几个零售点和制定其行程路线，使送货成本最小。已知条件为：配送中心位置坐标以及拥有的车辆数；客户位置坐标和订货量。限制条件为：车辆的载重能力；每个客户只能被一辆车访问；送货时间（即时间窗问题，本文暂不涉及该约束）。

二、节约矩阵法

设配送中心为O点，位置坐标为（xO，yO）；客户为A、B…N，位置坐标为（xA，yA）、（xB，yB）……（xN，yN），求解步骤如下：

第一，确定距离方阵。即确认任何将要经过的两个地点间的距离（式（1），且K、M取O和A～N间任意点），从而构造出距离方阵（N+1阶对称阵）。Dist（K，M）=■（1）。

第二汕头到六安物流，确定节约方阵。节约方阵是指将两个客户的订货放在一辆货车联合运送时节约的累积。O－K－O这一行程表示始于配送中心，送货给客户后返回配送中心。节约S（K，M）表示将两个行程O－K－O、O－M－O合并成一个行程O－K－M－O后节约的距离，节约距离计算（K，M取值同式1），见式（2），需要注意的是K等于M时节约距离为0。S（K，M）=Dist（O，K）+Dist（O，M）-Dist（K，M）（2）。

第三，将客户划归不同运输车辆。即先把每一客户划分到各自独立的运输线路中，然后不断把已有线路与剩下的某点进行合并。节约距离越大，则合并优先权越大。合并可行性规则指两条运输线路上运输总量不超过货车最大载重量，每一辆车合并过程持续到合并不可行为止。

第四，排定车辆的初始送货线路。主要方法有最远插入法、最近插入法和最近邻居法。本文采用最远插入法，即以配送中心为运输线路初始点，以规划到同一车辆的尚未纳入运输线路的客户点为集合，分别测算出每一点插入到已有线路的任何位置（起始点除外）后得到的线路长度的增加值，从中选出最小值。然后比较所有点的最小增加值，选取最大值，并将其对应的客户纳入已有线路，得到新行程。重复这一过程，直到所有属于该线路的客户全部被纳入为止。

第五，优化初始送货线路。一般采用二分法或三分法改进初始送货线路，使运输行程变短，运输成本变小。然而，使用最远插入法或最近插入法得到的初始线路无需再改进，已是最优线路。

三、实例

某公司配送中心（DC）于某天收到12个不同客户的订单，且DC位置坐标为（0，0），客户坐标分别为（-12，0）、（-5，6）、（-15，7）、（-12，9）、（-3，15）、（0，20）、（2，17）、（4，7）、（6，1）、（6，15）、（7，20）和（9，7）；订货量分别为74、55、68、109、81、41、74、52、80、40、103和75。

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

解：第一，先用式（1）计算距离方阵（略）。第二，由式（2）求出节约矩阵表，见表1。

表1 节约矩阵表

第三，将客户划归不同运输车辆。由表1知最大的节约来自客户6和11，节约量为34，总运量144，小于最大载重量225，将6和11合并；与6或11相关的下一个最大的节约是6和7，节约量33，总运量218，小于225，将11、7、6合并。最终，将6、7和11划归为第一条线路。排除11、6、7，继续采用此法，可将3和4划归第二条线路；再排除3和4，可以将5、10和12划归第三条线路；最后剩下1、2、8和9，韶关到六安物流总运量221，构成第四条线路。

第四，排定每辆卡车的最优送货线路。对于第一组{6，7，11}，最初的行程只包括配送中心，长度为0。纳入客户11，长度增加42；纳入客户6，长度增加40；纳入客户7，长度增加34；根据最远插入法，首先纳入11，得到线路{DC、11、DC}，长度42。然后纳入客户6，长度增至48；纳入客户7，长度增至44。因而纳入6，得到长度48的线路{DC、11、6、DC}。把剩下的客户7安排在6之后。至此，第一条最优线路为DC－11－6－7－DC，长度49，卡车载重量218。

采用此法可确定第2条最优线路为DC－3－4－DC，长度40，卡车载重量177；第3条为DC－10－5－12－DC，长度50，卡车载重量225；第4条为DC－1－8－2－9－DC，长度56，卡车载重量221。

四、结语

针对目前我国物流业存在的问题，本文提出用节约矩阵法对我国物流企业尤其是中小物流企业的配送中心送货线路进行优化。通过对实际应用问题的求解，可看出节约矩阵法操作简明且优化汕头到澳门物流效果良好，可以帮助我国物流企业降低送货成本，对物流企业送货线路的优化与决策具有一定的实用价值。

参 考 文 献

[1]Sunil Chopra，Peter Meindl．供应链管理－战略、规划与运营[M]．香港：社会科学文献出版社，2004：314～323

[2]李波，王海亮．对我国中小物流企业发展方向的思考[J]．物流技术．2008，27（6）：12～13

[3]方金城，张岐山．物流配送车辆路径问题算法研究[J]．徐州工程学院学报．2007，2（22）：84～88

[4]李炜．浅析国内物流国际物流发展[J]．企业导报．2010（7）：129

[5]陈晓伟，张悟移，耿继武．节约法在配送路线选择中的应用[J]．昆明理工大学学报．2003，28（4）：140～143