Национальная академия наук Беларуси


Использование технологии гибкого управления для оптимизации движения транспорта по магистрали



страница2/16
Дата28.11.2017
Размер3.17 Mb.
ТипТезисы
1   2   3   4   5   6   7   8   9   ...   16

Использование технологии гибкого управления для оптимизации движения транспорта по магистрали
C.В. Анфилец, В.Н. Шуть

Брестский государственный технический университет, Беларусь



e-mail: lucking@mail.ru
Развитие транспортной инфраструктуры, в том числе развитие улично-дорожной сети, всегда значительно отстает от роста количества автомобильного транспорта. Это приводит к увеличению загрузки уличной сети и снижению эффективности использования транспорта [1].

Одним из способов, позволяющих сгладить проблемы, связанные с суточными колебаниями интенсивности движения транспорта, является использование многопрограммного жесткого регулирования [2], координированного управления.

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

Можно модифицировать алгоритм программ местной коррекции координированного регулирования, если возложить некоторые дополнительные функции на детекторы транспорта. Для реализации предлагаемого алгоритма улавливания групп транспортных средств необходимо, чтобы детекторы транспорта фиксировали на подходе к перекрестку начало группы.

Современные детекторы транспорта позволяют фиксировать не только наличие транспортных средств, но и подсчитывать их, фиксировать их скорость, а также состав транспортного потока. Предлагается алгоритм поэтапной настройки, который основывается на построении распределения импульса интенсивности в светофорном цикле.

Моделирование данных алгоритмов проводилось на одинаковых участках улично-дорожной сети с одинаковыми характеристиками потоков. В результате моделирования были получены следующие статистические данные: средняя скорость движения транспортного потока, количество автомобилей на проезжей части перекрестка, количество автомобилей на входе перекрестка. Данные характеристики были получены отдельно для каждого входа перекрестка. Шаг моделирования – 5 с.

При использовании алгоритма жесткого задания фаз максимальная длина очереди с западного направления достигала 26 автомобилей, средняя скорость движения транспортного потока составила 34,1 км/ч; с северного направления – 31автомобиль и 33,16 км/ч; с восточного – 7 автомобилей, 35,44 км/ч; с южного – 22 автомобиля, 33,58 км/ч.

При использовании алгоритма поэтапной настройки сдвигов фаз максимальная длина очереди с западного направления достигала 26 автомобилей, средняя скорость движения транспортного потока составила 36,1 км/ч; с северного направления – 18 автомобилей и 43,02 км/ч; с восточного – 8 автомобилей, 28,17 км/ч; с южного – 19 автомобиля, 39,76 км/ч.

При использовании алгоритма адаптивного управления на основе коррекции фаз максимальная длина очереди с западного направления достигала 14 автомобилей, средняя скорость движения транспортного потока составила 42,14 км/ч; с северного направления – 23 автомобиля, 41,84 км/ч; с восточного – 6 автомобилей, 37,58 км/ч; с южного – 22 автомобиля, 38,17 км/ч. Средняя длина приоритетной фазы – 32,4 с (при максимально возможном значении 50 с).
Список литературы


  1. Врубель, Ю.А. Определение потерь в дорожном движении / Ю.А. Врубель, Д.В. Капский, Е.Н. Кот. – Минск : БНТУ, 2006.

  2. Воробьев, Э.М. Автоматизированные системы управления дорожным движением / Э.М. Воробьев, Д.В. Капский, Ю.И. Мосиенко. – Минск : ТРОНТПРИНТ, 2004. – 8 с.

УДК 519.8


ОПТИМИЗАЦИЯ ОПЕРАЦИЙ ПО ПЕРЕМЕЩЕНИЮ

КОНТЕЙНЕРОВ НА ЖЕЛЕЗНОДОРОЖНОМ ТЕРМИНАЛЕ
М.С. Баркетов1, Э.Пеш2, Я.Шафранский1

1Объединенный институт проблем информатики НАН Беларуси, Минск

e-mail: barketau@mail.ru, shafr@newman.bas-net.by



2Университет Зигена, Германия
Рассматривается задача оптимизации операций погрузки-разгрузки контейнеров на железнодорожном терминале. Схематично железнодорожный терминал изображен на рисунке.

