一些路线和调度问题的算法与理论研究

The traveling salesman problem (TSP) is one of the most important problems in combinatorial optimization. Some significant breakthroughs in the study of approximation algorithms for TSP and related problems just happen in recent years. With the great developments, in this project, we will investigate the multiple traveling salesmen problem, the multiple vehicle routing/scheduling problem, and the related graph cover problem. These studied problems all have a very wide range of practical applications, but most of them are NP-hard, and have some kind of lower bounds of inapproximability, and the existing algorithms cannot meet the needs of applications. The main purpose of the project is to develop polynomial time approximation algorithms for them, but in some circumstances, we also study heuristics such as local search methods, in order to promote applications. In addition, we discuss some fundamental theoretical issues of some problems, such as the inapproximability and polyhedral properties. In the research, we will make creative use of various combinatorial optimization methods, such as network flow, matroid, linear and integer programming, randomization, etc. We wish to explore some new methods, and thus promote the development of combinatorial optimization.

旅行商问题是组合最优化中最重要的问题之一，关于它及其相关问题的近似算法的研究在最近几年才刚刚取得突破性发展，本项目将以此为契机，对多旅行商问题、多车辆路径和调度问题，以及相关的图覆盖问题进行研究。这些问题有极其广泛的应用场景，但大部分是NP困难问题，而且存在某种不可近似性下界，现有算法不能满足实际应用的需要。项目主要研究高效的多项式时间近似算法，在一些情况下也考虑局部搜索等启发式算法，促进相关的应用。另外，项目也研究一些问题的不可近似性质和多面体性质等基础理论问题。在这些研究中，我们会创造性地综合利用多种组合最优化方法，比如网络流、拟阵、线性和整数规划、随机化方法等等，并期望发展和发掘一些新技巧、新方法，从而推动整个组合最优化学科的发展。

旅行商问题及其相关的一些路线问题、调度问题是组合优化研究的重要领域，这些问题不仅有极其广泛的应用场景，也是理论研究的前沿，关于它们的近似算法的研究在最近几年才刚刚取得突破性发展，本项目以此为契机，对这些路线问题进行研究，得到了一些具有良好性能比的算法。研究多源和多源多终端哈密尔顿路问题，首次就这两个问题给出了性能比小于2的近似算法，并在旅行商个数为常数时，得到了性能比为1.5+ε和5/3+ε的近似算法，相关技术可应用于类似问题。研究最小-最大圈（树/路）覆盖问题（MMCCP/MMTCP/MMPCP），证明了MMCCP和多根MMCCP的下界至少为3/2，无容量限制的单根MMPCP和MMTCP的下界至少为5/4和4/3；给出了有容量限制的带根MMCCP的6-近似算法，以及有容量限制的带根MMTCP和MMPCP的7-近似算法。研究最小圈（树/路）覆盖问题（MCCP/MTCP/MPCP），提出了新的线性规划松弛，证明了它们的整性间隙分别不超过6、4、4；对于树形网络上的单根MCCP和MPCP，提出了新的有效不等式，得到了整性间隙不超过5/2和5的线性规划松弛。新的整性间隙明显缩小了与当前最好近似算法性能比的距离。研究乡村邮递员和中国邮递员覆盖问题，分别得到了5-近似和4-近似算法。此外，还研究了最小-最大乡村邮递员和中国邮递员覆盖问题（MMRPCP/MMCPCP），分别给出了6-近似和4-近似算法。对于最小-最大乡村邮递员路覆盖问题（MMRPWCP），给出了5-近似算法。在邮递员个数为常数时，分别给出了MMRPWCP 和MMRPCP的3+ε近似和4+ε近似算法。研究目标函数为车辆派出数量及总旅行费用的加权和的带距离约束的车辆路径问题（DVRP-TC），在树形网络时，给出了2-近似算法以及无根情形的3-近似算法，对于一般网络和线形网络，分别给出了无根情形的5-近似算法和多项式时间最优算法。此外，DVRP-TC的几个线性规划松弛的整性间隙被证明。研究有服务等级约束的同类机在线可分排序问题，给出了基于线性规划的最优算法和下界方案。