检索结果-内蒙古大学图书馆

您好，读者！请登录

内蒙古大学图书馆

首页
概况
党建
资源
服务
科研支持
- 论文收录引用证明
- 科技查新
知识产权
档案馆
帮助

咨询与建议

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

您的常用邮箱：*

您的手机号码：*

问题描述：

当前已输入0个字，您还可以输入200个字

全部搜索
期刊论文
图书
学位论文
标准
纸本馆藏
外文资源发现
数据库导航
超星发现

高级检索

时间限定

出版年份：

-

文献类型

图书期刊文献学位论文多媒体

馆藏选择

电子馆藏纸本馆藏

核心期刊

全部期刊 SCI 收录期刊 SSCI 收录期刊 EI 收录期刊 CSCD 收录期刊 CSSCI 收录期刊

语言

中文英文

文献类型

期刊文献图书学位论文标准纸本馆藏

帮助

文字说明：

T=题名（书名、题名），A=作者（责任者），K=主题词，P=出版物名称，PU=出版社名称，O=机构（作者单位、学位授予单位、专利申请人），L=中图分类号，C=学科分类号，U=全部字段，Y=年（出版发行年、学位年度、标准发布年）

检索规则说明：

AND代表“并且”；OR代表“或者”；NOT代表“不包含”；(注意必须大写,运算符两边需空一格)

检索范例：

范例一：(K=图书馆学 OR K=情报学) AND A=范并思 AND Y=1982-2016
范例二：P=计算机应用与软件 AND (U=C++ OR U=Basic) NOT K=Visual AND Y=2011-2016

分类表

所选分类

>> <<

限定检索结果

文献类型

2 篇 学位论文

馆藏范围

2 篇 电子文献
0 种 纸本馆藏

日期分布

学科分类号

