《毕业设计论文用遗传算法解决车辆优化调度》由会员分享，可在线阅读，更多相关《毕业设计论文用遗传算法解决车辆优化调度（45页珍藏版）》请在金锄头文库上搜索。
1、摘 要近年来，物流作为“第三方利润的源泉”受到国内各行业的极大重视并得到了较大的发展。在高度发展的商业社会中，传统的VSP算法已无法满足顾客需求对物流配送提出的要求，于是时间窗的概念应运而生。带有时间窗的车辆优化调度问题是比VSP复杂程度更高的NP难题。本文在研究物流配送车辆优化调度问题的基础上，对有时间窗的车辆优化调度问题进行了分析。并对所采用的遗传算法的基本理论做了论述。对于有时间窗的非满载VSP问题，将货运量约束和软时间窗约束转化为目标约束，建立了非满载VSP模型，设计了基于自然数编码，使用最大保留交叉、改进的反转变异等技术的遗传算法。经实验分析，取得了较好的结果。由于此问题为小组成员共
2、同研究，本文重点论述了本人完成的关于适应度函数和变异操作的部分。关键词：物流配送 车辆优化调度 遗传算法 时间窗Abstract Recent years, logistics, taken as third profit resource”, has been developing rapidly. In the developed commercial society, traditional VSP algorithm have been unable to meet the requirement that Quick Response to customer demand had b
3、rought forth, then the conception of Time Window has come into being. The vehicle-scheduling problem with time window is also a NP-hard problem being more complicated than VSP. This text has been researched to the vehicle-scheduling problem with time window on the basis of researched to logistic veh
4、icle scheduling problem. And it has explained the basic theory of genetic algorithm.On the VSP with time window, while the restraints of capacity and time windows are changed into object restraints, a mathematic model is established. We use technique such as maximum preserved crossover and design ge
5、netic algorithm on nature number, which can deal with soft time windows through experimental analysis, have made better result. Because this problem was studied together for group members, this text has expounded the part about fitness function and mutation operator that I finished.Key words: logist
6、ic distribution vehicle scheduling problem genetic algorithm time windows目 录摘 要IAbstractII目 录III引 言1第1章 概 述21.1 研究背景21.2 物流配送车辆优化调度的研究动态和水平41.2.1 问题的提出41.2.2 分类51.2.3 基本问题与基本方法61.2.4 算法61.2.5 货运车辆优化调度问题的分类81.3 研究的意义91.4 研究的范围10第2章 有时间窗的车辆优化调度问题(VSPTW)112.1 时间窗的定义112.2 VSPTW问题的结构13第3章 遗传算法基本理论143.1 遗
7、传算法的基本原理143.1.1 遗传算法的特点143.1.2 遗传算法的基本步骤和处理流程153.1.3 遗传算法的应用163.2 编码173.2.1 二进制编码183.2.2 Gray编码183.2.3 实数向量编码183.2.4 排列编码193.3 适应度函数193.3.1 目标函数映射成适应度函数193.3.2 适应度定标203.4 遗传算法的基因操作213.4.1 选择算子213.4.2 交叉算子223.4.3 变异算子253.5 遗传算法控制参数设定28第4章 遗传算法求解有时间窗非满载VSP304.1 问题描述304.2 数学模型314.2.1 一般VSP模型314.2.2 有时间
8、窗VSP模型324.3 算法设计334.3.1 算法流程图334.3.2 染色体结构334.3.3 约束处理354.3.4 适应度函数364.3.5 初始种群364.3.6 遗传算子364.3.7 控制参数和终止条件374.4 算法实现394.5 实验及结果分析394.5.1 控制参数选定394.5.2 实例实验434.5.3 实例数据444.5.4 实例数据分析44结 论45参考文献47谢 辞4841引 言随着市场经济的发展，大量经营规模较大的制造企业和商业企业纷纷建立起配送中心向商品流通效率化发起挑战，与此同时，相当部分的大型运输、仓储和航运企业开始转向第三方物流经营。此外，我国具有强大物
9、流配送资源优势的邮政业更是在递送包裹的基础上为企业、商家和电子商务网站积极开展配送业务。物流配送开始在我国迅速兴起发展起来，对物流配送的研究引起了国内物流专家学者的广泛关注。 目前国内采用遗传算法解决物流配送的车辆优化调度问题的研究还处在起步阶段。本文针对客户提出时间约束这一配送需求，对有时间窗的物流配送车辆优化调度问题（VSPTW）进行数学分析，研究探索性能更强的解决VSPTW的遗传算法。 本文第1章研究目前物流配送车辆优化调度问题的研究动态和水平；第2章进一步研究有时间窗的物流配送车辆优化调度问题；第3章阐述和研究所采用遗传算法的基本理论；第4章详细论述如何采用遗传算法解决有时间窗的物流配
10、送车辆优化调度问题并通过实验数据分析所采用改进的遗传算法的性能。第1章 概 述1.1 研究背景随着社会主义市场经济的发展，在经济大循环中提高经济运作效率的物流对经济活动的影响日益明显，越来越引起人们的重视。据中国物流信息中心统计测算，2004年，全国社会物流总额达38.4万亿元，同比增长29.9%(按现价计算)，增幅比上年同期提高2.9个百分点。虽然我国物流发展持续加速，但与国民经济发展的要求还相差甚远，这就要求我们对物流产业的各个环节进行研究。 配送是物流中一个重要的直接与消费者相连的环节。我国国家标准物流术语中对配送的定义是：“在经济合理区域范围内，根据用户要求，对物品进行拣选、加工、包装
11、、分割、组配等作业，并按时送达指定地点的物流活动。”配送是在集货、配货基础上，按用户要求，包括种类、品种搭配、数量、时间等方面的要求所进行的运送，是“配”和“送”的有机结合形式，其主要功能是输送。配送的流程一般如下图所示。 用户 工厂 进货 送货 集货 存储 配货 车辆 配装 图1-1 配送流程图在传统的配送系统中，由于商品的需求量及种类较少，零售商可凭借较多的存货及较常的定货周期来减少供货商的配送频率，以降低运输成本。但是在现代的配送系统中，零售商为了减少资金积压及提供多样化的商品，势必要减少各种商品的存货数量，而同时又必须考虑到提供最好的服务品质(不允许缺货)。物流中心的功能就在于对商品的
12、仓储与运输进行有效的统筹规划以降低配送成本。所谓“物流中心”，根据美国物流管理协会(The Council of Logistics Management, CLM)定义：“以适合顾客要求为目的，对原物料、在制品、制成品与其相关信息，从产地到消费者的间的流程与保管，为求有效率且最小的机会成本，而进行计划、执行、控制的场所(Depot) ”。在物流配送系统中，物流配送中心的成立可有效的简化配送程序与减少配送的频率，以i个供应商和j个零售商为例，传统的配送模式是假设j个零售商的需求都是由i个供应商自行配送，则一共有ij次的运送，如图1-2所示。假设零售商与供应商之间通过一个物流配送中心来配送，则只
13、需i+j次配送，如图1-3所示，如此一来即可减少(ij-(i+j)的配送次数，当供应商与零售商数目越多，节省的配送次数也就会越多。 供应商（S） 零售商（R） 图1-2 传统的物流配送模式物流中心配送作业的重点是如何将车辆有效的使用并决定其最经济的行驶路线图，使商品能在最短的时间内送到顾客的手中。国外将此类问题称之为Vehicle Scheduling Problem，简称为VSP问题。该问题一般定义为:对一系列装（卸）货点，组织适当的行车线路，使车辆有序的通过它们，在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等)下，达到一定的目标(如路程最短、
14、费用最少、时间尽量少、使用车辆数尽量少等)。供应商（S） 零售商（R） 物流中心 图1-3 以物流中心为主的配送模式 1.2 物流配送车辆优化调度的研究动态和水平1.2.1 问题的提出物流配送车辆优化调度问题最早是由Dantzig和Ramser于1959年首次提出，自此，很快引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家与运输计划制定者和管理者的极大重视，成为运筹学与组合优化领域的前沿与研究热点问题。各学科专家对该问题进行了大量的理论研究及实验分析，取得了很大的进展。国外对物流配送车辆优化调度问题作了大量而深入的研究，例如早在1983年Bodin, Golde
15、n等人在他们的综述文章中就列举了700余篇文献。在Christofides(1985)，Golden和Assad(1988)编辑的论文集，以及Altinkermer和Gavish(1991)，Laporte(1992)，Salhi(1993)等的综述文章中都进行了详尽阐述。该领域的代表人物有Bodin，Christfids，Golden，Assad，Ball，Laporte，Rinnooy Kan，Lenstra，Desrosiers和Desrochers等人。国内对物流配送车辆优化调度问题的研究相当少，主要研究对象是旅行商问题(Traveling Salesman Problem，简称TSP)、中国邮递员问题(Chinese Postman Problem ,简称CPP
