车辆调度算法研究及其应用【毕业设计】.doc

1、 本科 毕业 设计 (论文 ) （二零 届） 车辆调度算法研究及其应用 所在学院 专业班级 计算机科学与技术 学生姓名 学号 指导教师 职称 完成日期 年 月 摘要 ： 随着物流业的蓬勃发展，特别是专业物流公司的出现，降低物流成本正成为企业的第三利润源，这使得人们越来越关注物流成本的下降，降低 运输成本对降低物流成本有举足轻重的作用。车辆调度问题是物流运输研究领域内一个非常重要的问题。 论文首先对车辆调度问题进行了简单的描述 ,介绍了车辆调度算法的一些基本理论及当前相关的一些实际问题，给出了相应的 VRP 解决方法 ,并对动态车辆调度和静态车辆调度进行了比较。其次对最典型的启发式算法 节约算法

2、单独作了介绍，最后提出了其改进算法，并将改进后的算法应用于物流信息管理系统的设计中。物流信息管理系统实现了货物托运管理和信息查询等功能。 关键词 ： 车辆调度；物流配送；动态车辆调度 ;物流信息管理系统 Vehicle Scheduling Algorithms And Its Application Abstract: Reduce logistics cost is becoming the third profit source with the vigorous development of the logistics industry, especially professional

3、 logistics companys appearance. This makes people pay more and more attention to the logistics cost and to reduce the transportation cost down to reduce logistics cost a pivotal role. Vehicle scheduling problem is logistics transportation research field is a very important question. In this paper, t

4、he problems of the vehicle scheduling, some basic theories of the vehicle scheduling algorithm, and the current practical issues related were simply described firstly,the corresponding VRP solution was determined, and dynamic and static vehicle scheduling were compared. Secondly, the most typical he

5、uristic algorithm- saving algorithm was introduced separately, finally the improved algorithm was proposed and used in the design of logistics information management system. The functions of cargo shipment management and information query could be realized in this system. Keywords: vehicle schedulin

6、g; logistics distribution; dynamic vehicle scheduling; logistics information management system 目 录 1 绪论 . - 1 - 1.1 课题的研究背景 . - 1 - 1.1.1 车辆调度 问题研究的历史背景 . - 1 - 1.1.2 车辆调度 问题 算法 的发展现状 . - 1 - 1.2 课题研究的目的与意义 . - 2 - 1.3 课题的研究内容 . - 2 - 1.4 课题的研究方法 . - 3 - 1.5 论文的组织 . - 3 - 2 基础知识简介 . - 5 - 2.1 数据库技术

7、. - 5 - 2.1.1 数据库设计的基本步骤 . - 5 - 2.1.2 数据库设计的原则 . - 6 - 2.2 VB 语言 . - 6 - 3 车辆调度算法概述 . - 8 - 3.1 车辆调度算法的提出及其分类 . - 8 - 3.2 动态车辆调度问题和静态车辆调度问题 . - 8 - 3.3 配送车辆调度问题的描述 . - 10 - 3.4 配送车辆调度问题的构成要素分析 .- 11 - 3.5 配送车辆调度问题的分类 . - 13 - 4 车辆调度算法基本理论 . - 15 - 4.1 组合优化与计算复杂性 . - 15 - 4.1.1 组合优化问题 . - 15 - 4.1.2

8、 算法及算法分析 . - 15 - 4.2 启发式算法理论 . - 18 - 5 车辆调度算法基本问题 . - 20 - 5.1 旅行商问题 . - 20 - 5.1.1 概述 . - 20 - 5.1.2 TSP 的算法分析 . - 20 - 5.2 最短路径问题 . - 23 - 5.2.1 概述 . - 23 - 5.2.2 最短路径问题的算法分析 . - 23 - 5.3 最少费用流问 题 . - 25 - 5.3.1 概述 . - 25 - 5.3.2 最少费用流问题算法描述 . - 25 - 5.4 中国邮递员问题 . - 27 - 5.4.1 概述 . - 27 - 5.4.2