Терминал состоит из нескольких параллельных путей, на которые прибывают железнодорожные составы с контейнерами. На железнодорожном терминале имеется автомобильная дорога, на которой паркуются грузовики. Вся площадь терминала разбита на непересекающиеся зоны по количеству подъемных кранов. Выбранный кран работает только с теми вагонами, которые находятся в его зоне. Составы загоняются на терминал партиями. Каждый из выгружаемых составов должен попасть на «свой» грузовик. Грузовик может быть размещен на любом из парковочных мест. Для каждого контейнера известно время, необходимое для его перемещения на парковочных местах. После выполнения всех операций по перемещению контейнеров, партия составов покидает терминал (все составы партии покидают терминал одновременно).
Требуется минимизировать время обработки партии составов, что эквивалентно минимизации времени работы наиболее загруженного крана (крана, завершающего работу последним). Детальное описание железнодорожного терминала можно найти в работе [1].

Приведенная задача может быть формализована следующим образом. Дан полный взвешенный двудольный граф G G(UVE), где U и V – множества вершин, а E – множество ребер графа. Для каждого ребра e=(u, v)  E, uU, vV, задан его рациональный вес w(e) ≥ 0. Множество U разбито на m подмножеств U1, U2, …, Um, называемых компонентами. Для произвольного максимального паросочетания  определим вес компонента Ui как сумму весов ребер с вершиной, принадлежащей этому компоненту: . Максимальным весом паросочетания  будем называть максимальный из весов компонентов: . Задача заключается в том, чтобы найти максимальное паросочетание с минимальным максимальным весом.

В представленной формулировке вершины множества U сопоставлены контейнерам, а вершины множества Vпарковочным местам. Вес ребра (u, v) равен времени перемещения контейнера u на место v. Компонент Ui представляет множество контейнеров, находящихся в зоне работы i-го крана, а вес компонента Ui в паросочетании  соответствует времени работы i-го крана при назначении контейнеров на парковочные места, определяемые паросочетанием .

Специальный случай рассматриваемой задачи, когда m=1, представляет собой известную задачу о максимальном паросочетании минимального веса, решение которой сводится к решению задачи о назначениях. Задача с m > 1 в литературе ранее не рассматривалась.

Доказывается, что отыскание приближенного решения рассматриваемой задачи с отношением значения целевой функции к минимальному значению менее 2 является NP-трудной в сильном смысле задачей.

Предлагается приближенный алгоритм, который находит решения с относительной погрешностью, не превышающей в среднем 1 %. Алгоритм включает решение серии специальным образом построенных задач о максимальном паросочетании минимального веса, а также локальный поиск.


Список литературы
1. Boysen, N. New bounds and algorithms for the Transshipment Yard Scheduling Problem / N. Boysen, F. Jaehn, E. Pesch // Submitted to Transportation Science. – 2011.
УДК 621.9.06: 658.512.2
Оптимизация режимов групповой многоинструментальной обработки деталей

на многопозиционном оборудовании
Г.М. Левин, Б.М. Розин

Объединенный институт проблем информатики НАН Беларуси, Минск



e-mail: {levin,rozin}@newman.bas-net.by
Рассматриваются групповые технологические процессы многоинструментальной обработки на многопозиционном оборудовании конвейерного типа идентичных циклически повторяющихся групп деталей нескольких наименований. Каждая деталь группы в заданной последовательности обрабатывается на каждой рабочей позиции соответствующим этой позиции и детали набором инструментов. В общем случае инструменты каждой позиции сгруппированы в блоки (шпиндельные коробки). Предполагается, что каждый инструмент используется для обработки одинаковых элементов различных деталей на одинаковых режимах. Множества инструментов каждого блока, обрабатывающие различные детали, могут различаться между собой. Каждый такт обработки состоит в одновременной обработке на всех рабочих позициях соответствующих (такту и позиции) деталей. При этом одновременно работают все необходимые инструменты всех блоков. Принято, что смена инструментов выполняется независимо, по истечении для каждого из них соответствующего расчетного периода стойкости, зависящего от режимов обработки.

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

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

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

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

Для рассматриваемой задачи предлагается двухуровневая декомпозиционная схема решения, основанная на методах Лагранжевой релаксации и параметрической декомпозиции [1]. В качестве функции Лагранжа принята линейная комбинация себестоимости и времени обработки группы. На нижнем уровне отыскиваются режимы, доставляющие минимум функции Лагранжа при фиксированном значении множителя Лагранжа. На верхнем уровне отыскиваются значение этого множителя, при котором время обработки группы равно предельно допустимому. Эта задача сводится к поиску корня уравнения с монотонной левой частью.

