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

1基于节约矩阵法的配送中心送货路线优化问题研究[摘要]针对物流配送中心送货路线优化问题的各种算法，本文选择适合我国物流业发展现状的节约矩阵法，从而为客户提供个性化服务。然后，详细介绍节约矩阵法的基本思路及求解步骤，并将其用于一个现实问题的求解。求解结果表明节约矩阵法可以简单有效的对我国物流企业送货路线进行优化。[关键词]送货路线；节约矩阵法；优化；最远插入法Studyoftheoptimizationofdistributionroutingproblembasedontheeconomy-matrixmethodAbstract：Basedonvariousalgorithmsforlogisticsdistributioncenterdeliveryrouteoptimizationproblem,thispaperchoosesthesavingmatrixmethodsuitableforthecurrentdevelopmentofChina'slogisticsindustry,thusprovidingcustomerswithpersonalizedservice.Thenthispapergivesbasicprincipleandsolutionstepsofthismethodindetailsandusedittosolvearealproblem.TheresultsshowedthatthismethodcanbeasimpleandeffectivewaytooptimizedeliveryroutesforChina'slogisticsenterprisesKeywords：Distributionrouting;Saving-matrixmethod;Optimization;Furthestinsertmethod1引言物流配送是指按照用户订货要求，在配送中心进行分货和配货，然后将货物及时送交收货人，其当前趋势是朝着小批量、多品种、多批次的即时送货方向发展，及时满足客户的个性化需求[1]。影响物流配送体系的因素众多，其中送货线路的规划是非常重要的运营决策，其对加快配送速度、提高物流服务质量和降低配送成本有重要影响。然而，由于我国物流业起步晚，发展速度慢、物流行业基础设施不足且技术落后，当前我国物流企业基本处于小、少、弱、散的状况[2]。此外，目前我国大部分自营物流配送中心的运营现状是：送货业务量小且终端客户多；缺乏合理的送货规划；缺乏送货线路优化软件；物流规划专业人才缺乏等。由于这些问题的存在，我国物流企业尤其是中小物流企业送货成本较高。考虑到中小物流企业是构成我国物流行业的主体，且今后较长时间内我国物流业仍将以中小物流企业为主体，因而我国物流行业迫切需要降低送货成本，因而找到一种适合我国物流发展现状而且简单实用的送货线路优化方法具有重要的现实意义。本文主要关注从物流配送中心调用多辆车满足向各零售点的送货服务，即通过为多辆车分2配客户并分别制定各辆车的合理行驶线路的多车辆路径问题VRP（VehicleRoutingProblem）优化算法的实现，从而快速且经济的将货物送达用户。关于多车辆路径问题算法的研究，国内外学者提出了很多方法，如遗传算法、禁忌搜索算法、模拟退火算法等[3]。这些算法能够解决复杂的配送路线优化问题，但存在模型复杂、求解难、运算量大的缺点，由此限制了它们在我国物流企业中的推广应用[4]。本文提出的节约矩阵法，已知条件较少、操作方法简单、优化效果良好，而且可以很容易的根据送货时间限制和其他限制进行修改。采用节约矩阵法决定哪些货车为哪些客户送货，以及确定每辆货车的最优送货路线，适用于我国现有的中、小型物流企业[5]。本文运用节约矩阵法进行送货线路优化时，优化目标为：确定每一个参与送货的车辆该运多少货物，走什么线路，送货到哪几个零售点），从而使送货总费用最小[6]。已知条件为：①配送中心的位置坐标以及拥有的车辆数；②每个客户的位置坐标和订货量。限制条件为：①车辆的载重能力约束；②每个客户点只能被一辆车访问。实际中可能还存在客户对送货时间的约束，即时间窗问题），本文暂且不涉及该约束。2节约矩阵法由于交通运输是一个网状结构，因此可以把分布于这个网状结构中的配送中心和用户假定成一个个数学上的点，把配送中心与用户以及用户与用户之间的运输线路假定成一条条的线。那么，送货线路优化问题就可转化为在一个以许多“点”和“线”组成的“图”中寻找各点与点间的最佳路径问题。设配送中心为O点，位置坐标为（xO，yO）；订货客户为A、B、……N，位置坐标分别为（xA，yA）、（xB，yB）……（xN，yN）。节约矩阵法主要步骤如下：（1）确认距离方阵[1]确认距离方阵是要确认任何将要经过的两个地点之间的距离。坐标系中任意两点之间的距离公式，见式1。22),(MKMKyyxxMKDist（1）式中，K、M都可以取O和A～N之间的任意点。这样，就构造出一个N＋1阶的距离方阵。由于两点之间距离的对等关系，亦即Dist(K，M)=Dist(M，K)，因而该距离方阵是一个对称阵。因此可以将其简化为上三角或下三角阵。（2）确认节约方阵[1]节约方阵是指将两个客户的订货放在一辆货车上联合运送时节约的累积。节约可以按照距离、时间或者货币来计量，本文按照距离建立节约矩阵。3运输工具的行程依其所经过地点的顺序不同来确认。O－K－O这一行程表示始于配送中心，送货给客户后返回到配送中心。节约S(K，M)表示将两个行程O－K－O、O－M－O合成为一个行程O－K－M－O后而节约的距离，节约距离的计算（其中K，M的取值范围同式1）公式，见式2，节约方阵表见表1。MKDistMODistKODistMKS,,,,（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]将客户划归到不同运输线路的运输车辆，其目标是在完成送货任务的同时使总的节约最大化。划分步骤：先把每一客户划分到各自独立的运输线路中，然后不断把已有线路与剩下的某点进行合并。合并优先权按照两条线路的节约距离大小加以确定，即节约越大，优先权越高。合并可行性规则是指两条运输线路上的运输总量不超过货车的最大载重量。每一辆车的合并过程持续到合并不可行为止（即合并运货量超过车辆的最大载重量），然后进行另一辆车的合并，直到所有的客户订货量都被划归到相应的运输车辆中。（4）排定车辆的初始送货线路[1]排定送货线路就是确定每一辆车为客户送货的先后顺序，使车辆的以运输行程代表的运输成本最小化，排定车辆的初始送货线路方法主要有三种：最远插入法、最近插入法和最近邻居法。本文采用最远插入法，其基本原理为：以配送中心为运输线路初始点，以规划到同一车辆的尚未纳入运输线路的客户点为集合，分别测算出集合中的每一点插入到已有线路的任何位置（起始点除外）后得到的线路长度的增加值，从中选出最小值，即求得该点插入后对已有线路原有长度的最小增加值；然后把集合里所有点的最小增加值进行比较，选取其中的最大值，并将该值对应的客户点纳入已有线路，得到一个新的行程。重复进行这一过程，直到所有属于该线路的客户点全部被纳入为止。因为距离当前线路最远的客户被一一纳入，因此这种方法被称为最远插入法。（5）优化初始送货线路4在运用最远插入法、最近插入法或最近邻居法得到某种初始送货线路后，可以运用二分法或三分法对其进行改进，从而使运输行程变短，即运输成本变小。实际上，使用最远插入法和最近插入法（与最远插入法相反，总是把距离当前线路最近的客户纳入）得到的初始送货线路无需再进行路线改进，因为采用这两种方法得到的送货路线已经是最优路线[1]。但是，如果采用最近邻居法，则需要采用二分法或三分法改进得到最优送货路线。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距离方阵DC123456789101112DC01120289031781004159840515179141106202315201660717221320165408817919161114100961812222017201660510162314221998481401121281826221176131950121122142421141612579130②运用式2确定的节约方阵，见表4。表4节约方阵123456789101112102110321150418152805101418190691317192907712141627330837612121415090211467801051011122128291680115111214253432168330121545121516141018190③将客户划归不同运输车辆。由表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划归到第三6条线路。排除客户5、10和12。接下来最大的节约来自1和2，节约量为11，两者总运量为129，小于货车的最大载重量225，因此1和2合并。剩下客户8和9，加入客户8，三者总运量为181，合并可行。加入客户9，四者总运量为221，合并可行，从而将客户1、2、8和9划归到第四条线路。④排定每辆货车的最优送货线路。本例采用最远插入法排定初始送货线路，因而排定的初始送货线路也是最优线路。对于第一组{6，7，11}，最初的行程只包括配送中心，长度为0。纳入客户11，长度增加了42；纳入客户6，长度增加了40；纳入客户7，长度增加了34；运用最远插入法，首先纳入客户11得到一条新的线路（配送中、客户11、配送中心），长度为42。下一步再纳入客户6，使行程长度增加至48；纳入客户7，使行程长度增加至44。因此，纳入客户6，得到了长度为48的一条新线路（配送中心、客户11、客户6、配送