|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
Combined Algorithm for Solving the Asymmetric Traveling Salesman Problem as Applied to Transport Logistics Problemsстатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК- Авторы: Ulyanov M.V., Fomichev M.I.
- Журнал: Информационные технологии
- Том: 28
- Номер: 3
- Год издания: 2022
- Издательство: Новые технологии
- Местоположение издательства: Москва
- Первая страница: 141
- Последняя страница: 147
- DOI: 10.17587/it.28.141-147
- Аннотация: Задача коммивояжера в общей постановке состоит в поиске гамильтонова цикла, обладающего минимальной суммой весов дуг в полном ориентированном асимметричном графе. Несмотря на простую постановку, задача коммивояжёра является NP – трудной. Метод ветвей и границ является основой наиболее эффективного по времени алгоритм решения задачи коммивояжера, доставляющего точное решение. Однако, для ряда прикладных задач, время получения решения с использованием этого алгоритма практически не приемлемо. Несмотря на веер эвристических алгоритмов, разработанных для задачи коммивояжера, для некоторых прикладных задач в бизнес-информатике и логистике актуально получение точных решений в диапазоне малых размерностей. В статье приведены результаты по разработке и статистическому исследованию комбинированного алгоритма решения задачи коммивояжера, получающего точные решения, в условиях ограничения по среднему времени решения для размерностей, не превышающих 55, возникающих при решении задач транспортной логистики (данные предоставлены компанией ООО «Группа КИТ»). Рассматривается реализация метода ветвей и границ в комбинации с метаэвристическим алгоритмом Lin-Kernighan-Helsgaun. Описаны подходы, позволившие при разработке этого комбинированного алгоритма существенно сократить время решения индивидуальных задач коммивояжера, и удовлетворить требование компании по временной эффективности. Ключевые слова: задача коммивояжера, комбинированный алгоритм, метод ветвей и границ, алгоритм Lin-Kernighan-Helsgaun, временная эффективность, транспортная логистика
- Добавил в систему: Ульянов Михаил Васильевич