课程设计 有时间窗的车辆调度优化问题.docVIP

目录 目录 1 第一章 课程设计的目的及意义 2 第二章 课程设计的题目及要求 2 2.1 配送车辆调度问题的描述 2 2.2任务的特征及要求 5 第三章 题目分析 6 3.1一般VSP模型 6 3.2 时间窗VSP模型 8 3.3 关于时间窗的宽度 8 第四章 计算原理及流程图 9 4.1算法原理 9 4.2 流程图 11 第五章 计算过程 11 5.1计算各点对间连接的费用节约值 11 5.2构造线路 12 第六章 算法的总结与分析 15 6.1处理其他的约束 15 6.2算法的进一步讨论 15 6.3算法的推广 15 6.4结论 16 附录一 代码设计 18 第一章 课程设计的目的及意义 《运输组织学》是交通运输类专业的一门必修专业课，通过理论教学环节，是同学们了解公路运输的基本理论和基本方法，并可以初步掌握公路运输企业生产组织管理的基本理论、基本方法，使同学们具备进行公路运输企业组织管理的基本知识。 课程设计是理论教学环节的延伸。是对学生们的一次实战演练，通过课程设计，以检验和提高学生运用所学理论知识解决实际问题的能力，使学生较全面和系统的实践交通运输组织的基本理论，方法和技能，初步具备运用现代化科学方法进行公路运输生产组织管理的能力，完成培养公路运输业高级管理人才所需的运输组织管理方面的专业知识和技能的基本训练。 当前，现代物流已被公认为是企业在降低物质消耗、提高劳动生产率以外创造利润的第三个重要源泉，也是企业降低生产经营成本，提高产品市场竞争力的重要途径[1]。配送是物流系统中的一个重要环节，它是指按客户的订货要求，在物流中心进行分货、配货工作，并将配好的货物及时送交收货人的物流活动。在配送业务中，配送车辆调度问题的涉及面较广，需要考虑的因素较多，对配送企业提高服务质量、降低物流成本、增加经济效益的影响也较大。该问题包括集货线路优化、货物配装及送货线路优化等，是配送系统优化的关键。 国外将配送车辆调度问题归结为VRP（Vehicle Routing Problem，即车辆路径问题）、VSP（Vehicle Scheduling Problem，即车辆调度问题）和MTSP（Multiple Traveling Salesman Problem，即多路旅行商问题）。该问题于1959年由Dantzig和Ramser提出后[2]，很快便引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家以及运输计划制定者的极大重视，并一直是运筹学与组合优化领域的前沿与热点问题。在现实生产和生活中，邮政投递问题、车船调度问题、电力调度问题、管道铺设问题、计算机网络拓扑设计问题等都可以抽象为配送车辆调度问题。可见，研究配送车辆调度问题具有重要的理论和现实意义。 第二章 课程设计的题目及要求 2.1 配送车辆调度问题的描述 配送车辆调度问题可以描述为：在一个存在供求关系的系统中，有若干台车辆、若干个物流中心和客户，要求合理安排车辆的行车路线和出行时间，从而在给定的约束条件下，把客户需求的货物从物流中心送到客户，把客户供应的货物从客户取到物流中心，并使目标函数取得优化。 配送车辆调度问题可归结为如下的一般网络模型[3]：设G=（V，E，A）是一个连通的混合网络，V是顶点集（表示物流中心、客户、停车场等），E、A分别为无向的边集和有向的弧集，E中的边和A中的弧均被赋权（可以表示配送的距离、时间或费用），V’、E’、A’分别为V、E、A的子集，求满足约束条件（包括客户的货物需求或供应数量约束、需求或供应时间约束、配送车辆一次配送的最大行驶距离约束、车辆的最大载重量约束等），并包含V’、E’、A’的一些巡回路线，使目标函数取得优化，目标函数可以取配送总里程最短、 2 配送车辆总吨位公里数最少、配送总费用最低、配送总时间最少、使用的配送车辆数最少、配送车辆的满载率最高等。 3 配送车辆调度问题的构成要素分析 配送车辆调度问题主要包括货物、车辆、物流中心、客户、运输网络、约束条件和目标 函数等要素。 （1）货物。货物是配送的对象。可将每个客户需求（或供应）的货物看成一批货物。每批货物都包括品名、包装、重量、体积、要求送到（或取走）的时间和地点、能否分批配送等属性。 货物的品名和包装，是选用配送车辆的类型以及决定该批货物能否与其它货物装在同一车辆内的依据。例如，一些货物因性质特殊需要使用专用车辆装运；一些货物因性质特殊不能与其它货物装在同一车辆内；一些货物虽然性质特殊，但由于包装条件很好，故也能与其它货物装在同一车辆内。 货物的重量和体积是进行车辆装载决策的依据。当某个客户需求（或供应）货物的重量或体积超过配送车辆的最大装载重量或容积时，则该客户将需要多台车辆进行配送。 货物的送到（或取走