9、算法描述 . - 28 - 6 节约算法在车辆调度中的应用 . - 32 - 6.1 引言 . - 32 - 6.2 节约算法 . - 32 - 6.2.1 节约量公式 . - 32 - 6.2.2 节约算法的思路和程序 . - 32 - 6.2.3 节约法计算实例 . - 33 - 6.3 C-W 在装配企业采购物流中的应用 . - 36 - 6.3.1 C-W 算法在配送领域的应用 . - 36 - 6.3.2 C-W 法在采购领域的应用条件 . - 37 - 6.4 C-K 节约算法在配载车辆调度问题上的应用 . - 37 - 6.5 基于节约算法的多车种分送式运输模型 . - 38 -

10、 6.5.1 问题描述 . - 38 - 6.5.2 模型分析 . - 39 - 6.5.3 算法及求解步骤 . - 39 - 6.6 车辆路线安排的一种改进的节约算法 . - 41 - 6.6.1 改进的节约法的思路和程序 . - 42 - 6.6.2 计算实例 . - 42 - 7 车辆调度算法应用 物流管理系统 . - 45 - 7.1 系统目标 . - 45 - 7.2 适用范围 . - 45 - 7.3 运行环境 . - 45 - 7.4 系统分析 . - 45 - 7.4.1 需求分析 . - 45 - 7.4.2 数据流程分析 . - 46 - 7.5 系统功能确定 . - 47

11、 - 7.6 系统功能实现 . - 47 - 7.6.1 主界面的实现 . - 47 - 7.6.2 基本信息设置模块的实现 . - 48 - 7.6.3 货物 管理模块的实现 . - 49 - 7.6.4 信息查询模块的实现 . - 50 - 7.6.5 系统管理模块的实现 . - 51 - 7.6.5 主要算法 代码 . - 52 - 8 总结及展望 . - 56 - 8.1 本文总结 . - 56 - 8.2 展望 . - 56 - 致 谢 . 错误 !未定义书签。 参考文献 . - 57 - - 1 - 1 绪论 1.1 课题的研究背景 1.1.1 车辆调度 问题研究的历史背景 195

12、9 年， Dantzig 等人首先从旅行商问题（ Traveling Salesman Problem，简称 TSP 问题，）得到启发，提出了车辆分配问题 TDP（ Truck Dispatching Problem）。这是一类具有重要研究价值的问题。一方面，它代表了一类典型的组合优化问题，具有深远的理论意义；另一方面，它是一类重要的物流运输问题，直接影响着相关企业的运转效率，具有广泛的实践意义。半个世纪以来，许多的专家学者对该问题进行了广泛而深入的研究，并将这类问题统称为车辆路径调度问题（ Vehicle Routing Problem，简称为 VRP 问题）。他们从基本问题出发，根据不同的

13、约束和目标，构 建了不同的模型，并有针对性地开发出了有效的算法 1。 1.1.2 车辆调度 问题 算法的发展现状 随着定位导航技术、数据通讯技术、自动控制技术、图像分析技术以及计算机网络和信息处理技术的快速发展，车辆优化调度问题作为智能交通系统的一个重要组成部分，在很多国家受到关注。 80年代以来，随着 ITS研究领域和内容的不断深入发展，逐渐形成了美国、欧洲和日本三大智能交通体系，且三大体系研究方面各有侧重。目前，某些常用且较成熟的算法并已被人们运用的有实际的动态车辆调度系统，美国利用最短路径算法、启发式算法开发计算机配送调度 系统用来解决货运汽车作业计划路线优化选择和车辆分配等问题，使汽车

14、里程利用率提高 5%-15%，运输成本和运输时间也有了明显下降。目前已经开发并应用于实践的动态车辆调度系统有美国 IBM公司开发的 VIIPX系统，其核心算法为最短路径算法和启发式算法；日本富士通公司开发的 VSS系统，以节约为核心算法；美国美孚公司开发的 HOCAD系统，以扫描为核心算法。 由于该问题在交通运输、工业生产管理等领域具有广泛而重要的应用，因此近年来引起了人们极大的兴趣，运筹学、应用数学、组合数学、网络分析、图论、计算机应用等学科的专家与运 输计算制定者和管理者进行了大量的理论研究及实验析，取得了很大的进展。运用这些研究成果，车辆优化调度问题已被成功运用到邮件速递、出租车服务、奶

