中国邮递员问题50年

首先介绍一般邮递员问题, 涉及费用、服务侧、衔接费用、次序等要素. 然后简要综述过去50年来中国邮递员问题、有向图上中国邮递员问题、带风向的邮递员问题、混合图上邮递员问题以及乡村邮递员问题等一般邮递员问题的特殊情况的研究进展, 突出问题的线性规划描述及相应的组合多面体结构, 着重讨论问题的模型、精确算法及其时间复杂度、NP-困难情形下的近似算法及其性能比.

Chinese postman problem over 50 years

We introduce the general postman problem firstly, involving issues such as serving and traversing cost, sides of serving, turn cost and serving hierarchy and so on. We then survey briefly the research on the Chinese postman problem, the Chinese postman problem on directed graphs, postman problems on mixed graphs, on graphs with wind and on rural districts, focusing on their linear programming formulations and the structures of the corresponding polyhedra, addressing the models of problems, exact algorithms and their time complexities, and the approximation approaches and their performance.