On $m$-capacitated peripatetic salesman problem

We consider a particular case of the problem of finding $m$ Hamiltonian cycles with capacity restrictions on edges usage ($m$-Capacitated Peripatetic Salesman Problem, $m$-$\mathrm{CPSP}$): the $2$-CPSP on minimum and maximum with edge weights from an integer segment $\{1,q\}$. The edges capacities are independent identically distributed random variables which assume $2$ with probability $p$ and $1$ with probability $1-p$. Polynomial algorithms for $2$-$\mathrm{CPSP_{min}}$ and $2$-$\mathrm{CPSP_{max}}$ with guarantee approximation ratio in average for all possible inputs are presented. In the case when edge weights are $1$ and $2$, the presented algorithms have approximation ratio $(19-5p)/12$ and $(25+7p)/36$ for the $2$-$\mathrm{CPSP_{min}}$ and the $2$-$\mathrm{CPSP_{max}}$ correspondingly. Ill. 17, bibliogr. 20.