15、品配送、生产计划、紧急服务等业务之中。车辆的优化调度问题是一种具有相当广泛实用价值的学术研究- 2 - 问题，在理论上属于复杂的组合优化问题。 当前，现代物流已被公认为是企业在降低物质消耗、提高劳动生产率以外创造利润的第三个重要源泉，也是企业降低生产经营成本，提高产品市场竞争力的重要途径。配送是物流系统中的一个重要环节，它是指按客户的订货要求，在物流中心进行分货、配货工作，并将配好 的货物及时送交收货人的物流活动。在配送业务中，配送车辆调度问题的涉及面较广，需要考虑的因素较多，对配送企业提高服务质量、降低物流成本、增加经济效益的影响也较大。该问题包括集货线路优化、货物配装及送货线路优化等，是配

16、送系统优化的关键 2。 1.2 课题研究的目的与意义 国外将配送车辆调度问题归结为 VRP（ Vehicle Routing Problem，即车辆路径问题）、VSP（ Vehicle Scheduling Problem，即车辆调度问题）和 MTSP（ Multiple Traveling Salesman Problem，即多路旅行商问题）。该问题于 1959年由 Dantzig和 Ramser提出后，很快便引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家以及运输计划制定者的极大重视，并一直是运筹学与组合优化领域的前沿与热点问题。在现实生产和生活中，邮政投递

17、问题、车船调度问题、电力调度问题、管道铺设问题、计算机网络拓扑设计问题等都可以抽象为配送车辆调度问题。可见，研究配送车辆调度问题具有重要的理论和现实意义。 1.3 课题的研究内容 本课题研究旨在通过应用动态规划思想， 改进求解 VRP问题的节约法，建立不断增加节约量的动态规划数学模型，使其能够得到全局最优解，并将此算法应用于物流配送管理车辆系统中。具体内容叙述如下： 算法研究 对多种车辆路径优化的算法进行简述比较，主要对节约法进行研究。简述节约算法的原理，实现途径；对节约法的优缺点进行分析，在此基础上提出节约法的改进意见，并以节约法为基础，提出一个配送计划的制定规划及步骤，使运输行驶总距离最短

18、。 物流配送车辆管理系统的研究 物流配送车辆管理系统的研究主要是提供给管理人员的一个平台，方便管理人员对车辆的调度管理。系统 集节约算法与数据库管理分析于一体，进行货物配送方案的优化，并以报- 3 - 表形式向用户提供方案。总体内容为：基础数据库建立、信息维护、运输计划制定、查询、统计分析、系统管理。系统功能模块如图 1-1所示： 物 流 管 理 系 统信息查询货物托运管理基本信息设置系统管理退出系统车辆资料司机资料客户资料货物配送跟踪车辆调度安排货物托运信息车辆在途跟踪车辆调度信息数据清理用户管理数据备份图 1-1 物流管理系统功能模块图 1.4 课题的研究方法 由于本课题一方面是对车辆调度

19、算法的研究，主要是通过对文献的研究、整理来得出结论 ; 另一方面是对物流配送车辆管理系统的研究，通过阅读大量关于物流配送车辆管理的文献，根据相关文献，对系统进行需求分析和可行 性分析，从而确定自己的研究方向和实现方法。通过数据库设计方法使用 SQLserver设计出结构完整并适合管理的数据库。最后运用面向对象编程工具 VB.NET，来完成物流配送车辆管理系统的开发。 1.5 论文的组织 论文共有八章，其中第一章绪论，说明问题课题研究背景、课题研究意义、课题研究内容和课题研究方法；第二章基础知识简介，对论文中用到的一些基础的知识进行概括性的介绍； 第三章车辆调度算法概述，说明车辆调度算法的提出及其分类，对动态车辆调度算法和- 4 - 静态车辆调度算法进行分别介绍，并叙述车辆调度算法在物流中的应用和其 应用分类；第四章 车辆调度算法基本理论，介绍了组合优化问题，车辆调度问题的算法求解；第五章车辆调度算法基本问题，介绍了旅行商问题、最短路径问题 200753225103、最小费用流问题和中国邮递员问； 第六章约算法在车辆调度中的应用，介绍节约算法，对引用前人相对于节约算法提出的解决模型，研究改进了的节约算法，并研究分析了节约算法在物流上应用；第七章车辆调度算法计算机实现 物流管理系统介绍，介绍物流管理系统的设计与实现；第八章总结及展望：对本文进行总结并对进一步研究做出展望。