Вероятностный анализ одной задачи маршрутизации

Рассматривается задача маршрутизации транспортных средств, состоящая в нахождении совокупности последовательностей обхода клиентов с минимальными транспортными затратами при условии выполнения ограничений на максимальное число клиентов в каждом маршруте (вместимость транспортного средства). Для решения задачи известна эвристика ITP (Iterated Tour Partitioning). Эта эвристика является $2$-приближённым алгоритмом в случае детерминированных входных данных и $(2-c)$-приближённым алгоритмом ($c>0$) в случае, если координаты вершин графа являются независимыми случайными величинами с равномерным распределением на единичном квадрате. Оценка точности $2-c$ эвристики ITP обоснована для равномерного распределения в круге единичной площади. Ил. 3, библиогр. 7.