Details

For graphs of modest size, the method of integer linear programming can be used to solve the routing problem and the traveling salesman problem. The other two problems can be solved even for graphs of very large size by using the blossom algorithm for finding a perfect matching of minimal weight.

For the plotter problem, we form the complete graph whose vertices are all odd-degree vertices, with weights being the straight-line distance between the vertices. Then a minimal-weight perfect matching of this graph tells us which edges can be added so that the resulting graph (possibly with multiple edges) has only vertices of even degree. An Eulerian tour of the resulting graph gives the optimal plotter path, since the pen-up distance is minimized.

For the Chinese postman problem, one takes a similar approach, but the weight of an edge joining two odd-degree vertices is taken to be the length of the shortest path between them in the original network. Again, the blossom algorithm can find a minimal perfect matching, and the resulting even-degree graph is Eulerian. We find an Eulerian cycle and then replace each non-edge by the corresponding shortest path in the original network.