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

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.

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

本项目中，我们首先研究了直线上对称的Rendezvous值的上下界问题，我们将下界由4.1520提高到4.1872；研究了偶数圈上对称的Rendezvous值的问题，基本解决了圈数为4, 6和8的圈上对称的Rendezvous值的问题；归纳和分析了偶数圈上的对称的Rendezvous值的一些规律；研究了直线上对称的Rendezvous值问题，偶数圈上对称的Rendezvous值问题的规律，对直线上对称的Rendezvous值问题的研究提供了重要的启示和有用的帮助。我们研究了模糊规避和风险规避下的报童问题，Scarf在1958年对经典的报童问题进行了推广，研究了模糊规避，即分布鲁棒下的报童问题，给出了订货公式，我们进一步研究了模糊规避和风险规避下的报童问题，推广了Scarf的订货公式。该结果发表在运筹学领域国际顶尖学术期刊《Operations Research》上。本项目中，我们还研究了直线上防策略的厌恶型选址问题的机制设计问题，我们分别完全刻画了单个代理、两个代理以及多个代理的防策略机制的特征，在此基础上给出了直线上防策略厌恶型选址问题的近似比，并进一步解决了文献中关于近似比下界的一个open问题。