Задача нижнего уровня при фиксированном значении множителя Лагранжа заменяется эквивалентной параметризованной задачей отыскания значений длительностей всех тактов и режимов на каждом такте. Эта задача сводится к задаче поиска кратчайшего пути в некотором бесконтурном орграфе. Для ее решения предложен метод, основанный на идеях динамического программирования [2].
Список литературы


  1. Левин, Г.М. Параметрическая декомпозиция задач оптимизации / Г.М. Левин, В.С. Танаев // Весцi НАН Беларусi, сер. фiз.-мат. навук. – 1998. – № 4. – С. 121–131.

  2. Левин, Г.М. Выбор оптимальных длительностей последовательно-параллельного выполнения пересекающихся множеств операций / Г.М. Левин, Б.М. Розин // Доклады Пятой Междунар. науч. конф. «Танаевские чтения», 28–29 марта 2012. – Минск : ОИПИ НАН Беларуси, 2012. – С. 49–54.

УДК 004.896



ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ
ДЛЯ РЕШЕНИЯ ЗАДАЧИ ТРАНСПОРТИРОВКИ ГРУЗА


ГРУППОЙ РОБОТОВ

В.А. Сычёв, Г.А. Прокопович

Объединенный институт проблем информатики НАН Беларуси, Минск

e-mail: {rprakapovich, vsychyov}@robotics.by
Для повышения гибкости и адаптивности роботизированных комплексов требуется применение групп роботов, способных функционировать в недетерминированной среде и при неполных начальных данных [1]. Рассмотрим задачу транспортировки объекта в некоторую точку с помощью группы, состоящей из N мобильных роботов (МР) и не имеющей единого центра управления. МР соединяются с транспортируемым объектом S и совместными действиями перемещают его в заданную точку t (рис. 1). МР функционируют на ровной поверхности без препятствий, при этом МР M1 и M2, находящиеся слева и справа от объекта транспортирования, жестко соединенные с ним, могут двигаться только вперед или назад со скоростью VL и VR соответственно. Возможность проскальзывания при этом не учитывается. Диапазон изменения скоростей – от 0 км/ч до 1 км/ч, что соответствует характеристикам малогабаритной мобильной робототехнической платформы типа Rover 5 classis, которую предполагается использовать для реальных испытаний полученных результатов. Каждый из роботов оснащен сенсорной системой. Сенсорная система робота представляет собой установленный в центре робота (С) сканирующий ультразвуковой дальномер с диапазоном 4–500 см и углом сканирования 270°, позволяющий определить дальность до цели с точностью до 1 см. Задача заключается в подборе таких значений скоростей обоих МР, двигаясь с которыми, им удастся уже в процессе движения к цели минимизировать угол между перпендикуляром, опущенным в центр оси, на которой находятся робот и груз, и самым коротким отрезком между этим центром и целью ΔΘ и расстояние до цели ΔL. Сенсорные системы МР располагают информацией об изменении угла ΔΘ и расстояния ΔL до точки t. В данной работе описанная выше задача была решена с помощью генетических алгоритмов (ГА). Далее в тексте будет использоваться терминология ГА [2].

В среде Matlab была создана компьютерная модель описываемой задачи. Целью компьютерного моделирования был поиск оптимальных управляющих параметров с помощью ГА.









Рис. 1. Схема транспортировки объекта группой роботов

Рис. 2. Траектория движения
по результатам компьютерного моделирования

На первом этапе моделирования создается начальная популяция, представляющая собой набор правил выбора скорости и направления движения каждого из двух МР в зависимости от угла ΔΘ. На виртуальной карте создаются цель и два МР, жестко соединенные с объектом транспортирования. Координаты МР и цели так же, как и угол наклона ΔΘ, выбираются случайным образом. Из начальной популяции выбирается хромосома, кодирующая действия МР для того угла наклона, который был установлен при размещении МР на карте. После чего вычисляются фитнесс-функции для выбранной хромосомы и для некоторого числа соседних хромосом. Устанавливается максимальное число поколений, и к выбранным хромосомам применяются генетические операторы скрещивания и мутации. Полученная в результате хромосома используется для вычисления следующего положения МР, затем процедура повторяется для новых координат [2, 3]. Пример траектории движения и наклона относительно осей координат груза, транспортируемого двумя МР, показан на рис. 2. За время движения к цели роботам не удается выработать оптимальных законов управления. Тем не менее МР достигают конечной точки. В дельнейших исследованиях планируется доработать предложенный подход с использованием действующих макетов роботов.


