面向旅行商问题的频率四边形及其应用

来源:党委研究生工作部、可再生能源学院发布时间:2018-12-27

【讲座题目】面向旅行商问题的频率四边形及其应用

【讲座时间】2018年12月28日(星期五)14:00-16:00

【讲座地点】北京校部教四楼D405

【主 讲 人】王永 副教授

【主讲人简介】

王永,1978年2月出生,博士,华北电力大学可再生能源学院副教授,硕士生导师。主讲《风力发电机组设计与制造》、《制造工程学》、《公差与金属材料》、《Wind Power system》等本科生和研究生课程。曾主持或参加国家自然科学基金、国际科技合作项目等研究项目3项。目前主要研究方向组合优化与图论算法、装配过程优化等。已在国内外正式发表科研论文30余篇,其中SCI收录10余篇。获得北京市教学成果奖2项。

【讲座内容简介】

旅行商问题是一个典型的组合优化问题,该问题最早由爱尔兰数学家W.R. Hamilton 和英国数学家T.P. Kirkman提出。旅行商问题的一个等价问题是Hamiltonian回路问题(或Hamiltonian图判定问题)。与Euler回路问题不同,Hamiltonian回路问题至今没有找到充分必要条件。旅行商问题是很多工业应用问题的数学模型,其求解方法或简化技术均具有广阔的应用前景。频率四边形近年来由王永和J. Remmel教授共同提出,具有良好的性质;采用频率四边形计算边的频率,最优Hamiltonian圈内边与大多数其他边存在很大区别。并且,最优Hamiltonian圈内边的频率随着旅行商问题规模增大而趋近一个极值。这些发现为简化旅行商问题提供一种理论支撑。通过实验,基于频率四边形可以计算出一个稀疏图,稀疏图上旅行商问题的求解空间大大降低。


返回