ПРО МАТЕМАТИЧНІ МОДЕЛІ ЗАДАЧ КЛАСІВ  ЛИСТОНОШІ ТА КОМІВОЯЖЕРА

Андрій Васильович Морозов

doi:10.26642/tn-2015-2(73)-167-173

Автор(и)

Андрій Васильович Морозов Житомирський державний технологічний університет, Ukraine

DOI:

https://doi.org/10.26642/tn-2015-2(73)-167-173

Ключові слова:

транспортна мережа, задача комівояжера, гамільтонова задача комівояжера, загальна задача комівояжера, задача про китайського листоношу, задача про сільського листоношу, гамільтонова та кільцеві задачі про сільського листоношу

Анотація

Запропоновано класифікацію задач маршрутизації класів листоноші та комівояжера. Класифікація ґрунтується на описі базової моделі транспортної мережі, з якої випливають різні постановки важливих практичних завдань побудови маршрутів, що задовольняють заданим обмеженням і є оптимальними у розумінні обраного критерію. Одним з обмежень, що суттєво ускладнює вирішення цих задач, є вимога замкненості маршрутів, яка висувається у тих випадках, коли транспортний засіб починає і закінчує рух в одному пункті (базі). Інше обмеження полягає у тому, що замкнений маршрут транспортного засобу повинен містити визначені пункти та ділянки транспортної мережі. І, врешті, потрібно, щоб замкнений маршрут проходив кожну вказану ділянку і кожний вказаний пункт лише один раз.

У статті розглянуто такі задачі, як задача маршрутизації транспорту, класична задача комівояжера, гамільтонова задача комівояжера, задача про китайського листоношу, задача про сільського листоношу, загальна задача комівояжера, гамільтонова та кільцева задачі про сільського листоношу.

В умовах кожної з розглянутих задач маршрутизації міститься опис мережі комунікацій, яка визначає множину можливих шляхів слідування одного або декількох рухомих об'єктів. Тому для кожної задачі одним з вхідних параметрів є зважений граф з множиною вершин V і множиною ребер U.

Посилання

Dantzig G.B. The Truck Dispatching Problem / G.B. Dantzig, J.H. Ramser // Management Sci. – 1959. – Vоl. 6., № 1. – P. 80–91.

Панишев А.В. Модели и методы оптимизации в проблеме коммивояжера : монография / А.В. Панишев, Д.Д. Плечистый. – Житомир : ЖГТУ, 2006. – 300 с.

Панишев А.В. Модели и методы оптимизации замкнутых маршрутов на транспортной сети : монография / А.В. Панишев, А.В. Морозов. – Житомир : ЖГТУ, 2014. – 316 с.

Бронштейн Е.М. Детерменированные оптимизационные задачи транспортной логистики / Е.М. Бронштейн, Т.А. Заико // Автоматика и телемеханика. – 2010. – № 10. – С. 133–147.

Морозов А.В. Метод гілок та меж у гамільтоновій задачі про сільського листоношу / А.В. Морозов, А.В. Панішев // Системні дослідження та інформаційні технології. – 2012. – № 2. – С. 57–66.

Панишев А.В. Модификация метода Литтла для решения кольцевой задачи о сельском почтальоне / А.В. Панишев, А.В. Морозов, В.А. Скачков // Искусственный интеллект. – 2010. – Вып. 3. – С. 103–115.

Майника Э. Алгоритмы оптимизации на сетях и графах / Э. Майника. – М. : Мир, 1981. – 323 с.

Пападимитриу Х. Комбинаторная оптимизация. Алгоритмы и сложность / Х.Пападимитриу, К.Стайглиц. – М. : Мир, 1985. – 510 с.

Ovezgeldyyev A.O. Developing the Branch and Bound Method in the Problem of Searching for the Optimal Cyclic Route (Cyclic Rural Postman Problem) / A.O. Ovezgeldyyev, A.V. Morozov // Cybernetics and Systems Analysis. – September 2013, Vol. 49, Issue 5. – Pр. 739–748.

Morozov A. Modified branch and bound algorithm for solving the Hamiltonian Rural Postman Problem / A.Morozov, A.Panishev // Information Models of Knowledge. – Kiev ; Sofia, 2010. – Pр. 442–450.