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

基于节约矩阵法的配送中心送货路线优化问题研究 [摘要]针对物流配送中心送货路线优化问题的各种算法，本文选择适合我国物流业发展现状的节约矩阵法，从而为客户提供个性化服务。然后，详细介绍节约矩阵法的基本思路及求解步骤，并将其用于一个现实问题的求解。求解结果表明节约矩阵法可以简单有效的对我国物流企业送货路线进行优化。 [关键词]送货路线；节约矩阵法；优化；最远插入法 Study of the optimization of distribution routing problem based on the economy-matrix method Abstract：Based on various algorithms 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 this 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 enterprises Keywords： Distribution routing; Saving-matrix method; Optimization; Furthest insert method 1 引言 物流配送是指按照用户订货要求，在配送中心进行分货和配货，然后将货物及时送交收货人，其当前趋势是朝着小批量、多品种、多批次的即时送货方向发展，及时满足客户的个性化需求[1]。影响物流配送体系的因素众多，其中送货线路的规划是非常重要的运营决策，其对加快配送速度、提高物流服务质量和降低配送成本有重要影响。然而，由于我国物流业起步晚，发展速度慢、物流行业基础设施不足且技术落后，当前我国物流企业基本处于小、少、弱、散的状况[2]。此外，目前我国大部分自营物流配送中心的运营现状是：送货业务量小且终端客户多；缺乏合理的送货规划；缺乏送货线路优化软件；物流规划专业人才缺乏等。由于这些问题的存在，我国物流企业尤其是中小物流企业送货成本较高。考虑到中小物流企业是构成我国物流行业的主体，且今后较长时间内我国物流业仍将以中小物流企业为主体，因而我国物流行业迫切需要降低送货成本，因而找到一种适合我国物流发展现状而且简单实用的送货线路优化方法具有重要的现实意义。 本文主要关注从物流配送中心调用多辆车满足向各零售点的送货服务，即通过为多辆车分配客户并分别制定各辆车的合理行驶线路的多车辆路径问题VRP（Vehicle Routing Problem）优化算法的实现，从而快速且经济的将货物送达用户。关于多车辆路径问题算法的研究，国内外学者提出了很多方法，如遗传算法、禁忌搜索算法、模拟退火算法等[3]。这些算法能够解决复杂的配送路线优化问题，但存在模型复杂、求解难、运算量大的缺点，由此限制了它们在我国物流企业中的推广应用[4]。本文提出的节约矩阵法，已知条件较少、操作方法简单、优化效果良好，而且可以很容易的根据送货时间限制和其他限制进行修改。采用节约矩阵法决定哪些货车为哪些客户送货，以及确定每辆货车的最优送货路线，适用于我国现有的中、小型物流企业[5]。本文运用节约矩阵法进行送货线路优化时，优化目标为：确定每一个参与送货的车辆该运多少货物，走什么线路，送货到哪几个零售点），从而使送货总费用最小[6]。已知条件为：①配送中心的位置坐标以及拥有的车辆数；②每个客户的位置坐标和订货量。限制条件为：①车辆的载重能力约束；②每个客户点只能被一辆车访问。实际中可能还存在客户对送货时间的约束，即时间窗问题），本文暂且不涉及该约束。 2 节约矩阵法 由于交通运输是一个网状结构，因此可以把分布于这个网状结构中的配送中心和用户假定成一个个数学上的点，把配送中心与用户以及用户与用户之间的运输线路假定成一条条的线。那么，送货线路优化问题就可转化为在一个以许多“点”和“线”组成的“图”中寻找各点与点间的最佳路径问题。 设配送中心为O点