An optimal algorithm for the mixed Chinese postman problem

DOI<97::AID-NET1>3.0.CO;2-8 10.1002/(SICI)1097-0037(199603)27:2<97::AID-NET1>3.0.CO;2-8zbMath0851.90128OpenAlexW1968384435MaRDI QIDQ4887738

Jean-Claude Picard, Yves Nobert

Publication date: 5 August 1996

Full work available at URL: https://doi.org/10.1002/(sici)1097-0037(199603)27:2<97::aid-net1>3.0.co;2-8

zbMATH Keywords

Chinese postman problemGomory cutsblossom inequalitiesbalanced set constraints

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10)

Related Items

Approximation algorithms for solving the constrained arc routing problem in mixed graphs, Two-phase branch-and-cut for the mixed capacitated general routing problem, Routing problems: A bibliography, Modeling and solving several classes of arc routing problems as traveling salesman problems, Arc routing problems: A review of the past, present, and future, Approximation algorithms for multi-vehicle stacker crane problems, Zigzag inequalities: a new class of facet-inducing inequalities for arc routing problems, Lower and upper bounds for the mixed capacitated arc routing problem, A comparison of two different formulations for arc routing problems on mixed graphs, Lower bounds for the mixed capacitated arc routing problem, Uncertain multi-objective Chinese postman problem, A GRASP heuristic for the mixed Chinese postman problem, An integer programming approach for the Chinese postman problem with time-dependent travel time, The time-dependent rural postman problem: polyhedral results