《基于节约矩阵法的配送中心送货路线优化问题研究》由会员分享，可在线阅读，更多相关《基于节约矩阵法的配送中心送货路线优化问题研究（7页珍藏版）》请在金锄头文库上搜索。
1、基于节约矩阵法的配送中心送货路线优化问题研究摘要针对物流配送中心送货路线优化问题的各种算法，本文选择适合我国物流业发展现状的节约矩阵法，从而为客户提供个性化服务。然后，详细介绍节约矩阵法的基本思路及求解步骤，并将其用于一个现实问题的求解。求解结果表明节约矩阵法可以简单有效的对我国物流企业送货路线进行优化。关键词送货路线；节约矩阵法；优化；最远插入法Study of the optimization of distribution routing problem based on the economy-matrix methodAbstract：Based on various algorit
2、hms for logistics distribution center delivery route optimization problem, this paper chooses the saving matrix method suitable for the current development of Chinas logistics industry , thus providing customers with personalized service. Then this paper gives basic principle and solution steps of t
3、his method in details and used it to solve a real problem. The results showed that this method can be a simple and effective way to optimize delivery routes for Chinas logistics enterprisesKeywords： Distribution routing; Saving-matrix method; Optimization; Furthest insert method1 引言物流配送是指按照用户订货要求，在配
4、送中心进行分货和配货，然后将货物及时送交收货人，其当前趋势是朝着小批量、多品种、多批次的即时送货方向发展，及时满足客户的个性化需求1。影响物流配送体系的因素众多，其中送货线路的规划是非常重要的运营决策，其对加快配送速度、提高物流服务质量和降低配送成本有重要影响。然而，由于我国物流业起步晚，发展速度慢、物流行业基础设施不足且技术落后，当前我国物流企业基本处于小、少、弱、散的状况2。此外，目前我国大部分自营物流配送中心的运营现状是：送货业务量小且终端客户多；缺乏合理的送货规划；缺乏送货线路优化软件；物流规划专业人才缺乏等。由于这些问题的存在，我国物流企业尤其是中小物流企业送货成本较高。考虑到中小物
5、流企业是构成我国物流行业的主体，且今后较长时间内我国物流业仍将以中小物流企业为主体，因而我国物流行业迫切需要降低送货成本，因而找到一种适合我国物流发展现状而且简单实用的送货线路优化方法具有重要的现实意义。本文主要关注从物流配送中心调用多辆车满足向各零售点的送货服务，即通过为多辆车分配客户并分别制定各辆车的合理行驶线路的多车辆路径问题VRP（Vehicle Routing Problem）优化算法的实现，从而快速且经济的将货物送达用户。关于多车辆路径问题算法的研究，国内外学者提出了很多方法，如遗传算法、禁忌搜索算法、模拟退火算法等3。这些算法能够解决复杂的配送路线优化问题，但存在模型复杂、求解难
6、、运算量大的缺点，由此限制了它们在我国物流企业中的推广应用4。本文提出的节约矩阵法，已知条件较少、操作方法简单、优化效果良好，而且可以很容易的根据送货时间限制和其他限制进行修改。采用节约矩阵法决定哪些货车为哪些客户送货，以及确定每辆货车的最优送货路线，适用于我国现有的中、小型物流企业5。本文运用节约矩阵法进行送货线路优化时，优化目标为：确定每一个参与送货的车辆该运多少货物，走什么线路，送货到哪几个零售点），从而使送货总费用最小6。已知条件为：配送中心的位置坐标以及拥有的车辆数；每个客户的位置坐标和订货量。限制条件为：车辆的载重能力约束；每个客户点只能被一辆车访问。实际中可能还存在客户对送货时间
7、的约束，即时间窗问题），本文暂且不涉及该约束。2 节约矩阵法由于交通运输是一个网状结构，因此可以把分布于这个网状结构中的配送中心和用户假定成一个个数学上的点，把配送中心与用户以及用户与用户之间的运输线路假定成一条条的线。那么，送货线路优化问题就可转化为在一个以许多“点”和“线”组成的“图”中寻找各点与点间的最佳路径问题。设配送中心为O点，位置坐标为（xO，yO）；订货客户为A、B、N，位置坐标分别为（xA，yA）、（xB，yB）（xN，yN）。节约矩阵法主要步骤如下：（1）确认距离方阵1确认距离方阵是要确认任何将要经过的两个地点之间的距离。坐标系中任意两点之间的距离公式，见式1。 （1）式中，
8、K、M都可以取O和AN之间的任意点。这样，就构造出一个N1阶的距离方阵。由于两点之间距离的对等关系，亦即Dist(K，M)= Dist(M，K)，因而该距离方阵是一个对称阵。因此可以将其简化为上三角或下三角阵。（2）确认节约方阵1节约方阵是指将两个客户的订货放在一辆货车上联合运送时节约的累积。节约可以按照距离、时间或者货币来计量，本文按照距离建立节约矩阵。运输工具的行程依其所经过地点的顺序不同来确认。OKO这一行程表示始于配送中心，送货给客户后返回到配送中心。节约S(K，M)表示将两个行程OKO、 OMO合成为一个行程OKMO后而节约的距离，节约距离的计算（其中K，M的取值范围同式1）公式，见
9、式2，节约方阵表见表1。 （2） 表1节约方阵表 客户A客户B客户I客户N客户AS(A，A)客户BS(B，A)S(B，B)客户IS(I，A)S(I，B)S(I，I)客户NS(N，A)S(N，B)S(N，I)S(N，N)（3）将客户划归不同运输车辆 1将客户划归到不同运输线路的运输车辆，其目标是在完成送货任务的同时使总的节约最大化。划分步骤：先把每一客户划分到各自独立的运输线路中，然后不断把已有线路与剩下的某点进行合并。合并优先权按照两条线路的节约距离大小加以确定，即节约越大，优先权越高。合并可行性规则是指两条运输线路上的运输总量不超过货车的最大载重量。每一辆车的合并过程持续到合并不可行为止（即
10、合并运货量超过车辆的最大载重量），然后进行另一辆车的合并，直到所有的客户订货量都被划归到相应的运输车辆中。（4）排定车辆的初始送货线路 1排定送货线路就是确定每一辆车为客户送货的先后顺序，使车辆的以运输行程代表的运输成本最小化，排定车辆的初始送货线路方法主要有三种：最远插入法、最近插入法和最近邻居法。本文采用最远插入法，其基本原理为：以配送中心为运输线路初始点，以规划到同一车辆的尚未纳入运输线路的客户点为集合，分别测算出集合中的每一点插入到已有线路的任何位置（起始点除外）后得到的线路长度的增加值，从中选出最小值，即求得该点插入后对已有线路原有长度的最小增加值；然后把集合里所有点的最小增加值进行
11、比较，选取其中的最大值，并将该值对应的客户点纳入已有线路，得到一个新的行程。重复进行这一过程，直到所有属于该线路的客户点全部被纳入为止。因为距离当前线路最远的客户被一一纳入，因此这种方法被称为最远插入法。（5）优化初始送货线路 在运用最远插入法、最近插入法或最近邻居法得到某种初始送货线路后，可以运用二分法或三分法对其进行改进，从而使运输行程变短，即运输成本变小。实际上，使用最远插入法和最近插入法（与最远插入法相反，总是把距离当前线路最近的客户纳入）得到的初始送货线路无需再进行路线改进，因为采用这两种方法得到的送货路线已经是最优路线1。但是，如果采用最近邻居法，则需要采用二分法或三分法改进得到最
12、优送货路线。3 实例某公司配送中心（DC）于某天上午收到来自12个不同客户的订单。配送中心及每个客户的位置坐标和订货量，见表2。该中心共有4辆卡车，每辆卡车的最大载重量是225单位（1单位0.1吨），采用节约矩阵法确定每辆卡车的送货客户及送货线路。 表2 客户坐标及订货量 X坐标Y坐标订货量配送中心-12074顾客1-5655顾客2-15768顾客3-129109顾客4-31581顾客502041顾客621774顾客74752顾客86180顾客961540顾客10720103顾客119775顾客12-12074解：运用式1确定的距离方阵，见表3。表3 距离方阵DC123456789101112
13、DC0112028903178100415984051517914110620231520166071722132016540881791916111410096181222201720166010162314221998481401121281826221176131950121122142421141612579130运用式2确定的节约方阵，见表4。 表4 节约方阵 12345678910111210211032115041815280510141819069131719290771214162733083761212141509021146780105101112212829168011
