1、 1 毕业论文 （ 设计 ） 文献综述 物流管理 德清县红丰纸业有限公司物流配送线路优化研究 近年来，随着物流业的不断发展，配送在整个物流系统中的作用变得越来越重要。运输系统是配送系统中最重要的一个子系统，运输成本占整体物流成本的一半左右，所以降低物流成本主要要降低物流配送的运输成本，形成高效的配送体系，而这主要取决于车辆路线是否合理。合理的车辆路线可以降低运输成本，进而降低物流成本。 1 国内外研究现状 1.1 配送的定义 根据 GB T 18354 2006物流术语，配送的定义为：在经济合理区域范围内，根据客户要求 ，对物品进行拣选、加工、包装、分割、组配等作业，并按时送达指定地点的物流活
2、动。（乔烨， 2008） 物流配送是物流中的一个重要环节，它直接与消费者相连，是货物从物流结点送达收货人的过程。配送是在集货、配货的基础上，按货物种类、品种搭配、数量、时间等要求所进行的运送，是“配”和“送”的有机结合。 物流是企业的“第三利润源泉 “，处于末端物流的配送具有提高物流经济效益，优化、完善物流系统，改善服务，降低成本的功能，在物流系统中占有重要的地位。“配送”这个词来自于日语原词，日本工业标准 (ULS)物流用语中将配送定 义为：“将货物从物流据点送交给收货人。 按照国家质量技术监督局发布的中华人民共和国国家标准“物流术语”，其中关于配送的解释是这样的：在经济合理区域范围内，根据
3、用户的要求，对物品进行拣选、加工、包装、分割、组配等作业，并按时送达指定地点的物流活动。一般来说，配送一定是根据用户的要求，在物流中一种特殊的、综合的活动形式。它将商流与物流紧密结合起来，既包含了商流活动，也包含了物流活动中若干功能要素。 配送的英语原词为 Dilivery，但不能将它简单地理解为交货、运送。从配2 送活动活动的实施过程来看，配送包括两个方面 的活动：“配 “是对货物进行集中、分拣和组配，“送 “是以各种不同的方式将货物送达指定地点或用户手中。（王晓静， 2008） 1.2 配送路线优化研究意义 随着物流系统的集约化、一体化的发展，常将配送的各环节综合起来，其核心部分为配送车辆
4、的集货、货物配装及送货过程。进行配送系统的优化，主要就是配送车辆优化调度，包括集货路线优化、货物配装及送货路线优化，以及集货、货物配装等。对配送车辆进行优化调度，可以提高物流经济效益、实现物流科学化。（王晓静， 2008） 在配送运输中，由于配送用户多，城市交通路线又较复杂 ，如何组成最佳路线，如何使配装和配送路线有效搭配等，是配送运输的特点，也是难度较大的工作。采用科学的、合理的方法来确定配送线路，成为提高物流配送车辆效益、实现物流配送科学化的重要途径。（乔烨， 2008） 对于物流配送中心和第三方物流企业的货物配送，运输车辆调度和路线优化是工作的重点，正确合理的路线优化可以有效减少车辆的空
5、驶率，实现合理路线运输，从而有效减少运 输成本，节约运输时间，提高经济效益。 车辆路径问题 (VRP， Vehicle Routing Problem)，是物流运作管理面临的难点问题。选取恰当的 车辆路径，可以加快对客户需求的响应速度，提高服务质量，增强客户对物流环节的满意度，降低服务商的运作成本，即制定合理的配送路径，快速而经济地将货物送到用户手中。（张志军， 2010） 1.3 配送路线的研究方法 温惠英，孙博（ 2011）在基于离散粒子群算法的协同车辆路径问题中指出国内外学者对 VRP 的研究主要分为：多配送中心 VRP (Multi depot VRP，MDVRP)、带时间窗约束的 V
6、RP、带容量约束的 VRP、随机需求 VRP 和装卸货物一体化的 VRP 等，而协同车辆路径问题 (CollaborativeVehicle Routing Problem， CVRP)研究却很少。 CVRP 是 MDVRP 的发展的高级阶段，围绕各物流企业通过 Intenet 等信息技术创造协同环境共享各种信息和资源，如顾客、仓库和车队等，为所属不同公司的客户统一装卸货物以降低物流配送成本。文章采3 用自适应离散粒子群算法 (Selfadaptive Discrete Particle Swarm Optimization，SA DPSO)，并构造该问题潜在解的粒子编码方式来求解该问题，取得
7、了良好的效果。 李艳冰（ 2010）在配送线路车辆优化调度 问题浅谈一文中，主要在节约里程法思想的基础上，研究在考虑时间要求的同时又考虑空间位置要求的非满载车辆优化调度问题，对企业如何安排配送线路具有一定的指导意义。 余昌艳（ 2009）在基于蚁群算法的粮食加工企业物流配送路径优化研究中提到车辆路径问题的算法主要有两种：（ 1）精确算法。只能有效地求解小规模的车辆路径问题。该算法的一个明显特征是对每一条行车路线的确定总是基于修改后的网络流模型的最优解，大大提高了算法结果的优化质量。（ 2）启发式算法。指研究人员根据某种启发式的信息，对已知的可行解进行改善，通过若干次的迭代 获得相对满意的解。该
8、算法能够在相对较短的时间内找到满意解，所以在大规模复杂的车辆路径问题上应用十分广泛。 李泽华（ 2009）在带时间窗约束的生鲜产品配送车辆路径优化问题研究中提到李军和郭耀煌等用传统启发式算法解决了一些相对简单的 VRP 问题，如送货点比较少的容量约束、时间窗约束冲；蔡延光用遗传算法、模拟退货算法等研究重载 VRP，取得了一些成绩；张涛等通过遗传算法来保证搜索的全局性，用 3-OPT 算法来加强局部搜索能力，得到针对 VRP 的混合算法；谢秉磊、郎茂祥等用遗传算法在容量约束和时间窗约束的冲上做了一些工 作。他们的这些研究对于我国车辆路径研究有一定的促进意义。 汪云华（ 2008）在物流配送多环节
9、的建模优化求解方法中从物流配送的路线优化和车辆配装两个作业环节，提出了建模优化求解方法解决物流配送合理化问题，并应用于实例中，用实例证明了建模优化求解方法的合理性和可行性。 刘思婧，张锦（ 2008）在一种带时间约束的综合节约算法研究中基于模糊综合评判，考虑客户重要程度和配送道路路况，将单纯的距离节约转变为综合节约，并考虑客户点存在时间限制的情形，给出具体的算法，拓展了传统节约算法的适用性。 2 国外研究现状 1959 年， Dantzing 和 Ramser 首次提出运输车辆的优化调度问题。 1962 年，4 Balinski 等人首先提出 VRP 的集分割，直接考虑可行解集合，在此基础上进
10、行优化，建立了最简单的 VRP 模型。 1971 年， Eilon 等人提出将动态规划法用于固定车辆数的 VRP，通过递归方法求解。 1974 年， Wren、 GiUett 等人提出 Sweep算法 (扫描法 )。目的在于求解车辆调度问题，并针对当时几个求解相似问题的算法进行了比较，证明该算法所求得的解较优于其它方法。 1981 年， Christofides等人提出了 k 度中心树和相关算法 ，对固定车辆数 m 的 m TSP 进行了进行 k度中心树松弛。后来， M L Fishet 对这种方法做了进一步改进，可求解有 134个客户的 VRP。 1991 年， Gendreau 等人将禁忌
11、搜索方法应用于 VRP，它是比较好的启发式算法，可以成功地应用于许多经典的 VRP。 1996 年， J Lawrencet将遗传算法用于 VRP 的研究，有效的求解出带时问窗限制的 VRP。 目前， VRP 问题的求解算法很多，可大致分为精确算法和启发式算法两大类。精确算法的计算量一般随着问题规模的增大而呈指数增长，所以多用于规模较小的问题。而对于求解 大规模的 NP(Non deterministic Polynomial Probtena)难题，则较常用模拟退火算法 (SA)、禁忌搜索算法 (TS)、遗传算法(GA)、神经网络 (NN)、蚂蚁算法 (AS)等现代启发式算法。 蚁群算法是由
12、意大利学者 M Dorigo、 A Colomi、 V Manizzo 等人在 90年代初提出的一类新的现代启发式算法，该算法的特点是模拟自然界中蚂蚁的群体行为，自然蚁群总是能够发现从蚁巢到食物源的最短路径。 M Dorigo 将蚁群算法应用于求解 TSP 问题，取得了较好的结果。 G Bilchev等人研究了求解连续空间优化问题的蚁群系统模型，并用来解决某些实际工程设计问题“”。为了克服基本蚁群算法的不足，提高搜索效率，避免过早停滞，一系列改进蚁群算法相应提出，其中主要的一些算法如下： M Dorigo 和 Maniezzo V 在 1996 年提出了 Ant Q System，在该算法中对
13、每一只蚂蚁个体的移动规则进行了修改，并修改了全局更新公式，该算法有利于实现全局搜索。 ThomasStutzle 和 HolgerHoos 在 1997 年提出了 MMAS(Max2min ant system)算法，其基本思想是：在 蚁群算法中仅对每一次循环中的最优蚂蚁所走路径上的信息素进行调整容易出现停滞现象，为了避免停滞，将 分支因子引入，使其作为衡量群体多样性的一个指标。当 分支因子低于某一数值时，便对各个路径上的信息素浓度进行动态调整，以避免过早出现停滞。但 分支因子计算较为复5 杂，且对其界限不容易把握，不便于实际应用。 LM Gambardella 和 M Dorigo 在 20
14、00 年提出了混合型蚁群算法 HAS，在该算法中，经过每次循环蚂蚁建立各自的解，再以各自的解为起点用某种局部搜索算法求出局部最优解，从而可以迅速提高解的质量。 W I Gutjahr 在 2000 年提出了一种以图为基础构建的蚁群系统框架，在一定条件下每次迭代所得到的解能以近似于 1 的概率向最优解收敛。 Kolen、 Desrochers、 Fisher、 Kohl 等人将各种精确算法如分支定界法等应用于 VRPTW 的求解中，成功的解决了理论和现实中的一些规模较小的 VRPTW（带时间窗的车辆路径问题）。采用精确算法虽然可以得到最优解，但是需要消耗大量计算量和计算时间，不适用于现实中大规模
15、的车辆路径问题，过去的研究结果也证明了这一点。近几年来，国外研究者都致力于设计新的高效省时的启发式方 法来构建或改进 VRPTW 问题的解。禁忌搜索法、模拟退火及遗传算法等启发式方法陆续被引入到 VRPTW 的求解中，取得了显著的效果。 参考文献 1 温惠英，孙博基于离散粒子群算法的协同车辆路径问题 J公路交通科技， 2011，28（ 1） ： 149-151 2 李艳冰 . 配送线路车辆优化调度问题浅谈 J科技论坛， 2010： 75-76 3 余昌艳基于蚁群算法的粮食加工企业物流配送路径优化研究 D武汉：武汉科技大学， 2009 4 李泽华带时间窗约束的生鲜产品配送车辆路径优化问题研究 D
16、大连：大连海事大学， 2009 5 汪云华物流配送多环节的建模优化求解方法 J福建：中国集体经济 .商贸流通， 2008：121-122 6 刘思婧，张锦 一种带时间约束的综合节约算法研究 J四川：铁道运输与经济 .现代物流， 2008， 30（ 11）： 69-72 7 郝会霞 基于改进蚁群算法的物流配送车辆路径优化方法的研究 D西安：长安大学， 2008 8 张志军 物流配送中车辆路径生成策略的研究与实现 D江苏：江苏大学， 2010 9 陈韦志 配送中心的运输路径 优化研究 D武汉：武汉理工大学， 2007 6 10 刘凯现代物流技术基础 M北京：北京大学出版社， 2010 11 董维忠
17、物流系统规划与设计（ 第 2 版 ） M北京：电子工业出版社， 2011 12 于宝琴，吴津津现代物流配送管理（第二版） M北京：北京大学出版社， 2009 13 Fisher M L. Optimal solution of vehicle routing problems using minimum k-treesJ. Operation Reseacrh, 1994, 42(4): 624-626. 14 Gendreau M, Hertzt A, Laporte G A tabu search heuristic for the vehicle routing porblemM. Mo
18、nteml: Publication#777, Center de recherche surles transpors, 1991. 15 Lwarence S, Mohammad A. Parametric experimentation with a gegetic algorithmic configuation for solving the vehic le routing porblemA. Proceedings-Annual Meeting of the Decision sciences InstituteC. Decis Scil Inst. 1 996, 488-490.7
