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

МИНИСТЕРСТВО СВЯЗИ РОССИЙСКОЙ ФЕДЕРАЦИИ Московский технический университет связи и информатики

Р Г Б О Д На ПРаВаХ РУКОПИСИ

I 3 УЛЬЯНОВ Владимир Вячеславович

УДК 656.861:621.39

ИССЛЕДОВАНИЕ И РАЗРАБОТКА ИНФОРМАЦИОННО-ТЕХНОЛОГИЧЕСКИХ СРЕДСТВ АВТОМАТИЗАЦИИ УПРАВЛЕНИЯ МОБИЛЬНОЙ ПОЧТОЙ

Специальность: 05.12.16 -Автоматизация и механизация предприятий и средств связи

Автореферат диссертации на соискание ученой степени кандидата технических наук

Москва 1996

Работа выполнена на кафедре Автоматизированных систем управления технологическими процессами и проектирования в связи Московского технического университета связи и информатики.

Научный руководитель - Заслуженный деятель науки Российской

Федерации, доктор технических наук, профессор И.А.МАМЗЕЛЕВ. Научный консультант - кандидат технических наук,

доцент В.А.МИЦКЕВИЧ. • Официальные оппоненты - доктор технических наук,

профессор В.А.РУЛЕВ; кандидат технических наук, доцент В.Н.МАКСИМЕНКО. Ведущее предприятие - Научно-исследовательский и проектно-

конструкторский институт почтовой связи.

» 1996 г. в/У'^ч,

Защита диссертации состоится 'У У" 1996 г. В'0 ча-

сов на заседании диссертационного совета К 118.06.02 по присуждению ученой степени кандидата технических наук в Московском техническом университете связи и информатики по адресу: 111024, Москва, Авиамоторная ул., д. 8а.

С диссертацией можно ознакомиться в библиотеке университета.

Автореферат разослан Оч-п^ил 1996 г.

Ученый секретарь диссертационного совета К 118.06.02

канд. техн. наук, доцент

- 3 -

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Задачи, которые ставятся и решаются при создании ускоренной почты Российской Федерации, касаются прежде всего оптимизации магистральных перевозок почты. В НИИ Почтовой связи на основе принятых моделей магистральной почтовой связи разработано программное обеспечение для российско-французского совместного предприятия EMS "Гарант-Пост", оптимизирующее городские перевозки почтовых отправ-чений. По оценке специалистов она позволяет уменьшить пробег автомобиля, развозящего почту из отделения перевозки почты клиентам, в среднем на Ъ% .

Характеризуя в целом состояние проблемы, можно утверждать, что lo настоящего времени рассматривались статические задачи большой >азмерности для построения маршрутов перевозки почты. Разработанные [ланы перевозки почты предполагалось использовать длительное время, шлоть до момента возникновения изменений во внешней среде. Единс-■венным динамически меняющимся фактором была неравномерность во ремени почтовых потоков и связанная с этим возможность нагрузки на ранспортные средства.Данные условия если и выдвигали требования к роизводительности алгоритмов и компьютеров, то они были связаны п ервую очередь с размерностью задачи, а не с необходимостью работы режиме реального времени. В задачах, поставленных в предлагаемой аботе, на первое место выдвигаются требования оперативности полу-о.ния решения, что обусловливает требования к производительности агеритмов и компьютеров. При этом подход к выбору методов ускоре-

- 4 -

пня решения задач неизбежно меняется.

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

Цель и задачи исследования. Целью

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

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

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

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

3. Создать параллельные варианты алгоритмов маршрутизации поч ты и реализовать их в программных модулях. Оценить эффективное! разработанных алгоритмов.

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

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

- 5 -

I

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

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

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

3. Разработанные эвристики для реализации метода декомпозиции, считывающие приоритетные направления концентрации заказов, примени-1Ы к динамическим задачам маршрутизации, что принципиально отличает IX от известных ранее.

4. Применение квазидиагональной матрицы кратчайших расстояний в >бобщенном методе естественных границ позволяет снижать размерность 1адачи маршрутизации, проводить предварительные расчеты, преиму-;ественно используя скоростные транспортные магистрали и при сохра-ении в машинной памяти только значимых элементов, экономить ресур-ы ЭВМ на 60 и более процентов.

Основные положения, выносимые на а щ и т у:

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

2. Принципиально переменный состав клиентов оперативной почты элает необходимым привлечение картографических баз данных, в частости, географических информационных систем (ГИС) для расчета мат-1Ц кратчайших расстояний в задачах маршрутизации. В противном слу-

- б -

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

3 . Наибольший эффект от распараллеливания управляющего вычислительного процесса удалось получить на этапах декомпозиции и распределения заказов по средствам автотранспорта, в котором организован межпроцессорный обмен информацией. Эффект от распараллеливания алгоритмов маршрутизации меньше, что объясняется особенностью распараллеливания точных методов линейного программирования в задача> маршрутизации. Алгоритмы точных методов от всего дерева маршруто! отсекают "не перспективные" параллельные ветви, то есть преобразуют задачу, имеющую по своей природе параллельный характер, в последовательную. Вновь распараллеливать полученный последовательный процесс неэффективно.

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

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

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

Практическая ценность и реализ; ция результатов работы. Разработанные алгори-мы реализованы в виде пакета прикладных программ на языке програ] нирования ПАСКАЛЬ. Результаты работы внедрены на двух предприяти Министерства связи Российской федерации. Акты о внедрении прилаг ,этся.

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

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

