关于直线上对称相遇值问题及相关问题的研究

项目名称： 关于直线上对称相遇值问题及相关问题的研究

项目编号： No.11271009

项目类型： 面上项目

立项/批准年度： 2013

项目学科： 数理科学和化学

项目作者： 韩乔明

作者单位： 浙江财经学院

项目金额： 60万元

中文摘要： 本项目将研究直线上对称的相遇问题及其相关的一些问题。直线上对称的相遇值问题是搜索和相遇领域最重要的open问题，我们从06年就开始研究此问题，得到了一些有趣的结果，相关论文发表在08年的《Operations Research》上。本项目中，我们将进一步对此问题进行深入的研究，通过改进算法，提高下界和改进上界，用数值的方法证明或否定直线上对称的相遇值为4.25的猜想。另一方面，我们将研究不同长度的圈上的相遇问题，发现和总结其规律，并研究如何把圈上的规律推广到直线上。因为直线可以看成是一个无穷大的圈，这样可以帮助我们寻找有关的理论方法，严格地证明直线上对称的相遇值为4.25。本项目还将研究一些相关的问题，如一般图上的相遇问题等。直线上的相遇问题是一类重要的理论问题，在自动控制、在线算法、信息科学以及军事科学领域，都有重要的应用，因而本项目的研究具有重要的理论意义和实际的应用价值。

中文关键词： 搜索与相遇；对称相遇问题；半定规划；报童问题；机制设计

英文摘要： This project will focus on the symmetric rendezvous problems on the line and some other related problems. It is an notorious open problem in the field of rendezvous research to decide the rendezvous value of the symmetric rendezvous search on the line. We obtained significant insight on this problem through our past work (<<Operations Research>>, Vol.56, 772-782). We wish to continue our research work on this topic with the hope to resolve or obtain significant additional insight on this challenge that remained open for many years. In this project we will try to refine the existing methods to improve the lower and upper bound of the symmetric redezvous value on the line so as to verify the conjecture of the symmetric rendezvous value on the line being 4.25 by numerical methods. On the other hand, we will also study the rendezvous problem on the circles of various length, which is expected to provide insight in proving the conjecture since line can be viewed as a circle with infinity length. Rendezvous problems are fundamental in vast applications in rescuing operation, automatic robots design, information management and military science etc. We aslo plan to study some rendezvous problems on general graphs in this project.

英文关键词： Search and Rendezvous；symmetric rendezvous problem；semi-definite programming；Newsvendor problem；mechanism design