本科学生毕业论文 基于遗传算法的物流配送车辆调度问题 院系名称： 数 学 系 专业班级： 信息与计算科学 学生姓名： 指导教师： 职 称： 副 教 授 黑 龙 江 工 程 学 院二一一年六月The Graduation Thesis for Bachelors DegreeThe logistics of the vehicle scheduling problem based on genetic algorithm Candidate：Luo JieSpecialty：Information and Computing ScienceClass：07-02 Supervisor：Lecturer.Wu Chang Heilongjiang Institute of Technology2011-06Harbin摘 要 随着科学技术的不断进步，经济的飞速发展，物流作“第三利润源泉”在国内受到了极大的重视并得到飞速的发展。如何节约成本，提升自我竞争能力，是每个物流公司也是整个物流行业所面临的实际问题。在物流配送业务中，配送车辆调度问题涉及面较广，需要考虑的因素较多，对企业提高服务质量、降低物流成本、增加经济效益的影响也较大，是物流系统优化中关键的一环。可以说对物流配送车辆调度问题进行系统研究是物流集约化发展、构建综合物流系统、建立现代调度指挥系统、发展智能交通运输系统的基础。在现实生产和生活中，邮政投递问题、管道铺设问题、电力调度问题、公交车行驶线路问题等都可以看做是物流配送车辆调度问题，是NP困难问题。但是由于问题约束条件的增多，参与计算数据规模的过大，求解时间呈几何数字扩大，传统的求解方式已不能满足求解需求，所以我们用遗传算法来解决此问题。本文首先分析了物流配送中车辆调度优化问题的概述，通过概述后建立了一个模拟的物流中心和一个客户群，以及客户群与物流中心彼此的位置关系，然后在对遗传算法详细介绍的基础上，设置相应的运行参数，再对该模型应用MATLAB70实现了对遗传算法效果的仿真，验证了遗传算法解决配送路径优化问题的可行性。关键词：物流配送，车辆调度，遗传算法，最短路问题，人工智能算法ABSTRACT Along with the science and technology unceasing progress, the rapid development of economy, the logistics as third profit source in the domestic received great attention and get rapid development. How to save cost and enhance self competition ability, is each logistics company also is the whole logistics in logistics and distribution services, the distribution vehicle scheduling problem in a wide range of factors needed more, for enterprises, and improve the service quality, reduce logistics cost and increase economic benefits is larger also, the influence of logistics system optimization is a key part of. Say the distribution vehicle scheduling problem of logistics system study is intensive development, constructing logistics comprehensive logistics system, establishing modern scheduling command system, developing intelligent transportation system foundation. In actual production and life, postal delivery problems, pipeline problem, power scheduling problem, buses driving circuit can be regard as problems concerning the distribution vehicle scheduling problem is logistics, is standard np-hard problem. But due to the constraint condition of increasing problems involved in the calculated data, the excessive, solving time scale shows geometrical figure, the traditional way of solving the expanding already cannot satisfy solving demand, so we use genetic algorithm to solve the problem. Industry faces the actual problem. This paper first analyzes the logistics distribution vehicle scheduling optimization problem, after an overview of the overview established a simulated logistics center and a customer base, and customer base and logistics center of each other, and then to the position relations in the genetic algorithm based on detailed introduction, set up corresponding operation parameters of the model, and applied to genetic algorithm MATLAB7.0 realized the simulation proves effect of genetic algorithms to solve the feasibility of distribution path optimization problem.Key words: Logistics distribution，Vehicle scheduling，Genetic algorithm， The shortest path problem，Artificial intelligence algorithm目 录摘 要IABSTRACTII目 录1第1章 绪 论11.1课题研究背景与实际意义11.2国内外研究现状及分析21.3本文的研究方法3第2章 物流配送车辆调度问题的综述42.1物流配送车辆调度问题的概述42.2物流配送车辆调度问题的分析5第3章 遗传算法的概述与应用83.1 遗传算法理论概述83.1.1遗传算法的起源于发展83.1.2遗传算法的工作特点93.2遗传算法的运用103.2.1遗传算法的步骤103.2.2遗传算法的数学模型11第4章 基于遗传算法的车辆调度模型144.1模型的建立144.2模型的求解184.2.1.确定染色体的编码和初始群体184.2.2.适应性函数194.2.3.染色体的选择204.2.4.染色体的交叉214.2.5.染色体的变异224.2.3.控制参数224.2.3.运行结果234.3总结23主要参考资料24致 谢25附 录26第1章 绪 论1.1课题研究背景与实际意义在经济全球化和信息化的推动下，现代物流业已从为社会提供传统运输服务，扩宽到以现代科技、管理和信息技术为支柱的综合物流系统。物流是在20世纪50年代新发展起来的一门实践性很强的综合性交叉学科，是当代最有影响的新科学之一，它全面融会了运筹学、经济科学及管理科学，揭示了运输、储存、装卸搬运、包装、流通加工、物流信息等物流各要素的内在联系，物流在经济发达国家被视为继原材料、劳动力以外的“第三利润源泉”在现代物流集约化、一体化的发展中，车辆优化调度是直接与消费者相连的重要环节，涵盖的面也比较广其中包括配货作业，即货物的分拣过程，根据各个用户的不同需求，在配货中心将所需要的货物迅速的挑选出来的过程，加大车辆调配执行的效率，这需要仓储的优化：车载货物的配装，即在配送货物时要考虑车辆的载重和容积，使车辆的载重和容积充分利用，还要考虑配送多个客户的问题：配送线路的确定，配送线路合理与否对配送速度、成本、效益影响很大，特别是多用户配送线路的确定更为复杂。采用科学的、合理的方法来确定配送线路是车辆优化调度的核心部分，是物流系统优化、物流科学化的关键一环。对车辆进行优化调度，即合理的进行配货优化、货物配装优化，特别是配送路线优化，能够提高里程利用率，降低行驶费用，大大减少车辆空驶里程，增加货运量，节约燃料，降低大修费，提高营运收入，从而带来巨大的经济效益。另外，还可以产生良好的社会效益，体现在减少废气排放量，降低城市空气污染水平。目前，在我国一些地区，公路货物运输一方面存在超负荷运行：另一方面由于缺乏科学组织，造成货运车辆使用效率低下，浪费严重。运输经营管理落后是一个重要问题，表现为先进的管理手段采用较少，管理方法落后，一般仍凭经验调度，调度质量差、优化程度低，空驶率高、严重浪费，不能充分发挥运输工具的效能。而在国外一些发达国家，货运车辆优化调度己广泛地运用于生产、生活的各个方面，如报纸投递线路的优化、牛奶送达线路优化、电话预定货物的车辆线路设计、垃圾车的线路优化及垃圾站选址优化、连锁商店的送货线路优化等等为了改善货物运输的质量状况，充分发挥运输车辆的效能，除了进一步扩大和改善城市道路系统和交通设施之外，加强运输的科学组织管理也是极其重要的一个方面而且从所需投资和见效迅速等方面考虑，后者往往更为现实，从而意义更大经济的发展要求协调的综合运输体系支持，即整个运输形成网络，这样对相应的组织管理也提出了更高的要求。因此，加强货运组织的科学管理，对货运车辆进