1、 1 毕业论文 （ 设计 ） 文献综述 物流管理 改进节约里程法在物流配送中的应用研究 物流配送路径优化问题最早是由 Dantzig 和 Ramser 于 1959 年首次提出，自 此，很快引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家与运输计划制定者和管理者的极大重视，成为运筹学与组合优化领域的前沿与研究热点问题。各学科专家对该问题进行了大量的理论研究及实验分析，取得了很大的进展。 节约里程法是基于 1964 年由 Clarke & Wright 首次提出的一种用于解决车辆路径优化 VRP 问题的著名的启发式方 法，用该方法虽然不一定能求得物流配送车辆路径优
2、化问题的精确最优解，且有时易受实际环境因素的影响而使计算结果无法适应实际应用情况，但相对而言仍然可以高效地得到问题的近似最优解。具有计算步骤简单，计算速度快，且易于考虑各种实际问题并将重要的实际变量纳入计算模型的优点，应用前景十分广阔。基于这样的研究现状，我们试着对节约里程法的历史发展、前人的研究成果进行归纳，并剖析其理论核心，力求能够归纳总结出节约里程法实际应用中存在的问题，从而提出切合实际的应用改进方案，使其有效应用于物流配送规划。 本文献综述首先从节约里程 法的概念及发展历程入手，其次介绍节约里程法的优缺点，进行节约里程法改进的必要性分析，最后提出节约里程法的改进措施。 1 节约里程法的
3、相关概念及发展历程 节约里程法由英国学者 G.Clarke & J.W.Wright于 1964年在 Scheduling of vehicles from a central depot to a number of delivery points一文中首先提出的一种迭代算法 。 当一 个配送中心向多个客户点进行共同送货，且在一条配送线路上的所有客户的需求总量不得大于该运输车辆的额定载重量时，由这辆车配装所有客户需求的货物，按照一条预先设计好的最佳路线依次将货物送到每一客户中，这样既可保证将货物按照客户的要求及时送交，同时亦能节约行驶里程，缩短整个配送2 的送货时间，节约配送的费用，是解决车
4、辆路径问题的成熟的方法。它考虑了对车辆路径问题的理论影响，根据配送中心的运输能力及其到各客户之间的距离和各客户之间的相对距离来制定配送线路，使总的配送车辆吨公里数达到或接近最小的配送方案。它的核心思想是在车 辆载重能力范围内，依照节约里程大小的次序将 运输问题中的若干配送线路合并为一个配送线路，每次使合并后的总运输距离减小的幅度最大，直到达到单个运输车辆的装载限制时，再进行下一辆车的优化。此方法既适合手算也适合通过计算机建模实验计算。 1997年 9月， Jens Lysgaard在 Clarke & Wrights Savings Algorithm一文中简要得阐述了克拉克和 莱特 所提出的
5、节约里程法，并证明了该方法在实际案例中 的运用。 1999 年， Jesper Larsen 在 Parallelization of the Vehicle Routing Problem with Time Windows一文中提出了平行优化法（ parallel algorithm） ， 研究带时间窗口的车辆路径问题（ VRPTW），将 VRPTW中的问题分为主要问题（准确抵达客户）及次要问题（运力和时间窗），目的在于加快配送时间，减少成本，求得最优解。 郑静，程幼明（ 2010）在基于时间约束的节约里程法配送路径优化研究一文中提出基于时间约束的节约里程 法配送路径优化，同时考虑了物流配
6、送的运行距离和时间因素，使双方面都达到合理化 ,在保证交货期的同时降低了物流配送成本，也提高了车辆的工作效率，使企业和客户达到双赢的效果。 2006年， Ann Melissa Campbell在 The vehicle routing problem with demand range 一文中提出和设定车辆路径问题的需求范围，在传统的车辆路径方面是一个新的变化。在有需求范围的车辆路径问题中，客户的需求是在一个范围内灵活变化，通过将这种变化来解决车辆路径优化问题，使车辆配送总成本的 下降具备巨大的潜力。 2 节约里程法相关概念分析 韩冰源 ,肖生灵（ 2005）在配送中心线路优化方法的探讨一文
7、中认为物流配送路线优化方案的优劣 ,取决于数学模型与现实情况的符合程度以及对数学模型求解的精确程度这两个因素的共同作用。若追求数学模型与现实状况完全符合，则所建数学模型必定非常复杂，无法求出最优解；若数学模型建得太简单，虽然易解，但会与现实情况偏差太大 ,无实际意义。因此，找到二者的临界点，才能搜索到最优配送路线。并指出每种搜索方法都有其自身的适用范围和局限性，应针对配3 送优化问题的具体类型 ,寻找最适合 的求解方法，搜索最优配送路线。否则，即便找到最优解也不会是全局最优解，甚至是无效解，故在迭代计算过程中可忽略影响小的约束条件以简化搜索过程，提高配送路线的优化效率。朱永升，韩伯棠，夏平，李
8、振键（ 2004）在交通限制条件下城市物流配送路线优化选择一文中认为，对于城市配送而言 。 由于受交通堵塞和各种交通管制的影响，导致配送路径寻优更具复杂性，作者通过对具有动态的交通堵塞和交通拥挤限制信息及静态禁止通行等限制信息的实际配送网络的描述 。 提出解决两种限制情况下配送网络寻优的方法，通过对影响权重的各种因素的深入剖析， 建立基于成本的权重模型，并提出将交通限制条件下城市物流配 送 网络转化成无限制的有向图网络 。 运用 Dijkstra 算法对其寻优。徐剑，牟燕妮，张尹聪，王中颖（ 2006）在物流配送车辆调度优化方法比较研究中分析认为，节约里程法作为 VRTPW 的传统启发算法，优
9、点是提高了车辆的利用率，可以解决大规模问题，但节约里程法所得出的解是较优的可行解，不一定是最优解。 3 节约里程法的改进措施 在基于节约法在优化配送路线的研究一文中，姜福川，吕传红（ 2003）认为节约里程法是可改进的，在配送路线选择决策时，通常考虑较优的 原则。提出的改进建议为： (l)深入了解客户，加强与客户的信息交流。 (2)对客户需求的时间变化进行分类，以增加配送的灵活性。 (3)路线决策过程中实施多路线同步决策。 (4)节约法的实施过程，要综合考虑路程长短和时间因素。 (5)在优化配送过程中，不但要优化配送路线和配送过程，还要提高配送过程其他环节的管理水平和设备的现代化水平 。轩 华
10、（ 2010）在基于改进节约法的配送路线优化问题研究一文中提出改进的节约里程法来解决考虑实际路况的配送路线优化问题，首先通过对配送线路本身的线路等级进行线路划分，得到相应等级线路的 转化系数，然后利用转化系数和实际距离的乘积确定配送点间的有效距离，进而利用改进节约法确定最佳配送线路。这使得配送线路优化分析更具有实际意义。 经过对材料的分析总结，我们可以发现节约里程法尚还处于发展阶段，有许多需要完善的地方，使其更有效得服务于实际问题的解决 。 相信只要对此方法进行持续得改进，不断得将实际变量融入到该优化方法中，定会有相当大的理论突破。本4 文出于此目的，针对节约里程法在实际应用方面的欠缺，通过分
11、析影响模型最优解的影响因素，将这些因素统一转化为一类可衡量的数量化指标，根据对最 优解影响的大小将其转化为权重系数，并将相应的权重系数和节约里程法结合起来进行相应的分析改进和完善。权重系数是表示某一指标项在指标项系统中的重要程度，它表示在其它指标项不变的情况下，这一指标项的变化，对结果的影响。这种思想是对车辆配送路径优化的一种 有益的 尝试。通过对于现有的节约里程法进行分析改进，由此可见改进的节约里程法具有相当大的发展前景，把它运用于物流配送优化问题中，可以达到降低配送成本，提高配送服务质量，最大化利用企业资源，提高企业效益，并使理论模型更具实践性的目的 。 为节约里程法在区域配送领域的深入应
12、用的实现打下基础。 而 高效的配送将加快物资流动，降低运输成本，改善客户服务，对区域经济的发展起到推动的作用，增强区域内及区域之间社会经济的有机联系。 参考文献 1 韩世莲 . 带时间窗的多目标配送线路选择问题的目标规划模型 J.物流技术， 2005（ 1） . 2 姜福川 . 吕传红 . 基于节约法在优化配送路线的研究 J.辽宁工程技术大学学报， 2003（ 5） . 3 张颖敏 . 基于节约里程法的物流配送线路优化与改进研究 J.物流科技， 2011（ 4） . 4 赵常朋 . 基于客户满意度的物流配送中心路线优化 研究 D.重庆：重庆交通大学， 2009. 5 轩华 . 基于改进节约法的
13、配送路线优化问题研究 J.物流技术， 2010（ 12） . 6 郑 静，程幼明 . 基于时间约束的节约里程法配送路径优化研究 J.物流技术， 2010（ 10） . 7 刘浩 . 基于最短路径算法的物流配送方案优化研究 D.山东：山东大学， 2006. 8 朱永升 ， 韩伯棠 . 交通限制条件下城市物流配送路线优化选择 J.武汉理工大学学报，2004（ 3） . 9 刘凯 . 现代物流技术基础 M，清华大学出版社，北京交通大学出版社， 2004. 10 郑克俊 . 仓储与配送管理 M，科学出版社 ， 2010. 11 韩世莲 . 带时间窗的多目标配送线路选择问题的目标规划模型 J. 物流技术
14、， 2008（ 1） . 12 蒋长兵，胡立夏 . 物流系统工程 M.电子工业出版社， 2011. 13 林强 . 物流工程 M.清华大学出版社 ,2009. 14 梁金萍 . 运输管理 M.机械王业出版社， 2009. 15 李永生，郑文玲 . 仓储与配送管理 M.机械工业出版社， 2009. 16 李如姣 . 节约里程法在某物流公司配送中心的 实际运用 J.科技资讯， 2008(28). 5 17 (日 )中田信哉著，陶庭义译 . 物流配送 M 海天出版社 ， 2001. 18 钱芝网 . 配送管理实务 M.中国时代经济出版社， 2007 19 梁金萍 . 运输管理 M.机械王 业出版社，
15、 2009 21 Marco Dorigo. Ant system: optimization by a colony of cooperating agentsD.1996. 22 G.Clarke & J.W.Wright. Scheduling of vehicles from a central depot to a number of delivery pointsD.1962. 23 Jesper Larsen. Parallelization of the Vehicle Routing Problem with Time WindowsD. 1999. 24 Ann Melissa Campbell. The vehicle routing problem with demand rangeJ. Springer Science Business Media, LLC.2006.
