摘要近年来，物流作为“第三方利润的源泉”受到国内各行业的极大重视并得到了较大的发展。
在高度发展的商业社会中，传统的VSP算法已无法满足顾客需求对物流配送提出的要求，于是时间窗的概念应运而生。
带有时间窗的车辆优化调度问题是比VSP复杂程度更高的NP难题。
本文在研究物流配送车辆优化调度问题的基础上，对有时间窗的车辆优化调度问题进行了分析。
并对所采用的遗传算法的基本理论做了论述。
对于有时间窗的非满载VSP问题，将货运量约束和软时间窗约束转化为目标约束，建立了非满载VSP模型，设计了基于自然数编码，使用最大保留交叉、改进的反转变异等技术的遗传算法。
经实验分析，取得了较好的结果。
由于此问题为小组成员共同研究，本文重点论述了本人完成的关于适应度函数和变异操作的部分。
关键词：物流配送车辆优化调度遗传算法时间窗AbstractRecent years, logistics, taken as "third profit resource”, has been developing rapidly. In the developed commercial society, traditional VSP algorithm have been unable to meet the requirement that Quick Response to customer demand had brought forth, then the conception of Time Window has come into being. The vehicle-scheduling problem with time window is also a NP-hard problem being more complicated than VSP.This text has been researched to the vehicle-scheduling problem with time window on the basis of researched to logistic vehicle scheduling problem. And it has explained the basic theory of genetic algorithm.On the VSP with time window, while the restraints of capacity and time windows are changed into object restraints, a mathematic model is established. We use technique such as maximum preserved crossover and design genetic algorithm on nature number, which can deal with soft time windows through experimental analysis, have made better result. Because this problem was studied together for group members, this text has expounded the part about fitness function and mutation operator that I finished.Key words:logistic distribution vehicle scheduling problem genetic algorithm time windows目录摘要 (I)Abstract (II)目录......................................................................................................... I II 引言.. (1)第1章概述 (2)1.1研究背景 (2)1.2物流配送车辆优化调度的研究动态和水平 (4)1.2.1 问题的提出 (4)1.2.2 分类 (5)1.2.3 基本问题与基本方法 (6)1.2.4 算法 (6)1.2.5 货运车辆优化调度问题的分类 (8)1.3 研究的意义 (9)1.4 研究的范围 (10)第2章有时间窗的车辆优化调度问题(VSPTW) (11)2.1 时间窗的定义 (11)2.2 VSPTW问题的结构 (13)第3章遗传算法基本理论 (14)3.1 遗传算法的基本原理 (14)3.1.1 遗传算法的特点 (14)3.1.2 遗传算法的基本步骤和处理流程 (15)3.1.3 遗传算法的应用 (16)3.2 编码 (17)3.2.1二进制编码 (18)3.2.2Gray编码 (18)3.2.3实数向量编码 (18)3.2.4排列编码 (19)3.3 适应度函数 (19)3.3.1 目标函数映射成适应度函数 (19)3.3.2 适应度定标 (20)3.4 遗传算法的基因操作 (21)3.4.1 选择算子 (21)3.4.2 交叉算子 (22)3.4.3 变异算子 (25)3.5 遗传算法控制参数设定 (28)第4章遗传算法求解有时间窗非满载VSP (30)4.1 问题描述 (30)4.2 数学模型 (31)4.2.1 一般VSP模型 (31)4.2.2 有时间窗VSP模型 (32)4.3 算法设计 (33)4.3.1 算法流程图 (33)4.3.2 染色体结构 (33)4.3.3 约束处理 (35)4.3.4 适应度函数 (36)4.3.5 初始种群 (36)4.3.6 遗传算子 (36)4.3.7 控制参数和终止条件 (37)4.4 算法实现 (39)4.5 实验及结果分析 (39)4.5.1控制参数选定 (39)4.5.2实例实验 (43)4.5.3实例数据 (44)4.5.4实例数据分析 (44)结论 (45)参考文献 (47)谢辞 (48)引言随着市场经济的发展，大量经营规模较大的制造企业和商业企业纷纷建立起配送中心向商品流通效率化发起挑战，与此同时，相当部分的大型运输、仓储和航运企业开始转向第三方物流经营。
此外，我国具有强大物流配送资源优势的邮政业更是在递送包裹的基础上为企业、商家和电子商务网站积极开展配送业务。
物流配送开始在我国迅速兴起发展起来，对物流配送的研究引起了国内物流专家学者的广泛关注。
目前国内采用遗传算法解决物流配送的车辆优化调度问题的研究还处在起步阶段。
本文针对客户提出时间约束这一配送需求，对有时间窗的物流配送车辆优化调度问题（VSPTW）进行数学分析，研究探索性能更强的解决VSPTW 的遗传算法。
本文第1章研究目前物流配送车辆优化调度问题的研究动态和水平；第2章进一步研究有时间窗的物流配送车辆优化调度问题；第3章阐述和研究所采用遗传算法的基本理论；第4章详细论述如何采用遗传算法解决有时间窗的物流配送车辆优化调度问题并通过实验数据分析所采用改进的遗传算法的性能。
第1章 概 述1.1 研究背景随着社会主义市场经济的发展，在经济大循环中提高经济运作效率的物流对经济活动的影响日益明显，越来越引起人们的重视。
据中国物流信息中心统计测算，2004年，全国社会物流总额达38.4万亿元，同比增长29.9%(按现价计算)，增幅比上年同期提高2.9个百分点。
虽然我国物流发展持续加速，但与国民经济发展的要求还相差甚远，这就要求我们对物流产业的各个环节进行研究。
配送是物流中一个重要的直接与消费者相连的环节。
我国国家标准《物流术语》中对配送的定义是：“在经济合理区域范围内，根据用户要求，对物品进行拣选、加工、包装、分割、组配等作业，并按时送达指定地点的物流活动［７］。
”配送是在集货、配货基础上，按用户要求，包括种类、品种搭配、数量、时间等方面的要求所进行的运送，是“配”和“送”的有机结合形式，其主要功能是输送。
配送的流程一般如下图所示。
图1-1 配送流程图在传统的配送系统中，由于商品的需求量及种类较少，零售商可凭借较多的存货及较常的定货周期来减少供货商的配送频率，以降低运输成本。
但是在现代的配送系统中，零售商为了减少资金积压及提供多样化的商品，势必要减少各种商品的存货数量，而同时又必须考虑到提供最好的服务品质(不允许缺货)。
物流中心的功能就在于对商品的仓储与运输进行有效的统筹规划以降低配送成本。
所谓“物流中心”，根据美国物流管理协会(The Council of Logistics Management, CLM)定义：“以适合顾客要求为目的，对原物料、在制品、制成品与其相关信息，从产地到消费者的间的流程与保管，为求有效率且最小的机会成本，而进行计划、执行、控制的场所(Depot) ”。
在物流配送系统中，物流配送中心的成立可有效的简化配送程序与减少配送的频率，以i 个供应商和j 个零售商为例，传统的配送模式是假设j 个零售商的需求都是由i 个供应商自行配送，则一共有i×j 次的运送，如图1-2所示。
假设零售商与供应商之间通过一个物流配送中心来配送，则只需i+j 次配送，如图1-3所示，如此一来即可减少(i×j-(i+j))的配送次数，当供应商与零售商数目越多，节省的配送次数也就会越多。
图1-2 传统的物流配送模式 物流中心配送作业的重点是如何将车辆有效的使用并决定其最经济的行驶路线图，使商品能在最短的时间内送到顾客的手中。
国外将此类问题称之为Vehicle Scheduling Problem ，简称为VSP 问题。
该问题一般定义为:对一系列装（卸）货点，组织适当的行车线路，使车辆有序的通过它们，在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等)下，达到一定的目标(如路程最短、费用最少、时间尽量少、使用车辆数尽量少等)［３］。
图1-3 以物流中心为主的配送模式1.2 物流配送车辆优化调度的研究动态和水平1.2.1 问题的提出物流配送车辆优化调度问题最早是由Dantzig 和Ramser 于1959年首次提出，自此，很快引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家与运输计划制定者和管理者的极大重视，成为运筹学与组合优化领域的前沿与研究热点问题。
各学科专家对该问题进行了大量的理论研究及实验分析，取得了很大的进展。
国外对物流配送车辆优化调度问题作了大量而深入的研究，例如早在1983年Bodin, Golden 等人在他们的综述文章中就列举了700余篇文献。