Исследование и разработка моделей оперативных оптимизационных задач на сетях с постоянными и переменными параметрами тема диссертации и автореферата по ВАК РФ 05.13.06, кандидат технических наук Сергейчук, Иван Михайлович

• Сергейчук, Иван Михайлович
• кандидат технических наук
• 1984

Оглавление диссертации кандидат технических наук Сергейчук, Иван Михайлович

ВВЕДЕНИЕ.

ГЛАВА I. ПОСТАНОВКА ЗАДАЧИ ИССЛЕДОВАНИЯ И АНАЛИЗ ПОДХОДОВ К ЕЕ РЕШЕНИЮ.

IЛ.Анализ методов организации автотранспортного процесса.

1.2. Современное состояние управления движением автотранспортных средств.

1.3. Анализ задач определения оптимальных путей на транспортных сетях и существующих методов,алгоритмов и моделей их решения.

1.4. Постановка задачи проектирования системной модели для решения оперативных задач оптимизации.

ВЫВОДЫ.

ГЛАВА П. ИССЛЕДОВАНИЕ МЕТОДОВ И РАЗРАБОТКА АЛГОРИТМОВ РЕШЕНИЯ ОПЕРАТИВНЫХ ОПТИМИЗАЦИОННЫХ ЗАДАЧ В РЕАЛЬНЫХ ТРАНСПОРТНЫХ СЕТЯХ

2.1.Метод идентификации оптимального пути в реальной дорожно-транспортной сети.

2.2. Алгоритм решения задачи поиска и вывода оптимального пути в сети с переменными параметрами.

2.3. Задача определения оптимального места и времени встречи транспортных средств /корреспондентов/ на сети с переменными параметрами. . ^

2.4. Алгоритм построения оптимальной сети связи.

2.5. Алгоритм формирования кода оптимального пути для оперативного управления движением автотранспортных средств.

2.6. Общий алгоритм оптимизации.

ВЫВОДЫ.

ГЛАВА Ш. РАЗРАБОТКА СИСТЕМНОЙ МОДЕЛИ ДЛЯ РЕШЕНИЯ ОПЕРАТИВНЫХ ЗАДАЧ ОПТИМИЗАЦИИ НА СЕТЯХ С ПЕРЕМЕННЫМИ ПАРАМЕТРАМИ.

