排序和路线问题：复杂性和在线算法

本项目的主要内容是对一些排序和路线问题的复杂性和算法，特别是在线算法进行研究。排序和路线问题都是有很强应用背景的组合最优化问题，关于它们的在线算法的研究是当前国际上组合最优化领域的研究前沿，有很高的研究价值和研究难度，特别是本项目将要开展的关于在线Dial-a-Ride问题的研究在国际上才刚刚兴起，在国内更是一个新的方向，这方面的研究将具有开拓性。本项目是一项跨应用数学、运筹学和理论计算机科学的交叉项目，在本项目的研究中我们将利用近年来在这些学科的发展中出现的一些新方法，如随机算法、PCP理论，这些新方法的应用和发展不仅对于排序和路线问题的研究是有意义的，而且对于推动组合最优化这门交叉学科的发展也是有意义的。