Given a connected mixed graph with costs on its edges and arcs, the mixed postman problem consists of finding a minimum cost closed tour of the mixed graph traversing all of its edges and arcs. It is well-known that this ...