Приближенные алгоритмы с оценками для задач маршрутизации на случайных входах с ограниченным числом клиентов в каждом маршруте

Для задач маршрутизации с ограниченным числом клиентов в каждом маршруте ($k$-VRP и Multi-depot $k$-VRP) предложены приближённые алгоритмы. Получены оценки качества работы алгоритмов и условия их асимптотической точности в случае полного графа, в котором веса рёбер (дуг) являются независимыми случайными величинами с общей функцией распределения.

Статья представлена к публикации членом редколлегии: А. И. Кибзун