多目标进化计算在物流配送车辆途径问题之应用研究.docVIP

　　多目标进化计算在物流配送车辆途径问题之应用研究 第一章绪论 1.1车辆路径问题的研究背景与意义 随着全球经济的迅猛发展，我国在物流产业方面的发展也有了更广阔的空间.现代物流作为新兴的第三产业在我国已经广泛兴起，它已逐渐成为推动我国现代经济社会发展的重要组成部分.作为ldquo;第三方利润源泉rdquo;的现代物流主要负责商品存储、运输与配送，是企业与客户之间的纽带.其发展引起越来越多的企业及学者的普遍关注.配送是物流配送过程的核心环节，它是在一定经济合理范围内的局部的物流活动.企业根据客户订单对产品进行分拣、包装、并将产品准时、准确的送到客户手中.配送作为连接企业和客户的直接环节，其完成的质量的好坏将直接影响到客户对企业的看法及满意程度.因此，现代配送系统中，配送中心必须按照配送合理化的要求，在全面计划的基础上制定科学的、距离较短的货运路线，选择经济、迅速、安全的运输方式，来高效、及时地满足客户的配送需求.这种有关配送车辆路径的优化，将对整个物流系统的运输速度、成本、效益产生尤为重要的影响.由中国仓储协会对100多个企业的调查可知，整个物流费用中，用于配送所需的费用比例分别为：生产企业原料物流58%，生产企业成品物流73%，商业物流52%[gt;].随着现代物流的兴起，尤其是各种配送方案的釆用，对物流运输成本、运输时间的有效控制日渐成为城市配送车辆路径优化问题（Vehicle Routing Problem,简称VRP)的重要目标.寻求一种既满足客户需求，又降低成本提高物流服务质量的高效配送管理模式显得更加迫切.如何在这三者间找到一个平衡点，已成为国内外企业及应用学者们的关注焦点，VRP是其中一个重要且迫切的研究课题.VRP是物流配送过程中的一个关键问题，而运输成本的高低，客户的满意程度主要取决于运输方式的选择、车辆调度和路径的选择等问题.配送线路的优化是运输合理高效化的重要内容，线路是否合理对配送的速度，时间，成本，效益影响盛大，因此，对VRP问题的研究具有较强的实际意义.本文将对物流配送中VRP问题作较为深入的研究. 1.2国内外研究现状 国内外相关领域对VRP问题研究幵始于50年代，车辆路径问题(VRP)由Dantzig和Ramser于1959年首次提出，很快便引起了包括应用数学、运筹学、网络分析、组合数学、计算机科学等学科领域的专家学者的高度关注，他们在理论研究、试验分析方面投入了大量精力，使该问题逐渐应用到实际生活的很多方面，比如邮政投递、物流配送、紧急服务、铁路飞机调度等等.该问题是组合优化中的一典型问题，是已被证实了的NP难题[31，近二十多年，国内外对VRP问题的研究成果显著.目前，对于VRP模型的研究，国内的李军、刘浩、张潜等都作出了较大的贡献.他们根据不同的约束条件、目标建立了不同类型的VRP数学模型.他们研究提出的模.型主要有：（1)由物流中心的数目分单车场、多车场问题，（2)由车辆载货状况分满载、非满载问题(3)由车辆类型分单车型、多车型问题，（4)由优化目标的数目分单目标、多目标问题M，(5)由客户要求时间分有时间窗、无时间窗问题[9]，(6)由任务的特征分纯送货、纯取货、取送混合问题等等.国外的学者中，国外学者中，Dror等人构造了分批交货VRP的数学模型Cordeau等人于1997, 2001，2002年分别构造了周期性并基于多供货点的模型、场所依赖VRP数学模型以及带时间窗限制的VRP数学模型[11]，Gendreau等人构造了多车型模型.随着社会的发展，VRP也在不断的发展变化，一些新要素也出现了，对研究起着至关重要的作用.从解法上来看，国内外用于求解VRP问题的算法大致可以分为两种：精确算法和启发式算法.精确算法是可以求出最优解的算法，但该方法只能用于求解较小规模的VRP问题，在实际问题中其应用范围有限.20世纪90年代，人工智能的发展促进了VRP问题算法的研究，文献[11]运用模拟退火算法和遗传算法求解多重车辆调度问题，并将其集成为智能算法库，作为设计智能运输调度系统的依据.鞍山钢铁学院李大卫等和东北大学姜大立等分别针对有时间窗和无时间窗约束下的车辆路径问题用基因编码遗传算法求解，结果在较快速度下得到了近似优解封全喜、刘诚在初始化不同种群时，用随机初始化法和构造初始化法等两种不同的方法，以改变种群内部平衡蒋忠中、汪定伟考虑车辆行驶时间和顾客服务时间的不确定性，通过优化设计车辆配送路径，使得配送的总费用最小。 第二章车辆路径优化问题与求解算法 2.1车辆路径问题基本概念 2.1.1车辆路径优化问题 VRP问题最早由Danting和Ramser于1959年提出，该问题一般被描述为：从物流中心用多台汽车向多个地理位置分散的客户送货，并且在完成配送任务后，返回物