收益可变定向问题研究及应用

发布时间：2022-11-10 21:57

　　定向问题（Orienteering Problem,OP）是一类特殊的NP-hard组合优化问题,其基本定义为:在指定的时间限制内有序的经过部分带有一定收益的点,使形成的路径最终获得的收益最大。由于良好的模型特性,定向问题越来越受到国内外研究学者的关注,其基本模型及变体被广泛应用于旅行规划、物流运输、救灾救险、选址规划等实际应用场景中,以优化资源分配,减少成本,获取最大利益。按照求解的路径个数,定向问题可分为单路径定向问题（OP）和多路径团队定向问题（team Orienteering Problem,TOP）。本文主要研究单条路径的优化问题。在介绍完国内外研究现状后,引出本文研究的收益可变定向问题,考虑收益变化的两种情况:一类是在整个时间限制内收益可变的定向问题,称为收益可变泛化定向问题;另一类是在时间窗内收益变化的定向问题,称为带时间窗收益可变定向问题。考虑收益可变情况的定向问题,进一步丰富了该领域的研究,同时将收益可变的定向问题应用到实际应用场景中,体现了其应用价值。具体的,考虑实际灾后搜救场景中,每个救援点有多种不同类型、不同重要程度的待救物资,且其价值会随着救援时间的延长而面... 

【文章页数】：65 页

【学位级别】：硕士

【文章目录】：
摘要
abstract
1 绪论
    1.1 研究背景与意义
    1.2 国内外研究现状
        1.2.1 定向问题研究现状
        1.2.2 收益可变定向问题相关研究现状
    1.3 本文研究内容
    1.4 论文结构
2 遗传算法在定向问题上的应用
    2.1 遗传算法概述
    2.2 基于遗传算法的收益可变定向问题研究
        2.2.1 选择算子
        2.2.2 交叉算子
        2.2.3 变异算子
        2.2.4 本文采用的遗传算法
    2.3 本章小结
3 收益可变泛化定向问题
    3.1 问题描述及建模
    3.2 算法求解
        3.2.1 染色体编码及适应值计算
        3.2.2 种群初始化
        3.2.3 遗传算子
    3.3 仿真实验
        3.3.1 仿真数据
        3.3.2 算法及参数
        3.3.3 实验结果及分析
    3.4 本章小结
4 带时间窗收益可变定向问题
    4.1 问题描述及建模
    4.2 算法求解
        4.2.1 染色体编码及适应值计算
        4.2.2 种群初始化
        4.2.3 遗传算子
    4.3 仿真实验
        4.3.1 仿真数据
        4.3.2 算法及参数
        4.3.3 实验结果及分析
        4.3.4 模型应用
    4.4 本章小结
5 总结与展望
    5.1 总结
    5.2 展望
致谢
参考文献
附录


【参考文献】：
期刊论文
[1]基于蚁群算法的m-团队定向问题求解[J]. 吕志民,杨娟,徐金梧.  计算机工程. 2006(24)
[2]遗传算法在组合优化问题中的应用[J]. 马立肖,王江晴.  计算机工程与科学. 2005(07)
[3]基于小生境遗传算法的物流配送路径优化研究[J]. 王辉,任传祥,尹唱唱,郝新刚.  计算机应用. 2009(10)
[4]遗传算法研究综述[J]. 葛继科,邱玉辉,吴春明,蒲国林.  计算机应用研究. 2008(10)
[5]基于蚁群算法的定向运动问题求解研究[J]. 杨理云.  计算机工程与设计. 2009(10)
[6]遗传算法选择策略比较[J]. 张琛,詹志辉.  计算机工程与设计. 2009(23)
[7]一种改进蚁群算法研究和旅游景区路径规划问题求解[J]. 胡军国,祁亨年,董峰,汪杭军.  计算机应用研究. 2011(05)
[8]动态团队定向问题的模型及其优化算法[J]. 柯良军,尚可,冯祖仁.  西安交通大学学报. 2011(06)
[9]一类求解带时间窗的团队定向问题的改进蚁群算法[J]. 柯良军,章鹤,尚可,冯祖仁.  计算机科学. 2012(04)
[10]基于改进蚁群算法的定向问题研究[J]. 冯禹.  物流工程与管理. 2013(09)

博士论文
[1]基于局部搜索策略的若干组合优化问题求解算法研究[D]. 李睿智.东北师范大学 2017

硕士论文
[1]改进的遗传算法求解TSP问题的应用与研究[D]. 葛海明.江西理工大学 2016



本文编号：3705352