Сети и системы почтовой связи (стр. 16 )

Для обеспечения возможности выбора направлений прохождения письменной корреспонденции через объекты почтовой связи необходимо чтобы упаковки письменной корреспонденции к нисходящим объектам более высокого уровня иерархии содержали в себе упаковки письменной корреспонденции к нисходящим объектам более низшего уровня иерархии; отмеченные упаковки письменной корреспонденции, в свою очередь, содержали в себе упаковки письменной корреспонденции к нисходящим объектам еще более низкого уровня иерархии, и так пока в последних упаковках не останется письменная корреспонденция к нисходящим объектам самого низкого уровня иерархии. Так, в четырехуровневой сети СПС-А, сформированные в ГО упаковки (например контейнеры) до каждого из нисходящих объектов должны заключать в себе упаковки до каждого из нисходящих (районных объектов) соответствующих областей (например, мешки), а последние – упаковки к каждому из нисходящих ОС соответствующих районов (например постпакеты).

Рис 22

Рис 22.1

Рис 22.2

 

1 … i … l 1 … j … n 1 … k … m а)

 

1 … i … l 1 … j … n 1 … k … m б)

 

1 … i … l 1 … j … n 1 … k … m в)

 

Накопители Накопители Накопители

общей определённых детальной

сортировки направлений сортировки

Рис 22.3

сортировки

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

19.2 Разработка планов сортировки почты

План сортировки ПО – это документ, регламентирующей распределение направлений сортировки ПО между накопителями сортировочной машины. Задача построения плана сортировки ставится так: сортировочная машина содержит n накопителей А1, А2,…, Аn. Почтовые отправления, которые поступают на сортировку, должны быть рассортированы по m направлениям N1, N2, …, Nm, информацию о которых содержат почтовые индексы. Заданы вероятности принадлежности почтовых отправлений каждому из направлений p1, p2,..., pm, причём p1 ³ p2 ³…³ pm, а p1 + p2 +…+ pm = 1.

Известно, что m > n, вследствие чего ПО должны сорти-роваться по этапам, то есть проходить через сортировочную машину несколько раз. ПО, адресованное по направлению Ni, сортируется si раз (s1 £ s2 £ …£ sm).

Необходимо минимизировать среднее количество сортировок одного почтового отправления

s = .

Возможны два основных метода организации сортировки: метод выделения направлений и метод группи-рования направлений. На рис. 22.3 приведены примеры сор-тировки по 100 направлениям при наличии 10 накопителей (а – методом выделения направлений, б – методом группирования направлений, в – комбинированным методом). Цифры в овалах – группы направлений, цифры в кругах – выделенные направления, цифры в прямоугольниках – этапы сортировки.

Согласно первому методу на каждом из этапов сортировки в каждый из n-1 накопителей направляются ПО очередных n - 1 направлений, остальные направляются в n-й (сборный) накопитель, из которого на следующем этапе сортировки опять выделяются n-1 направлений до тех пор, пока все ПО не будут отсортированы по своим направлениям (рис 22.3, а)

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

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

Литература: [2] р-5 , [3] р-4

Самостоятельно: Оптимизация сортировки письменной

корреспонденции в объектах иерархической

сети почтовой связи[13].

19.3 Организация маршрутной сортировки почты

Маршрутная сортировка широко применяется при сортировке почтовых отправлений по последовательности пунктов обмена почты, расположенных на пути прохождения почтового маршрута (магистральные, областные, районные маршруты, маршруты обмена почты с городскими отделениями связи, маршруты ГСП), а также на почтовые ящики получателей (маршруты почтальонов). Формально задача маршрутной сортировки ставится как задача переформирования неупорядоченной входной последовательности почтовых отправлений, адресованных по n направлениям i, j,…, k где (i, j,…, k = 0, 1,…, n - 1) в упорядоченную исходную последовательность 0, 1,…, n - 1, в которой количество ПО, адресованных по любым направлениям, является произвольным целым числом.

Указанная задача выступает также как частный случай известной математической задачи сортировки (преобразо-вания) некоторой исходной неупорядоченной последо-вательности чисел i, j, …, k (0 ≤ i, j, …, k ≤ n - 1)) в выходную упорядоченную последовательность 0 ≤ 1 ≤ … ≤ n - 1.

Например, последовательность ПО, адресованных по направлениям 03, 06, 05, 05, 10, 10, 00, 07, 08, 01, 05, 01, 03, 04, 15, 13, 00, 02, 02, 07, 07, 12, 03, 08 должна быть переформирована в последовательность 00, 00, 01, 01, 02, 02, 03, 03, 03, 04, 05, 05, 05, 06, 07, 07, 07, 08, 08, 10, 10, 12, 13, 15.

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