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

Abstract

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