Proposition of an exact solution to the Mixed Chinese Postman Problem through the pseudo-edges methodology.

The waste collection service is essential for maintaining public health, preserving the environment and quality of life in both urban and rural areas. In this context, it is of paramount importance that the garbage collection trucks of a given city use efficient routes in order to serve the largest number of streets, without excessive repetitions that can impact the expenses associated with this service.

One of the approaches to solve this problem is the use of the solution methods for the Chinese Postman Problem (CCP), which aims to find the shortest route by visiting, at least once, all the edges of a graph that represents the set of streets traveled. In the mixed version of PCC,  we have an extension of the main idea of the problem to graphs that can contain both edges (bidirectional) and arcs (unidirectional). This work presents an exact algorithm to find the solution of such a version, based on the creation of structures called pseudo-edges, which function as a substitution for the edges of the original graph. 

The approach used to resolve mixed PCC is based on the exact algorithm proposed by Sherafat (1988). Such an approach consists of first transforming the mixed graph into a directed graph through the expansion of the edges in the so-called pseudo-edges. A pseudo-edge consists of a subset of four vertices joined by five arcs, where two of the vertices are the same as those belonging to the original edge