Balancing Directed Routes for the Chinese Postman

Why Directed Routes Need Balancing

For an undirected network, the Chinese postman problem is to find a least-cost closed route that traverses every edge at least once. In a directed network, each arc has a prescribed direction, so a route that duplicates arcs in the wrong direction can make the imbalance worse. The key is to measure, at each vertex, how many more arcs leave than enter. The extra route must correct that difference, and finding the least-cost correction is a minimum-cost flow problem.

Throughout, consider a finite directed graph whose arcs have positive costs. The graph is strongly connected on the vertices incident with arcs: for each ordered pair of such vertices, there is a directed path from the first to the second. Isolated vertices do not affect a route and may be ignored. This connectivity assumption ensures that a closed route covering all arcs is possible after the degrees are balanced. Repeated traversals are treated as extra copies of arcs, even though the original directed graph is simple.

The total imbalance is zero: each original arc contributes one to an outdegree and one to an indegree, so \(\sum_{v\in V}b(v)=0\). Consequently, total excess outdegree equals total excess indegree. Vertices with excess indegree must send out extra route; vertices with excess outdegree must receive extra route. This direction is important.

The Minimum-Cost Flow Formulation

Let \(c(e)>0\) be the cost of traversing arc \(e\). For each arc \(e\), let \(x_e\) be the nonnegative integer number of extra copies of that arc. The integer condition matters: a route can duplicate an arc only a whole number of times. The extra copies have net outdegree minus indegree \(d^-(v)-d^+(v)\) at each vertex exactly when

Among all such choices, minimize \(\sum_{e\in E}c(e)x_e\). There are no upper capacities: any original arc can be copied as often as needed. The original traversal cost \(\sum_{e\in E}c(e)\) is fixed, so minimizing the extra cost also minimizes the total route cost.

There is also a useful path-based version. Set \(s(v)=d^-(v)-d^+(v)\). Vertices with \(s(v)>0\) are supplies of extra route, and vertices with \(s(v)<0\) are demands. For a supply vertex \(u\) and demand vertex \(v\), let \(D(u,v)\) be the cost of a cheapest directed path from \(u\) to \(v\). The path-based problem sends integer amounts \(y_{uv}\) from supplies to demands, with each supply sending \(s(u)\) units and each demand receiving \(-s(v)\) units, at cost \(\sum_{u,v}D(u,v)y_{uv}\).

Why can the arc-flow and path-based formulations be used interchangeably? A feasible integer arc flow can be decomposed into directed paths from supply vertices to demand vertices, together with directed cycles. One way to see this is to add a temporary source with \(s(u)\) outgoing units to each supply vertex, and a temporary sink receiving \(-s(v)\) units from each demand vertex. At every original vertex the resulting flow is conserved. Trace positive-flow arcs from the temporary source: conservation lets the trace continue until it reaches the sink, after removing any cycle encountered along the way. Subtract one unit along that source-to-sink path and repeat. Any remaining positive flow is balanced and can be removed as directed cycles. Since every arc cost is positive, removing these cycles cannot increase cost. Each supply-to-demand path costs at least \(D(u,v)\). Conversely, sending \(y_{uv}\) units along a cheapest path for each pair gives a feasible arc flow of exactly the path-based cost. Thus the minimum costs agree.

Why the Flow Gives a Postman Route

Proof. First take any closed route traversing every original arc at least once, and let \(x_e\) count its extra traversals of arc \(e\). In a closed route, every vertex is entered as many times as it is left. Therefore the augmented outdegree equals the augmented indegree at each vertex. Subtracting the original degrees gives the balance equation, so these extra traversals form a feasible integer balancing flow. Their cost is the route’s extra cost. The minimum flow cost is therefore no greater than the extra cost of any postman route.

Conversely, take any feasible integer balancing flow and add \(x_e\) copies of each arc \(e\). The balance equation makes the augmented indegree and outdegree equal at every vertex. The augmented directed graph remains strongly connected on its vertices incident with arcs, because it contains the original strongly connected graph. By the directed Euler circuit characterization established in the earlier material on directed Euler circuits, a strongly connected directed graph with equal indegrees and outdegrees has a circuit using every arc exactly once. Apply that result to the augmented graph. Its Euler circuit is a closed postman route, and its extra cost is \(\sum_{e\in E}c(e)x_e\). A minimum-cost flow therefore produces a route of minimum extra cost, proving the equality. \(\square\)

This characterization also gives a practical workflow: compute the degree imbalances, send route from excess-indegree vertices to excess-outdegree vertices along directed paths, and choose the least-cost feasible flow. Then add the corresponding arc copies and use a directed Euler-circuit construction to list the route.

A Sign Error to Avoid

Common mistake: sending extra route from a vertex with excess outdegree toward a vertex with excess indegree. In the first example, this would mean duplicating \(a\to c\), which costs \(4\). But \(a\) already has one more outgoing arc than incoming arc, and the extra \(a\to c\) increases that difference to \(2\). At \(c\), it increases the excess indegree from \(1\) to \(2\). The correction is to send route from the excess-indegree vertex \(c\) back to the excess-outdegree vertex \(a\), duplicating \(c\to a\) at cost \(3\). Check the sign by writing the balance equation at each vertex before choosing paths.

The flow formulation is useful because it separates two tasks: degree balance determines how much extra route each vertex needs to send or receive, while arc costs determine which directed paths should carry that route. A path that is cheap in the undirected network may be unavailable or expensive in the directed one; only directed paths from supplies to demands are valid.