一类邮递员送信问题

摘要

本文讨论了一类有约束的邮递员送信问题，不同于经典的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 .