The capacitated Canadian postman problem

The capacitated Chinese postman problem (CCPP) is one of the most important arc routing problems. This article presents two algorithms adapted to the Canada Post Corporation context (CPC context): a general heuristic for merging cycles (used to group arcs together) and an algorithm to sequence the arcs of a route (Euler’s tour with penalties). These two algorithms are tested or postal distribution problems in Canada.