Approximate algorithms with estimates for routing problems on random inputs with a bounded number of customers per route

We propose approximate algorithms for routing problems with a bounded number of clients on each route ($k$-VRP and Multi-Depot $k$-VRP). We derive estimates of the algorithms' quality and conditions for their asymptotic exactness in the case of a complete graph in which the weights of the edges (arcs) are independent random variables with a common distribution function.

Presented by the member of Editorial Board: A. I. Kibzun