VC393 用遗传算法解决车辆优化调度问题论文

摘 要
近年来，物流作为“第三方利润的源泉”受到国内各行业的极大重视并得到了较大的发展。在高度发展的商业社会中，传统的VSP算法已无法满足顾客需求对物流配送提出的要求，于是时间窗的概念应运而生。带有时间窗的车辆优化调度问题是比VSP复杂程度更高的NP难题。
本文在研究物流配送车辆优化调度问题的基础上，对有时间窗的车辆优化调度问题进行了分析。并对所采用的遗传算法的基本理论做了论述。
对于有时间窗的非满载VSP问题，将货运量约束和软时间窗约束转化为目标约束，建立了非满载VSP模型，设计了基于自然数编码，使用最大保留交叉、改进的反转变异等技术的遗传算法。经实验分析，取得了较好的结果。由于此问题为小组成员共同研究，本文重点论述了本人完成的关于适应度函数和变异操作的部分。

关键词：物流配送 车辆优化调度 遗传算法 时间窗
1.2.5  货运车辆优化调度问题的分类
    根据任务的性质将货物运输分成以下几类：
    1、非满载车辆优化调度问题
    当货物量小于车辆容量时，用一辆车执行任务，存在不满载运行情况，调度时可安排一辆车执行多项任务，即在一辆车上同时载有不同货主的货物。该类问题根据任务特征又分为以下两类：
    （1）集货或送货的车辆优化调度
    所有任务全是集货点或全是送货点，车辆空车从车场出发，去各货主处装满货后返回车场。这种情况下，货运量总数不超过车辆容量的任务可用一辆车来完成。
    （2）集货和送货一体化的车辆优化调度
每一项货运任务都有自己的集货点和送货点，车辆从车场出发，去某一任务的集货地点装货后运至其送货地点卸货（即装卸混合），完成所有任务后返回车场。
    2、满载车辆优化调度问题
当货主的货物量不小于车辆容量时，执行每项任务需要的车辆可能不只一辆，车辆为完成任务，需满载运行。根据任务特征可分为以下两类：
（1）集货或送货的车辆优化调度
    载货车辆由车场出发到几个集货点装货后返回车场（仅有装货），或是车辆出发到几个送货点卸货（仅有卸货）后返回车场。 think58.com [版权所有：http://think58.com]
（2）集货和送货一体化的车辆优化调度
每一项货运任务都有自己的集货点和送货点，各项任务需要的车辆数不一致，这时需要对车辆进行优化调度，确定行车路线。
1.3  研究的意义
目前有关VSP的研究，多致力于单一车种或多车种优化调度问题，很少涉及结合时间窗口的VSP问题。所谓时间窗口是指配送车辆或顾客希望服务或被服务的时间范围。由于消费者需求趋于多样化，对送货时间的要求日趋严格，尤其是运送有时效性的商品，例如海鲜、花卉、蔬菜、水果等讲究新鲜度的货物，除了因缺货造成的机会成本的损失外，由于配送不及时也会造成货物价值的大大降低。因此，在配送运输上，时间因素是十分重要的。
有时间窗的VSP问题也称为VSPTW(Vehicle Scheduling Problem with Time Windows），根据时间约束的严格与否，分为软时间窗和硬时间窗的VSP。由于有时间窗的VSP是典型的NP—难题，会随着节点的增加出现组合爆炸的现象，因此求解的困难度及时效性会有影响。
1.4  研究的范围
由于有时间窗约束的车辆优化调度问题所牵涉的因素相当多，本研究仅针对具有普遍性的物流中心予以探讨，就研究范围与假设界定如下：
1、仅考虑区位己知的单一物流配送中心和供应商；
2、物流配送中心无缺货的可能，而且商品种类单一； 本文来自think58 [资料来源：http://think58.com]
3、物流配送中心已知顾客的基本配送资料(需求量、地理位置、时间窗约束等)；
4、物流配送中心拥有足够数量的同类型配送车辆，即每辆车的载重量、时速相同。
 
第2章  有时间窗的车辆优化调度问题(VSPTW)
2.1  时间窗的定义
VSPTW问题是传统的车辆优化调度问题加上时间窗约束，时间窗约束可分为硬时间窗、软时间窗与混合型时间窗。三者分述如下：
1、硬时间窗(Hard Time Windows)：指配送车必须在特定时间区段(如图2-1中的 )内将货品送达顾客手中，不论是迟到或早到都完全不予接受。图2-1为一惩罚函数(Penalty Function)当货品送达时间超出 时，其惩罚值 等于一个非常大的正值，表示硬时间窗的限制。Desrochers (1988)曾指出硬时间窗宽度会影响寻优程序，并提出时间窗宽度评价指标，时间窗越宽则VSPTW问题越接近路线安排(Routing)问题，越窄则越近似行程安排(Scheduling)问题。
 
            图2-1  硬时间窗约束示意图
2、软时间窗(Soft Time Windows)：指配送车辆如果无法将货物在特定的时段(如图2-2的 )内送到顾客手中，则必须按照违反时间的长短施以一定的罚金或其它惩罚法则。图2-2就是一种可能的惩罚函数。

think58

[来源：http://www.think58.com]

 
               图2-2  软时间窗约束示意图
3、混合型时间窗(Mixed Time Windows )：系统中有些顾客属于硬时间窗，有些则属于软时间窗；同一顾客，往往软、硬两种时间窗混合使用。在实际的物流配送中，配送车辆如果能在最佳时段(如图2-3中的 内将货物送到顾客处，则不处罚；若在图2-3中的（ 或 ）时段内才送达，则顾客的满意度降低(转化为惩罚函数)，而且顾客不接受上述两个时段以外的时间 （ 或 ）收货。 think58

目 录
摘 要 I
Abstract II
目 录 III
引 言 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.2  Gray编码 18
3.2.3  实数向量编码 18
3.2.4  排列编码 19
3.3  适应度函数 19
3.3.1  目标函数映射成适应度函数 19
3.3.2  适应度定标 20 [资料来源：THINK58.com]
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 本文来自think58 [来源：http://www.think58.com]