Список литературы


  1. Каляев, И.А. Проблемы группового управления роботами / И.А. Каляев, С.Г. Капустян // Мехатроника, автоматизация, управление. – 2009. – № 6. – С. 33–40.

  2. Holland, J.H. Adaptation in natural and artificial systems / J.H. Holland. − MA, USA : MIT Press Cambridge, 1992. – 211 p.

  3. Скобцов, Ю.А. Основы эволюционных вычислений / Ю.А. Скобцов. – Донецк, 2008. – 326 с.

УДК 50.51.17
Энергосберегающий синтез

комбинационных КМОП-схем
Л.Д. Черемисинова

Объединенный институт проблем информатики НАН Беларуси, Минск



e-mail: cld@newman.bas-net.by
В последние годы все большее значение придается проектированию микросхем с малым энергопотреблением. Снижение энергопотребления проектируемой схемы может обеспечиваться на разных уровнях ее проектирования. В частности, на логическом уровне (за счет построения удачной логической структуры) можно достичь сокращения энергопотребления на 10–20 % без ущерба для быстродействия и сложности схемы [1].

В настоящей работе рассматривается задача энергосберегающего синтеза многоуровневых логических схем из библиотечных элементов, КМОП СБИС. Компоненты СБИС, выполненные по этой технологии, потребляют подавляющую часть необходимой для функционирования энергии во время переключения, соответственно их энергопотребление существенно зависит от переключательной активности узлов схемы, которая определяется динамикой функционирования и структурой схемы. Последовательность входных воздействий на схему существенно зависит от ее применения и может быть спрогнозирована проектировщиком на вероятностном уровне, при этом помимо функционального описания проектируемой схемы задаются вероятностные оценки активности изменения сигналов на ее входах, по которым вычисляется их переключательная активность.

Предлагается подход к синтезу, позволяющий минимизировать площадь и среднее значение мощности, рассеиваемой микросхемой. Подход основан, как и большинство известных методов синтеза, на разбиении процесса логического синтеза на стадии технологически независимой оптимизации и технологического отображения. За количественные оценки качества проектирования на первом этапе принимается оценка по Квайну (суммарное число входных полюсов вентилей), на втором этапе – число транзисторов (библиотечных элементов) и для обоих этапов – суммарная переключательная активность узлов схемы [2].

Исходя из принятых критериев оптимальности сети, при технологически независимой оптимизации целесообразно выделять и реализовывать однократно общие части булевых функций реализуемой системы. Этап технологически независимой оптимизации начинается с совместной минимизации реализуемой системы функций (полностью или частично определенных) в классе ДНФ, а принимая во внимание специфику КМОП-библиотеки (ее элементами реализуются и функции, и их инверсии), рационально проводить ее и с учетом полярности функций, выбирая ту ее форму (ДНФ или ее инверсию), которая имеет меньшую сложность (число литералов) и переключательную активность [3].

Исходя из полученной двухуровневой схемы из вентилей И, ИЛИ предлагается строить далее многоуровневую схему в технологически обусловленном базисе многовходовых вентилей, на которые распадаются структуры основных элементов КМОП-библиотеки [4].

Для преобразования исходной минимизированной системы ДНФ в многоуровневую схему в выбранном технологически обусловленном базисе вентилей используется алгебраическая декомпозиция, имеющая целью уменьшение значений прогнозируемых оценок сложности и энергопотребления. Эта задача сводится: 1) к совместной факторизации, сводящейся к поиску и выделению общих частей логических выражений: конъюнкций и дизъюнкций минимизированной системы ДНФ как алгебраических выражений; 2) к раздельной факторизации, сводящейся к итеративному вынесению литералов ДНФ за скобки [4].

