车辆调度算法研究及其应用【开题报告】.doc

1、 毕业设计开题报告 计算机科学与技术 车辆调度算法研究及其应用 一、选题的背景、意义 1959 年， Dantzig 等人首先从旅行商问题（ Traveling Salesman Problem，简称 TSP 问题，）得到启发，提出了车辆分配问题 TDP（ Truck Dispatching Problem）。这是一类具有重要研究价值的问题。一方面，它代表了一类典型的组合优化问题，具有深远的理论意义；另一方面，它是一类重要的物流运输问题，直接影响着相关企业的运转效率，具有广泛的实践意义。半个世纪以来，许多的专家学者对该 问题进行了广泛而深入的研究，并将这类问题统称为车辆路径调度问题（ Vehi

2、cle Routing Problem，简称为 VRP 问题）。他们从基本问题出发，根据不同的约束和目标，构建了不同的模型，并有针对性地开发出了有效的算法。 当前，现代物流已被公认为是企业在降低物质消耗、提高劳动生产率以及创造利润的第三个重要源泉，也是企业降低生产经营成本，提高产品市场竞争力的重要途径。配送是物流系统中的一个重要环节，它是指按客户的订货要求，在物流中心进行分货、配货工作，并将配好的货物及时送交收货人的物流活动。在配送业务中 ，配送车辆调度问题的涉及面较广，需要考虑的因素较多，对配送企业提高服务质量、降低物流成本、增加经济效益的影响也较大。该问题包括集货线路优化、货物配装及送货线

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

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

5、距离最短。 物流配送车辆管理系统的研究 物流配送车辆管理系统的研究主要是提供给管理人员的一个平台，方便管理人员对车辆的调度管理。系统集节约算法与数据库管理分析于一体，进行货物配送方案的优化，并以报表形式 向用户提供方案。总体内容为：基础数据库建立、信息维护、运输计划制定、查询、统计分析、系统管理。 系统的功能模块图如 1 所示。 物流配送车辆管理系统 系统管理 分析查询 信息管理 运输计划确定 系统导航 用户权限管理 日常数据管理 需求计划表 货运计划查询 司机信息查询 车辆信息查询 多车运输计划 单车运输计划 最优化路径 商品目录 车辆 司机 无时间窗 有时间窗 图 1 系统功能模块图 2.

6、 拟解决的主要问题 算法研究主要解决的问题 深入研究节约算法，改进节约算法，并将此算法应用于 物流配送车辆管理系统。 物流配送车辆管理系统解决的问题 基础数据库建立：将收集到的用户、车辆、司机信息录入系统，并可做相应修改。 信息维护：输入货物需求 计划，并对建好后的基础数据发生变化时进行处理。 运输计划制定：通过车辆优化调度模型的计算，形成优化配送方案。具体可以求解任意两点间的最优路径；求一天内所有货运任务的分派方案。 查询：系统可按照给定的查询条件从不同方面查询用户、车辆、司机和运输货物信息。 统计分析：系统可按照给定的统计条件从不同方面统计分析用户、车辆、司机和运输货物信息。 系统管理：提

7、供整个系统的管理和维护功能。 三、研究的方法与技术路线、研究难点，预期达到的目标 1. 研究方法 由于本课题一方面是对车辆调度 算法的研究，主要是通过对文献的研究 、 整理来得出结论 ; 另一方面是对物流配送车辆管理系统的研究， 通过阅读大量关于物流配送车辆管理的文献，根据相关文献，对系统进行需求分析和可行性分析，从而确定自己的研究方向和实现方法。通过数据库设计方法使用 SQLserver 设计出结构完整并适合管理的数据库。最后运用面向对象编程工具 VB.NET，来完成服装电子商务管理系统的开发。 2. 技术路线 阅读研究相关文献，提出配送路线优化算法。 查询相关资料，了解物流配送车辆管理系统

8、的研究意义。 通过查询资料了解该系统要如何 做，及要做那些东西。 设计出大体功能模块，画出功能模块图。 通过进一步的了解，对每个功能模块进行细化，将每一部想清楚。制定出每一步的做法和注意的地方。 根据功能要求进行数据库设计。 代码设计。 对设计好的程序进行调试，完善系统。 整理各阶段的设计记录文档，写成论文稿。 技术路线如图 2 所示。 图 2 技术路线图 3. 研究难点 对节约法的优缺点比较，通过比较提出节约法的改进建议。 、以改进的节约法设计物流配送车辆管理系统。如系 统功能模块图的确定，数据库的建立。由于需要对整个系统有一定的概念形成，对系统需要实现的功能明确，才能画出系统的功能模块图从

