Введение к работе
Актуальность проблемы. Уменьшение объеиа почтовых операций, растущая конкуренция как со стороны новых электронных средств коммуникаций, так и операций традиционного плана (перевод денежных средств с помощью банковских операций) заставляют Федеральную почтовую связь искать альтернативные источники дохода за счет новых форм своей деятельности и расширения наменклатуры предоставляемых услуг-. Одной из инновационных форм деятельности является организация таких видов мобильной почты, как экспресс-почта и оперативная доставка почты. В Федеральной службе почтовой связи Российской федерации, в научных учреждениях (НИИ Почтовой связи, Московском техническом университете связи и информатики и др.) разрабатывается концепция создания.ускоренной почты как стратегического направления развития почтовой службы Российской Федерации.
Задачи, которые ставятся и решаются при создании ускоренной почты Российской Федерации, касаются прежде всего оптимизации магистральных перевозок почты. В НИИ Почтовой связи на основе принятых моделей магистральной почтовой связи разработано программное обеспечение для российско-французского совместного предприятия EMS "Гарант-Пост", оптимизирующее городские перевозки почтовых отправ-neniw. По оценке специалистов она позволяет уменьшить пробег автомобиля, развозящего почту из отделения перевозки почты клиентам, в среднем на 5% .
Характеризуя в целом состояние проблемы, можно утверждать, что
\о настоящего времени рассматривались статические задачи большой
>азмерности для построения маршрутов перевозки почты. Разработанные
таны перевозки почты предполагалось использовать длительное время,
іплоть до момента возникновения изменений во внешней среде. Единс-
венным динамически меняющимся фактором была неравномерность во
ремени почтовых потоков и связанная с этим возможность нагрузки на
ранспортные средства.Данные условия если и выдвигали требования к
роизводительности алгоритмов и компьютеров, то они были связаны п
ервую очередь с размерностью задачи, а не с необходимостью работы
режиме реального времени. В задачах, поставленных в предлагаемой
аботе, на первое место выдвигаются требования оперативности полу-
о.ния решения, что обусловливает требования к производительности
агсритмов и компьютеров. При этом подход к выбору методов ускоре-
- 4 -пня решения задач неизбежно меняется.
Отличительной особенностью диссертационной работы является то, что в ней ставятся и решаются задачи развивающихся и проектируемых .почтовых служб. Опережающее развитие теоретических методов необходимо при проектировании наукоемких управленческих технологий. К этим технологиям можно отнести и автоматизированную диспетчеризацию почты.
Цель и задачи исследования. Целью
диссертации является разработка эффективных методов автоматизированного управления мобильной почтой ка основе анализа специфических задач и построения соответствующих алгоритмов, способных действовать в режиме реального времени.
Поставленная цель обусловила необходимость решения следуюздиэ задач теоретического и прикладного характера.
-
Разработать и обосновать подходы к решению сложной проблемі оперативного управления различными организационно-технологическим) структурами мобильной почты с учетом необходимости получения решения в режиме реального времени при большой размерности задачи и от сутствии готовой матрицы кратчайших расстояний, поставленная задач; разделена на блоки, реализация функций которых имеет самостоятель ную ценность.
-
Разработать для каждой из предлагаемых организационно-техно логических структур мобильной почты математическую модель на основ концепции коллектива вычислителей, что позволит обосновать примене ние конкретных типов распределенных вычислительных структур.
3. Создать параллельные варианты алгоритмов маршрутизации поч ты и реализовать их в программных модулях. Оценить эффективное! разработанных алгоритмов.
4. Предложить эвристики для реализации синтезирующих, дестру* тнвных и смешанных алгоритмов декомпозиции, отличающихся быстроте решения. Ряд алгоритмов декомпозиции использовать в программных м< пулях и опробировать их на модельных примерах, произвести их сраї нительный анализ.
Методы исследования. В качестве методов и следований используются элементы теории математической логики, эл :іентьі теории множеств, теория сообщающихся конкурентных процессо теория десеквенции (распараллеливания алгоритмов, программ, вычи лєний), формально-эвристические методы оптимизации.
- 5 -
Научная новизна работы заключа-
етсявследующем:
1. Однозначное соответствие разработанных информационно-матема
тических моделей мобильной почты моделям теории коллектива вычисли
телей обусловило применение аппарата распараллеливания алгоритмов в
постановке и решении задач мобильной почты. В частности, распрост
ранены положения теории распараллеливания вычислительных процессов
на методы маршрутизации применительно к задачам пересылки почтовых
отправлений. При распараллеливании максимальный эффект наблюдается
для наиболее несовершенных алгоритмов, при этом распараллеливание
следует применять не столько для ускорения "быстрых" алгоритмов,
сколько для увеличения скорости "медленных".
2. Предложены и обоснованы структуры сложных многоступенчатых алгоритмов управления мобильной почтой, различным образом объединяющих задачи маршрутизации и декомпозиции. Метод декомпозиции в данном случае используется как для снижения размерности задачи, так и цля распределения заказов по средствам доставки.
-
Разработанные эвристики для реализации метода декомпозиции, считывающие приоритетные направления концентрации заказов, примени-1Ы к динамическим задачам маршрутизации, что принципиально отличает їх от известных ранее.
-
Применение квазидиагональной матрицы кратчайших расстояний в >бобщенном методе естественных границ позволяет снижать размерность іадачи маршрутизации, проводить предварительные расчеты, преиму-;ественно используя скоростные транспортные магистрали и при сохра-
ении з машинной памяти только значимых элементов, экономить ресур-
ы ЭВМ на 60 и более процентов.
Основные положения, выносимые на
а щ и т у:
1. Для решения задач управления мобильной почтой необходим омплексный подход с согласованием математических, организационных технических решений.
2. Принципиально переменный состав клиентов оперативной почты
элает необходимым привлечение картографических баз данных, в част
ости, географических информационных систем (ГИС) для расчета мат-
іц кратчайших расстояний в задачах маршрутизации. В противной слу-
- б -чае понадобилось бы вычислять и хранить данные о 10 возможных расстояниях для такого города, как Москва.
3 . Наибольший эффект от распараллеливания управляющего вычислительного процесса удалось получить на этапах декомпозиции и распределения заказов по средствам автотранспорта, в котором организован межпроцессорный обмен информацией. Эффект от распараллеливания алгоритмов маршрутизации меньше, что объясняется особенностью распараллеливания точных методов линейного программирования в задача> маршрутизации. Алгоритмы точных методов от всего дерева маршрутої отсекают "не перспективные" параллельные ветви, то есть преобразуют задачу, имеющую по своей природе параллельный характер, в последовательную. Вновь распараллеливать полученный последовательный процесс неэффективно.
4. В соответствии с типами организационно-технологически;
структур мобильной почты разработаны их математические модели, поз
волившие формализовать процесс управления мобильной почтой и послу
жившие основой создания программного обеспечения системы управле
ния. В соответствии с теорией коллектива вычислителей информацион
но-вычислительные структуры экспресс-почты и, оперативной доставк
почты определяются как сосредоточенная и распределенная вычисли
тельная системы. '
5. Экспериментальное исследование алгоритмов маршрутизации по казало, что предпочтительно использование смешанной эвристики сип тезирующего алгоритма декомпозиции для экспресс-почты (предложеі: ее конкретная математическая формула) и варианта скалярной эвристк ки для оперативной доставки почты.
Личный вклад. Все основные научные результаті изложенные в диссертации, получены автором лично.
Практическая ценность и реализ; ция результатов работы. Разработанные алгори-иы реализованы в виде пакета прикладных программ на языке програї мирования ПАСКАЛЬ. Результаты работы внедрены на двух предприяти Министерства связи Российской Федерации. Акты о внедрении прилаг ,этся.
Результаты диссертационной работы могут быть применены не тол ко в задаче управления экспресс-почтой и оперативной ее доставк но и в задачах перевозки для непостоянного состава клиентов и не
- 7 -колькими транспортными средствами, например, для доставки телеграмм. При этой компьютерный терминал в транспортном средстве дополняется печатающим устройством для вывода текста телеграмм, которые передаются по системе сотовой связи. Второй пример - доставка на дом получателям посылок из укрупненных доставочных отделений связи. В последнем случае отпадает необходимость установки компьютерного терминала в транспортном средстве. Маршрут может выдаваться в распечатанном виде одновременно с передачей группы посылок.
Апробация работы. Основные результаты работы
докладывались на Всесоюзном научно-техническом семинаре "Районные распределенные вычислительные системы". г.Москва, Всесоюзное научно-техническое общество радиотехники, электроники и связи им. А.С.Попова, 28-29 июня 1990 г.; IV Международной конференции молодых ученых; Высшая инженерная школа, г. Желина (Германия), 12-14 сентября 1990 г.; Научно-техническом семинаре "Передача и обработка данных в системах управления сетями ЭВМ", Киев, ионь 1991 г.; Всесоюзной научно-технической конференции "Однородные вычислительные системы, структуры и среды", Москва, Всесоюзное научно-техническое общество радиотехники, электроники и связи им. А.С.Попова, 1991.; Научно-технической конференции профессорско-преподавательского состава, научных и инженерных работников и аспирантов, Москва МТУСИ, 28-30 января 1992 г.; Международном форуме информатизации 111-го Всемирного конгресса ITS-92 "Информационные коммуникации, сети, системы и технологии" (секция Информатизация почтовой связи), Москва, Международная академия информатизации, 23-28 ноября 1992 г.; Научно-технической конференции профессорско-преподавательского и инженерно-технического состава. Москва, МТУСИ, 26-20 января 1993 г.; Международном форуме информатизации IV-ro Всемирного конгресса ITS-94 "Информационные технологии, системы, коммуникации и сети" (секция Телекоммуникационные и вычислительные системы связи), Москва, Международная академия информатизации, 22 ноября 1994 г.; Научно-технической конференции профессорско-преподавательского и инженерно-технического состава, посізященной 100-летиему юбилею Е'адио, г. Москва, МТУСИ, 1995.
Публикации. По материалам диссертации опубликовано 12 научных работ.
Ст р у ктура и объем работы- Работа
состоит из введения, пяти глав, заключения, списка литературы и двух
приложений. Диссертация содержит 132 страницы машинописного текста и 38 рисунков. Список литературы содержит 106 наименований.