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