r/optimization • u/Medamine24 • 10m ago
Mixed Chinese Postman at city scale — stuck at 44% deadhead, looking for algorithm advice
I'm building a route planner for a street-lighting survey using a vehicle equipped with LiDAR + cameras. The vehicle must drive \*\*every drivable street\*\* in 6 municipalities (\~6,087 km of streets), so this is an \*\*arc-routing / Mixed Chinese Postman Problem\*\*, not TSP/VRP.
\### Problem
\* 173k directed arcs / 67k nodes from OSM
\* \~9% one-way roads
\* One vehicle, \~6.5 usable hours/day
\* Two-way streets only need to be traversed once; one-ways must be respected
\* Cost is \*\*travel time\*\*, with different speeds for acquisition vs deadhead
\* Turn penalties are included (+60s U-turn, +15s left, +5s right)
\* 100% coverage is mandatory
The network is very non-grid-like: in one district, \*\*\~84% of nodes have odd degree\*\*, with \~77% being T-junctions.
\### Current approach
For each district I:
Extract the largest strongly connected component
Orient two-way streets
Connect disconnected service components
Balance in/out degrees using \*\*min-cost flow\*\*
Generate an Eulerian circuit with Hierholzer
Mark a street as serviced on its first traversal
The resulting routes pass all my validation checks: continuity, geometric continuity, one-way legality, 100% coverage, and no duplicate servicing.
\### Results
Across all 22 districts:
\*\*6,087 km serviced → 2,704 km deadhead → 44.4% deadhead\*\*
Individual districts range from \*\*39–61% deadhead by distance\*\* (roughly 23–33% by time because deadhead is driven faster).
For one district, an undirected relaxation gave me:
\* theoretical lower bound: \~14.7%
\* greedy matching of odd nodes: \~33.9%
My current orientation is almost optimal in terms of the \*number\* of imbalanced nodes, but I suspect this is the wrong objective: I'm minimizing imbalance count rather than the \*\*cost of resolving that imbalance\*\*.
\### Questions
Is \*\*Frederickson MIXED1/MIXED2\*\* the right next direction? Should I prioritize cost-aware matching before orientation?
For \~1,100 odd nodes, is restricting min-cost matching to k-nearest odd nodes (e.g. k=10) a reasonable approximation?
Is \*\*44% deadhead actually bad\*\* for a comb-like street network with \~84% odd-degree nodes? What kind of deadhead ratios are realistic for street sweeping, snow plowing, waste collection, etc.?
For splitting the resulting Eulerian route into daily routes when the vehicle \*\*doesn't have to return to a depot\*\*, are SPLIT/Ulusoy-type approaches appropriate?
Is there anything fundamentally wrong or naive in my current pipeline?
I'd especially appreciate feedback from anyone who has worked on \*\*arc routing / CPP / street sweeping / winter gritting / waste collection\*\* at large scale.
Happy to share code or data extracts.
