遗传算法解决车辆优化调度问题的设计与实现

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

关键词：物流配送 车辆优化调度 遗传算法 时间窗
 
Abstract
  Recent 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
 
物流配送车辆优化调度问题最早是由Dantzig和Ramser于1959年首次提出，自此，很快引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家与运输计划制定者和管理者的极大重视，成为运筹学与组合优化领域的前沿与研究热点问题。各学科专家对该问题进行了大量的理论研究及实验分析，取得了很大的进展。
国外对物流配送车辆优化调度问题作了大量而深入的研究，例如早在1983年Bodin, Golden等人在他们的综述文章中就列举了700余篇文献。在Christofides(1985)，Golden和Assad(1988)编辑的论文集，以及Altinkermer和Gavish(1991)，Laporte(1992)，Salhi(1993)等的综述文章中都进行了详尽阐述。该领域的代表人物有Bodin，Christfids，Golden，Assad，Ball，Laporte，Rinnooy Kan，Lenstra，Desrosiers和Desrochers等人

为简化货运车辆优化调度问题的求解，常常应用一些技术将问题分解或转化成一个或几个已经研究过的基本问题，再用相应比较成熟的基本理论和方法，以得到原货运车辆优化调度问题的最优解或满意解。
    常用的基本问题有：旅行商问题、分派问题、运输问题、背包问题最短路问题、最小费用流问题、中国邮路问题等。
    常用的基本理论和方法有：分枝界定法、割平面法、线性规划法、动态规划法、匹配理论、对偶理论、组合理论、线搜索技术、列生成技术、概率分析、统计分析、最差情况分析、经验分析等。

算法
货运车辆优化调度问题的求解方法非常丰富，目前主要有以下四类：
1、系统仿真法(Simulation )
此方法最早由Golden和Skiscim于1986年提出，主要应用于行车线路与物流中心区位的选择，优点在于可直接观察系统安排的效率与效果，但由于问题的实际情况多变且具有不确定性，是否能将实际的配送情形系统逻辑化为仿真程序，往往令人质疑。
2、人机互动法
此方法结合人类决策与计算机计算能力，在求解的过程中，通过高度的人机交互模式，结合专家的决策信息，并据以计算出结果；优点是寻优的过程中，决策者可以很清楚地看到各约束条件之间的替代关系，以及参数变化可能导致的成本变化。
3、精确解法(Exact procedures )
精确解法指可求出最优解的算法，精确解法主要有：分枝界定法(Branch and Bound Approach)、割平面法(Cutting Planes Approach)、网络流算法(Network Flow Approach)、动态规划方法(Dynamic Programming Approach)。精确算法的计算量一般随着问题规模的增大呈指数增长。
    4、启发式解法(Heuristics)
由于上述三种方法的求解效率较差，所以大部分的学者都致力于启发式解法的发展。该方法在解题时可减少搜寻的次数，所以是一种容易且快速的求解困难问题的算法。

 遗传算法的应用
遗传算法是60年代由美国J. Holland教授首先在《自然结合人工智能系统的适应性》一书中提出的，是一种新兴的自适应随机搜索方法，具有极强的鲁棒性和内在的并行计算机制，特别适合于非凸空间中复杂的多极值优化和组合优化，在机器学习、自动控制、机器人技术、电器自动化以及计算机和通信领域以取得了非凡的成就。
遗传算法的应用总的来说可以分为如下三大类：
    1、优化计算
优化计算是遗传算法最直接的应用，应用面也最广。对于复杂的函数优化问题(如非线性、不连续、多峰值函数的优化等)和组合优化问题(如VSP, TSP,0-1背包问题、工作计划制定等)都有广阔的发展前景。目前在运筹学、机械优化设计、电网设计、生产管理等应用学科中都尝试着用遗传算法解决现实优化计算问题。
    2、机器学习
基于遗传算法的机器学习也是遗传算法应用研究的一个重要方面。机器学习是为解决专家系统设计中的知识获取瓶颈问题而设计的。遗传算法从其开始就与机器学习有着密切的联系。分类器CS-1是Halland与Keitman实现的第一个基于遗传算法的机器学习系统。
    3、神经网络
遗传算法的另一个活跃的研究方向是在神经网络方面的应用，这包括优化神经网络的连接权系数、网络的空间结构等。遗传算法与神经网络的相结合应用于机械设计、结构优化、决策分析。
近些年来，人们在用遗传算法解决现实中的各种组合优化问题上进行了探索，如在生产调度问题中的应用、对一般TSP (Traveling Salesman Problem,旅行商问题)问题的求解都取得了一些成果(Oliver和Smith, 1989:Fogel, 1993 )。但在VSP中的应用才刚刚开始，已有文献利用遗传算法对VSP进行求解(Berthold,1995;Malmborg,1996;Ochi和Luiz 1998 )，但仅仅是开始尝试阶段，还有待于进一步的研究。

本文在分析和研究物流配送车辆优化调度问题和遗传算法基本理论的基础上，对有时间窗的车辆优化调度问题进行了深入研究，设计了针对这一问题的遗传算法，并进行了实验分析。本算法采用基于线性排序的轮盘赌方法进行选择操作，有效的防止了搜索陷入局部最优；采用最优保留的顺序交叉算子，有效防止了在算法执行过程中出现的一些接近最优解的染色体结构因算法的随机性被破坏，并通过实验分析初步证实了此交叉算子随问题规模的增大，对算法性能的增强起积极作用；采用改进的反转变异算子，抑制了染色体经选择和交叉操作造成的有效基因的缺失，并防止了非法染色体的出现。
此算法经实验验证，具有良好的寻优性能，且收敛速度较快，是一个针对有时间窗车辆优化调度问题的良好的解决方案。






目 录
摘 要 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
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