3.1. Синтез (функционального процессорного элемента модели поиска оптимального пути.

3.2. Модель поиска оптимального места и времени встречи транспортных средств на сетях с переменными параметрами

3.3. Модель оптимальной сети связи.

3.4. Модель управления движением транспортных средств.

ВЫВОДЫ.

ГЛАВА 1У. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ И ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ УСТРОЙСТВА ОПЕРАТИВНОГО ОПРЕДЕЛЕНИЯ И ВЫВОДА ОПТИМАЛЬНОГО ПУТИ В СЕТИ С ПЕРЕМЕННЫМИ ПАРАМЕТРАМИ

4.1. Техническая реализация устройства "СИМ-Г'.

4.2. Информационное обеспечение процесса решения оперативных оптимизационных задач.

4.3. Аналоговая модель определения и регистрации оптимального пути.

4.4. Оценка эффективности использования результатов исследования в АСУ перевозочным процессом.

ВЫВОДЫ.

Введение диссертации (часть автореферата) на тему «Исследование и разработка моделей оперативных оптимизационных задач на сетях с постоянными и переменными параметрами»

В Основных направлениях экономического и социального развития СССР на I98I-I985 годы и на период до 1990 года большое внимание уделяется проблемам интенсификации экономики, повышения эффективности общественного производства и дальнейшего совершенствования методов планирования и управления народным хозяйством /62/.

Перед транспортом в качестве основной поставлена задача полного и своевременного удовлетворения потребностей народного хозяйства, и населения в перевозках, повышения эффективности и качества работы транспортной системы.

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

Автомобильный транспорт занимает особое место в единой транспортной системе страны. Он является основным видом транспорта в осуществлении экономических связей внутри городов,областей, краев, автономных республик и экономических районов страны. На его долю приходится свыше 80 % обьема всех перевозимых в стране грузов и более 90 % пассажиров /65/. От организации его работы в значительной степени зависит повышение эффективности и качества труда в промышленности,строительстве,сельском хозяйстве и торговле.

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

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

В Минавтотрансе РСФСР создается отраслевая АСУ "Автотранспорт", охватывающая все уровни управления. В рамках АСУ "Автотранспорт" на единой методологической,информационной и технической базе создаются АСУ министерства, транспортных управлений /АСУ ТУ/ и авторемонтных заводов /АСУП/, технологических процессов перевозок грузов и пассажиров /АСУ ТП/, системы диспетчерского управления автобусными перевозками / АСДУ-А/, таксомоторными перевозками / АСДУ-Т/, грузовыми перевозками /АСДУ-Г/.

Автоматизированная система управления направлена на решение главных задач - планирования,контроля и оценки работы автотранспорта. Решение с помощью ЭВМ задач определения оптимальных графиков, маршрутов и планов перевозок требует разработки весьма трудоемкого специального программно-математического обеспечения управления и перестройки системы управления как в сфере организационных структур,так и методов принятия решений. Использование ЭВМ для учета,сбора и обработки статической отчетности также связано с рядом трудностей,главная из которых - это то, что технология выполнения учетных работ с применением ЭВМ получается неэкономичной из-за отсутствия периферийных устройств сбора и обработки информации,каналов связи и программно-математического обеспечения ЭВМ.

- б

Создание отраслевой АСУ "Автотранспорт" и специализированных подсистем управления отдельными видами деятельности авто -транспортной системы,связанных с выполнением наиболее важных работ в области перевозок грузов, в области ремонта и технического обслуживания автомобилей, в области управления подвижным составом,а также в сферах обеспечения этих видов деятельности, позволит повысить оперативность управления, эффективность перевозок и улучшить качество выполняемых работ.

В развитие теории транспортного процесса перевозок внесли большой вклад ученые Афанасьев Л.Л., Бронштейн JI.A. ,ВеликановД.П.„ Панов С.А. и другие.Развитию науки об эффективных методах организации перевозок и внедрению в практику ее достижений способствовали Государственный НИИАТ Министерства автотранспорта РСФСР, ГосавтотрансНИИпроект Министерства автотранспорта УССР, Центральный экономико-математический институт АН СССР /ЦЭМИ/ и ряд дру -гих НИИ и лабораторий.

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

Организация централизованных перевозок создает благоприятные условия для применения маршрутизации перевозок. Маршрутизация перевозок грузов представляет собой решение транспортной задачи /26/ на наилучшее сочетание ездок автомобилей, достижение минимума затрат, максимальной производительности автомобилей и ускорения доставки грузов потребителю. Маршрутизация перевозок является высокоэффективным методом организации перевозок грузов. Однако возможности рациональной маршрутизации перевозок грузов используются еще недостаточно. Так, по данным 1983 года коэффициент использования пробега автомобилей по УССР составил -0,502 /94/, а по производственному обьединению "Киевгорстройтранс" -0,515. Увеличение коэффициента использования пробега автомобилей на 0,01 позволит только по производственному обьединению "Киевгорстройтранс" дополнительно на расстояние 17,5 км. перевезти 20 тысяч тонн груза и снизить на 0,1% себестоимость транспортной работы.

Прогрессивным методом организации междугородних перевозок является система тяговых плеч. Организация автоперевозок по данной системе позволила в 3 раза сократить сроки доставки грузов по сравнению с перевозкой по железной дороге /84/. Сокращение потерь времени на погрузочно-разгрузочные операции за счет применения тягачей с полуприцепами обеспечивает улучшение технико-эксплуатационных показателей работы подвижного состава.

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

Значительную часть автоперевозок составляет также доставка партионных грузов. О масштабах мелкопартионных перевозок можно судить по следующему факту. В целом по СССР сеть розничной торговли и общественного питания насчитывает более I млн. пунктов, через которые за год проходит 120-130 млн.т. товаров, поставляемых преимущественно мелкими партиями. На пути от изготовителей до пунктов торговли,проходя систему баз и складов, партии этих товаров дробятся и перегружаются более 10 раз, увеличивая тем самым нагрузку на транспорт /33/.

Партионные перевозки выполняются,Как правило, в городских условиях,для которых характерны следующие особенности /34/:

- весьма существенное влияние на планирование и продолжительность этих перевозок оказывают изменение интенсивности движения и фактор загруженности транспортной сети города;

- в условиях тесного соседства грузовых и людских потоков остро встает проблема безопасности движения и оперативного управления движением;

- для многих грузов значение перевозок не определяется только узкотранспортными показателями,а имеет значение своевременность доставки и сохранность скоропортящихся грузов;

- в городских условиях поток автомобилей является одним из источников загрязнения воздушного бассейна города и основным источником щума,поэтому обостряется проблема разумного регулирования перевозок и перераспределения транспортных потоков.

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

Одним из основных направлений совершенствования структуры управления автотранспортным производством является концентрация и специализация автопарка в крупных предприятиях и включение их в автотранспортные объединения /23/. Сосредоточение функций управления перевозочным процессом в централизованной эксплуатационной службе /ЦЭС/ атотранспортного объединения или треста позволяет эффективно использовать автоматизированные системы управления и экономико-математические методы при планировании и организации работы подвижного состава на линии. Например, за время работы ЦЭС в обьединении "Киевавтотранс'коэффициент использования пробега автомобилей повысился с 0,5 до 0,7 /84/.

Мы рассмотрели пути повышения эффективности автотранспортного процесса.Однако значительно возрастающее из года в год раз-, витие автомобильных перевозок и автопарка страны,повышение грузоподъемности транспортных средств,возрастание доли легковых автомобилей транспортных потоков ставит проблем более эффективного использования существующей дорожно-транспортной сети, особенно в крупных городах страны. Одним из наиболее перспективных путей решения этой проблемы является оперативное управление движением транспортных потоков на автомобильно-дорожной сети. Работы по данной проблеме проводятся как в нашей стране, так и в наиболее развитых зарубежных странах : США,Японии,ФРГ,Великобритании и др.

Значительный вклад в решение проблемы управления движением транспортных потоков внесли зарубежные и советские ученые Дрю Д., Хейт Ф.,Иносэ X., Хамада Т.,Гаврилов А.А.,Брайловский Н.и.,Пе|1ер-ский М.П., Грановский Б.И.,Хорович Б.Г.,Васильев А.П.,Фримштейн М.И. и другие.

В последние годы происходит процесс интенсивного внедрения автоматизированных систем управления движением /АСУД/ с помощью дорожной сигнализации. АСУД являются эффективным средством оптимизации процесса движения и повышения безопасности всех его участников.

Зарубежный опыт эксплуатации автоматизированных систем управления дорожным движением в городах показывает,что они позволяют уменьшить задержки автомобилей на перекрестках в среднем на 20%, количество остановок на 25%,количество ДТП на 15%,расход топлива на 4-8%, повысить среднюю скорость на 30% /23/.

Массовое оснащение автомобилей радиоприемниками,портативными телевизорами привело работников служб организации движения к идее использования автомобильных радио и телеприемников для сообщения различной управляющей информации. Фо Франции создана система "РААС",предназначенная для предупреждения по радио водителей об условиях движения /119/. В ФРГ разработана система радиоинформации водителей об условиях и режимах движения на дорогах, охватывающая всю страну. В США также разрабатывается автоматическая система информации водителей по радио о наличии загруженных маршрутах и погодных условиях. Предлагается даже применение специального кабеля,прокладываемого вдоль дороги под каждой полосой движения. Радиосигнал,излучаемый кабелем,поступает через антену в автомобильный приемник и затем через емкостную связь "автомобиль-земля" возвращается на .передающую радиостанцию. Аналогичные системы разрабатываются в Англии,Италии,Швейцарии,Японии и в других странах.

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

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

Решение указанных оперативных задач сводится к отысканию оптимальных путей,удовлетворяющих заданному критерию оптимизации. Широкое практическое использование указанных выше задач и обусловило появление значительного количества различных методов и средств их решения как с. помощью ЭВМ,так и специализированных технических устройств в условиях функционирования АСУ.

С помощью ЭВМ выполняются сложные расчеты,оперативно обрабатывается информация больших объемов и с большей точностью.Вместе с тем не всегда экономически оправданным является их применение для решения сетевых оптимизационных задач,а в ряде случаев их использование на данном этапе не дает требуемых результатов в виду специфики самых задач. Так,при решении задачи оптимизации маршрутов перевозок в реальной дорожно-уличной сети крупных городов время проезда автотранспортным средством единицы длины дороги является величиной переменной,зависящей от интенсивности транспортного потока, состава движения и дорожных условий. Интенсивность и состав транспортного потока за время реализации маршрута перевозок существенно изменяются,особенно на маршрутах значительной продолжительности. В этих условиях задача определения /поиска/ оптимального пути движения транспортных средств не может быть поставлена и решена в рамках классической постановки задачи о кратчайшем пути в сети с постоянными параметрами.

Решение задачи поиска оптимального пути в сети с переменными параметрами при использовании ЭВМ требует значительных затрат времени,превышающих время;в течение которого изменяются параметры сети при реализации найденного маршрута /104/.

Вопросам исследования и решения оптимизационных задач на сетях с переменными параметрами уделяется недостаточно внимания, что можно объяснить отсутствием эффективных вычислительных методов их решения. В подавляющем большинстве случаев сетевые оптимизационные задачи ставились и решались применительно к сетям с постоянными параметрами. Исследования показали,что постановка оптимизационных задач применительно к сетям с постоянными параметрами далека от реальности /55,95,99,119/,а существующие ана

Г' логовые,цифровые и гибридные специализированные средства решения задач оптимизации рассчитаны в основном на моделирование сетей с постоянными параметрами/18,19,20,26,30,31,32,33/.

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

Существующие АСУ дорожным движением рассчитаны на управление транспортными потоками,но не отдельной транспортной единицей по найденному оптимальному пути.

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

В целом это определило выбор темы диссертационной работы и направление исследований.

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

Для достижения намеченной цели в работе необходимо решить следующие задачи:

- исследовать известные методы организации автотранспортного процесса и управления движением транспортных средств,которые требуют оперативного определения оптимальных путей на сетях с переменными параметрами;

- исследовать существующие методы,алгоритмы и специализированные технические средства для решения задач об оптимальном пути на сетях с постоянными и переменными параметрами;

- обосновать принцип построения системной модели и логической схемы решения локальных оперативных задач оптимизации;

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

- разработать алгоритм формирования кода оптимального пути для представления информации о маршрутах движения автотранспортных средств в удобной для практического использования форме;

- разработать алгоритм решения сетевых оперативных задач оптимизации на основе метода идентификации оптимального пути;

- синтезировать функциональный процессорный элемент-модель двунаправленной ветви сети с изменяющимися параметрами, с целью получения типового проектного решения оперативных зада^ оптимизации ;

- разработать информационное обеспечение для решения оперативных оптимизационных задач на сетях с переменными параметрами;

- разработать системную модель для решения оперативных задач управления и маршрутизации автоперевозок по критерию "время" в реальной дорожно-транспортной сети;

- решить практическую задачу определения минимальных по времени маршрутов перевозок строительных грузов в.дорожно-улич-ной сети г.Киева в условиях АСУ перевозочным процессом.

Обьектом исследования является:

- разработка системной модели,методологически связывающей обьект управления и процесс его оптимизации;

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

Выбор обьекта исследования определяется необходимостью повышения эффективности работы автотранспортных средств и недостаточностью теоретических и практических разработок в области решения оперативных задач на сетях с переменными параметрами.

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

Научная новизна исследований и полученных в диссертационной работе результатов заключается в следующем:

- предложен системный подход к решению класса оперативных оптимизационных задач на транспортных сетях с переменными параметрами;

- разработан метод идентификации неразветвленного оптимального пути между любой парой узлов в сети с переменными парамет -рами,на основе которого разработан алгоритм поиска и вывода оптимального пути мевду заданными узлами в реальной транспортной сети;

- разработана методика синтеза функционального процессорного элемента системной модели,выполняющего функции определения, запоминания и вьщачи информации об оптимальности моделируемой двунаправленной ветви сети с изменяющимися параметрами;

- разработан алгоритм формирования кода оптимального пути в дорожно-транспортной сети;

- разработаны математическая модель и алгоритм решения задачи поиска оптимального места и времени встречи корреспондентов и путей их следования на сети с переменными параметрами;

- предложен способ документирования решения задачи определения последовательности ветвей оптимального пути между заданными узлами сети;

- предложен принцип построения системной модели для решения оперативных задач оптимизации на сетях с переменными параметрами в реальном масштабе времени.

Практическая ценность выполненных исследований заключается в разработке устройства для оперативного определения и вывода оптимального пути на сети с переменными параметрами "СИМ-1". Устройство может быть использовано в автотранспортных обьединениях в АСУ перевозочным процессом,для определения оптимального места встречи автопоездов и маршрутов их следования, для определения оптимального времени встречи различных видов транспорта в большом транспортом узле,в организациях ГАИ МВД для автоматизированного сопровождения транспортной единицы по рекомендуемому оптимальному пути в АСУ дорожным движением.

В результате внедрения в ПО "Киевгорстройтранс" устройства определения и вывода оптимального пути и алгоритмов оптимизации маршрутов перевозок строительных грузов с учетом переменных параметров транспортной сети г.Киева повышена среднетехническая скорость движения автомобилей на 13,9% и производительность транспортных средств на 5,8%. Годовой экономический эффект от внедрения частичных результатов диссертационной работы только в ПО "Киевгорстройтранс" составил 45,16 тыс.рублей.

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

Заключение диссертации по теме «Автоматизация и управление технологическими процессами и производствами (по отраслям)», Сергейчук, Иван Михайлович

ВЫВОДЫ

1. Разработано на современной элементной базе техническое устройство "СИМ-1" для оперативного определения и вывода оптимального пути между заданными узлами исследуемой сети. Устройство обладает универсальностью,так как позволяет решать оперативные задачи как на сетях с переменными,так и постоянными параметрами,удовлетворяющие различным критериям оптимизации. Устройство приспособлено для определения оптимальных путей на сетях с изменяющейся топологией. Устройство защищено авторским свидетельством на изобретение.

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

3. Предложен алгоритм работы устройства "СИМ-1" с ЭВМ, обеспечивающий процесс решения оптимизационных задач информацией об изменениях параметров на участках исследуемой дорожно-уличной сети.

- 134

4. Предложен способ документирования результатов решения задачи поиска оптимального пути между любой парой узлов сети в виде регистрации последовательности ветвей искомого пути.

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

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

7. Проведена оценка эффективности практического использования в АСУ перевозочным процессом результатов исследования минимальных по времени маршрутов перевозок строительных грузов с учетом текущих изменений параметров дорожно-уличной сети г.Киева. Годовой экономический эффект от внедрения по тресту "Киевгорстройтранс" составил 45,16 тыс.рублей.

ЗАКЛЮЧЕНИЕ

В результате выполнения диссертационной работы автором получены следующие научные и практические результаты:

I. Предложен системный подход к решению оперативных задач оптимизации маршрутов перевозок,управления движением транспортных средств по рекомендуемому пути,сети связи для развозки партионных грузов,места и времени встречи транспортных средств корреспондентов/ с учетом изменения параметров дорожно-транспортной сети и удовлетворяющих заданному критерию оптимизации.

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

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

4. Разработаны математическая модель и алгоритм решения задачи поиска оптимального места и времени встречи транспортных средств и маршрутов их следования на сети с переменными параметрами .

5.Разработан алгоритм формирования кода оптимального пути, позволяющий закодировать сложную сеть ограниченным числом знаков /кодов/,не превышающим количества ветвей,принадлежащих наиболее сложному узлу исследуемой сети и получить информацию о маршрутах следования транспортных средств между заданными узлами сети в виде последовательности кода,цифропечати,перфорации либо сигналов-указателей осуществления маневра в каждом из последующих узлов рекомендуемого пути.

6. Предложен принцип построения системной модели для решения в реальном масштабе времени оперативных задач оптимизации на сетях с переменными параметрами,заключающийся в построении моделей локальных оптимизационных задач на основе разработанного функционального процессорного элемента - электронной модели двунаправленной ветви сети с изменяющимися параметрами. ФПЭ практически выполнен в виде двуполюсника по отношению к узловым точкам моделируемой двунаправленной ветви вследствие включения в цепь обратной связи диодов,являющихся частью моделей узлов сети.

Такой принцип построения оптимизационных моделей позволяет сравнительно'просто моделировать транспортные сети большого обьема,с изменяющейся топологией и переменными параметрами.

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

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

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

- 137

10. Разработано на современной элементной базе техническое устройство "СШ-1" для 'оперативного определения и вывода оптимального пути между заданными узлами исследуемой сети. Устройство приспособлено для определения оптимальных путей на сетях с изменяющейся топологией. Оно обладает универсальностью, так как позволяет решать оперативные задачи как на сетях с переменными, так и постоянными параметрами, удовлетворяющие различным критериям оптимизации. Системотехнические решения,полученные при проектировании устройства,обладают новизной и защищены авторским свидетельством на изобретение.

11. Проведена оценка эффективности практического использования в АСУ перевозочным процессом результатов исследования минимальных по времени маршрутов перевозок строительных грузов с учетом текущих изменений параметров дорожно-уличной сети г.Киева. Показано,что определение минимальных по времени маршрутов движения целесообразно осуществлять для маршрутов протяженностью десять и более километров по сравнению с перевозками грузов на исследуемых маршрутах по критерию "расстояние". Годовой экономический эффект от внедрения частичных результатов работы только в ПО "Киевгорстройтранс" составил 45,16 тыс.рублей.

Результаты диссертационной работы при непосредственном участии автора реализованы при разработке электронных моделей для определения оптимальных маршрутов проезда автотранспорта по г.Харькову /по плану постоянной комиссии комплексных проблем транспорта Президиума АН УССР/, при внедрении модели и алгоритмов оптимизации маршрутов перевозок строительных грузов с учетом переменных параметров дорожно-уличной сети г.Киева в производственном автомобильном объединении "Киевгорстройтранс" / в соответствии с договором о творческом содружестве КАДИ и

Киевгорстройтранс"/, при выполнении заданий института кибернетики имени В.М.Глушкова АН УССР по программе работ целевой комплексной проблемы 0Ц.027 при решении задач планирования и управления транспортным процессом,при программировании жизненных циклов объектов новой техникиАгтос.регистрации 01827000153/.

Результаты теоретических и практических исследований диссертационной работы докладывались на: семинаре Научного совета по проблеме "Кибернетика" АН УССР "Конструирование технических средств математических машин и систем"./г.Киев,1974/,XXX-ХХХУ научно-технических конференциях профессорско-преподавательского состава КАДИ /г.Киев,1974-1979г.г./,семинаре Научного совета по проблеме "Теоретическая электротехника и электроника" АН УССР "Специализированные электронные моделирующие машины и устройства" /г.Киев,1976г./, Ш Всесоюзной научно-технической конференции "Пути повышения безопасности дорожного движения" /г.Киев,1978г./, объединенном Республиканском семинаре по проблеме "Кибернетика" АН УССР "Системное проектирование сложных систем управления" и "Математические методы планирования транспорта и размещения производства"/г.Киев,1984г./.

Список литературы диссертационного исследования кандидат технических наук Сергейчук, Иван Михайлович, 1984 год

1. Автоматизированные системы управления дорожным движением за рубежом. - М.: Б.и., 1978. - Збс.

2. Александров Л'.А. Организация и планирование грузовых автомобильных перевозок М.: Высш.шк.,1977. - 336 с.

3. Алферова З.В. Теория алгоритмов. М.: Статистика, 1973. - 164 с.

4. Аникеич А.А.,Грибов А.Б., Сурин С.С. Сменно-суточное планирование работ грузовых атомобилей на ЭВМ. М.: Транспорт, 1976. - 152 с.

5. Анисков В.В.,Витенберг И.М.,и др. Моделирование задач исследования операций. М.: Энергия, 1978. - 216 с.

6. Атанс Н.,Фалб П. Оптимальное управление. М.: Машиностроение, 1968. - 764 с.

7. Афанасьев Л.Л.,Цукерберг С.М. Автомобильные перевозки. М.: Транспорт, 1973. 320 с.

8. Бабков В.Ф.Дорожные условия и организация движения. -М.: Транспорт, 1974.- 238 с.

9. Бадинер С.М.,Бабарикин В.М.,Дагович В.М. АСУ на автотранспорте. М.: Транспорт, 1978. - 159 с.

10. Бакаев А.А.,Афанасьев В.Н.,Кулаковский В.А. Развитие автоматизированных систем управления на автотранспорте общего пользования УССР на 1976-1980г.г. К.: Знание, 1977. - 23 с.

11. Баклашов Н.И.,Бемонов А.Н. и др. Натурный эксперимент. М.: Радио и связь, 1982. - 304 с.

12. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. М.: Наука, 1965. - 458 с.

13. Беллман Р., Калаба Р. Динамическое программирование и современная теория управления. М.: Наука, 1969. - 400 с.

14. Берж К. Теория графов и ее применение. М.: Иност. лит., 1962. - 320 с.

15. Бочаров О.М. Технические средства в системах управления автомобильным транспортом. В кн.: Вопросы совершенствования управления автотранспортом. М.: МДНТП, 1974г. с.34-40.

16. Брайловский Н.0.,Грановский Б.И. Управление движением транспортных средств. М.: Транспорт, 1975. - 112 с.

17. Вагнер Г. Основы исследования операций: ВЗ-ХТ.- М.: Мир, 1972. T.I. 336 с.

18. Васильев В.В., Додонов А.Г. Многопроцессорные вычислительные структуры для анализа экстремальных задач на сетях. -В кн.: Проблемы электроники и вычислительной техники. Киев: Наук, думка, 1976. с. 85-97.

19. Васильев В.В. Специализированные вычислительные структуры для решения сетевых задач и их применение. В кн.: Неоднородные вычислительные системы. Киев : Наук.думка, 1975.с.43 55.

20. Васильев В.В.,Додонов А.Г. Гибридные модели задач оптимизации. К.: Наук.думка, 1974. - 216 с.

21. Васильев А.П.,Фримштейн М.И. Управление движением на автомобильных дорогах. М.: Транспорт, 1979. - 296 с.

22. Воркут А.И. Грузовые автомобильные перевозки. К.: Вища шк. 1979. - 392 с.

23. Гаврилов А.А.,Покровский А.К.,Романова Л.П. Автомобилизация: управление,развитие. М.: Знание, 1983. - 64 с.

24. Глушков В.М. Введение в АСУ. К.: 1974. - 320 с.

25. Глушков В.М. Синтез цифровых автоматов. М.: Физматгиз, 1962. - 476 с.

26. Гольдштейн Е.Г.,Юдин Д.Б. Задачи линейного программирования транспортного типа. М.: Наука, 1969. - 382 с.

27. Говорущенко Н.Я. Основы управления автомобильным транспортом. X.: Вища шк. 1978. - 224 с.

28. Григорьев B.C.,Майетренко Л.С.,Старовойтенко О.А. и др. Развитие средств вычислительной техники за рубежом. К.: УкрНИИНТИ, 1981. - 52 с.

29. Гуревич JI.B.,1^шевский Л.В. Управление движением на улицах и дорогах. М.: Транспорт, 1971. - 199 с.

30. Гутенмахер Л.И. Новые аналоговые модели для целей управления. В кн.: Автоматы,гибридные и управляющие машины. - М.: Наука, 1972, с. 223-229.

31. Гутенмахер Л.И. Электрические модели. К.: Техника, 1975. - 175 с.

32. Данцинг Дж. Линейное программирование, его применения и обобщения. М.: Прогресс, 1966. - 600 с.

33. Деннис Дж.Б. Математическое программирование и электрические цепи. М.: Иностр.лит. 1961. - 215 с.

34. Дрю Д. Теория транспортных потоков и управление ими. М.: Транспорт, 1972. 424 с.

35. Евдокимов А.Г. Оптимальные задачи на инженерных сетях. X.: Вища шк. 1976. 153 с.

36. Ермольев Ю.М.,Мельник И.М. Экстремальные задачи на графах. К.: Наук, думка, 1968. - 176 с.- 142

37. Житков В.А. Планирование автоперевозок грузов мелкими партиями. М.: Транспорт, 1976. - 108 с.

38. Житков В.А.,Ким К.В. Методы оперативного планирования грузовых автомобильных перевозок. М.: Транспорт, 1982. - 184 с.

39. Жук К.Д. Методология системного проектирования. К.: Знание, 1979. - 28 с.

40. Жук К.Д.,Никифоров А.А. Логический аппарат системного проектирования. К.: Знание, 1980. - 24 с.

41. Жук К.Д., Тимченко А.А.,Доленко Т.Н. Исследование структур и моделирование логико-динамических систем. К.: Наук, думка, 1975. - 199 с.

42. Жук К.Д.,Тимченко А.А.,Родионов А.А. и др. Построение современных систем автоматизированного проектирования. К.: Наук.думка, 1983. - 248 с.

43. Заворицкий В.И.,Старовойда В.П.,Билятинский О.А.,За-бишный О.С. Распределение интенсивности движения в течение суток. Киев : Буд1вельник, 1972, вып. 10. с. 19-29.

44. Закревский А.Д.Алгоритмы синтеза дискретных автоматов. М.: Наука, 1971. 512 с.

45. Зайченко Ю.П. Исследование операций. К.: Вища шк. 1975. - 320 с.

46. Иносэ X., Хамада Т. Управление дорожным движением. М.: Транспорт, 1983. - 248 с.

47. Калинин А.Г. Междугородние перевозки грузов на Украине. К.: Автодорожник Украины, 1972, 2, с.26-28.

48. Кафтанюк Ю.А. Отраслевая автоматизированная система управления автомобильным транспортом. М.: Транспорт, 1977. -112 с.

49. Клинковштейн Г.И. Организация дорожного движения. М.: Транспорт, 1975. - 192 с.

50. Коваленко П.П.,Инатьев Ю.В., Вальц В.К. О закономерностях движения автомобильных потоков на городских улицах. Изв. ВУЗов. Строительство и архитектура. 1968, вып. 4, с. 68-70.

51. Коршунов Ю.М. Математические основы кибернетики. М.: Энергия, 1972. - 376 с.

52. Костенко Л.И.,Тимршенко А.Г.Драйнин Э.З. Электронное моделирование задач исследования операций. К.: Наук, думка, 1973. - 164 с.

53. Кофман А. Модели, методы и целочисленное программирование. М.: Мир, 1977. - 432 с.

54. Кременец Ю.А., Печерский М.П., Шелков Ю.Д. Применение технических средств для управления дорожным движением. М.: Высш. шк. 1974. - 173 с.

55. Кук К.Л.Долсей Э. Кратчайший путь через сеть с переменным временем пробега по дугам. Кибернетический сборник. -М.: Мир, 1968, вып. 5. с.189-194.

56. Лазарев В.Г.,Пийль Е.И. Синтез управляющих автоматов. М.: Энергия, 1978. 408 с.

57. Левит Б.Ю.,Лившиц В.Н. Нелинейные транспортные задачи. М.: Транспорт, 1972. 144 е.

58. Лисицын Б.М.,Цуканов И.М. и др. Алгоритм и комплекс программ оптимизации и управления автомобильными перевозками для ЕСЭВМ. Автомобильный транспорт, 1983, вып. 20. с. 27-29.

59. Лисицын Б.М.,Яцкивский Л.Ю. Теория составления расписания грузовых автомобильных перевозок по системе тяговых плеч. -Харьков: Автомобильный транспорт, 1972. вып. 9.

60. Лобанов Е.М. ,Сыльянов В.В.,Ситников Ю.М. Пропускная способность автомобильных дорог. М.: Транспорт, 1973. -152 с.

61. Ловецкий С.Е., Житков В.А.,Плотинский Ю.М. Задачи маршрутизации перевозок на транспортной сети. В кн.: Организация управления транспортом. - М.: ВИНИТИ, 1980, вып. 2.с. 74-128.

62. Материалы ХХУ1 съезда КПСС. М.: Политиздат, 1981. 223 с.

63. Майоров С.А.,Новиков Г.И. и др. Проектирование цифровых вычислительных машин. М.: Высш.шк. 1972. - 342 с.

64. Мамиконов А.Г. Основы построения АСУ. М.: Высш.шк. 1981. - 248 с.

65. Михин А.А.,Ястребцов Г.И. Комплексная программа развития транспорта. М.: Знание, 1983. - 64 с.

66. Модин А.А. Автоматизированная система управления. -М.: Знание, 1973. 144 с.

67. Моисеев Н.Н. Основы теории оптимальных систем. М.: Наука, 1976. - 223 с.

68. Наапетян М.Р.,Сушко С.М. Совершенствование организации работы автотранспорта.- К.: Техника, 1982. 135 с.

69. Нородное хозяйство УССР в 1983г. Статистический ежегодник. Киев: Техн1ка, 1984. - 384 с.

70. Одинцов Д.Г.,Жаворонков Е.П. Совершенствование грузовых перевозок в строительстве. Механизация строительства,1972, вып. 3, с.5-7.

71. Панов С.А.,Поляк A.M.,Поносов Ю.К. Управление грузовыми автомобильными перевозками. М.: Транспорт, 1979. - 127 с.

72. Панов С.А. Модели маршрутизации на автотранспорте. М.: Транспорт, 1974. 152 с.

73. Перлин В.М. Конвейерный метод перевозки контейнеров. М.: Знание, 1982. 64 с.

74. Печерский М.П.Дорович Б.Г. Автоматизированные системы управления дорожным движением в городах. М.: Транспорт, 1979. - 175 с.

75. Повороженко В.В. Координация и взаимодействие различных видов транспорта. М.: Знание, 1982. - 64 с.

76. Попков Ю.С.,Посохин М.В.,Гутнов А.Э. и др. Системный анализ и проблемы развития городов. М.: Наука, 1983. - 512 с.

77. Поспелов Д.А.-Логические методы анализа и синтеза схем. М.: Энергия, 1972. 368 с.

78. Прим Р.К. Кратчайшие связывающие сети и некоторые обобщения. Кибернетический сборник. - М.: Иностр.лит. 1961, вып.2.

79. Проектирование АСУ на автомобильном транспорте. М.: Транспорт, 1975. - 94 с.

80. Пухов Г.Е. и др. 0 перспективных направлениях развития быстродействующих вычислительных средств. Математическое моделирование и теория электрических цепей. - Киев : Наук.думка, 1973, вып. 10. - с. 5-7.

81. Раскин Л.Г. Анализ сложных систем и элементы теории оптимального управления. М.: Советское радио, 1976. - 344 с.

82. Рева В.М.Дигум Ю.С.,Вайншток М.А. и др. Оперативное управление городским пасажирским автотранспортом. К.: Техн1ка, 1982. - 174 с.

83. Резер С.М. Внедрение АСУ на транспорте. В кн. : Совершенствование планирования и управления на транспорте. М.: Знание, 1982. с. 11-25.

84. Решетников Б.В.,Голованенко С.Л.,Посыпай В.Г. и др. Передовые методы грузовых автомобильных перевозок. К.: Техн1-ка, 1978. - 178 с.

85. Румшиский Л.З. Математическая обработка результатов эксперимента. М.: Наука, 1971. - 192 с.

86. Санников Ю.И. Исследование и совершенствование средств и методов автоматизации учета характеристик движения на автодорогах. К.: Автореферат КАДИ, 1975. - 24 с.

87. Сергейчук И.М. Вычислительное устройство для оперативного решения сетевых задач одного класса. УС и М. 1977, № 3.с. 84-90.

88. Сергейчук И.М.,Федотов Л.В. А.с. 6I0I26(СССР}. Устройство для определения и вывода на печать кратчайшего пути через сеть с переменными параметрами ветвей. Опубл. в Б.и., 1978,21.

89. Сергейчук И.М.,Федотов Л.В. А.с. 619938 ( СССР). Аналоговая модель определения и регистрации кратчайшего пути. -Опубл. в Б.и. 1978, № 30.

90. Сильянов В.В. Теория транспортных потоков в проектировании дорог и организации движения. М.: Транспорт, 1977. -303 с.

91. Старовойда В.П. Некоторые закономерности изменения интенсивности движения транспортных средств на городских улицах.-Автомобильные дороги и дорожное строительство., 1978, 23, с.46-50.

92. США: Организационные проблемы управления. Под общ ред. Мильнера Б.З. М.: Мысль, 1976. - 280 с.

93. Тихомиров В.Д. Планирование и анализ эксперимента. М.: Легкая индустрия, 1974. - 262 с.

94. Украинская ССР в цифрах в 1983 году. К.: Техн1ка, 1984. - 150 с.

95. Федотов Л.В.,Филиппович Л.В. Решение задачи определения оптимального маршрута движения транспорта с учетом текущих ихменений интенсивности. Автомобильный транспорт, 1974,вып.II.

96. Федотов Л.В.,Филиппович Л.В.,Сергейчук И.М. Моделирование задачи определения узла встречи на сетях с переменными параметрами. УС и М, 1974, № 4, с. 101-104.

97. Федотов Л.В., Сергейчук И.М. Построение моделей на интегральных элементах для отыскания оптимальных путей на сетях с переменными параметрами. В кн.: Проектирование и внедрение новых средств вычислительной техники. -Киев : ИК АН УССР, 1975, с. 24-35.

98. Федотов Л.В.,Сергейчук И.М.,Филиппович Л.В. Построение оптимальной сети связи на логико-аналоговой модели. УС и М,1975, №2, с. II4-II6.

99. Федотов Л.В.,Сергейчук И.М. Моделирование некоторых экстремальных задач на сетях с переменными параметрами и информационное обслуживание транспортных потоков. Электроника и моделирование. - Киев: ИЭ АН УССР, 1977, вып. 15. с.61-65.

100. Федотов Л.В.,Сергейчук И.М. Разработка алгоритмических электронных моделей для построения кратчайших связывающих сетей. Науч.-техн. отчет. / КАДИ: Гр. 75007617; Киев, 1975. 36 с.

101. Федотов Л.В.,Сергейчук И.М.,Денисенко В.Г.,Ершов М.А. Разработка моделей для определения оптимальных маршрутов проезда автотранспорта по г.Харькову. Науч. -техн.отчет, / КАДИ;

102. Гр. 76064685; Киев, 1976. 55 с.

103. Филиппович Л.В. Исследование и разработка методов определения оптимальных маршрутов движения авторанспорта по критерию "время". К.: Автореферат, КПИ, 1975. - 24 с.

104. Форд Л., Фалкерсон Д. Потоки в сетях. М.: Мир,1966.

105. Хейт Ф. Математическая теория транспортных потоков. М.: Мир, 1966. 187 с.

106. Хомяк Я.В. Проектирование сетей автомобильных дорог. М.: Транспорт, 1983. 207 - с.

107. Четверухин Б.М.,Ершов М.А. Прогнозирование состояния транспортных потоков. Атомоб1льн1 дороги I дорожне буд1вницт-во, 1984, вып. 34, - с.88-95. '

108. Четверухин Б.М.,Вунтесмер И.А. Организация сбора информации о состоянии транспортных потоков автоматизированных систем контроля движения. Автомоб1льн1 дороги I дорожне бу-д1вництво, 1982, вып.30. с. 47-51.

109. ПО. Шинкарев Н.И. Научно-технический прогресс на транспорте. М.: Знание. 1982. - 64 с.

110. I. Якубайтис Э.А. Асинхронные логические автоматы. -Рига: Знание, 1966. 380 с.

111. H2.LUl$-Belle System Reck. J .J 9 65, И nhS. 113. Мс.СЫ$кгу £. AU mm nations o-f l>oole<iu fitKi-ciiotis. Bell sysiem Teckn. J., К 3Ft А/в, 41.zuscdL J. 6. Ол ilie Skoziesi Spavintv^ofaSzcupk a^oL the Salesman Pzoilem.

112. Рюс.Лтгг. JU&lh. So*. 19ГС, Vot.% 4S-F0p.

113. Pitzce I. „ Vized беагск Mgozithm f-ozTzuck ®cspatektKj fto-Mewl." P«t Г, Tzaus, R«v v. 3, w.4,p. Ю6-Ш.

114. Pluck-CLzd АкЬге. A. Le Sob pzoiection cUs autowo&lCsUs ci oialole a Ia ti^Cjulaiiovi (PAAC). Щ. QmLomoI!>.} 1974, k, m-zzs.