Апробация работы. Основные результаты работы докладывались на Всесоюзном научно-техническом семинаре "Районные распределенные вычислительные системы". г.Москва, Всесоюзное научно-техническое общество радиотехники, электроники и связи им. А.С.Попова, 28-29 июня 1990 г.; IV Международной конференции молодых ученых; Высшая инженерная школа, г. Желина (Германия), 12-14 сентября 1990 г.; Научно-техническом семинаре "Передача и обработка данных в системах управления сетями ЭВМ", Киев, ионь 1991 г.; Всесоюзной ■научно-технической конференции "Однородные вычислительные системы, структуры и среды", Москва, Всесоюзное научно-техническое общество радиотехники, электроники и связи им. А.С.Попова, 1991.; Научно-технической конференции профессорско-преподавательского состава, научных и инженерных работников и аспирантов, Москва МТУСИ, 28-30 января 1992 г.; Международном форуме информатизации 111-го Всемирного конгресса 1ТЗ-92 "Информационные коммуникации, сети, системы и технологии" (секция Информатизация почтовой связи), Москва, Международная академия информатизации, 23-28 ноября 1992 г.; Научно-технической конференции профессорско-преподавательского и инженерно-технического состава. Москва, МТУСИ, 26-28 января 1993 г.; Международном форуме информатизации 1У-го Всемирного конгресса 1ТБ-94 "Информационные технологии, системы, коммуникации и сети" (секция Телекоммуникационные и вычислительные системы связи), Москва, Международная академия информатизации, 22 ноября 1994 г.; Научно-технической конференции профессорско-преподавательского и инженерно-технического состава, посвященной 100-летиему юбилею Радио, г. Москва, МТУСИ, 1995.

Публикации. По материалам диссертации опубликовано 12. научных работ.

Ст р у ктура и объем работы. Работа

состоит из введения, пяти глав, заключения, списка литературы и двух

приложений. Диссертация содержит 132 страницы машинописного тскста и 38 рисунков. Список литературы содержит 106 наименований.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе рассмотрены цели и организационные структуры нескольких вариантов информационно-технологических систеки в мобильной почте.

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

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

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

Анализируется модель экспресс-почты, которая соответствует сос-

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

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

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

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

Заказ описывается группой данных 0.?=< К*тпЛ , , >,

