一类邮递员送信问题

One Type of Postman Problem

本文讨论了一类有约束的邮递员送信问题,不同于经典的TSP(Travelling Salesman Problem)问题,它要求经过部分顶点一次且仅一次,回到初始点的最短路径.这里建立了0-1规划模型,给出了求解此问题的一种方法,对于类似邮路问题有一定的借鉴意义.

This paper discusses a kind of constraint postman problem , which differs from typical TSP problem , requiring a shortest path that passes certain vertexes once and once only , and finally goes back to the initial vertex . We have presented a 0-1 programming model for solving this kind of postman problem , which has certain reference value for similar postman problems .