2 篇 工学
- 2 篇 控制科学与工程
- 2 篇 计算机科学与技术...
- 2 篇 软件工程
2 篇 管理学
- 2 篇 管理科学与工程(可...

主题

2 篇 旅行商问题
2 篇 最小最大
2 篇 分群旅行商问题
2 篇 多旅行商问题
1 篇 遗传算法
1 篇 近似算法
1 篇 组合最优化

机构

2 篇 上海海洋大学

作者

1 篇 徐磊
1 篇 王国俊

语言

2 篇 中文

检索条件"主题词=分群旅行商问题"

共 2 条记录，以下是1-10 订阅

全选清除本页清除全部题录导出标记到"检索档案"

详细简洁

排序：

最小最大分群旅行商问题的近似算法研究

最小最大分群旅行商问题的近似算法研究

引用

作者：徐磊上海海洋大学

学位级别：硕士

旅行商问题是计算机科学和运筹学中一个经典的组合优化问题,在诸多领域具有广泛应用。最小最大分群旅行商问题是旅行商问题的一个推广变形,因此它可以模拟更加复杂的实际问题,也就具有更加广泛的实际应用。由于旅行商问题是NP困难问题,... 详细信息

旅行商问题是计算机科学和运筹学中一个经典的组合优化问题,在诸多领域具有广泛应用。最小最大分群旅行商问题是旅行商问题的一个推广变形,因此它可以模拟更加复杂的实际问题,也就具有更加广泛的实际应用。由于旅行商问题是NP困难问题,因此最小最大分群旅行商问题亦是NP困难问题。针对NP困难问题,文献中主要有精确算法、智能算法、近似算法等研究方法。本文主要从近似算法的角度对最小最大分群旅行商问题开展研究,给出了具有较好近似比的近似算法,主要研究结果如下:本文研究的第一个问题是起点相同的最小最大分群旅行商问题。给定一个完全无向图G=（V,E）,V表示顶点集,E表示边集,顶点集V被划分成为K个子集,每个子集称为一个群。E中的每条边e（?）E均关联一个权重w（e）。给定k个旅行商,该问题的要求是计算k个环游,使得每个环游均从公共起点出发,所有环游能够经过V中所有顶点,并且每个群中的顶点被连续经过。问题的目标是极小化权重最大环游的权重。针对该问题,本文给出了一个近似比为（?）ρR+2ρP+1-1/k（?）的近似算法,这里ρR表示求解乡村邮递员问题的近似比,ρP表示求解旅行商路问题的近似比。算法的基本思想是,首先计算一条该问题对应的分群旅行商问题的可行环游,然后将该环游撕裂成k条权重相当的子路径,最后通过将每个子路径的两个端点与公共起点相连接,进而得到起点相同最小最大分群旅行商问题的一个可行解。本文研究的第二个问题是起点任意的最小最大分群旅行商问题。与第一个问题相比,该问题未给定所有环游的公共起点,即问题的要求是,计算k条能够经过所有顶点的环游,同时每个环游满足子集内顶点需连续服务的限制。针对该问题,本文给出了一个近似比为（4ρP+8ρR-2）的近似算法,这里ρR和ρP分别表示求解乡村邮递员问题和旅行商路问题的近似比。算法的基本思想是,给定问题的一个实例,首先给出该实例最优值的一个猜测值λ。针对该λ值,本文设计一个求解算法,使得该算法要么返回目标函数值不超过（4ρP+8ρR-2）的可行解,要么返回猜测值λ小于最优值。通过在区间[0,w（G）]内进行二分搜索,找到最小猜测值λ*,使得在该猜测值下算法返回满足上界限制的可行解,进而得到起点任意的最小最大分群旅行商问题的满足近似比要求的可行解。

关键词：组合最优化旅行商问题多旅行商问题分群旅行商问题最小最大近似算法

来源：评论

学校读者我要写书评

暂无评论

基于遗传算法求解最小最大分群旅行商问题

基于遗传算法求解最小最大分群旅行商问题

引用

作者：王国俊上海海洋大学

学位级别：硕士

旅行商问题是计算机科学和运筹学中一个经典的组合优化问题,而多旅行商问题和分群旅行商问题是它的两个被广泛关注的推广变形。这两个问题在现实生活中具有广泛应用,例如车辆路径规划、生产制造流程优化、计算机操作、印刷机调度、校车... 详细信息

旅行商问题是计算机科学和运筹学中一个经典的组合优化问题,而多旅行商问题和分群旅行商问题是它的两个被广泛关注的推广变形。这两个问题在现实生活中具有广泛应用,例如车辆路径规划、生产制造流程优化、计算机操作、印刷机调度、校车调度等等。因此,对这两个问题及其它们的推广变形进行科学研究具有重要的理论意义和实际价值。本文研究最小最大分群旅行商问题,它是多旅行商问题和分群旅行商问题的推广变形,其可以描述为:给定若干城市,它们分布在一个网络中。所有城市被划分成若干子集,每个子集称为一个群。给定若干旅行商,他们需要访问所有城市。问题的要求是,为每个旅行商设计一个环游,使得所有城市均能被访问且每个子集内的城市被连续访问。问题的目标是极小化权重最大环游的权重。本文从遗传算法的角度,对单仓库和多仓库最小最大分群旅行商问题展开了研究,其主要结果如下:本文研究的第一个问题是单仓库最小最大分群旅行商问题。给定一个完全无向图G=（V,E）和m个旅行商,V={1,2,,n}是该无向图的顶点集,其中1为所有旅行商的公共出发顶点,{2,,n}中每个顶点对应一个城市。顶点集V被划分成l个子集V1,V 2,,Vl,其中1V=分群旅行商问题。E是该无向图的边集,E中的每条边（i,j）关联一个非负实数dij,表示城市i与城市j之间的距离。给定一个子集E'（?）E,定义E'的权重为该子集内所有边的权重之和。问题的要求是,为每个旅行商设计一个环游,使得每个环游的起点和终点均为公共出发顶点1,同时所有环游综合一起能够访问所有城市,且每个子集内的城市被连续访问。问题的目标是极小化权重最大环游的权重。针对该问题,设计了一个基于遗传算法的两阶段求解方法。具体地,在第一阶段,首先在每个子集中抽象出一个旅行商问题,然后应用求解旅行商问题的遗传算法,最终确定子集内顶点的访问顺序;在第二阶段,首先将每个子集视为一个整体,然后结合第一阶段的结果并综合应用贪婪与随机的思想,定义每两个子集之间的距离,进而抽象出一个多旅行商问题,并应用求解多旅行商问题的遗传算法,最终确定子集间的访问顺序。仿真实验结果表明,在小规模算例中,与Cplex软件求解得到的精确结果相比,本文算法求解得到的最好结果的相对误差不超过1.5%,但求解时间显著减少;在中等规模和大规模算例中,与文献中两个相关求解策略相比,本文算法也表现出了良好的求解性能。本文研究的第二个问题是多仓库最小最大分群旅行商问题。与第一个问题相比,在该问题中,仓库的个数由1个增加至m个,即每个旅行商对应一个仓库。问题的要求是,为每个旅行商设计一个从它所在的仓库出发且最终回到该仓库的环游,使得所有城市均能被访问且每个子集内的城市被连续访问。问题的目标仍是极小化权重最大环游的权重。针对该问题,亦设计了一个基于遗传算法的两阶段求解方法。与第一个问题相比,在本求解方法的第二阶段,亦将每个子集视为一个整体,然后抽象出一个多旅行商问题。但在求解该多旅行商问题时,由于每个旅行商对应一个仓库,相同的子集分组,顺序不同对应的可行解也不同,故本阶段采用基于无序分组的遗传算法进行求解。仿真实验结果表明,在小规模算例中,与Cplex软件在限定时间内求解得到的结果相比,本文算法求解时间显著减少,同时求解精度更高;在中等规模和大规模算例中,与文献中两个相关求解策略相比,本文算法也表现出了良好的求解性能。

关键词：旅行商问题多旅行商问题分群旅行商问题最小最大遗传算法

来源：评论

学校读者我要写书评

暂无评论

没有更多数据了...

共1页 << < 1 > >>

检索报告对象比较合并检索0

隐藏清空

合并搜索

回到顶部

执行限定条件

内容：

评分：

请选择保存的检索档案：

请选择收藏分类：

订阅名称：

通借通还

温馨提示：

图书名称：

借书校区：

取书校区：

手机号码：

邮箱地址：

一卡通帐号：

电话和邮箱必须正确填写，我们会与您联系确认。

联系人：

所在院系：

联系邮箱：

联系电话：

内蒙古自治区呼和浩特市赛罕区大学西街235号邮编: 010021

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：