中国邮递员问题的整数规划模型

Integer Programming Modeling for Chinese Postman Problems

基于无向图的传统中国邮递员问题,给出了相应的显式整数规划模型,应用整数规划软件包求解可以方便地确定相应问题的最优投递路线,进一步地,讨论了一类基于有向图的广义中国邮递员问题,给出了相应的显式整数规划模型;并研究了随机中国邮递员问题,建立了相应的确定型等价模型。举例说明了各种模型的有效性。最后,讨论了中国邮递员问题的可能推广及其建模问题。

As far as the traditional Chinese Postman Problem（CPP） is concerned,based on the discussions in the undirected and directed graphs respectively,the corresponding integer programming models are proposed,some numerical examples are given to demonstrate the utility of the models.Furthermore,the models are extended to the case with stochastic weights（the corresponding problem is called Stochastic Chinese Postman Problem）.Finally,some possible generalizations of the Chinese Postman Problem are discussed briefly.