The Chinese Postman

The paths left open in 1997

The 1997 report ended with two proposed extensions and an observation about working shifts. Nearly thirty years later all three have been followed up, in the code and on the solver page. This page explains what each extension asks, how hard it is to solve, and how close the answers come to the best possible.

How hard is hard?

A problem is polynomial when an algorithm is known whose running time grows like a power of the network size: twice the streets, a few times the work. Such problems can be solved exactly, with a proof of optimality, on city-sized networks. The Chinese Postman Problem of 1997 is one of them.

A problem is NP-hard when it is at least as hard as every problem whose solutions can be checked in polynomial time. No polynomial algorithm is known for any of them, and finding one would settle the most famous open question in computer science. For these problems there are two honest answers. An exact method, here branch-and-cut (the heir of the 1997 branch-and-bound), finds the optimum and proves it, but its running time can explode on large networks. A heuristic answers quickly and comes with a lower bound: no route can be shorter than the bound, so the distance between the two is the most the heuristic can be off. Some heuristics also carry a guarantee, a proof that they are never more than a fixed factor from the optimum on any network.

P versus NP

Whether a polynomial algorithm can exist for these problems is the P versus NP question, posed formally by Cook (1971) and, independently, by Levin (1973). It is one of the seven Millennium Prize Problems announced by the Clay Mathematics Institute in 2000, each with a prize of one million dollars; of the seven, only the Poincaré conjecture has been solved. P versus NP is still open: proofs are claimed regularly, and none has been accepted.

If P = NP were proved, every NP-hard problem on this page would have an exact polynomial algorithm, and heuristics would no longer be needed in principle. Two caveats: the proof might show that such an algorithm exists without showing how to build it, or it might give one whose running time grows with so high a power of the network size that it is useless in practice. Much of today's cryptography, which relies on some problems being hard, would also be at risk. If P ≠ NP, as most researchers expect, there is no shortcut, and the combination used here, already proposed in 1997, is the right one: an exact search as far as it can go, and beyond that a heuristic with a bound.

The postman shows how thin the line is. Edmonds' method solves the Chinese Postman Problem in polynomial time, yet mixing one-way with two-way streets, leaving some streets without service, or adding a second postman is enough to put it on the other side.

Summary

ProblemComplexityExact methodHeuristic and its guaranteeMeasured distance from the optimum
Every street, two-wayPolynomialMatching (Edmonds), in polynomial timeNot needed0: always optimal
Every street, one-wayPolynomialMinimum-cost flow, in polynomial timeNot needed0: always optimal
Every street, mixed one-way and two-wayNP-hardBranch-and-cut: proved on every benchmark network, all towns of up to 400 junctions and 8 of 10 at 900 and 1,600Orientation + balancing + local search. No guarantee is proved for this variant; the related heuristics of Frederickson are within 5/3, and Raghavachari and Veerasamy's within 3/2Heuristic: mean 0.41%, worst 4.76% (121 networks solved exactly)
Every street, first pass dearer than the nextPolynomialMatching on the cost of later passesNot needed0: always optimal
Only some streets (rural postman)NP-hard; polynomial when the streets to serve form one pieceBranch-and-cut: proved on all 57 benchmark networks and 10 of 18 synthetic towns within two minutesFrederickson: never above 3/2 of the optimum; then local searchFrederickson: mean 2.63%, worst 8.33%; after local search: mean 0.66%, worst 4.75%
Several postmen, shortest longest routeNP-hardBranch-and-cut on small networks onlySplit one tour: never above 2 − 1/k of the optimum; then local searchSmall networks, against the exact optimum: split alone mean 2.91%, after local search mean 0.02%, worst 1.25%
Fleet with vehicle capacity (CARP)NP-hardNot attempted here; the literature uses branch-cut-and-priceSplit one tour by capacity (Ulusoy), then moves between routesAgainst the best known solutions: median 5.78%, mean 5.50%, worst 14.78%

1. One-way streets

“La resolución de CPP para el caso asimétrico, lo que permitiría su aplicación a un número mucho mayor de casos.”

“Solving the CPP for the asymmetric case, which would allow it to be applied to many more cases.” — 1997 report, chapter 13

When every street is one-way, the problem stays polynomial: each junction must be left as often as it is entered, and the cheapest extra passes that balance every junction are a minimum-cost flow. The directed version therefore needs no heuristic at all.

Real towns mix one-way and two-way streets, and this mixed problem is NP-hard (Papadimitriou, 1976). Branch-and-cut proves the optimum on every one of the 92 benchmark networks, in at most 5.8 seconds, on all 20 towns of up to 400 junctions and on 8 of the 10 towns of 900 and 1,600 junctions. A heuristic orients the two-way streets, balances the junctions exactly, and improves the result by reversing streets; where the optimum is proven, it averages 0.41% above it. The method follows the orient-then-balance idea of Frederickson (1979), whose heuristic is never more than 5/3 of the optimum (3/2 on planar networks); Raghavachari and Veerasamy (1999) reached 3/2 on any network.