-де Кд,.,, . ( Кпол р - координаты отправителя (получателя), ^игп • — сонтрольное время исполнения j -го заказа. Оператор декомпозиции 1елит множество заказов А = {о.*, -•• , ^п} между П<р Фурго-

¡ами экспресс-почты, Я)[А] = ¿{ 0.1,0.',..., О.® } *-■ \ А ^ , А, ,

А» .71 Г * г/6 1

. П(? , где А^а^.а^,. а^ - заказы ДЛЯ1-ГО

>ургона. общее задание С -му фургону А[ = + А|, • где

А? = { 0.;^ , О.? 2., • • • , 0-1, д^} ~ заказы для Ь -го фургона, 1соторые же начали выполняться к моменту расчета. Оператор (у выделяэт дан-ые для задачи маршрутизации С -го фургона. Тогда множество точек ля построения маршрута

К;. = £[АГЩ] = 6 [А*] + 6Е А*] =

Г «я к* къ к" ки \ г

1 '^ОГЛ,^ ^ПОЛ,!* • • • , ^ОТП.ГТ^ > ^ПОЛ,?^ 5 ЮЛ,1 > • • • **

ограничивающим условием, что событие С ( Котп^) предшествует С ( КВДЛ р. Множество дополняется координатой К^ ф нахождения фургона на момент расчета.

Оператором V/ обозначена операция маршрутизации — V/СК^З , где множество И представляет упорядоченное множество

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

Расчетное время доставки Тдост.1 = {^ОСТД} •• • > ^дост.т^ + Ц; | • Пусть оператор 5 выделяет временные данные 3 = {^исп И 4

} . Критерием успешного

решения задачи будет условие неотрицательности элементов множества Т1срит,1 = ""tjocrn.li • ' * ? "^иеп,пЧ+~~ ^осп^т!«^',. | или, если

перейти к интегральнын характеристикам, ('ЬиСП | ~

Возрастание характерно для более удачного решения построения

маршрута при соблюдении условия I Ш1п [1исМ ~ 1 ¡ОСТД ♦ • • • , ^ит.П^+д;" ""'Ьдос^иц.+^У I ^ ^доп • Критерием оценки задачи декомпозиции является минимальный разброс функций , что свидетельствует о равномерности загрузки фургонов ГЛОХ | X /Па> - 9: I/ £1 ф; /Пф < Ъ 14КП(Г

Iе 1 т т ^

Непрерывный процесс управления экспресс-почтой в операторной форм<

МС6[^[{А} + ана^ - {А^-Д^!. . Построение маршрут;

-экспресс-почты в общей''постановке представляет многопродуктовую задачу о перевозках с некоторыми особенностями по классификации линейного программирования (фургон с С^^ посылками на борту считается одним условным отправителем груза по адресам).

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

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

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

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

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

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

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

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

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

ить реальный отрезок маршрута. Далее отрезки объединяются в более

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

не сравняется с числом автофургонов.

Л*~ in* п*

Обозначение А ~ \ И-Ь "-г>—1ик/отражает множество нереализованных заказов. П Г ~ оператор декомпозиции с эвристиками Эк. Ф С AS) = {Ai, А*,Aj | э при выполнении условий A*=plAi, A¡. Л Aj=0, при ; i,j = 1,2,... ,í. Каждому множеству A¡. ставится в соответствие значение функции оценки У1 (А*) = •• • «^»Jt • Из совокупности £Al,At} . . . , Ак,... , Az } выбирается такое Ак , для которого достигает максимального (неблагоприятного) значения

K¡=Index < max СУ(А"). A J),... (Аяг)>.

Выбранное подмножество

А*, подвергается действию оператора маршрутизации G (А*;). Если

1 Г 1

оператор О не может построить маршрут, то оператор деструкции

применяют вновь 2) (Ak-.)U4Ai , А,.... « Аа V — А После оконча-

Г.» J А» J ' А» 1 ния процесса деления множество групп 1 A, Ai... . . А* Г объе-

{. Ц Д И t * Л М 1 J

"i » Aj , . . . , A n V , ( индекс "и"

обозначает выполняемые заказы ).

{А4, А«..... А.}- {АГ,А;.....АГ} А;, .. А;}

Далее проводится построение элементарных маршрутов ■{ G (Aj) , G С • С(Ап)^1. Определим оператор объединения элементарных маршрутов Е = {Эп+1,Эп+1, .. . Эщ}, где Эп+1, . • • < Эт -эвристики объединения. Максимальное значение функции оценки YCG(A{.)3 =

£ G (A¡_)3 , . . Yt EG(Aj.)3} соответствует наиболее простому маршруту.

-^{G(Ai), 6 (Al), ... , БСАпУ^еСЛИ П=П,р—завершение задачи

Kjt<= Index<max {Г[G(АДГСG(A2)],...,Y[G(AnV}>;

Kj, = Lndex<maxC{ YcGCAji, .. ,Y[G(An)j}-

-YCG(Ah)]]>; {G(AI),G(Ai)f ...,GCA„)}- GCAj,) - G(Ajt) + + ECGCAjP.GCAj^] , n-n-i.

Рассмотрен синтезирующий алгоритм декомпозиции применительно к задаче экспресс-почты. Каждая группа А; из множества Ч А| , А,,

ди 1 1

' ' ' > Пт ) 7- _ ( и м

дополняется координатами фургона йфД , ,

0.^. , 0.ф ь} . Оператор синтеза маршрутов С = { Э ^ , Э^, ... ,

распределяет по автофургонам еще не начавшие выполняться заказы A^-CCAi, Ai, ••• , АП(р, Ав]- { Ai, Aj, . . . , Ап,) } , далее наступает этап маршрутизации: | G ( A i), G( Aj>), . . ., GCAn^)^.

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

В разработанной классификации эвристики разделяются на типы с условными наименованиями: скалярные, векторные, смешанные, топологические и кластерные. __.

Последовательность действий трех первых эвристик:

- получение одного нового заказа;

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

- коррекция марирута с учетом нового заказа.

Маршрут определяется с помощью расчета функции тяготения 0: для каждого L-го маршрута. Выбирается • L = index < max (

Для скалярной эвристики ©¿=1/( titofp + li.HOA ), гДе ¿цотп ~

-mLn{|KjaK,OTn,Kmjl}> 2-П^ ; = mi-П (I К^пол, Kmj 1} , j*<j<2-nL.

Для векторной эвристики 0l~ Ф £чотп\гДе I Упарш-Улдас!,

Уцарщ.~ jL^ апд (KmjU, Kmj)/C2ni"i), Узп-К = Q.ng (Кзак,шп, Ksok,mJ.

Конкретный вид ( один из возможных ): ©¿ = 0 при COS bfj. ^ О и

eL=cos X/Хот

при COS yL n

Для смешанной эвристики = LCOS (У\/2)+2еЗ/( Ciom+ tihiv)-

3 конкретных расчетах принято ЭЕ=0,1 J fl=i.

Для задач оперативной доставки почты особое значение имеют ска-1ярные и смешанные эвристики.

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

Разработанные алгоритмы системы оперативного управления мобиль-ой почтой реализованы в виде пакета программ на языке ПАСКАЛЬ, ункция зака:

казов /\ = {cLi , Hi,.. . , Qn}

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

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

Далее работа эвристик оценивалась количественно по предложенным критериям равномерности распределения заказов по фургонам хг Первый них П^аак ~ Пер I / ПСр представляет

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

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

ее работы представляет интерес в силу своей противоречивос-

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

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

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

Для алгоритмов Литтла и Дейкстры удалось добиться ускорения расчетов только в 1,3 ... 1,8 раз, что объясняется большой долей последовательных участков в распараллеленном алгоритме.

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

Результаты сравнительного экспериментального анализа алгоритмов систем управления экспресс-почты и оперативной доставки доказали практическую применимость алгоритмов и дали прогнозируемые результаты о повышении эффективности управления мобильной почтой при увеличении поступления заказов (критерий: величина пробега транспортного средства на один заказ)г

г

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

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

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

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

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

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

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

- 17 -

менения картографических данных ГИС.

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

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

ОПУБЛИКОВАННЫЕ РАБОТЫ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Капелин Г.Г., Погодин А.Н., Ульянов В.В. Автоматизированный измерительный комплекс с использованием микрокомпьютера PSA в составе локальной сети ЭВМ. Тезисы докладов научно-технического семинара "Передача и обработка данных в системах управления сетями ЭВМ". - Киев: Знание, июнь 1991 г. - с. 12.

2. Погодин А.Н., Ульянов В.В. Локально-распределенная вычислительная система перспективного отделения связи. Тезисы докладов

.Всесоюзной научно-технической конференции "Однородные вычислительные системы, структуры и среды". Часть II. - М.: Всесоюзное научно-техническое общество радиотехники, электроники и связи им. А.С.Попова, 1991. - с. 151.

3. Погодин А.Н., Ульянов В.В. Аппаратные и программные средства локальной вычислительной сети предприятия почтовой связи. Тезисы докладов научно-технической конференции профессорско-преподавательского состава, научных и инженерных работников и аспирантов. -M.: МТУСИ, 28-30 января 1992 г. - с. 73.

4. Погодин А.Н., Прокопович A.B., Ульянов В.В. Локальная вычислительная сеть предприятия связи. Тезисы докладов научно-техни-

ческой конференции профессорско-преподавательского состава, научных и инженерных работников и аспирантов. - м.: МТУСИ, 2B-3G' января

1992 Г. - с. 73.

5. Прокопович A.B., Ульянов В.В. Программное обеспечение АРМ предприятий связи. Тезисы докладов научно-технической конференции профессорско-преподавательского состава, научных и инженерных работников и аспирантов. - М.: МТУСИ, 28-30 января 1992 г. - с. 72.

6. Ульянов В.В. Вычислительная система из персональных ЭВМ для исследования технологических объектов. Тезисы докладов IV Международной конференции молодых ученых.- Желина (Германия): Высшая инженерная школа, 12-14 сентября 1990 г. - с. 13.

7. Ульянов В.В. Некоторые элементы районной распределенной информационной системы почтовой связи. Тезисы докладов Всесоюзного научно-технического семинара "Районные распределенные вычислительные системы". - М.: Всесоюзное научно-техническое общество радиотехники, электроники и связи им. А.С.Попова, 28-29 июня 1990 г. -с. 18.

8. Ульянов В.В. Оперативное управление экспресс-почтой с помощью мультитранспьютерных вычислительных систем. Тезисы докладов на научно-технической конференции профессорско-преподавательского и инженерно-технического состава, посвященной 100-летнему юбилею Радио. - М.: МТУСИ, 1995. - С. 12.

9. Ульянов В.В. Оптимальные маршруты в почтовой связи. Тезисы докладов на Международном форуме информатизации III-го Всемирного конгресса ITS-92 "Информационные коммуникации, сети, системы и технологии" (секция Информатизация почтовой связи). - М.: Международная академия информатизации, 23-28 ноября 1992 г.-с.29.

10. Ульянов В.В. Оптимальные маршруты почтовой связи. Тезись докладов научно-технической конференции профессорско-преподавательского и инженерно-технического состава. М. : МТУСИ, 26-28 января

1993 г. - с. 4.

11. Ульянов В.В. Параллельные алгоритмы в задачах почтовой связи. В сборнике научных трудов учебных заведений связи "Анализ сигналов и систем связи", N 161. - С-П.: СПбГУТ, 1995. -с. 43-49.

12. Ульянов В.В., Баранов A.B. Использование географических информационных систем в отрасли связи. Тезисы докладов на Между народном форуме информатизации IV-го Всемирного конгресса ITS-94 "Информационные технологии, системы, коммуникации и сети" (секция Те-

лекоммуникационные и вычислительные системы связи). - М.: Международная академия информатизации, 22 ноября 1994 г. - с.38.

Подписано в печать 4 04 96. Формат 60x84/16, Печать офсетная.

2!15ем_1лО_^сл^п^л^_Тирая_100_экз__Заказ_147__________________

ЗАО "Информсвязьиздат". Москва, Авиамоторная, 8