Информационные системы и технологии
МАТЕМАТИЧЕСКОЕ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ
ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ И АВТОМАТИЗИРОВАННЫХ СИСТЕМ
УДК 004.78:656.13
С.В. БЕЛОКУРОВ, В.П. БЕЛОКУРОВ,
Р.А. КОРАБЛЕВ, Р.А. СПОДАРЕВ
АЛГОРИТМ ПОИСКА ДЛЯ МНОГОЦЕЛЕВЫХ
ОПТИМИЗАЦИОННЫХ ТРАНСПОРТНЫХ ЗАДАЧ
Стратегическое планирование транспортных процессов является
многоцелевой задачей. В ее реализации наиболее важным является
математическая возможность сравнения нескольких сценариев развития
транспортных процессов и получения количественного и качественного прогноза
по каждому из них. Для этого предложен и теоретически обоснован
эффективный алгоритм поиска на множестве Парето большой мощности.
Ключевые слова: моделирование; векторные схемы; транспортные
системы; оптимизация; множество; теория выбора; алгоритм; транспортные
потоки.
Securing the safety of transport movement is considered as many-aim task.
The main question in this task is mathematical opportunity to compare several variants
of developing transport process and get qualitative and quantitative analyze on each
question. For this task we use and theoretically developed algorithm of searching of a
number of cycles of Pareto of a large capacity.
Keywords: modeling; vector schemes; transport system; optimization; great
number; theory of choicing; algorithm; transport net.
Стратегическое планирование процессов функционирования дорожнотранспортных
систем представляет собой одну из самых значимых и сложных задач.
Транспортная система представляет собой сложную организационно-техническую
систему со сложно прогнозируемым поведением. При использовании системного
подхода в работе транспорта необходимо не только решение многоцелевых
транспортных задач, но и целесообразное использование математического аппарата, в
котором появляется возможность сравнивать несколько сценариев развития
транспортных проблем, в результате чего получаем количественный и качественный
прогноз по каждому направлению. Последнее позволяет воспользоваться
единственным оптимальным вариантом выбора при принятии безошибочного
решения.
Целью данной работы является разработка алгоритма анализа и отсева
решений для многоцелевых оптимизационных транспортных задач.
Методы и модели решения многоцелевых оптимизационных транспортных
задач, как правило, описываются достаточно большим количеством качественных и
количественных признаков, наличием сложных зависимостей между ними.
Моделирование и оптимизация параметров и режимов на всех этапах жизненного
цикла и на всех уровнях организации, функционирования и управления таких систем
представляет собой трудоемкую задачу большой размерности.
ИСиТ № 4/54(565)2009
5
Стр.1
Научно-технический журнал
Так, например, при выборе и распределении автотранспортных средств (АТС)
по маршрутной транспортной улично-дорожной сети (УДС), как правило,
преследуется множество разных целей. Такие многоцелевые задачи достаточно
сложны в реализации. Одним из путей решения таких задач является привлечение
эффективного аппарата многокритериальной оптимизации (МКО).
Численная реализация моделей МКО – трудоемкая и кропотливая работа,
связанная со значительным объемом вычислений, требующая больших временных
затрат, использования громоздких численных схем. Существующее математическое
обеспечение характеризуется узкой направленностью, связанной с конкретной
предметной областью и жестко заложенными численными схемами и алгоритмами и,
как правило, основано на случайном выборе или различных способах дискретизации
[1-8]. При этом нет объективных обоснований, почему был сделан выбор той или
иной части множества вариантов.
В связи с вышесказанным, целью данной работы являлась разработка
алгоритма выбора решений на множестве Парето большой мощности, позволяющего
эффективно проводить анализ и отсев недоминируемых вариантов решений без
потери качества и обладающего высокой скоростью поиска при относительной
простоте реализации.
Независимо от исходной области поиска (дискретной или непрерывной), на
итерациях поиска получается дискретный набор недоминируемых вариантов решения
задачи X. Определим на нем значения критериальных функций yi=qi(x)
y обозначим значение i–й критериальной функции в точке x
j
Будем считать, что (y y2 ,..., y ) (
j
i
Пронумеруем числа (y jj
1
1 ,
j
=1, p) в порядке убывания. Если при этом встретятся равные,
n = y y2 ,..., y )
j
1 ,
k
k
k
n
то нумеруем их в порядке убывания следующей координаты. Если (n–1) координата
двух точек совпадает, то выводим из рассмотрения точку, имеющую меньшую n–ю
координату. Аналогично нумеруем последующие координаты y jj
1
( =1,n).
множества допустимых оценок Y, множество {k} – точек с координатами (k1, k2, …,
kn), каждая из которых принимает целое значение из интервала [1, …, p]. При этом в
каждой из гиперплоскостей размерности n–1, параллельных координатным, лежит
одна и только одна из точек этого множества. Множество лежит в n–мерном кубе
размером (p–1)×(p–1)×…×(p–1).
В силу построения любая точка множества {k} лежит на пересечении n
гиперплоскостей размерности n–1, параллельных координатным гиперплоскостям и
проходящим через точки (k1, k2, …, kn). По той же причине из
(y y2 ,..., y ) (
i
1 ,
i
n ≥ y y ,..., y ) следует, что (k ki ,...,k ) (
i
1 ,
j
j
2
j
n
i ,
1
2
i
n ≤ k k ,..., y ), а значит, выделение
1
j ,
2
j
n
j
точек, оптимальных по Парето, на множестве значений критериев оптимизации Y
эквивалентно аналогичной операции в множестве {k}, только в смысле сравнения ≤.
Парето, необходимо,
p + ≥ + + + n
( 1) 1
n−
6
ki
1
ki
2
...
i
Теорема 1. Для того, чтобы точка множества {k} принадлежала множеству
чтобы ее
координаты удовлетворяли
k .
ИСиТ № 4/54(565)2009
условию:
В результате такого отображения мы поставили в соответствие точкам
j = (x x1 , 2 ,...,x j)( =1,n).
j
(
j
n
тогда и только тогда, когда j=k.
i =1,n). Через
j
Стр.2