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

Морозов, А.В.; Morozov, A.V.

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

Морозов, А.В.; Morozov, A.V.

URI: http://eztuir.ztu.edu.ua/123456789/2086

Date: 2015

Abstract (ukr):

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

Abstract (eng):

We propose a classification of problems of the Postman and Traveling Salesman. The classification is based on the description of the basic model of the transport network, which implies different productions of important practical problems of building routes that satisfy the given constraints and are optimal in the sense of the selected criteria. One of the limitations, substantially complicates the solution of these problems is the requirement of the closed route, which extends in the cases, when the vehicle starts and stops the movement of one point (the base). Another limitation is that the closed route of the vehicle must include certain items and portions of the transport network. And finally, you need to close the route passes through each designated portion, and each specified vertex exactly once. The article describes problems such as the Vehicle Routing Problem, classic Traveling Salesman Problem, the Hamiltonian Traveling Salesman Problem, the Chinese Postman Problem, the Rural Postman Problem, General Traveling Salesman Problem, Hamiltonian and Cyclic Rural Postman Problem. In the context of each of the considered problems of routing describes the communications network, which defines a number of possible ways of following one or more moving objects. Therefore, for each problem one of the inputs is a weighted graph with vertex set V and edge set U.

Show full item record