城市配送中心车辆路径优化问题研究

兰州交通大学毕业设计（论文）I摘要车辆路径问题是运输配送中的难题之一，也是物流系统优化的关键一环。对此，国内外学者进行了广泛而深入的研究，提出了不同条件下的多种求解方法。各种方法都优点和不足之处，也有其应用上的局限和障碍，如何有效而充分地运用这些方法解决实际问题，使之服务于物流配送实践，是重要的研究课题。基于配送车辆线路问题的复杂性和多样性，相关软件的使用将是一个必然趋势。本文简要介绍了国内外车辆路径问题的发展现状，对于配送中心车辆相关概念进行了介绍。对单车辆和多车辆配送情况简要介绍，并建立数学模型，介绍了车辆路径问题的相关算法，特别对节约里程法（克拉克-怀特算法）以及 Logware 软件中的ROUTER 模块的原理和方法深入研究，探讨了多辆车情况下的配送车辆线路问题。通过一个案例，应用节约里程法对算例进行线路安排，与 Logware 软件的得到的线路方案进行对比，二者结果相近，但软件的计算速度更快，效率更高。此外，分析了节约里程法和 Logware 软件对多车辆线路的结果。关键字：车辆路径问题；配送；节约里程法（克拉克-怀特算法） ；Logware 软件。兰州交通大学毕业设计（论文）IIAbstractThe vehicle routing problem is one of the difficult problems of transport distribution and one important part of the logistics system optimization. For this, the domestic and overseas scholars make much extensive and in-depth research, and put forward solutions under different conditions. Every method has its advantages and disadvantages, also has its limitation and obstacle on application. It is an important research subject that how to effectively make full use of these methods to solve the actual problem, and service the logistics distribution practice. Based on the complexity and diversity of the vehicle routing problem, to use of the related software will be a necessary trend. This paper briefly introduces the development status quo of vehicle routing problem at home, For distribution center vehicle related concepts are introduced .on a single vehicle and multiple vehicle distribution is briefly introduced, introduces the algorithm of vehicle routing problem, especially for saving mileage (Clark - White algorithm) and the principle and method of ROUTER module in Logware software research. discusses the distribution vehicle line car case arrangement problem. Through a case study, application of saving algorithm for line arrangement for example, compared with the circuits Logware software obtained arrangement scheme, the two results are similar, but the speed of calculation software faster, more efficient. In addition, analyses the arrangements of the vehicle line C-W algorithm and the result of Logware software.Key words: Vehicle Routing Problem, Distribution, Saving Mileage（Clarke Wright Algorithm）, Logware Software兰州交通大学毕业设计（论文）I目录摘要 .IAbstract .II第一章 绪论 .1第一节 研究背景和意义 .1第二节 研究现状 .3一、国外研究现状 .3二、国内研究现状 .4第三节 研究思路 .5第二章 基本理论概述 .7第一节 配送 .7一、配送的概念 .7二、配送的要素 .7三、配送的作用 .9第二节 物流及配送中心 .10一、物流的概念 .10二、配送中心的概念 .12三、配送中心的功能 .13第三节 旅行商问题 .15一、旅行商问题介绍 .15二、旅行商问题的数学模型 .15第三章 车辆路径问题及其相关算法 .18第一节 车辆路径问题 .18一、车辆路径问题概述 .18二、车辆路径问题的分类 .20三、车辆路径问题的构成要素 .23第二节 求解 VRP 问题的算法 .24一、求解 VRP 问题的启发式算法 .24二、求解 VRP 问题的精确算法 .27第四章 车辆路径问题的数学模型及求解方法 .34第一节 VRP 的数学模型 .34兰州交通大学毕业设计（论文）II一、物流配送中的 VRP 描述 .34二、物流配送中 VRP 的数学模型 .35第二节 节约里程算法解决 VRP 问题 .36一、节约里程算法介绍 .36二、节约历程算法原理 .37三、运算步骤 .38四、节约里程法优缺点 .39第三节 Logware 软件解决 VRP 问题 .40一、Logware 软件概述 .40二、利用 ROUTER 模块求解 VRP 问题 .40第五章 案例分析极其 结果分析 .46第一节 案例 .46第二节 节约里程法计算 .47第三节 Logware 软件运行 .53结论 .59参考文献 .61致谢 .62附录 .63兰州交通大学毕业设计（论文）1第一章 绪论第一节 研究背景和意义随着物流业向全球化、信息化及一体化发展, 配送在整个物流系统中的作用变得越来越重要。运输系统是配送系统中最重要的一个子系统, 运输费用占整体物流费用的50%左右, 所以降低物流成本首先要从降低物流配送的运输成本开始。其中, 运输线路是否合理直接影响到配送速度、成本和效益, 特别是多用户配送线路的确定是一项复杂的系统工程。选取恰当的车辆路径, 可以加快对客户需求的响应速度 , 提高服务质量, 增强客户对物流环节的满意度, 降低服务商运作成本。优化运输物流 , 降低运输成本, 是企业尤其是物流配送企业提高企业竞争力的有效途径之一。尽管物流活动自古有之，但直到1915年， “物流”这一名词才第一次出现在阿齐肖的市场流通中的若干问题一书中，经过数十年的理论研究和实际运作，人们认识到合理! 高效的物流能够从以下几方面创造社会财富：（1）促进国民经济合理布局，有利于社会资源的优化配置；（2）有效地使用流通设施和设备，节约社会资源；（3）减少流通环节，缩短生产周期，加速资金周转；（4）简化信息流通渠道，增强社会物质财富的可调节性；（5）促进社会分工，加速生产的集中化、规模化。物流配送一般定义为：根据用户的订货要求，在物流据点进行分货、配货工作，并将配好的货物送交收货人的一种物流方式，以最终完成社会物流运送，实现资源配置的优化。配送将销售与供应结合起来，是物流系统的最后一个环节，它体现了物流效率和顾客满意程度。配送将物流和商流紧密结合，包含了商流活动，也包含了物流中若干功能要素的一种活动形式。物流中心配送是伴随着大生产、大流通而出现的一种完成资源配置和满足消费需求的方式，它实现了定时、定量、准时性、计划性、即时性，低费用甚至可以实现客户的零库存，以至可以完全取代客户原有的供应系统，用更高的供应质量和更低的供应成本，实现对用户的供应，实现企业销售和用户供应的一体化。配送作为一种专业化、社会化的服务模式，适应了经济一体化的需要，适应了社会化大生产的发展，体现了现代经济的发展趋势。在物流管理学中，研究物流配送路径优化问题并选取恰当的配送路径，可以加快对客户需求的响应速度，提高服务质量，增强客户对物流环节的满意度，降低服务商兰州交通大学毕业设计（论文）2运作成本。车辆路径问题当不考虑时间要求，仅根据空间位置安排路线时称为车辆路线问题(Vehicle Routing Problem 简记 VRP)；当考虑时间要求安排路线时称为车辆调度问题(Vehicle Scheduling Problem 简记 VSP)；当同时考虑空间位置和时间要求时称为路线和调度混合问题。车辆路径问题还有确定性(Deterministic)模式和随机性(Stochastic) 模式之分。确定性模式假设：其一、客户的数目在配送开始前是已知且固定的；其二、客户的需求量在配送开始前是已知且固定的；其三、两点之间的旅行时间仅取决于这两点之间的距离。而随机性模式不要求以上一个或多个假设。随机性模式又称为随机需求车辆路径问题。（1）配送路径优化有利于提高物流经济效益。配送处于物流过程的末端，在一定程度上是物流活动的缩影。配送过程把若干物流功能结合起来，使它们有机地融为一体，从而提高了各项功能的效率；通过合理配货、共同配送，可以消除重复运输、空载运输，提高运输工具的利用率，实现合理运输，降低运输成本；通过路径的优化，可以缩短运输时间，降低运输成本，为企业提供更好的服务。（2）路径优化是配送环节中重要的组成部分之一。配送是直接连接最终客户的物流活动。由于配送中心网络覆盖面大，信息量大而传递快，物流手段先进、设备齐全、专业化程度高，所以其服务成为现代经济中客户不可缺少的后勤。由于设备齐全、管理方式先进、有大量的信息可以提供并且可以及时传递、有网络覆盖，这些都为路径优化提供了可能性。企业可以通过计算机设备，利用所收集到的信息，提供出一个路径优化的方案，并且可以根据网络的及时信息，在具体运输时，可以做到及时更改和监督的作用。例如，可以通过网络告知司机某路段的阻塞，以便于让司机作出及时的调整。物流配送车辆优化调度，是物流系统优化中关键的一环，也是电子商务活动不可缺少的内容。对配送车辆进行优化调度，可以提高物流经济效益、实现物流科学化。可以说对物流配送车辆优化调度理论与方法进行系统研究是物流集约化发展、构建综合物流系统、建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础。1 合理使用与调度运输工具，优化运输路线，降低企业物流成本，是物流管理的重要内容。针对物流管理中对运输车辆优化调配的要求，1959 年由 Dantzig 和 Ramser2首先提出了车辆路径问题(Vehicle Routing Problem, VRP)的数学模型。车辆路径问题已是近几十年来运筹学、应用数学、网络分析、计算机应用及交通运输等学科研究的一兰州交通大学毕业设计（论文）3个热点问题，并且在通讯、生产、国防、生物、计算机应用等领域得到了广泛的应用。本文将着重研究物流配送中的车辆路径问题。VRP 是一个复杂的组合优化问题，目前大都使用启发式算法求解，在可以接受的时间内获得问题的一个满意解。求解 VRP 的启发式算法可以分为两类，一类是经典启发式算法(19601990)，第二类是为元启发式算法 (meta-heuristics)3。在算法寻优能力上，元启发式算法要优于经典启发式算法。到目前，至少有六种元启发式算法被应用到车辆路径问题中，分别为遗传算法粒子群优化算法，神经网络，蚁群算法，禁忌搜索以及模拟退火算法 4。对于启发式算法,我们很难绝对地认为哪种算法更优越，其在问题求解中都有各自优缺点。物流的魅力在于其潜在着很大的利润空间，只要不断挖掘，将会产生很多意想不到的利润之源。提高物流经营水平，降低物流成本是现在物流追求的永恒主题。选址、库存与运输是决定物流管理绩效水平的三个主要驱动因素。本文以提高物流配送效率、质量为目标，对优化配送中运输调度的车辆路径问题（VRP）进行数学分析，并将改进的蚁群算法运用在路径优化策略中，研究如何建立计算机物流配送优化调度管理系统，这对于物流配送企业实现计算机配送调度，降低成本和提高物流经营管理水平将具有重要的参考价值。应该说，课题的研究具有较强的理论和实践意义。第二节 研究现状一、国外研究现状在国外，车辆优化调度研究已广泛用于生产、生活的各个方面，如报纸投递及路线的优化、牛奶配送及送达路线的优化、电话预定货物的车辆载货和线路设计、垃圾车的路线优化、连锁商店的送货及线路优化等等。目前，研究水平已有很大发展，其理论成果除在汽车运输领域外，在水运、航空、通讯、电力、工业管理、计算机应用等领域也有一定的应用，还用于轮船公司运送货物经过港口与货物安排的优化设计、交通车线路安排、生产系统中的计划与控制等多种组合优化。1962 年，Balinski 等人首先提出 VRP 的集分割，直接考虑可行解集合，在此基础上进行优化，建立了最简单的 VRP 模型。 1971 年，Eilon 提出将动态规划法用于固定车辆数的 VRP，通过递归方法求解。 1974 年，Wren Gillett 等人提出扫描算法，将该算法应用于车辆调度问题，并和当时其它算法进行了比较，证明该算法所求得的解较优于其它方法。1981 年，Christofides 等人提出了 k 度中心树和相关算法，对固定车辆数 m 的 m-兰州交通大学毕业设计（论文）4TSP 进行了进行 k 度中心树松弛。后来， MLFishe 对这种方法做了进一步改进，可求解有 134 个客户的 VRP。 1991 年，Gendreau 等人将禁忌搜索方法应用于 VRP，它是比较好的启发式算法，可以成功地应用于许多经典的 VRP。1996 年，JLawrence 将遗传算法用于 VRP 的研究，有效的求解出带时间窗限制的 VRP。二、国内研究现状在我国，有关车辆路径问题的研究是在 20 世纪 90 年代以后才逐渐兴起的，比国外相对落后。随着顾客需求的变化，运输车辆的调度显得日益重要。近年来，我国理论界逐渐开始关注车辆路径问题的研究，并已取得初步成果。蚁群算法、启发式算法以及一些混合算法被学者们广泛的利用，代表了较近的研究思想。启发式算法作为一种逐次逼近的算法，虽然不一定得到最优解，但是可以高效率地得到具有较高精度的解，而且也易于考虑各种实际问题，因此，现已成为解决 VRP 问题的重要方法。与传统的启发式算法相比，近年来所采用的一些新的启发式算法，通过对启发式规则和搜索方式的改进，在求解多节点、多约束的 VRP 问题上可以获得较快的收敛速度和较高质量的全局解。浙江大学蔡延光等人运用模拟退火算法和遗传算法求解多重车辆调度问题，并将其集成为智能算法库，作为设计智能运输调度系统的依据。鞍山钢铁学院李大卫 6和东北大学姜大力 7等分别针对有时间窗和无时间窗约束下的车辆路径问题用基因编码遗传算法求解，结果在较快速度下得到了近优解。崔雪丽、马良和范炳全 8等人基于近年来出现的新型智能优化思想：人工蚂蚁系统，给出了一种可快速求解 VRP的蚂蚁搜索算法。通过定义基本的人工蚂蚁状态转移概率，并结合局部搜索策略，用迭代次数控制算法的运行时间，从而使该方法具有使用意义和可操作性。经一系列数据测试和验证，与若干已有的经典算法相比较，获得了较好的结果。杨善林人等提出一种基于蚁群优化的混合算法来解决 VRP。首先提出一种 ACO 算子，然后加入局部搜索机制并使用基于问题的特定启发信息节约量来改进算法。尹小峰等针对了蚁群算法存在的过早收敛问题，引入节省量以及车辆载重利用率两种启发式信息对蚁群算法加以改进，并加入 2opt 方法对问题求解进行局部优化，计算机仿真结果表明，这种混合蚁群算法对求解车辆路径问题有较好的改进效果。由于物流对于中国来说，还算是一个新兴行业，所以在中国物流的发展当中，可以借鉴一下国外的发展经验。物流的发展，尤其是配送路线优化的发展，在中国存在兰州交通大学毕业设计（论文）5着以下几点的困难：（1）要进行配送路线的优化，先进设备的使用存在着一定的困难。因为物流的现代化，需要一系列配套设备的使用，投资比较大，成本回收慢。例如一家物流企业使用了先进的设备，但是与其往来的企业无法提供相应先进的设备和该企业配合，那么设备的利用率以及优势是无法体现出来的，现代化是无法展开的。（2）在中国社会中，对于物流行业的偏见，配送路线优化工作的展开有一定的困难。很多人并不了解物流，认为物流只是简单的运输，不愿意进行投资发展，忽略了其中的价值，这造成了物流发展的阻碍。（3）专业型人才短缺，使得没有专业型人才进行配送路线优化工作。先进的设备以及现代化管理，都需要物流专业型人才的加入，而在中国很多物流企业中，缺少这种物流专业型人才。（4）物流专业型软件没有得到广泛应用，使得配送路线优化存在着困难。第一，很多物流企业只是靠经验来判断路线，并没有真正得到优化，没有使用计算机以及与其配套的专业型软件，软件的使用可以使路线的选择更加优化，也可以减少劳力。第二，对于物流专业型软件以及系统的开发，没有得到重视。在中国，软件在物流中的应用，越来越广泛，并且带给企业以及社会很大的经济效益，帮助企业解决了很多困难。物流中的软件，正朝着定制化，通用化，行业化的方向前进发展着。第三节 研究思路本文是研究配送中心车辆路径问题的。Logware 是物流专用软件，可以通过软件来安排车辆的路线，优化配送过程，提高效率，增加经济效益。本文的研究思路如下：第一章，讲述研究意义、以及配送车辆路线的研究现状、发展现状和总体