1、 毕业论文文献综述 物流管理 节约里程法在一次性餐具配送线路优化中的运用研究 随着经济的不断发展，物流正扮演着一个重要的角色，在我国物流业发展水平不高的情况下，为促进我国物流业的快速现代化，实现高效率 、 高增值 、低成本的发展，必须将视角集中到配送高效率上，配送线路的优化是配送中的一个关键优化点，要用科学的方法选择合适的第低成本的配送线路。 1 国内研究现状 1.1 配送的定义 配送是指在全面配货的基础上，充分按用户的要求进行服务，它把配和送有机地结合起来，完全按照用户要求的数量、种类、时间等进行分货、配货、流通 加工等作业，并提供“门到门”的服务。配送和一般送货的重要区别在于，配送往往在物
2、流据点 (如配送中心等 )有效地利用分拣、配货等理货工作，使送货达到一定规模，以利用规模优势取得较低的送货成本。同时，配送以客户为出发点。强调“按客户的订货要求”为宗旨。为此，完善配送对于物流系统的提升，流通企业的发展，以及整个经济社会效益的提高，具有重要作用（张丹羽， 2005）。 我国的国家标准物流术语将配送定义为：“在经济合理区域范围内，根据客户要求，对物品进行拣选、加工、包装、分割、组配等作业，并按时送达指定地点的物流活动。 ”配送是“配”和“送”的有机结合体。配送是由集货、配货和送货三大部分有机结合而成的。采用科学的、合理的方法来确定配送线路，成为提高物流配送车辆效益、实现物流配送科
3、学化的重要途径。 货物配送是物流中一个直接与消费者相连的重要环节，对配送的路径和车辆调度进行优化，是物流系统优化中的关键一环（陈思勇， 2009）。 陈志伟在文中提出配送是在经济合理区域范围内，根据客户要求，对物品进行拣选、加工、包装、分割、组配等作业，并按时送达指定地点的物流活动。物流配送也就是在产品用户集中的区域，按用户的订货要求和时间计划，在物流中 心配货，并将配好的货物采用汽车巡回运送方式送交收货人的为多用户服务的运输。配送不是单纯的运输或是送货，而是运输与其它活动的组合，除了各种运输活动外，还要从事大量的集货、分货、配货、配装等工作，是配与送的结合（陈志伟， 2009） 。 1.2
4、配送线路优化研究意义 运输是“第三个利润源”的主要源泉， (1)运输是运动中的活动，它和静止的保管不同，要靠大量的动力消耗来实现这一活动，而运输又承担大跨度空间转移的任务，所以活动的时间长、距离长、消耗也大。消耗的绝对数量大，其节约的潜力也大。 (2)从运费上看，运费在全部物流 费中占最高的比例，一般综合分析计算社会物流费用，运输费在其中占接近 50%的比例，有些产品运费高于产品的生产费。所以节约潜力很大。 (3)运输里程大，运输总量巨大，通过体制改革和运输合理化可大大缩短运输的吨千米数，从而获得比较大的节约 VRP对 (VRP Vehicle Routing Problem,车辆路径规划问题
5、 )的一般描述是：对一系列给定的客户 (送货点或取货点 )，确定适当的配送车辆行驶路线，使其从配送中心出发，有序地通过它们，最后返回配送中心，并在满足一定的约束条件下 (如车辆载重量、客户需求量、时间窗限制等 )，使总运输成本达到最小 (如使用车辆数最少、车辆行驶路程或时间最短等 )（张丹羽， 2005）。 合理的配送规划将直接影响一个企业的成本控制、效率和竞争能力针对餐饮业的特点提出一个规划方案 ： 按货物品种来确定配送节点的方法 ， 并以此为基础 ， 分别从选择配送点和对路线变更方案进行了研究（屠一琳 ； 霍佳震， 2009） 。 随着商品经济的发展，对物流配送的时间性和服务质量方面的要求
6、越来越高，把合适的产品 （ The right Product） ，在合适的地点 (In the right place），以适当的数量（ In the right quantity），在所需要的时间 （ At the right Time）和适当的价格（ At the right price）提供给顾客日益成为衡量物流服务的质量标准。发展现代化的物流配送已成为提高物流的经济和社会效益，推动国家经济在高起点上持续发展的重要基础（韩世莲， 2005）。 1.3 配送线路优化的研究方法 陈志伟在 基于 GIS 的配送线路优化的研究与设计译文中提到配送线路优化的方法有： (1)Sweep 算法。该算
7、法是由 Wren， Gillett 等人提出的。即先计算出所要访问的点的极坐标，按照角度大小 排序。然后在满足可行性条件的前提下，按照角度大小归并到不同的子路径中。最后再根据 TSP 的优化算法对所得到的子路径进行优化。 (2) Chrisofides-Mingozzi-Toth 两阶段算法。它主要面向 CVRP 和 DVRP。该算法的求解过程分为两个阶段：第一阶段按最小路径的原则形成初始解，然后用 k-opt 算法对所得的各子路径分别进行优化；第二阶段是在各子路径间进行点的交换，以减小总行程，然后再用 k-opt 算法对点交换后的子路径进行优化。该算法的优点是，在计算过程中，考虑了所需要访问
8、的点数量增加的情况。 (3) 禁忌搜索。 Gendreau 等人最先将该方法应用于 VRP。先构造一系列的解，然后对所得解不断地进行改进。该算法所得到的解不一定早可行解，他们对可行性的偏离程度是通过目标函数里德罚函数来体现的。该算法求解过程中的邻域，是通过 GENI 过程得到的。它是针对 VRP 的比较好的启发式算法，可以成功地应用于许多经典的 VRP。其后 E.Tailard 等人通过按角度和路径重心对原问题的空间进行分割，再用禁忌搜索结合模拟退火对子问题求解，实现了对问题求解的并行化。 (4) 遗传算法。 J.Lawrence 最先将该方法用于 VRP 问题的研 究，并可有效求解带时间窗口
9、的 VRP 问题。鉴于传统的遗传算法是个大范围、粗粒度的寻优算法，因此 Brainier 将它与约束满足问题 (CSP)的技术相结合，通过遗传算法来处理 CSP 参数的子域 (基因的适应度是通过对CSP 解的计算得到的 )，从而减小搜索空间，降低 CSP 问题目标函数和遗传算法约束的复杂度 (陈志伟， 2009)。 张丹羽在现代物流配送中心车辆线路优化方案研究与应用中提到： 蚂蚁算法 (Ant Algortilllns)是一种源于大自然生物世界的新的仿生类算法，作为通用型随机优化方法，它吸收了昆虫王国中蚂蚁的 行为特性，通过其内在的搜索机制，在一系列困难的组合优化问题求解中取得了成效。 动态车
10、辆配送优化调度问题的高效求解算法 。 在分析配送车辆调度中造成车辆动态性的原因的基础上 ， 提出了一种考虑车辆故障和车辆多次巡回配送的动态车辆配送优化调度问题 。 利用了禁忌搜索算法全局搜索能力强的优势 ， 又充分利用局部搜索算法收敛速度快的优势 。 配送车辆优化调度是物流系统优化的关键。 (1) 通过分析配送业务中造成车辆动态性的原因 ， 提出了考虑车辆多次巡回配送和车辆故障的动态车辆配送优化调度问题 ， 使研究更加切合实际 。(2) 为动态车辆配送优化 调度问题设计了“制定整体优化计划 +实时局部优化调度”的两阶段求解策略 ， 第一阶段采用禁忌搜索算法制定优化的配送计划 ；第二阶段采用局部
11、搜索算法实时进行优化调度 。 既充分利用了禁忌搜索算法全局搜索能力强的优势 ， 又充分利用局部搜索算法收敛速度快的优势 ， 使动态车辆配送优化调度问题得到满意的解决 ， 试验计算的结果也充分证明了这一点 。(3) 在研究动态车辆配送优化调度问题时同时考虑了客户的时间窗要求 ， 解决了动态车辆配送优化调度问题中动态信息的时间依赖性与客户时间窗之间的时间二维性问题 （ 郎茂祥， 2009） 。 蚁群算法是一类寻 找最优解问题的算法，首先用来解决 TSP问题。在货物配送路径规划问题中。车场和各个客户点可以看作 TSP问题中的各个城市，其本质就是要找到优化的最短路径。这样，路径规划问题也就可以转换成带
12、有约束条件的 TSP问题。因此，货物配送路径规划问题可以借助于蚁群算法来解决（ 陈思勇， 2009）。 2 国外研究现状 运输车辆的优化调度问题由 Dantzing和 Ramser于 1959年首次提出。 1950年Dantzing和 Ramser(1959)利用整数规划模式来处理包含大约 10到 20个顾客点的小规模问题。 1960到 1964年 Clarke和 Wright(1964) 提出了一种启发式节约法来建立车队配送路线。 1970年提出了两阶段启发式算法来求解车辆调度问题，Gillett和 Miller(1974)提出的扫描法 (Sweep Algorithm)即属于先路径再分组的
13、方法， Christofides(1978)等人则提出先分组再路径的方法。此时学者Golden,Magnanti和 Nguyen (1977)指出虽然两阶段启发式方法可处理较大型问题，但其涉及运算效率是相当重要的问题。 1980年 Fihser和 Jaikumar(1981)提出以 数学规划为主的最优化方法来处理包含大约 50个顾客点的问题，同样其运算效率是一个巫待解决的问题。另外， Cullne,Jvaris和 Ratliff(1981)建立一种人机互动的启发式方法。 1990年 Fihser(1995)对最优化方法加以改善，己经可以解决 50到 100个顾客点的车辆调度问题，同一时期，有不
14、少学者利用启发式算法来解决车辆调度问题，包括模拟退火法、遗传算法、神经网络算法和禁忌搜索算法。如 Robuste(1990)等以及 Alaf.Heragu(1991)利用模拟退火算法求解车辆调度问题 :Sement和 Taill-ard(1993)、 Gendreau和 Laporte(1994)等人利用禁忌搜索算法求解车辆调度问题。 其中精确优化方法。包括制定下界及相关分枝定界算法 (Branch and bound approach)(算 法比较适 用于求解 小型问 题 )、切 平面法 (Cutting planes approach)(算法考虑所有可能的可行解子集，其算法本质是最短路径算
15、法结合分枝定界法 )、动态规划法 (Dynamic Programming approach)(算法针对固定车辆数的 VRP,通过递归方法求解 )、网络流算 法 (Network flow approach)(该方法结合图论中的一些传统算法 (如最短路径、宽度搜索算法等 )，经常可以解决一些搜索与动态规划无法解决的非 NP 问题 )。但精确算法的计算复杂度很高，随着运输系统的复杂化和对调度的多目标要求，获得整个系统的精确优化解越来越困难，花费的时间和费用太大，因此精确解法不能应用于规模较大的配送车路由问题的求解，仅用于运输调度的局部优化问题。启发式方法 (Heuristics)启发式算法指通过
16、对过去经验的归纳推理以及实验分析来解决问题的方法，即借助于某种直观推断或试探的方法。 启发式方法要求分析人员必须运用自己的感知和洞察力，从与研究问题有关而较基本的模型及算法中寻求其间的联系，从中得到启发，去发现解决问题的思路和途径。启发式方法作为一种逐次逼近的算法，虽然不一定得到问题的最优解，但是可以高效率地得到具有较优的解，能同时满足详细描绘问题和求解的需要，较精确优化方法更为实用，它的主要缺点是难于知道什么时候好的启发式解己经被求得。模拟方法，于 1986 年由Golden 和 Skiscim 最早提出，此方法通常是利用常数公式、逻辑表达式、图表、坐标图形等抽象概念表示实际运输系统内部状态
17、和输入输 出的关系，以便通过计算机对模型进行实验，通过实验取得改善运输系统或设计新运输系统所需信息。这种方法主要应用于行车路线与物流中心区位的选择，优点在于可直接观察系统安排的效率和效果，但由于问题的实际情况多变且具不确定性，是否能将实际的配送情形系统逻辑化为仿真程序，往往令人质疑。交互式优化法，该方法结合人类决策与计算机计算能力，在求解过程中，通过高度的人机交互模式，结合专家的决策信息，并据以计算出结果；优点是寻优的过程中，决策者可以很清楚地看到各约束条件之间的替代关系，以及参数变化可能导致的成本变化。缺点在于由于 在模型的优化过程中加入了人的主观因素，所以通常会增加模型最终实现并未被采用的
18、可能性。采用这种方法求解车辆路径问题的早期雏形是由 Krolab,Felts,Marble 和 Nelson 等人提出的。 目前，某些常用且较成熟的算法己被人们运用到实际的动态车辆调度系统，美国利用最短路径算法、启发式算法开发计算机配送调度系统用来解决货运汽车作业计划中路线优化选择和车辆分配等问题，使汽车里程利用率提高 5 阶15%,运输成本和运输时间也有了明显下降。 6 参考文献 1 张丹羽现代物流配送中心车辆线路优化方案研究与应用 D山东：山东大学， 2005 2 陈思勇供应商选择与货物配送路径规划研究及其应用 D北京：北京交通大学， 2009 3 陈志伟基于 GIS 的配送线路优化的研究
19、与设计 D浙江： 浙江工商大学， 2009 4 屠一琳 ， 霍佳震 餐饮物流配送路线的优化研究 J 重庆交通大学学报 （ 自然科学版 ），2009(10): 10-13 5 韩世莲物流配送线路多目标优化方法研究 D湖南： 东南大学， 2005 6 郎茂祥 动态车辆配送优化调度问题的两阶段算法 J 交通运输系统工 程与信息， 2009(08): 9-10 7 李军，郭辉煌物流车辆优化调度理论与方法 M北京：中国物资出版社， 2001: 76-78 8 刘凯现代物流技术基础 M北京：清华大学出版社；北京交通大学出版社， 2004 9 汤杰基于蚁群算法的物流配送模型研究 D重庆：重庆理工大学， 20
20、09 10 辛达基于蚁群算法的多配送中心车辆调度问题的研究 D安徽：合肥工业大学，2006 11 陈子侠基于 GIS 物流配送线路优化与仿真 M北京：经济科学出版社， 2007 12 王迎春配送中心动态选址路线安排问题研究 D黑龙江：哈尔滨工业大学， 2007 13 Bramel J, SimehiLevi D. A Location Based Heuristic for General Routing ProblemsJ. OPns. Res, 1995(43): 649660. 14 Fisher ML, Jaikumar R.A Generalized Assignment Heuristic for Vehicle RoutingJ. Newtokrs, 1981(11): 109124.