9、而建立数据库着两项又是建立系统的基础。因此系统功能模块图的确定，数据库的建立成为了建立系统的难点。 4. 预期达到目标 提出配送优化算法路线 了解系统的研究意义 了解系统的制作方法 画出功能模块图 细化功能模块 数据库设计 整理文档写成论文 文献研究法 数据库研究法 代码编写 完善系统 面向对象程序设计法 软件工程研究法 通过节约法在物流配送上的应用为例对节约算法（ C-W 算法）进行研究。得到 全局最优解，并将此算法应用于物流配送车辆管理系统中。 系统集节约算法与数据库管理分析于一体，进行货物配送方案的优化，并以报表形式向用户提供方案。实现基础数据库建立、信息维护、运输计划制定、查询、统计分

10、 析、系统管理功能。 四、论文详细工作进度和安排 1.第七学期第 12 周至第 17 周 ： 阅读有关参考文献，进行相关文献检索和资料收集，完成毕业论文（设计）的开题报告和外文翻译的撰写工作；初步拟定实现系统需要采取的研究方法和技术路线；完成系统开发语言和开发平台等相关技术的学习。 2.第七学期第 18 周至第 19 周及寒假 ： 继续查询并收集资料；确定车辆调度的优化方案；完成毕业论文大纲的撰写。 3.第八学期第 1 周至第 3 周 ： 选择具体实例，并对具体实例进行详细分析；完成毕业论文的初稿撰写。 4.第八学期第 4 周至第 6 周 ： 对车 辆调度优化方案加以实现；完成测试用例的设计；

11、继续撰写并修改毕业论文。 5.第八学期第 7 周至第 10 周 ： 完成应用实例的分析和设计；继续撰写并修改毕业论文。 6.第八学期第 11 周至第 12 周 ： 进行算法的测试和完善；完成毕业论文的定稿。 7.第八学期第 13 周至第 14 周 ： 提交毕业论文；准备毕业答辩各项事宜。 五、主要参考文献： 1王晓东 .计算机算法设计与分析 M北京 :电子工业出版社 ,2004. 2李长林 ,张丽华 ,王红 Visual Basic 数据库应用系统开发 M.北京 :电子工业出版社 ,2005. 3赵振华 ,王杰 ,娄春 .基于物流配送中车辆路径问题的模型及算法的研究 EB/OL.http:/

12、www.lunwentianxia.free.10001560.3/:2009-2-19. 4杨燕旋 ,宋士吉 .车辆调度问题的启发式算法综述 D.北京 ：清华大学自动化系， 2007. 5李艺 ,周宇 .考虑时间窗限制条件的配送路线节约法改进 J.中国储运 .2010.(8):98-99. 6姜福川 ,吕传红 .基于节约法在优化配送路线的研究 J.辽宁工程技术大学学报 (社会科学版 ).2003,5(5):54-56. 7张岩 .物流配送车辆路径智能优化方法研究 D.天津 :天津大学 ,2006. 8柳伍生 ,刘军 .一种改进节约法在车辆配送路径优化中的应用 J.现代交通技术 .2007,4

13、(6):72-78. 9袁际军 .现代物流配送优化研究 D.武汉 :武汉理工大学 ,2004. 10A.E.Rizzoli,F.Oliverio,R.Montemanni,L.M.Gambardella.Ant Colony Optimisation for vehicle routing problems:from theory to applicationsEB/OL. http:/www.idsia.ch/idsiareport/IDSIA-15-04.pdf:2010-12-12. 11Brian Henderson-Sellers. Object-Oriented Software Engineering MethodsJ. International Handbooks Information System.2006,(2): 485-519. 12Surajit Chaudhuri,Kris Ganjam,Venky Ganti,Vivek Narasayya,Theodore Vassilakis. Fuzzy Lookup and Fuzzy Grouping in SQL Server Integration Services 2005EB/OL. http:/