基于节约矩阵法的配送中心送货路线优化问题研究.doc
《基于节约矩阵法的配送中心送货路线优化问题研究.doc》由会员分享,可在线阅读,更多相关《基于节约矩阵法的配送中心送货路线优化问题研究.doc(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将客户划归到不同运输线路的运输车辆,其目标是在完成送货任务的同时使总的节约最大化。划分步骤:先把每一客户划分到各自独立的运输线路中,然后不断把已有线路与剩下的某点进行合并。合并优先权按照两条线路的节约距离大小加以确定,即节约越大,优先权越高。合并可行性规则是指两条运输线路上的运输总量不超过货车的最大载重量。每一辆车的合并过程持续到合并不可行为止(即
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 节约 矩阵 配送 中心 送货 路线 优化 问题 研究
链接地址:https://www.31doc.com/p-3315043.html