Том 21, номер 4, 2014 г., Стр. 42-53

УДК 519.8
Истомин А. М.
Вероятностный анализ одной задачи маршрутизации

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

Ключевые слова: задача маршрутизации транспортных средств, приближённый алгоритм, вероятностный анализ, гарантированная оценка точности.

Истомин Алексей Михайлович ^1,2
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: alexeyistomin@gmail.com

Статья поступила 13 декабря 2011 г.
Исправленный вариант — 13 февраля 2014 г.

Литература

[1] Гимади Э. Х., Глебов Н. И., Сердюков А. И. Об одной задаче выбора циклического маршрута и загрузки транспортного средства // Дискрет. анализ и исслед. операций. Сер. 2. - 1998. - T. 5, №1. - C. 12–18.

[2] Гимади Э. Х., Истомин А. М., Рыков И. А. О задаче нескольких коммивояжёров с ограничениями на пропускные способности рёбер графа // Дискрет. анализ и исслед. операций. - 2013. - T. 20, №5. - C. 13–30.

[3] Гимади Э. Х., Шахшнейдер А. В. Приближённые алгоритмы с оценками для задач маршрутизации на случайных входах с ограниченным числом клиентов в каждом маршруте // Автоматика и телемеханика. - 2012. - №2. - C. 126–140.

[4] Arora S. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems //JACM. - 1998. - Vol. 45, N5. - P. 753–782.

[5] Beardwood J., Halton J. L., Hammersley J. M. The shortest path through many points // Proc. Camb. Phil. Soc. - 1959. - Vol. 55. - P. 299–327.

[6] Bompadre A., Dror M., Orlin J. B. Probabilistic analysis of unit-demand vehicle routeing problems // J. Appl. Prob. - 2007. - Vol. 44. - P. 259–278.

[7] Haimovich M., Rinnooy Kan A. H. G. Bounds and heuristics for capacitated routeing problems //Math. Oper. Res. - 1985. - Vol. 10. - P. 527–542.