На этапе технологического отображения используются структурные методы (наиболее эффективные на практике) отображения многоуровневой схемы из вентилей в технологический базис библиотечных элементов [2]. Предполагается, что основные усилия по прогнозному сокращению энергопотребления схемы приходятся на этап технологически независимой оптимизации, когда определяется структура схемы, а на этапе технологического отображения покрытие производится таким образом, чтобы узлы схемы с наибольшей переключательной активностью по возможности оказались внутри библиотечных элементов.
Список литературы
1. Power Compiler. Automatic Power Management within Galaxy™ Implementation Platform // Synopsys: predictable success [Electronic resource]. – Mode of access : http://www.synopsys.com/Tools/Implementation/RTLSynthesis /Documents/ powercompiler_ds.pdf. – Date of access : 08.08.2012.

2. Черемисинова, Л.Д. Синтез комбинационных КМОП-схем с учетом энергосбережения / Л.Д. Черемисинова // Информатика. – 2010. – № 4. – С. 112–122.

3. Черемисинов, Д.И. Минимизация двухуровневых КМОП-схем с учетом энергопотребления / Д.И. Черемисинов, Л.Д. Черемисинова // Информационные технологии. – 2011. – № 5. – С.17–23.

4. Черемисинова, Л.Д. Синтез логических схем из вентилей с пониженным энергопотреблением / Л.Д. Черемисинова, Н.А. Кириенко // Танаевские чтения : доклады Пятой Междунар. науч. конф., 29–30 марта 2012, Минск. – Минск : ОИПИ НАН Беларуси, 2012.

UDC 519.8
MRP parameterization for multi-level assembly

system under random lead times
O. Ben Ammar, H. Marian, A. Dolgui

Ecole Nationale Supérieure des Mines, EMSE-FAYOL, CNRS UMR6158, LIMOS, F-42023 Saint-Etienne, France



e-mail: {obenammar, marian, dolgui}@emse.fr
Inventory control in Supply Chain is a very important element for the companies. Customers have to be satisfied at the lowest cost. For this reason, it is mandatory to possess necessary components in order to produce the requested products by the due date. In this study we deal with a model of a multi-level assembly system. The aim is to propose a tool to search parameters of MRP system, in particular, planned lead times, when such a company deals with uncertainties of production and supply lead times.

This study is interested in the problem of MRP parameterization under lead time uncertainties. It continuies works [1-5].

We are interested in a supply planning for multi-level assembly systems under a fixed demand and uncertainty of components lead times, more precisely to determinate planned lead times when the component procurement times are independent and identically distributed discrete random variables.

Tzone de dessin 64
he finish product demand for a given due date is supposed to be known. The optimization is made for only one-period demand. The developed model is for an infinite capacity assembly system.

Three-level assembly-system

The main aim is to find the values of planned lead times which minimize the sum of the average component holding cost and the average finished product backlogging or holding cost (Figure).The developed approach is based on a mathematical model of this problem with discrete decision variables and a Genetic Algorithm (GA). The developed approach is compared with a simulation model coupled with the same GA and validated in [1].

We consider the results of 1000 examples which are generated and grouped into 10 families. Each family gathers 10 examples with the same number of components in the last assembly system level.

The mathematical model coupled with GA is more accurate, efficient and converges faster than the simulation model coupled with the same GA.

The problems caused by lead time uncertainties are further exacerbated by the fact that MRP uses constant lead times when, in fact, actual manufacturing times vary continually. The users of the system must be trained to appreciate the need for safety lead time to guarantee timely deliveries.

Further research will consider the extension of this approach for problems with demand uncertainties. The main difficulty will be to express the total expected cost for multi-period multi-level assembly systems.


Каталог: event
event -> Доклад о ситуации с обеспечением прав человека в европейском союзе
event -> Разнарядка
event -> Занятие первое. Работа с файловым менеджером Total Commander
event -> Инструменты ретуши Adobe Photoshop
event -> Семинар будет проходить 27 и 28 января. Курс «Скульптура бровей»
event -> Пиганов Михаил Николаевич профессор кафедры ктэсиУ, член оргкомитета; Зеленский Владимир Анатольевич профессор кафедры ктэсиУ, отв секретарь оргкомитета. Пленарное заседание


Поделитесь с Вашими друзьями:
1   2   3   4   5   6   7   8   9   ...   16


База данных защищена авторским правом ©vossta.ru 2019
обратиться к администрации

    Главная страница