|
Дискретный анализ и исследование операций, 2014, том 21, выпуск 4, страницы 42–53
(Mi da784)
|
|
|
|
Вероятностный анализ одной задачи маршрутизации
А. М. Истоминab a Новосибирский гос. университет, ул. Пирогова, 2, 630090 Новосибирск, Россия
b Институт математики им. С. Л. Соболева СО РАН, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Аннотация:
Рассматривается задача маршрутизации транспортных средств, состоящая в нахождении совокупности последовательностей обхода клиентов с минимальными транспортными затратами при условии выполнения ограничений на максимальное число клиентов в каждом маршруте (вместимость транспортного средства). Для решения задачи известна эвристика ITP (Iterated Tour Partitioning). Эта эвристика является $2$-приближённым алгоритмом в случае детерминированных входных данных и $(2-c)$-приближённым алгоритмом ($c>0$) в случае, если координаты вершин графа являются независимыми случайными величинами с равномерным распределением на единичном квадрате. Оценка точности $2-c$ эвристики ITP обоснована для равномерного распределения в круге единичной площади. Ил. 3, библиогр. 7.
Ключевые слова:
задача маршрутизации транспортных средств, приближённый алгоритм, вероятностный анализ, гарантированная оценка точности.
Статья поступила: 13.12.2011 Переработанный вариант: 13.02.2014
Образец цитирования:
А. М. Истомин, “Вероятностный анализ одной задачи маршрутизации”, Дискретн. анализ и исслед. опер., 21:4 (2014), 42–53
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da784 https://www.mathnet.ru/rus/da/v21/i4/p42
|
Статистика просмотров: |
Страница аннотации: | 203 | PDF полного текста: | 70 | Список литературы: | 52 | Первая страница: | 14 |
|