Chapter 9 of the 2026 report gives the details.

2. The first pass costs more

“Resolver el CPP (simétrico y/o asimétrico) con la variante de que [...] el valor asociado en cada arista variara en función de que fuera o no la primera vez que se recorre. Esto se adaptaría más a la situación de que una misma carretera puede tener una dificultad de recorrerla muy distinta en función de que esté nevada o la nieve esté ya apartada; o que una calle no costará tanto de recorrer con los contenedores recogidos o por recoger.”

“Solving the CPP (symmetric and/or asymmetric) with the variant that the value of each edge changes depending on whether or not it is the first time it is traversed. This would better match the fact that a road can be very different to drive depending on whether it is covered in snow or already cleared, or that a street costs less to drive once its bins have been emptied.” — 1997 report, chapter 13

Today this is the distinction between service and deadheading: the pass that clears the snow or empties the bins, and any later pass that only travels. It leads to two problems of very different difficulty.

When every street needs service

Each street is served exactly once, so the service costs are fixed; only the extra passes can change, and they cost the travel price. The best tour is therefore the ordinary postman solution computed on the travel costs. The problem stays polynomial and is solved exactly, as in chapter 3 of the report.

When only some streets need service: the rural postman

Usually only some streets need service: the main roads when it snows, the commercial streets for night cleaning. The other streets may still be used to travel. This is the rural postman problem, and it is NP-hard (Lenstra and Rinnooy Kan, 1976). The difficulty is precise: if the streets to serve form a single connected piece, the old matching method still solves it exactly; when they fall into several pieces, choosing how to join the pieces is what is hard.

Of the 57 benchmark networks whose files mark only some streets for service, 51 have their streets to serve in a single piece and are solved exactly by matching, in at most 4 seconds; branch-and-cut proves the other 6 in at most 6 seconds. On 18 synthetic grid towns with 20% or 50% of the streets to serve, branch-and-cut proves 10 within two minutes, the largest with 387 streets to serve. Over the 16 networks with several pieces and a proven optimum, Frederickson's heuristic alone is a mean 2.63% above the optimum (worst 8.33%, well inside its guarantee of 50%), and the local search brings this to 0.66% (worst 4.75%). On the other 8 towns, with up to 870 streets to serve, the optimum is not proved in two minutes, but the best route is within 6.39% of the lower bound.

3. Several postmen

“[...] el trabajo que se puede realizar en media jornada (o incluso en una jornada laboral entera), después de la cual se debe volver al punto de partida, es claramente limitado.”

“The work that can be done in half a working day, or even a whole one, after which one must return to the starting point, is clearly limited.” — 1997 report, chapter 13

In 1997 this observation explained why networks in practice stay small. It also points to the next problem: a district too large for one shift is shared among several postmen, all starting and ending at the depot.

k postmen, the longest route as short as possible

This min-max k-postmen problem is NP-hard even when every street must be served (Frederickson, Hecht and Kim, 1978). The heuristic writes out one postman's tour, cuts it into k consecutive pieces at the points that make the longest route shortest (a dynamic programme finds the best cut points exactly), and then moves and swaps streets between routes. Cutting an optimal single tour is never worse than 2 − 1/k times the optimum: 1.5 for two postmen, 1.67 for three.

On 62 small networks where branch-and-cut finds the exact optimum (two or three postmen), the best cut of one tour is a mean 2.91% above it, and never more than 27% (the guarantee allows 50% to 67%); after the local search the routes are optimal in 61 cases, and a mean 0.02% above the optimum (worst 1.25%). On 142 benchmark networks with 2 to 10 postmen the exact optimum is out of reach, and only the bound is available: the longest route is within a median 6.22% of it (worst 37.13%). Much of that distance is the bound's: on the small networks, where the optimum is known, the same bound is up to 18% below it.

Vehicles with a capacity

When each street produces a load (refuse, salt to spread) and each vehicle carries a limited amount, the problem becomes the capacitated arc routing problem, the CARP. It is NP-hard (Golden and Wong, 1981), and the largest benchmarks are still open: 31 of the 197 used here have no proven optimum. The same idea applies: one tour, cut where the vehicle fills up (Ulusoy, 1985), then streets moved between routes.

On the 197 classical CARP instances, this simple method is a median 5.78% above the best solutions published (mean 5.50%; it matches the best known on 16), with the number of vehicles left free: 65 instances use more than the file states, and on the other 132 the median is 4.7%. The best published solutions come from decades of dedicated metaheuristics and exact methods; the point here is how far the 1997 tour already goes when it is simply cut into vehicle loads.

Try them

On the solver page, the Service settings choose which streets need service (every street, a random share, the main streets of an OpenStreetMap area, or those marked in a benchmark file) and how many postmen share the work. The page shows the routes, the lower bound and how far from it the answer can be. For a single postman with scattered streets to serve, it can also prove the optimum by branch-and-cut.

For one-way streets in OpenStreetMap, tick On foot to let the postmen walk them in both directions; the extensions above work on two-way networks.

References