How to prove NP-completeness of this mail-problem?
Given an instance of partition $X=\{x_1, x_2, \dots, x_n\}$ you can build the graph $G=(V,E)$ where $V=\{0, 1, \dots, n\}$ and, for any pair of indices $i$, $j$ with $0 \le i&lt;j \le n$, there is an edge $(i,j) \in E$ of weight $x_i$. Additionally, $E$ contains all edges $(i,0)$ for $1 \le i \le n$ with weight $0$.
The deposit will be vertex $0$. If you are able to find two cycles $C_1$, $C_2$ of the same length then the sets $\{x_i : i \ge 1 \wedge i \in C_1\}$ and $\{x_i : i \ge 1 \wedge i \in C_2\}$ will be a partition of $X$.
Similarly, a partition of $X$ induces two cycles of the same length in $G$.
This shows that the problem is $\mathsf{NP}$-hard even with just $2$ postmen.
You can generalize this reduction to any number $k$ of cycles by adding $k-2$ additional vertices $y_1, \dots, y_{k-2}$ along with all edges $(0, y_i)$ of weight $\frac{1}{2}\sum_{i=1}^n x_i$ and $(y_i, 0)$ of weight $0$.