多顺序时段批量批次货物运输车辆调度方法研究物流工程

安徽工业大学管理科学与工程学院 多顺序时段批量批次货物运输的车辆调度方法研究 共 53 页 第 1 页 装 订 线 多顺序时段批量批次货物运输的车辆调度方多顺序时段批量批次货物运输的车辆调度方 法研究法研究 物流工程 吴传良 089094232 指导教师：胡钢 副教授 摘要摘要 随着经济全球化时代的到来， 现代物流业发展的步伐日益加快， 国际以及国内物 流公司之间的竞争也愈演愈烈。目前，物流公司通过各种手段来降低物流成本，目的 是为了获得更大的市场份额以及谋取更多的利益。 而在国内物流成本构成比例中， 运 输所占比例高达百分之五十以上， 所以， 降低运输成本是国内物流业发展的必然趋势。 目前国内大多数运输还是以公路运输为主， 本文所研究的多顺序时段批量批次货物运 输的车辆调度问题就是通过对车辆进行有计划、 科学、 准确的调度以达到降低物流成 本的目的。 首先， 本文在对车辆调度问题的国内外研究现状进行了详细综述分析之后， 对车 辆调度问题进行了深入探讨， 将货物运输的车辆调度问题的各种约束条件逐一关联分 析。 其次， 针对多顺序时段内变化的速度， 本文采用线性最小二乘拟合方法以及相关 数学知识将变化的速度量化。 本文在加入时间窗约束、 容量约束的基础之上构建了多 顺序时段批量批次货物运输的车辆调度的数学模型。同时，通过lingo语言编程对小 规模车辆路径问题进行了合理优化，并且验证了所建数学模型的可行性。 最后，对车辆调度算法进行比较研究，针对基本蚁群算法进行相关改进，并通过 实例分析，对比了基本蚁群算法以及改进后蚁群算法的寻优结果。 关键词关键词： 车辆调度；曲线拟合；蚁群算法 安徽工业大学管理科学与工程学院 多顺序时段批量批次货物运输的车辆调度方法研究 共 53 页 第2页 装 订 线 Abstract With the arrival of the era of economic globalization, the development of modern logistics industry step speed up day by day, the international and domestic logistics company between competition has intensified. At present, the logistics company by any measure to reduce logistics costs, the purpose is to have a bigger share of the market and to seek more benefits. And in domestic logistics cost structure in proportion, transportation proportion of as much as fifty percent or more, so, reduce the transportation cost is the inevitable trend of the development of domestic logistics industry. At present the domestic majority transportation by the highway transportation primarily, the multi-smooth time interval batch raid of goods traffics vehicles scheduling problem which this article studies is through carries on to the vehicles has the plan, the science, the accurate dispatch to achieve reduces the physical distribution cost the goal. First, this article in has carried on the detailed summary analysis after the vehicles scheduling problems domestic and foreign research present situation, to the vehicles scheduling problem has carried on the thorough discussion, is connected the analysis one by one goods traffics vehicles scheduling problems each kind of constraints. Next, the speed which changes in view of the multi-smooth time interval, this article uses the linearity to be smallest two rides the speed quantification which the fitting method as well as the related mathematics knowledge will change. This article in joined the time window restraint, above the capacity restraint foundation to construct the multi-smooth time interval batch raid of goods traffics vehicles dispatch mathematical model. At the same time, has carried on the reasonable optimization through the lingo language programming to the small scale vehicles way question, and confirmed has constructed the mathematical model the feasibility. Finally, carries on to the vehicles dispatch algorithm quite studies, makes the related improvement in view of the basic ant group algorithm, and through the example analysis, after having contrasted the basic ant group algorithm as well as the improvement, the ant group algorithm optimization result. Keywords: vehicle scheduling；curve fitting,；Ant Colony algorithms 安徽工业大学管理科学与工程学院 多顺序时段批量批次货物运输的车辆调度方法研究 共 53 页 第3页 装 订 线 1绪论 1.1 研究背景及意义 1.1.1 研究背景 2012 年，中国市场的货物运输总量有望达到 125 万亿人民币，现代物流业的发 展前景被各行各业人员看好。现代物流（modern times Logistics）是指将信息、运 输、仓储、库存、装卸搬运以及包装等物流活动综合起来的一种新型的集成式管理， 其宗旨是尽可能降低物流的总成本， 为顾客提供最好的服务。 现代物流业已经被人们 公认为除第一利润来源“资源领域”和第二利润来源“人力领域”以外的第三利润来 源。 在 1980 年的全美物资讨论会上，研究者们就指出，在产品的整个生产过程中， 仅有 5%的时间用于加工和制造，剩余的 95%都用于储存、装卸、等待加工和输送。其 中运输和存储所占比重较大，下图数据来自中国物流与采购联合会网站，该图反映 2011 年国内重点物流企业物流成本构成情况。 运输成本 53% 管理成本 16% 保管成本 31% 图 1-1 国内重点企业物流成本构成图 由图 1-1 知，在国内，运输仍然是国内物流业成本构成的主要功能元素，2012 年预计国内物流业占 GDP 比重达 18%，这一比例为欧美国家的两倍。在欧美国家，运 输成本所占物流成本的构成比例较小， 其管理成本所占比例较大， 而我国应借鉴国外 的管理经验， 对国内物流成本中各功能元素构成比例进行调节， 从而达到国内物流业 全方位的改善；从微观上来说，应针对物流各功能元素进行有效管理，从而达到各功 能元素成本的降低。而目前在国内，降低物流运输成本是实现这一目标的重要手段， 运输成本的降低将提高物流配送效率，提高企业的服务质量，降低企业的运营成本， 增加企业的经济效益。 1.1.2 研究意义 车辆运输是物流中一个直接与消费者相连的环节， 也是物流公司成本的重要组成 安徽工业大学管理科学与工程学院 多顺序时段批量批次货物运输的车辆调度方法研究 共 53 页 第4页 装 订 线 部分，由图 1-1 数据显示我国物流业中运输占物流费用的百分之五十三左右，所以， 对于车辆调度方法的研究关系到物流企业的利益以及消费者的利益， 而对运输车辆进 行优化调度，可以均衡物流企业与消费者之间的利益，从而实现物流科学化。 车辆调度问题是在 1959 年由 Dantzig 和 Ramser 提出的 1，车辆调度需要结合许 多学科的相关知识，对车辆调度问题的理论与方法进行系统研究是物流集约化发展、 构建综合物流系统、 建立现代调度指挥系统、 发展智能交通运输系统和开展电子商务 的基础。 车辆运输调度问题应用前景广阔，一直成为运筹学与组合优化领域的研究热点。 最近几十年来， 对车辆运输调度问题的研究取得了很多有意义的成果， 已经广泛用于 生产、生活的各个方面，如报纸或货物投递、出租车调度和包裹快递等。 1.2 国内外研究现状 1.2.1 国外研究现状 上世纪 50 年代末 Dantzig 和 Ramser 提出了车辆调度问题， 他们主要描述了如何 将汽油如何科学合理的送达各加油站并建立了相关数学模型以及求解算法。 自他们以 后，大量学者开始对车辆调度问题进行深入研究，1962 年 Blinski 提出了在可行解 基础上进行优化的车辆调度优化模型 2。1971 年，Eilon 等学者采用动态规划的思想 解决固定车辆的车辆调度问题 3。1974 年,Wren 等人提出了扫描算法4。1991 年 Gendreau 等人提出启发式算法：禁忌搜索法解决车辆调度问题 5。1985 年，Laporte 和 Nobert 等人探讨了带距离和容量限制的车辆优化调度问题 6。1987 年，Solomon 和 Desrosier 等人最早把时间窗约束加入车辆优化调度问题中 7。1993 年， E.Taillard 等人利用禁忌搜索和模拟退火算法，实现了求解车辆调度问题的并行化 8。1996 年，J.Lawrence 采用另一种启发式算法：遗传算法，之后遗传算法开始大 量运用于车辆调度问题研究 9。1991 年，M.Dorigo 和他的同事们提出了蚁群优化算 法 10，蚁群算法成功解决了 TSP（旅行商）问题，后来许多学者在其基础上进行改进， 并大量应用于车辆调度问题中。可以说，20 世纪 90 年代以后，启发式算法是车辆优 化调度问题的主导方法。 1.2.2 国内研究现状 在国内，对于车辆调度问题的研究较少，上世纪 90 年代以后才发展起来。国内 学者通过外文资料以及自身对车辆调度问题的独到见解， 在车辆调度问题上也取得了 不少成果。郎茂祥对于车辆调度问题的研究可谓颇深，在其出版的配送车辆优化调 度模型与算法 一书中， 阐述了各类配送车辆优化调度问题的数学模型及其优化算法 11。2001 年，李军、郭耀煌在物流配送车辆优化调度理论与方法一书中以配送 货运车辆为研究对象， 将车辆调度问题分为满载以及非满载的车辆调度问题 12。 2000 年以后，国内大量学者开始采用通过现代启发式算法：如禁忌搜索算法、模拟退火算 法、基本遗传算法、混合遗传算法等等，解决了不同性质的车辆调度问题。马华伟、 安徽工业大学管理科学与工程学院 多顺序时段批量批次货物运输的车辆调度方法研究 共 53 页 第5页 装 订 线 左春荣等人通过建立数学模型， 以及设计出一种新的两阶段启发式算法很好的解决了 多时间窗的车辆调度问题 13。 乔文山对车辆调度中的货物配装问题和车辆路径问题进 行描述并构建问题的求解模型 14。 郭倩倩对蚁群算法做了相关改进并成功运用于车辆 调度中的路径问题 15。 魏晓明利用禁忌搜索算法对多站点、 带时间窗的定位路线的车 辆调度问题进行了深入研究 16。 1.3 论文的主要研究内容及技术路线 1.3.1 论文的主要研究内容 本文主要研究货物运输车辆调度问题中的车辆行驶路径的优化， 本文综合考虑以 下约束条件进行了车辆路径问题的优化： 多顺序时段内车速是不断变化的、 货物运输 的批量批次约束、客户时间窗要求。 本文主要内容如下： （1）通过采用曲线拟合以及定积分和夹逼准则的思想，将多顺序时段内随时间 变化的速度进行量化处理。 （2）在对变化速度的量化及时间窗函数建立基础之上，构建了多顺序时段批量 批次货物运输的车辆调度优化模型，并用 lingo 软件验证了所建模型的可行性。 （3）通过对基本蚁群算法的分析，设计出一种新的蚁群算法，并在实例分析中 分别采用基本蚁群算法和改进的蚁群算法进行了物流配送路径的优化。 1.3.2 论文的技术路线 论文采用理论分析和实验仿真（lingo、MATLAB）研究相结合的方法。通过分析 国内外学者专家对车辆调度问题的研究方法， 并针对本文研究的具体问题， 提出了多 顺序时段变化速度量化的方法， 并且构建了时间窗的惩罚成本函数， 最终建立了有时 间窗约束的多顺序时段批量批次的车辆调度问题的数学模型。 另外，本文借助于仿真 软件 lingo 验证了模型的准确性，借助于 matlab 编程实现了基本蚁群算法和改进蚁 群算法在车辆路径优化问题中的运用。 安徽工业大学管理科学与工程学院 多顺序时段批量批次货物运输的车辆调度方法研究 共 53 页 第6页 装 订 线 资料收集，作为知识储备 利用曲线拟合及高等数学相关内容将变 化的速度量化 对基本蚁群算法进行研究分析 结合车辆调度问题重新设计蚁群算法 编写matlab基本蚁群算法程序进行案例 仿真分析 Lingo小规模数据检验模型 建立有时间窗约束的多顺序时段批量批 次的车辆调度问题的数学模型 NO YES 编写matlab改进后蚁群算法程序进行案 例仿真分析 总结与展望 图 1-2 本文研究的技术路线 1.4 论文的组织结构 本文各章节具体内容如下： 第一章， 首先对论文的选题背景及研究意义进行了概述； 其次对车辆调度问题的 国内外相关研究现状进行了综述； 最后介绍了论文的主要研究内容、 技术路线和论文 的组织结构。 第二章， 首先对本文几个相关概念进行了概述； 然后针对车辆调度问题的分类进 安徽工业大学管理科学与工程学院 多顺序时段批量批次货物运输的车辆调度方法研究 共 53 页 第7页 装 订 线 行详细探讨；最后对货物运输的发展现状进行分析研究。 第三章， 首先将多顺序时段中变化的速度进行量化处理； 然后建立了带时间窗约 束的多顺序时段批量批次货物运输车辆调度问题的数学模型； 最后用 lingo 软件进行 了所建模型的小规模数据验证。 第四章， 首先对车辆调度问题的现有算法进行综述； 然后对基本蚁群算法进行研 究分析； 最后则是在基本蚁群算法研究基础之上并结合了车辆调度问题的相关约束条 件，进行了蚁群算法的改进。 第五章，通过 matlab 编程对多顺序时段批量批次货物运输的车辆调度问题进行 了基本蚁群算法以及改进后蚁群算法的仿真分析。 第六章，对论文进行总结，并对论文的不足和进一步研究的内容进行了展望。 安徽工业大学管理科学与工程学院 多顺序时段批量批次货物运输的车辆调度方法研究 共 53 页 第8页 装 订 线 2多顺序时段批量批次货物运输问题综述 目前， 全世界机动车总数已达 4 亿多辆， 全世界现代交通网中， 公路线长占 2/3， 约达 2 千万公里，公路运输所完成的货物运输量占整个货物运输量的 80%左右，货物 运输根据限制条件的不同可以分为若干类别。本章将详细介绍本课题相关的几个概 念， 另外， 本章也将对货物运输车辆优化调度问题以及货物运输发展现状进行详细阐 述。 2.1 几个相关概念 2.1.1 运输及配送的概念 广义的运输是指实现人和物空间位置变化的活动， 在物流领域运输定义为用设备 和工具，将物品从一地点向另一地点运送的物流活动。而货物运输即指用车、船、飞 机等交通工具把货物从一个地方运到另一个地方。 配送是指在经济合理区域范围内， 根据客户要求， 对物品进行拣选、 加工、 包装、 分割、组配等作业，并按时送达指定地点的物流活动。 运输一般分为运输和配送。关于运输和配送的区分，有许多不同的观点，但所有 物品的移动都是运输，而配送则专指短距离、小批量的运输。因此，可以说运输是指 整体，配送则是指其中的一部分，而且配送的侧重点在于一个“配”字，它的主要意 义也体现在“配”字上；而“送”是为最终实现资源配置的“配”而服务的。 而在本文中不研究货物的 “配”， 所以货物运输可以分为干线货物运输和支线货 物运输（即配送） 。如图 2-1 所示： 工厂 工厂 配送中心 需求点 需求点 需求点 干线运输 干线运输 配送（支线运输） 配送（支线运 输） 配送（支线运输） 图 2-1 货物运输方式图 2.1.2 多顺序时段的定义 多顺序时段没有规范的定义， 但时段指的就是一段时间， 顺序时段指一系列连续 的时间段， 多顺序时段是指一系列连续时间段的宽度。 本文中车辆调度问题的多顺序 时段涉及到两个方面： 一是多顺序时段内车辆行驶速度是不断变化的； 二是多顺序时 安徽工业大学管理科学与工程学院 多顺序时段批量批次货物运输的车辆调度方法研究 共 53 页 第9页 装 订 线 段内每个顾客要求的时间窗是不同的。 这两个约束条件也是本文车辆调度问题的研究 重点。 2.1.3 批量批次的定义 批量和批次是两个不同的概念。批量，是一个数量范围；而批次，是一个典型的 标识。 在本文中每个需求点的货物需求量是确定的， 配送中心可以一次性批量组织运 输也可以分多批次组织运输， 本文研究的是车辆调度中的小批量单批次的货物运输问 题。 2.2 货物运输车辆优化调度问题分类 2.2.1 货物运输的车辆优化调度问题概述 在物流领域中， 车辆优化调度的目的是为了保证运输合理化目标的实现， 运输合 理化不仅仅要求控制物流运输成本， 还要控制运输时间以及提高顾客满意率等等， 车 辆优化调度是实现物流科学化的有效途径。 在货物运输的车辆优化调度时， 当根据空间位置安排车辆路径时称为车辆线路安 排问题（Vehicle Routing Problem,VRP）;根据时间窗安排车辆路径时称为车辆调度 问题（Vehicle Scheduling Problem,VSP）;而同时考虑空间位置和时间窗时，也可 以将其称为有时间窗要求的车辆调度问题（Vehicle Routing Problem with Time Windows,VRPTW ） 。 另 外 ， 还 有 CVRP(Capacity Vehicle Routing Problem) 、 MDVRP(Multi-Depot Vehicle Routing Problem )、SVRP(Static Vehicle Routing Problem )、DVRP(Dynamic Vehicle Routing Problem )等等。 货物运输车辆调度的实质就是： 在已知运输网络中， 根据车辆分布状况以及约束 条件， 科学合理的安排在不同时段不同地域各需求点的运输任务， 以达到用最少的投 入获得最大产出的目的。 2.2.2 货物运输车辆优化调度问题分类 货物运输车辆优化调度问题由货物、车辆、配送中心、约束条件、客户、运输网 络和目标函数等等要素组成。 而针对不同的约束条件可以将货物运输车辆优化调度分类 17，具体见表 2-1： 表 2-1 车辆运输问题分类表 目标函数目标函数 1.运输成本最低 2.顾客满意率最大 3.车辆装载率 最大 4.所需车辆最少 5.行驶路程最短 约束条件约束条件 类别类别 目标数目 1.单目标问题 2.多目标问题 车场数目 1.单车场 2.多车场 车辆种类 1.单车辆问题 2.多车辆问题 任务特征 1.纯装问题 2.纯卸问题 3.装卸混合问题 服务时间 1.软时间窗问题 2.硬时间窗问题 3.无时间窗要求 运输网络 1.有向网络 2.无向网络 3.混合问题 安徽工业大学管理科学与工程学院 多顺序时段批量批次货物运输的车辆调度方法研究 共 53 页 第10页 装 订 线 车辆容量 1.所有车辆容量约束 2.不同车型车辆容量约束 3. 没有规定 运行距离 1.所有车辆最大运行距离相同 2.不同车型车辆最大 运行距离不同 3.没有规定 运行时间 1.所有车辆最大运行时间相同 2.不同车型车辆最大 运行时间不同 3.没有规定 运输成本 1.可变成本 2.变动成本 3.延迟或等待的惩罚费用 需求点性质 1.确定型的 2.随机型的 车辆载货状况 1.满载问题 2.非满载问题 3.混合问题 其它约束 由表 2-1 可以看出， 当约束条件不同， 货物运输车辆调度问题可以被分为很多类 别， 国内外学者针对各类别也做了相当多的研究， 但车辆优化调度问题是一个有约束 的组合优化问题，属于 NP 难题（Nondeterministic Polynomial Problem） 。货物运 输车辆调度问题目标函数的建立有多种方法， 而具体要针对其问题本身的约束条件和 实际情况进行数学建模。 2.3 货物运输发展现状 通过查阅中国统计年鉴，可得到中国近几年以来主要运输方式的货运量变化图， 见图 2-2： 各运输方式货运量走势图 2001200220032004200520062007200820092010 年份 货运量 0 50000 100000 150000 200000 250000 300000 350000 400000 铁路 公路 管道 图 2-2 各种运输方式货运量走势图 由图 2-2 可知我国近年来运输业的发展基本保持着快速、 稳步的增长趋势， 而公 路运输业发展也较快， 近年来我国对交通运输业也更加重视， 虽然新一轮的经济危机 对我国经济发展产生了许多不利影响，但强大的国内需求拉动了物流运输业的发展。 所以， 未来几年我国货物运输市场规模将继续扩大， 货物运输将成为拉动国民经济的 发展重要支撑点。 货运量的不断增长也促进了物流业的迅速发展， 有关预测中国的第三方物流企业 数量将以每年 1625的速度发展。但是物流企业数量增长将会加大物流企业之 安徽工业大学管理科学与工程学院 多顺序时段批量批次货物运输的车辆调度方法研究 共 53 页 第11页 装 订 线 间的剧烈竞争， 物流企业之间都在通过各方手段增强自身企业综合竞争力。 在我国物 流业的发展比较滞后， 大多数物流企业还停留在运输和仓储运作层面上， 所以货物运 输车辆调度优化是多数物流企业降低物流运营成本的有效手段。 2.4 小结 本章首先介绍了与论文相关的几个概念， 重点阐述了多顺序时段批量批次货物运 输的含义； 然后针对车辆调度问题进行了详细分析， 指出货物运输车辆优化调度问题 由货物、车辆、配送中心、约束条件、客户、运输网络和目标函数等等要素组成，并 给出了车辆调度问题的分类表； 最后对货物运输的发展现状进行详细了详细分析并验 证了研究车辆调度问题的必要性。 3构建多顺序时段批量批次货物运输车辆调度的 数学模型 自从 1959 年 Dantzig 和 Ramser 提出车辆调度问题以来， 现实中的很多问题也就 归结到了车辆调度问题来解决，到现在车辆调度问题已经有了非常庞大的理论体系。 由于考虑问题的复杂性和角度不一样， 也已出现了各种不同的车辆调度问题， 从而也 有了不同的车辆调度模型。 本章节也将根据课题研究内容构建多顺序时段批量批次货 物运输车辆调度的数学模型。 3.1 多顺序时段批量批次货物运输问题中变化速度的量化 3.1.1 综述 传统的车辆调度问题是基于理想状态下进行优化的， 在建模时忽略了每个顺序时 段内的不稳定因素，以至于现有多数优化方法以及模型的建立的前提是车辆速度恒 定。而每个顺序时段情况不同都会对车辆速度产生影响，如早上班、晚下班高峰期车 辆的速度较慢，据有关统计在北京奥运会期间实行单双号限行后，车流量降低 27%左 右， 而车速也提高了相应的比例， 也就是说在货物运输中配送车辆速度在一天不同时 段处于动态变化并与车流量成反比。 另外，车流量的大小主要取决于两个方面，一是道路宽度，这与城市以及地域经 济发展息息相关；二是取决于每个顺序时段人们日常生活的习惯（早晨上班、晚下班 等） 。对于货物的一般配送来说，由于配送区域内经济发展程度类似并且人们的生活 习惯也类似， 所以在配送区域内可以随机选择两个配送需求点之间的车流量建立车辆 速度变化与时间的函数。 由于动态变化的速度会增加车辆调度问题的复杂程度， 本文拟采用将变化的速度 量化并结合现有车辆调度算法进行本课题的研究。 将变化的速度量化的步骤大致如下： 安徽工业大学管理科学与工程学院 多顺序时段批量批次货物运输的车辆调度方法研究 共 53 页 第12页 装 订 线 （1）首先对配送区域内配送需求点之间的路径上的车流量进行统计。 （2） 然后将数据转换为车速数据， 利用曲线拟合思想并通过 matlab 实现车辆速 度与时间函数的建立。 （3）最后将变化的速度量化，具体有两种方法： 第一种是对求出的全局函数进行求导求出最大最小值， 建立速度与偏好系数的 关系式， 通过调节的大小调节速度的值， 这种方式适合于车辆在局部时段内行驶时 通过调节大小可以改变速度数值。 第二种是对局部点进行逐步曲线拟合， 用定积分的思想进行求解在多顺序时段内 的总路程，再除以总时间即是多顺序时段内的平均速度。 3.1.2 利用曲线拟合思想构建速度与时间的函数 在上节分析中， 需要对车流量转化成的车速数据建立一个与时间变化的函数关系 式， 在数学中， 对于m个点( ,y ),1,2,3 ii xim， 如果要确定y和x的关系有两种方法： 插值法和曲线拟合。 虽然插值法和曲线拟合都是用来求函数的， 插值法求出的近似曲 线y( )f x要完全通过所有m个已知点 ( 即要满足插值原则 )；而曲线拟合求出的 近似曲线y( )f x不要求完全通过所有m个已知点，只要求得的近似曲线y( )f x能 反映数据的基本趋势即可。曲线拟合求得的近似曲线y( )f x比插值法求得的近似曲 线y( )f x更能反映客观实际。所以在本文中对于数据的处理采用曲线拟合的方法。 曲线拟合也就是用连续的曲线近似的刻画或比拟平面上离散点数组表示的坐标 之间的函数关系的一种数据处理方法。例如有m个点( ,y ),1,2,3 ii xim，其中 i x数 值互不相同，而现在求解出一个函数y( )f x与所有数据点尽量逼近，这个函数也就 能表达两者的函数关系。 曲线拟合中常用的是最小二乘拟合思想。 最小二乘拟合又分 为线性和非线性的最小二乘拟合。 （1）线性最小二乘拟合 首先令： 1 12 2 ( )( )( )( ) m m f xar xa r xa rx； (3.1) 其中 1 ( )() m kk r xmn 是一组事先选定与线性无关的函数， 1 m kk a 是一组待定系 数。寻求系数 1 m kk a 使得 i y和( ) i f x的距离(1,2, ) i d in的平方和最小。这种准则称 为最小二乘准则，其求系数 1 m kk a 的方法称为线性最小二乘拟合。 系数 1 m kk a 的求法 若： 22 1 11 ( ,) ( ) nn miii ii J aadf xy ，则J为 1, , m aa的二次函数，由数学 知识知J达到最小的充分必要条件是： 0(1,) k J km a (3.2) 即若要J达到最小，必须要求解以下线性方程组： 11 ( )( )0(1,) nm jik kii ik r xa r xyjm (3.3) 安徽工业大学管理科学与工程学院 多顺序时段批量批次货物运输的车辆调度方法研究 共 53 页 第13页 装 订 线 即求解线性方程组： 111 ( )( )( )(1,) nmn jik kijii iki r xa r xr x yjm (3.4) 若记： 111 11 1 ( )( ) ,(,) ()() m T T mm nmn n m r xrx RAaaYyy r xrx (3.5) 则方程组可表示为： TT R RAR Y。 由于当 1 ( ),( ) m r xrx线性无关时，R列为满秩， T R R可逆，所以上述方程组有 唯一解， 1 () TT AR RR Y 。 线性拟合的无误差一般有以下两种形式： 最小平方误差： 1/2 1 1 ( ) n ii i yf x 最大偏差： 2 1 i max( ) ii n yf x 1 ( )m kk r x 的选择 面对一组数据( ,),1,2, ii x yin，用线性最小二乘法做曲线拟合时，需要恰当的 选取 1( ), ,( ) m r xrx。一般来说我们也可以通过分析确定 1( ), ,( ) m r xrx，若无法了解数 据( ,),1,2, ii x yin之间的关系，可以直观的进行判断用什么样的曲线拟合。 常用的有：直线： 12 ya xa；多项式： 11 m mm ya xa xa 以及双曲线指数 曲线等等。 （2）非线性最小二乘拟合 非线性最小二乘法是假设( )f x是待定系数 1 m kk a 的任意非线性函数， 在最小二乘 法求其系数 1 m kk a 。 常用的数学模型有： / ( ), ( ), ( ) bxb xb f xaef xaef xax等等。 其思想和线性最小二乘拟合类似， 本文不再探讨， 且本文主要运用线性最小二乘 拟合并结合 matlab 编程进行速度与时间函数的构建。 3.1.3 将连续变化的速度量化表示 本文将变化速度量化的方法有两种。 （1）借助夹逼准则思想建立速度与偏好系数的关系式 夹逼准则思想是一个求极限的思想， 例如( )( )( )g xf xh x， 当函数( )g x和( )h x 趋近于一极限值时， 则函数( )f x也趋向于这一极限值。 而本文并不是求( )f x的极限， 只是借鉴于这种夹逼的思想，将( )f x约束在一定的范围之内。 建立速度与偏好系数的关系的具体操作如下： 通过对曲线拟合出来的速度与函数关系进行求导可以得出速度的最大最小值。 将求得的 max V和 min V，则变化的车辆速度可以建立与参数关系： minmax (1)(01)VVV (3.6) 安徽工业大学管理科学与工程学院 多顺序时段批量批次货物运输的车辆调度方法研究 共 53 页 第14页 装 订 线 其中：表示车辆速度变化与各顺序时段的影响系数， 例如在上班高峰期时取 值则较大，反之取值较小。也就是说在进行车辆优化调度过程中，的变化会影响 到最优结果。 （2）利用定积分思想将变化的速度量化（求平均速度） 定积分定义：设函数( )f x在 , a b上有界，在 , a b中任意插入若干个分点把区间 , a b分 成n个 小 区 间 01121 , , , , , nn x xx xxx ， 各 个 小 区 间 的 长 度 依 次 为 1102211 , nnn xxxxxxxxx ， 在 每 个 小 区 间 1 , ii xx 上 任 取 一 点 i 1i ( ii xx ），作函数值 i ( )f与小区间长度 i x的乘积 i ( )(1,2, ) i fx in，并作 出和 i 1 ( ) n i i Sfx 。 记 12 max, n xxx。只要当0时，和S总趋于确定的极限I，这时 我们称这个极限I为函数( )f x在区间 , a b上的定积分，记作( ) b a f x dx 。 通过对定积分定义的详细描述， 则知函数值 i ( )f与小区间长度 i x的乘积逐步累 加才得到最后的结果。 由于上文拟合出多顺序时段的曲线并不能覆盖所有点， 而如果 将采用定积分的思想， 对多顺序时段内多个连续时间段进行逐步拟合再累加除以总时 间得到平均速度，公式如下： 2 12 i 1ii ( )( )( )/ mmn t mn m Vf x dxfx dxf x dxn （3.7） 其中：n表示时间段总间隔时间，例如 8：00-17：00 则时间间隔为 11 小时； / 1tn m；m为设定的小段时间间隔；( )f x为小段时间间隔内利用线性最小二乘 法拟合出的速度关于时间的函数，其思想如图 3-1 所示： 0 y x m2m3mn-mn 图 3-1 分段拟合曲线图 （3）两种量化方法的比较 第二种求平均速度的方法较为严谨， 它是一个局部拟合再累加的过程， 本文在进 行案例仿真时首选此种方法。 但是第一种方法有利于车辆调度人员根据主观判断， 当 出现特殊情况时，车辆调度人员通过调节偏好系数的值对变化速度的进行量化。 安徽工业大学管理科学与工程学院 多顺序时段批量批次货物运输的车辆调度方法研究 共 53 页 第15页 装 订 线 3.2 多顺序时段批量批次货物运输车辆调度数学模型的建立 3.2.1 时间窗问题综述 本文主要研究多顺序时段批量批次的车辆调度问题， 现在各家物流公司为提高自 身竞争力都尽量满足顾客所提出的条件， 这其中就包括送货时间窗的限制， 而有时间 窗的车辆调度问题主要包括硬时间窗、软时间窗以及混和时间窗三类。 （1）硬时间窗（Hard Time Windows） ：在物流配送中是指物流公司必须在顾客 规定的时间段 , a b内进行配送，早到或晚到顾客都不会接受，并且惩罚值M较大， ( )P t表示时间惩罚函数，具体函数图形如图 3-2 所示： t P(t) M ab 图 3-2 硬时间窗惩罚函数 （2）软时间窗（Soft Time Windows） ：在物流配送中是指物流公司如果在顾客 要求时间段 , a b之外到达需求点，则给予一定的惩罚，惩罚函数( )P t一般成线性变 化。具体函数图形如图 3-3 所示： t P(t) ab M 图 3-3 软时间窗惩罚函数 （3）混合时间窗（Mixed Time Windows） ：在物流配送中一般是有两种情况，一 指物流公司所配送的点中的顾客有的是硬时间窗要求， 有的是软时间窗要求， 第二种 情况是同一顾客软硬时间窗混合使用。在 , a b时间段是顾客要求的时间段，c, a和 安徽工业大学管理科学与工程学院 多顺序时段批量批次货物运输的车辆调度方法研究 共 53 页 第16页 装 订 线 b, d时间段内送货会有一定的惩罚，而其它时间段内惩罚值M非常大。具体函数图 形如图 3-4 所示： t P(t) ab M cd 图 3-4 混合时间窗惩罚函数 3.2.2 时间窗惩罚函数的建立 在物流配送中带有顾客时间窗配送的路径优化问题中，软时间窗的配送应用较 为广泛。对于现代物流业来说，顾客对物流公司的配送要求一般都不是硬性的，只是 规定在一定的时间段内， 而如果物流公司过早到达， 可能会占用顾客资源或者顾客并 没有来的及组织搬运，物流公司过晚到达会造成顾客成本的损失，另外，过早或过晚 到达会给物流公司形象带来损害， 顾客的满意度也随之下降， 而这些都转化为时间惩 罚函数( )P t。也就是说，早到或者晚到对于物流公司都有成本增加。 本论文在研究多顺序时段批量批次货物的调度中， 时间窗惩罚函数建立在以下条 件基础上： （1）车辆在规定时间窗内到达，没有惩罚成本。 （2）车辆在时间窗之外到达，都有一个最小惩罚值，其余惩罚成本呈线性变化。 （3）早到或晚到惩罚成本系数是根据经验得出的。 1 2 *() ()0 * iiii kiiii iiii ceaETETa P ETaETb cfETETb （-b） （3.8） 式 3.8 中，惩罚函数() ki P ET是指车辆k在 i ET时刻到达顾客i点的惩罚成本，而 如果车辆在顾客规定时间窗 iii aETb内到达，则惩罚函数值为 0，若车辆到达时刻 在规定的时间窗之外，就会有惩罚成本。车辆早到的固定惩罚成本为 1 c，晚到的固定 惩罚成本为 2 c，早到和晚到各自的惩罚系数分别为e和f。总体上来说，顾客对时间 要求越高（时间窗宽度越窄） ，则相应的e和f值则会越大。 安徽工业大学管理科学与工程学院 多顺序时段批量批次货物运输的车辆调度方法研究 共 53 页 第17页 装 订 线 3.2.3 多顺序时段批量批