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

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

На правах рукописи Мула Елена Альбертовна

УДК 656.861.44

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

Специальность 05.12.16 - Механизация и автоматизация

предприятий и средств связи

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

Москва 1993

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

Научный рукоьодитель - доктор технических'наук,

профессор Ь.А.РУЛЕВ

официальные оппоненты - доктор технических наук,

профессор В.А.ГОРЕЛИК; - кавдвдат технических наук, доцент А.С.В0Р02Ц0В

Ведущее предприятие - Научно-исследовательский

институт почтовой связи (НИШ1С)

Еащита состоится . л?., на заседании специализированного совета K-118.Q6.02 при Московском ордена Трудового Красного Знамени техническом университете связи и информатики по адресу: 111024, Москва, Е-24, ул.Авиамоторная, 8а.

С диссертацией молшо ознакомиться в библиотеке МГУ СИ.

Автореферат разослан " yyi&UL l££3 г.

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

jо

•В.ДШИНА

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

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

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

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

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

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

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

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

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

гИ

- 3 -

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

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

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

3. Разработка методов решения задач оптимизации планов перевозки почты по'городской сети почтовой связи.

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

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

Методы исследования. Б основу диссертации положены метода математического программирования, в частности модифицированный симплекс-метод, метод генерирования столбцов, метод ветвей и границ, метод Флойда - Уоршелла.

Основные новые научные результаты работы.

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

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

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

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

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

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

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

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

1. При разработке автоматизированной системы диспетчерского ¿■правления городскими перевозками почты с учетом основной эксплуатационной деятельности транспорта (перевозки почты) формализованы две задачи:

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

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

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

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

3. Разработанный алгоритм метода генерирования столбцов

в зависимости от их порядковых номеров, работающий как составная часть модифицированного симплекс-метода, позволяет экономить оперативную память ЭВМ на 25 % по сравнению с существующими методами генерирования столбцов и в среднем в 3 рада с$кра-тить время сч^та.

4. Скорость сходимости приближенного метода во много раз превышает скорость сходимости метода полного перебора и метода динамического программирования. Оптимальные планы были получены в среднем в 75 % всех случаев. Б остальных случаях отклонения от оптимума составили не более 5-7 %.

Практическая ценность работы.

Работа выполнялась в соответствии с хоздоговором между МТУСИ и НТВФ "Технопочта" Минсвязи РФ.

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

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

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

Реализация результатов работы.

Разработанная автоматизированная система диспетчерского управления городскими перевозками почты реализована при разработке планов перевозки почты в г. Набережные Челны.

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

в учебном процессе М17СИ по кафедре робототехники, механики и материалов.

Апробация раб о. ты. Результаты диссертационной работы докладывались и обсуждались на научных конференциях профессорско-преподавательского состава, сотрудников и аспирантов лТУСИ (1991,1992,1993гг.), на международном форуме информатики на секции "Оптимизация сложных динамических систем в экономике и технике" (Москва, 1992).

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

Структура и объем работы. Диссертация состоит из введения, четырех глав основного текста, заключения и 2 приложений. Работа содержит ш страниц печатного текста, 17 рисунков, 11 таблиц. Список литературы включает 106 наименований.

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

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

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

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

Каждой дуге полносвязной сети можно поставить в соответствие число су , определяемое выражением

100-1+4,

не

где I - номер узла, являющегося началом дуги; ^ - номер узла, являющегося концом дуги. Число у соответствующей дуги вычисляется по мере необходимости в ходе решения задачи, исходя из порядкового номера К дуги по формулам:

1 = (к-1) / (тч)*'; (2)

