Многокритериальные задачи маршрутизации

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

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

Первая глава посвящена однокритериальным задачам маршрутизации. Выделены основные классы задач маршрутизации, рассмотрены как классические постановки (такие, как задачи поиска оптимального маршрута на ациклическом и произвольном графах, задача коммивояжера), так и их модификации. Подробно описаны формулировка, математическая постановка, и алгоритмы решения с оценкой их вычислительной сложности для каждой из рассмотренных задач.

Вторая глава посвящена многокритериальным задачам маршрутизации. Подробно рассмотрены постановки задач и подходы к их решениям, преимущества и недостатки каждого из подходов, вычислительная сложность и трудоемкость задач. Особое внимание уделено общим схемам решения задач многокритериальной оптимизации (такие, как введение схем компромисса между критериями, построение полной и представительной совокупностей эффективных оценок), а также выводу общих рекуррентных соотношений для построения полной совокупности эффективных оценок в многокритериальных задачах.