最小邮递员覆盖问题的近似算法

发布时间：2022-10-08 16:04

　　随着时代的发展与进步,物流调度、出租车调度、机械与人工调度在社会及企业中扮演着越来越重要的角色,引起了众多数学家和经济学家的关注。本文主要研究了最小乡村邮递员覆盖问题（MRPCP）和最小中国邮递员覆盖问题（MCPCP）,提出了图分解算法,并在此基础上给出了近似算法。最小乡村邮递员覆盖问题是在一个无向赋权图G=（V,E）上,通过最少数量的回路覆盖给定的边子集,其中这些回路的长度不超过上界λ。而最小中国邮递员覆盖问题是最小乡村邮递员覆盖问题的一个特殊情况,即边子集R就是图上的所有边集E的情况（R=E）。首先,我们由圈覆盖问题的近似算法进行简单的推广得到了关于最小乡村邮递员覆盖问题的7近似算法;其次,考虑到在圈覆盖问题中主要用到了树分解的思想,由此我们提出一套关于在一般图上的图分解算法,借用图分解算法,我们先后得到了关于最小乡村邮递员覆盖问题的两个不同复杂度的5近似算法。最后,我们还研究了中国邮递员覆盖问题,得到了4近似算法。 

【文章页数】：41 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第1章 引言
    1.1 背景
    1.2 论文主要工作
第2章 预备知识
    2.1 乡村邮递员问题和中国邮递员问题
    2.2 最小乡村邮递员路径覆盖问题和最小中国邮递员路径覆盖问题
    2.3 最小乡村邮递员覆盖问题和最小中国邮递员覆盖问题
    2.4 树分解和图分解
第3章 最小乡村邮递员覆盖问题的近似算法
    3.1 一个复杂性为O(n~2 log n)的7近似算法
    3.2 一个简单的复杂性为O(n~2 log n+nR|E|)的5近似算法
    3.3 一个更快的复杂性为O(|E|+nlogn)的5近似算法
第4章 最小中国邮递员覆盖问题
    4.1 一个复杂性为O(n~3)的4近似算法
第5章 总结
参考文献
致谢
发表以及完成论文


【参考文献】：
期刊论文
[1]中国邮递员问题50年[J]. 高敬振,高勃.  运筹学学报. 2013(01)
[2]中国邮递员问题的研究与发展[J]. 杨静,殷志祥,邹德杰.  科技信息. 2012(32)
[3]邮政速递网络流程优化问题探讨[J]. 苏伟灿.  邮政研究. 2010(01)
[4]中国邮递员问题的DNA计算[J]. 李玮,王雷.  计算机应用. 2009(07)
[5]求解中国邮递员问题的一种思路[J]. 吴杰.  科技资讯. 2007(14)
[6]中国邮递员问题的动态规划算法研究[J]. 费蓉,崔杜武.  计算机研究与发展. 2005(02)
[7]中国投递员问题综述[J]. 管梅谷.  数学研究与评论. 1984(01)
[8]奇偶点图上作业法[J]. 管梅谷.  数学学报. 1960(03)



本文编号：3688012