^ = к-(с-0-(тч)

где т - число узлов в сети. Б случае, если , то ¿-¿'Ю-

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

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

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

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

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

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

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

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

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

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

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

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

(3)

при ограничениях:

че

¿¿Е

«-< ^ * (Б) ¿¿Г 4 =

<б>

€-< ид.

е.

±1«, 2-(»Г "«.«'И»'«' «>

Ы 1*1

и

¿кг = ^ *** <1 ^ . _

(8)

с.т.

' ' (9)

II = п/>¥ *

Сч^ к^л, ^¿¿еК. (1С)

где ^п - количество почтовых отправлений, подлежащее перевозке из УС в ¿-е ОС; - количество почтовых отправлений , подлежащее перевозке из I -го ОС в УС; ¿1 - общее количество почтовых отправлений, которое необходимо вывезти из УС; ¿1 - общее количество почтовых отправлений, которое необходимо ввезти в УС; £ - количество типов автомашин, используемых для перевозки почты по городской сети почтовой связи; - вместимость £ -го автомобиля; - множество узлов,в

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

Хцк - число рейсов агтомобиля С -го типа по дуге су , соединяющей узел с с узлом ^ .Индекс « может принимать два значения: 1 - в случае положительного потока почтовых отправлений,« 2 - в случае отрицательного потока.

Условие (4) предотвращает скопление автомашин в узлах сети. Условие (5) отражает перераспределение потоков автомашин между множествами узлов V", и . Условия (4) и (5) образуют совокупность связующих ограничений. Ограничения (6) - (9) реализуют условия перевозки всех почтовых отправлений и образуют систему блочных ограничений. Таким образом, математическая модель задачи сводится к виду: минимизировать

при ограничениях:

+ Аг^г. >

Эф * К

у; 9.0, £

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

Как показал анализ процесса перевозки в различных городах России, в большинстве случаев дая перевозки почты автотранспортом по городской сети почтовой связи используются однотипные автомашины ГАЗ с грузоподъемностью Зт и вместимостью 14,5 м , зтот позволил свести четырехиндексную задачу

оптимизации к трехиндексной. Б этом случае правые части уравнений и неравенств (5) - (S) выражают необходимое количество автомашин для перевозки почты из УС во все ОС и обратно и являются целыми числами. Учитывая, что все коэффициенты при неизвестных задачи равны 0, +1, -1, то решение задачи определения оптимального плана перевозки почта будет целочисленным.

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

К я П I

Z = H t I CuX.ÍÁ (и)

г--< сj=o ° 4

при ограничениях:

к n g __

X¿J (12)

e-i а »

* n е _

X¿j =i, ¿ = /,rt; €=< ¿»ч <1

(13)

к я f i-i

(14)

к n e

X X x¡o - *; 4

¿i. 4 >A> vve*' t:"7<

l'1 j-4

(15)

где - кратчайшее расстояние из узла с в узел ^ ;

И - число ^2лов в сети; К - число автомашин, участвующих в перевозках; р - число переездов'в маршруте; Х^ = 1, если дуга входит в маршрут; х^' = С, если дуга ¿у не входит в маршрут; и,- и и^' - вспомогательные переменные, равные порядковому номеру предприятия связи е маршруте.

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

Если для развозки печати по опорным пунктам доставочного участка, по газетным киоскам и объезда почтовых ящиков досаа-точно одной автомашины, то уравнения (12) и (14), а также уравнения (13) и (15) можно представить как два уравнения, уравнение (16) потеряет свой смысл, и в этом случае задача определения оптимальных маршрутов развозки печати по опорным пунктам доставочного участка, по газетным киоскам и объезда почтоечх яликов одной автомашиной математически сводится к задаче коммивояжера. ■

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

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

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

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

Анализ математической модели задачи показал, что существуют определенные структурные закономерности ь матрице ограничивающих условий между порядковым номером столбца и положением его ненулевых элементов. С ¿-четом этого разработан алгоритм организации вычислительного процесса на этапах вычисления оценки Д и разложения вектора, включаемого в базис, по векторам базиса. Таким образом, отпала необходимость в хранении матрицы ограничивающих условий задачи в памяти ЭВМ в явном Еиде, что позволило повысить скорость счета, свести к минимуму затраты оперативной памяти ЗБМ и решить проблему большой размерности.

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

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

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

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

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

теп {♦ ^ (с{1 * С;н„)} у а

где «. - номер узла в маршруте; Су - расстояние от узла с до узла ^ . Минимальная из 2(1 - 2) сумм определяет дугу (I, I +1) для исключения из марщрута и три дуги вида (С, п), (1,1) , (1) ¿ц) для включения в маршрут.

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

Задача определения оптимальных планов перевозки почты по городской сети почтовой связи решалась на примере Челябинска и Магнитогорска, сети которых содержат 84 и 54 узла соответственно.

Математическая модель задачи для г. Магнитогорска содержала 159 строк и 6050 столбцов. Задача решалась на ЭВМ ЕС-1036. На получение оптимального плана потребовалось 417 итераций при времени счета 3 часа 40 минут.

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

условия местности, такие как река, железная дорога, лесополоса И..ДР- Ь соответствии с этим сеть почтовой связи г.Чеяябин-* ска была разбита на 5 подсетей.Решение было получено за 58,5 минут на ЭЕМ ЕС-1С36. Отклонение от оптимального решения составило 9 %. Затраты машинного времени на решение задачи на всей сети составили 7-8 часов.

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

Задача определения оптимальных маршрутов развозки печати по спорным пунктам доставочного участка, по газетным киоскам и объезда почтовых ящикое решалась на сетях, содержащих 11, 1£, 31 узел на ЭВМ ЕС-1036 за время от 30 секунд до 7 минут. Из полученных результатов решения видно, что метод ветвей и границ позволяет получить решение для любой сети поч-тоео" связи за время, не превышающее 1-2 часа.

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

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

С - матрица исходных данных; X - переменные задачи, при-ннлающие ьначения 1 иле 0 ; ¡9 - некоторая константа.

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

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

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

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

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

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

- задача определения оптимальных марщрутов объезда почто-еых ящиков.,

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

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

4. Разработан алгоритм модифицированного симплекс-метода

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

5. Получены оптимальные планы перевозки почтовых отправлений по сетям почтовой связи Челябинска и Магнитогорска.

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

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

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

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

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

Опубликованные работы по теме диссертации

1. Езжева Е.А., Басаргин А.Е., Рулев Б.А. Постановка и алгоритм решения задачи по определению оптимальных маршрутов перевозки почты. - М., 1991, - 16 с. Деп. в ДЕГГИ "И»1ормсвязь", № 1872-св. от 24.1C.S1.

2. Рулев Б.А., Езжева Е.А. Алгоритм получения целочисленного решения в задаче нахождения оптимальных маршрутов перевозки почты. - М., 1992, - 5 с. Деп. в ЩТИ "ИщормсЕязь",

J5 1S44-CB. от C5.11.S2.

3. Езжева S.A.О выборе оптимальных решений при организации внутригородских перевозок почты. - М., 1992, - 7 с. Деп. в ЦЙТИ "Ин^ормсвязь", № 1946-св. от 11.11.92.

4. Езжева Е.А. Вопросы оптимального планирования.перевозок почты. В кн.: Тезисы докладов 3 конгресса " Информационные коммуникации, сети, системы и технологии". - М., 1S92, - 162 с.

5. Езжева Е.А. О решении задачи оптимизации автомобильных .маршрутов перевозки почты. Б кн.: Тезисы докладов НТК МТУСИ.

- М., 1993, - 9 с.

6-7. Исследования по созданию системы диспетчерского управления городскими перевозками почты с применением вычислительной техники ьа примере г.г. Челябинска и Магнитогорска. Отчеты по КИР К 54С/90, Б? С29ССС47224, 0291СС44827. - М.: МГ/СИ, 1990 - 1992. - 32 е., Р6 с.