-
题名装箱问题的一种新的近似算法
被引量：24
- 1
-
-
作者
孙春玲
陈智斌
李建平
-
机构
云南大学数学系
-
出处
《云南大学学报（自然科学版）》
CAS
CSCD
2004年第5期392-396,共5页
-
基金
国家自然科学研究基金资助项目 ( 10 2 7110 3 )
云南省自然科学研究基金资助项目 ( 2 0 0 3F0 0 15M ) .
-
文摘
研究了一维装箱问题 (BinPackingProblem) ,给出了一个新的近似算法 :交叉装填算法 (简称CF算法 ) .证明了CF算法达到装箱问题的最好的近似值 32 ;并且当这些物件的大小按非增性质预先排序后 。
-
关键词
装箱问题
NP-完备
近似算法
交叉装填算法
CF算法
-
Keywords
Bin-Packing problem
NP-completeness
approximation algorithm
-
分类号
TP301.5
[自动化与计算机技术—计算机系统结构]
O157.6
[自动化与计算机技术—计算机科学与技术]
-
-
题名分块分层优化的旅游路线规划问题研究
被引量：8
- 2
-
-
作者
钟仪华
罗仕明
-
机构
西南石油大学理学院
-
出处
《运筹与管理》
CSSCI
CSCD
北大核心
2017年第9期62-67,共6页
-
基金
四川省人民政府及四川省教育厅的项目"工学类硕士研究生数学课程体系与教学改革及试验(030039007)"
西南石油大学项目"最优化理论与控制"青年科研创新团队(2013XJZT004)
-
文摘
针对旅游路线规划决定着自驾旅游者的旅游成败问题,利用分块分层优化的思想解决了旅游路线规划这一网络优化问题。用赋权图和近邻聚类的思想构建分块网络加权图,建立考虑旅游时间、行车时间和游览时间的改进旅行商优化模型,规划区块内景点的自驾旅游路线;然后将各区块视为节点、区块间旅游时间作为时间权值之一,建立改进的多旅行商优化模型,并用模拟退火算法规划出区块间的自驾旅游路线;其次,用类比一维装箱问题的思想,建立了求最少旅游年数的一维装箱模型,并用交叉装填算法求得其最小值;最后,应用提出的方法为西安市的自驾旅游爱好者规划出了满足多种约束的游遍全国201个5A级景区的最佳旅游路线。
-
关键词
网络优化
旅行商模型
一维装箱模型
模拟退火法
交叉装填算法
-
Keywords
network optimization
TSP model
one-dimensional packing model
simulated annealing method
cross filling algorithm
-
分类号
O221.7
[理学—运筹学与控制论]
-
