遗传算法在带时间窗的车辆路径问题中的应用

发布时间：2024-01-30 10:16

　　经济的发展使得物流成为了一门重要的产业，车辆路径问题(VRP, Vehicle RoutingProblem)是物流中最重要的一部分，引起了学者与企业管理者的高度重视。由于消费者对配送时间的要求越加严格，因而对带时间窗的车辆路径问题(VRPTW, Vehicle RoutingProblem with Time Windows)的研究具有重要的现实意义。 本文针对基本遗传算法的不足作了一系列的改进，并用C语言进行了编程实现。用程序对具体的带时间窗的车辆路径问题实例进行求解，证实了本文改进算法的有效性。 本文的主要工作包括： （1）建立了有惩罚函数的VRPTW的数学模型。设置惩罚函数，对车辆提前到达或延后到达加以惩罚，根据客户不同的服务要求，设置了两类惩罚函数，一类是线性函数，一类是二次函数，其中二次函数的模型更符合实际，因为当配送车辆提前或延后送达的时间较小时对顾客的满意度不会有太大的影响，而当提前或延后的时间较大时则会严重降低客户的满意度。 （2）提出了一种新的交叉算子。新交叉算子将已寻优的部分路径段（优良基因段）作为一个整体，交叉后不会破坏优良的基因段。此外，比较了交叉前后的染色体...

【文章页数】：58 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
目录
第一章 绪论
    1.1 研究背景及意义
    1.2 本文主要内容与结构
第二章 车辆路径问题概述
    2.1 车辆路径问题描述
    2.2 车辆路径问题的研究现状
        2.2.1 国外研究现状
        2.2.2 国内研究现状
第三章 遗传算法概述
    3.1 遗传算法的理论基础
        3.1.1 模式定理
        3.1.2 遗传算法的收敛性分析
    3.2 遗传算法的具体流程
    3.3 遗传算法的特性
    3.4 遗传算法存在的问题
第四章 遗传算法求解带软时间窗的车辆路径问题
    4.1 带时间窗的车辆路径问题的概念
        4.1.1 时间窗的定义
        4.1.2 带软时间窗的车辆路径问题的数学模型
    4.2 遗传算法求解带软时间窗的车辆路径问题的步骤
        4.2.1 编码与解码
        4.2.2 种群初始化
        4.2.3 适应度函数设计与分析
        4.2.4 选择操作
        4.2.5 交叉操作
        4.2.6 变异操作
        4.2.7 算法终止条件判断
第五章 算例分析及实现
    5.1 算例说明
    5.2 实验分析
第六章 总结与展望
    6.1 工作总结
    6.2 研究展望
参考文献
攻读学位期间的研究成果
致谢



本文编号：3889961