The Geometric Directed Chinese Postman Problem

Code and data supporting the article "The Directed Chinese Postman Problem with Angle-Dependent Turn Costs: Exact Formulation, Performance Guarantees, and Computational Analysis." This archive contains the complete Python implementation of the two-stage algorithm for the directed Chinese Postman Problem with geometry-derived turn penalties (minimum-cost flow for arc multiplicities, followed by per-vertex Hungarian matching with sub-cycle merging), together with the integer-programming reference solvers used for benchmarking: the certified lower bound, its LP relaxation, and an exact solver that separates transition-connectivity constraints in a cutting-plane loop. Also included are generators for four synthetic instance families (orthogonal grids, grids with diagonals, one-way grids, and radial networks), two comparison baselines, and an OSMnx pipeline for extracting real road networks from OpenStreetMap. The results directory provides one CSV per table and figure in the paper's computational section: the scaling study, the robustness study across turn-cost functions, the baseline comparison, the full perturbation study, the data behind the scaling figure, and the real-network run for the City of Fairfax, Virginia. All optimality gaps are reported against certified lower bounds and are therefore upper bounds on the true gaps. A single self-contained driver script regenerates every table and figure, including the network extraction, on a free hosted CPU runtime in roughly 10 to 25 minutes. The script validates itself against nine independently computed lower bounds before reporting results. The exact execution environment and a SHA-256 file manifest are included. Licence: CC BY 4.0. Requires Python 3.10 or later; dependencies are pinned in requirements.txt.