Маршрутизация партионных перевозок.

Лекция 7

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

 

 

Орган государственной власти Учреждение органа в городе Адрес, телефон
Министерство охраны окружающей среды и природных ресурсов Российской Федерации Комитет экологии и природных ресурсов Санкт-Петербурга и Ленинградской области 191186, Санкт-Петербург, ул.Б.Конюшенная, 29 тел.3112155, факс (812) 3127977
Государственный комитет санитарно-эпидемиологического надзора Российской Федерации Центр госсанэпиднадзора в Санкт-Петербурге 191011, Санкт-Петербург, ул. Малая Садовая, 1 тел. 3199811
Госатомнадзор России Северо-Европейский округ Госатомнадзора РФ Санкт-Петербург, ул. Малая Монетная, 2 тел. 2786111
Комитет Российской Федерации по геологии и использованию недр Северо-Западный региональный геологический центр 199155, Санкт-Петербург, ул.Одоевского, 24, к.1
Федеральный горный и промышленный надзор России Северо-Западный округ Госгортехнадзора 191028, Санкт-Петербург, Моховая ул., 3 тел. 2735521
Министерство внутренних дел: Государственный пожарный надзор Противопожарная служба ГУВД Санкт-Петербурга и Ленинградской области наб.р.Мойки, 85 факс 3157330

 

 

Приложение 2

 

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

 

 

Ленкомприрода

Морская инспекция

Госгортехнадзор

Гострудинспекция

Министерство внутренних дел (пожарная охрана)

Госатомнадзор

Госсанэпиднадзор

 

 


[1] О мерах по реализации Основ законодательства РФ об охране здоровья граждан. Приказ по Минздраву Российской Федерации от 22 сентября 1993 г. № 222.- М., 1993.- 63 с. Ст.1. С. 1-2.

[2] Относится только к краям, областям, городам, автономным округам.

[3] Конституция Российской Федерации. - М.: «Юридическая литература», 1993. -С.9.

[4] Конвенции и рекомендации, принятые Международной конференцией труда 1919-1990 гг.-Женева: МБТ, 1991.- Т.1,2.

[5] Резюме международных трудовых норм МБТ.- Женева, 1988; Иванов С.А. Применение конвенции МОТ в России в переходный период. Некоторые проблемы // Государство и право, 1994.- № 8-9.

[6] Составлено совместно с О.Н.Макаровым.

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

Решение находится путем расчета последовательно по нескольким этапам.

1. Нахождение кратчайшей связывающей все пункты сети.

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

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

Рассмотрим пример.

Расстояния м\у пунктами указаны в таблице 1 .

Таблица 1-Матрица кратчайших расстояний

  А Б В Г Д Е Ж З И К Л М Н
А  
Б  
В  
Г  
Д  
Е  
Ж  
З  
И  
К  
Л  
М  
Н  

 

Необходимо завести грузы из пункта А в пункты Б,В,..,М. Объемы завоза составляют:

Таблица 2 – Объемы завоза груза в промежуточные пункты, т

Пункт отправления, А Б В Г Д Е Ж З И К Л М Н
  0,2 0,3 0,4 0,1 0,3 0,2 0,1 0,2 0,1 0,1 0,3 0,4

 

Для перевозок используется а\м УАЗ-451, грузоподъемностью 1 т. Характер гр позволяет полностью использовать грузоподъемность а\м.

Построение кратчайшей связывающей сети необходимо начать с первой точки (пункта отправления). Выпишем из таблицы 1 первую строку (строку А), при этом сверху обозначим столбцы, а снизу – строки.

Столбец Б В Г Д Е Ж З И К Л М Н
Ряд 1
Строка А А А А А А А А А А А А

 

Из чисел этого ряда найдем наименьшее (5), соответствующее ему звено А-З занесем в таблицу 4. Сравним соответствующие числа ряда 1 и строки З таблицы 1. Из каждой сопоставляемой пары выберем наименьшее, получим ряд 2.

Столбец Б В Г Д Е Ж И К Л М Н
Ряд 2
Строка А А А З А З З А А З З

 

Наименьшее число 6 соответствует звену А-Г, его занесем в таблицу 4. Сравним числа строки Г с числами ряда 2, получим ряд 3.

Столбец Б В Д Е Ж И К Л М Н
Ряд 3
Строка Г Г З Г З З Г Г Г З

 

Наименьшее число 2 соответствует звену Г-Б, его занесем в таблицу 4. Сравним числа строки Б с числами ряда 3, получим ряд 4.

Столбец В Д Е Ж И К Л М Н
Ряд 4
Строка Г З Г З З Г Г Г З

Наименьшее число 2 соответствует звену Г-В, его занесем в таблицу 4. Сравним числа строки В с числами ряда 4, получим ряд 5.

Столбец Д Е Ж И К Л М Н
Ряд 5
Строка З Г З З Г Г Г З

Наименьшее число 3 соответствует звену Г-Е, его занесем в таблицу 4. Сравним числа строки Е с числами ряда 5, получим ряд 6.

Столбец Д Ж И К Л М Н
Ряд 6
Строка Е З З Е Г Г З

 

Наименьшее число 3 соответствует звену Е-К, его занесем в таблицу 4. Сравним числа строки К с числами ряда 6, получим ряд 7.

Столбец Д Ж И Л М Н
Ряд 7
Строка Е З З К Г З

 

Наименьшее число 5 соответствует звену З-Ж, его занесем в таблицу 4. Сравним числа строки Ж с числами ряда 7, получим ряд 8.

Столбец Д И Л М Н
Ряд 8
Строка Ж Ж К Ж Ж

 

Наименьшее число 5 соответствует звену Ж-И, его занесем в таблицу 4. Сравним числа строки И с числами ряда 8, получим ряд 9.

Столбец Д Л М Н
Ряд 9
Строка Ж К Ж Ж

 

Наименьшее число 6 соответствует звену Ж-Д, его занесем в таблицу 4. Сравним числа строки Д с числами ряда 9, получим ряд 10.

Столбец Л М Н
Ряд 10
Строка К Ж Ж

 

Наименьшее число 6 соответствует звену К-Л, его занесем в таблицу 4. Сравним числа строки Л с числами ряда 10, получим ряд 11.

Столбец М Н
Ряд 11
Строка Л Ж

 

Наименьшее число 6 соответствует звену Ж-Н, его занесем в таблицу 4. Последний 12 ряд:

Столбец М
Ряд 12
Строка Л

или

Столбец М
Ряд 12
Строка Н

 

Таблица 4 – Звенья кратчайшей связывающей сети

Порядковый номер звена Звено Длина звена, км Порядковый номер звена Звено Длина звена, км
А-З З-Ж
Д-Г Ж-И
Г-Б Ж-Д
Г-В К-Л
Г-Е Ж-Н
Е-К Л-М или Н-М

 

Кратчайшая связывающая сеть представлена на рис.1,2

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

М(0,3)
Н(0,4)
И(0,2)
Д(0,1)
Ж (0,2)
З(0,1)
Б (0,2)
Г(0,4)
В (0,3)
Е(0,3)
К (0,1)
Л (0,1)
А

 

 

Рисунок 1 – Кратчайшая связывающая сеть

М(0,3)
Н(0,4)
И(0,2)
Д(0,1)
Ж (0,2)
З(0,1)
Б (0,2)
Г(0,4)
В (0,3)
Е(0,3)
К (0,1)
Л (0,1)
А

 

 

Рисунок 2 – Кратчайшая связывающая сеть

 

 

Этап 2. Набор пунктов в маршруты.

По каждой ветви сети, начиная с той, кот имеет наибольшее количество звеньев, группируют пункты для включения в маршрут. В каждый мар-т группируют пункты с учетом кол-ва ввозимого груза и вместимости подвижного состава. При составлении мар-ов с помощью связывающей сети процесс нужно начинать от пункта, наиболее удаленного от грузопоставщика (М). В нашем примере грузоподъемность а\м позволяет объединять в маршруте пункты потребления суммарный завоз в кот не превышает 1,7 т.

При выборе мар-ов могут возникать различные варианты. Рассмотрим 2 из них в таб 5.

Таблица 4 – Развозочные маршруты движения автомобилей, составленные визуально

Маршрут движения Загрузка,т. Длина маршрутов, км
1. А-М-Л-К-Е-В-Б-А 1,3
2. А-Н-И-Ж-Д-З-Г-А 1,4
ИТОГО 2,7

Таблица 5 – Развозочные маршруты движения автомобилей, полученные по кратчайшей связывающей сети

Маршрут движения Загрузка, т. Длина маршрута, км
Вариант 1    
1. А – М –Н – И – Д – Ж – З – А 1,3
2. А – Л – К – Е – Г – В – Б – А 1,4
ИТОГО 2,7
Вариант 2    
1. А-М-Н-Ж-И-Д-З-А 1,3
2. А – Л – К – Е – Г – В – Б – А 1,4
ИТОГО 2,7

 

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

 

Этап 3. Определение очередности объезда пунктов маршрута.

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

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

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

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

Продолжим рассматривать пример.

Применим метод "суммирования по столбцам". Составим матрицу расстояний для первого маршрута и подсчитаем сумму расстояний по каждому столбцу (таблица 6).

Таблица 6 – Матрица расстояний и суммы столбцов для 1-го маршрута

  А М Н И Д Ж З
А -
М -
Н -
И -
Д -
Ж -
З -
Сумма

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

А-М-Д-А, его длина 47 км.

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

Dlkp= lki+lip-lkp,

где l- расстояние , км,

i- индекс включаемого пункта,

k,p- индексы первого и второго пунктов из пары.

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

А-И-М-Д-А, DlАМ =lАИ+lИМ-lАМ=15+14-19= 10км;

А-М-И-Д-А, DlМД =lМИ+lИД-lМД=14+11-12=13 км;

А-М-Д-И-А, DlДА =lДИ+lИА-lДА=11+15-16=10 км.

Таким образом, пункт И можно включить либо между А и М, либо между Д и А, т.к. приращение длины в этих случаях одинаковое. Включаем И в исходный маршрут между пунктами А и М. Следующим включаем пункт Н (сумма 60).

А-Н-И-М-Д-А , DlАИ =lАН+lНИ-lАН=16+8-15=9 км;

А-И-Н-М-Д-А, DlИМ =lИН+lНМ-lИМ=8+7-14=1 км;

А-И-М-Н-Д-А, DlМД =lМН+lНД-lМД=7+12-12=7 км;

А-И-М-Д-Н-А, DlДА =lДН+lНА-lДА=12+16-16=12 км.

Выгоден 2-ой вариант, его берем за основу и включаем пункт З (сумма 56).

А-З-И-Н-М-Д-А, DlАИ =lАЗ+lЗИ-lАИ=5+10-15=0 км;

А-И-З-Н-М-Д-А, DlИН =lИЗ+lЗН-lИН=10+11-8=13 км;

А-И-Н-З-М-Д-А, DlНМ =lНЗ+lЗМ-lНМ=11+14-7=18 км;

А-И-Н-М-З-Д-А, DlМД =lМЗ+lЗД-lМД=14+11-12=13 км;

А-И-Н-М-Д-З, DlДА =lДЗ+lЗА-lДА=11+5-16=0 км.

В данном случае пункт З можно включить либо между А и И, либо между Д и А, т.к. приращение длины маршрутов равно 0. Выбираем 5 вариант, его берем за основу и включаем пункт Ж (сумма 45).

А-Ж-И-Н-М-Д-З-А, DlАИ =lАЖ+lЖИ-lАИ=10-5-15=0 км;

А-И-Ж-Н-М-Д-З-А, DlИН =lИЖ+lЖН-lИН=5+6-5=6 км;

А-И-Н-Ж-М-Д-З-А, DlНМ =lНЖ+lЖМ-lНМ=6+9-7=8 км;

А-И-Н-М-Ж-Д-З-А, DlМД =lМЖ+lЖД-lМД=9+6-12=3 км;

А-И-Н-М-Д-Ж-З-А, DlДЗ =lДЖ+lЖЗ-lДЗ=6+5-11=0 км;

А-И-Н-М-Д-З-Ж-А, DlЗА =lЗЖ+lЖА-lЗА=5+10-5=10 км.

Одинаковое нулевое приращение имеют 1 и 5 варианты, их длина составляет:

1. 10+5+8+7+12+11+5=58 км ,

5. 15+8+7+12+6+5+5=58 км. Это на 3 км короче, чем исходный маршрут, поэтому можно использовать любой из них.

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

Таблица 7 – Матрица расстояний и суммы столбцов для второго маршрута

  А Л К Е Г В Б
А -
Л -
К -
Е -
Г -
В -
Б -
сумма

 

Исходный маршрут Л-А-К-Л, в него включаем пункт В, с суммой 40 км.

1. Л-В-А-К-Л, приращение длины 4 км;

2. Л-А-В-К-Л, приращение длины 4 км;

3. Л-А-К-В-Л, приращение длины 16 км.

Выбираем 1-ый вариант, в него включаем пункт Б (сумма 39).

1. Л-Б-В-А-К-Л, приращение длины 3 км;

2. Л-В-Б-А-К-Л, приращение длины 2 км;

3. Л-В-А-Б-К-Л, приращение длины 3 км;

4. Л-В-А-К-Б-Л, приращение длины 16 км.

Выбираем 2-ой вариант маршрута, в него включаем пункт Е (сумма 34).

1. Л-Е-В-Б-А-К-Л, приращение длины 0 км;

2. Л-В-Е-Б-А-К-Л, приращение длины 7 км;

3. Л-В-Б-Е-А-К-Л, приращение длины 7 км;

4. Л-В-Б-А-Е-К-Л, приращение длины 0 км;

5. Л-В-Б-А-К-Е-Л, приращение длины 6 км.

Выбираем 4-ый вариант маршрута, в него включаем пункт Г (сумма 31).

1. Л-Г-В-Б-А-Е-К-Л, приращение длины 0 км

2. Л-В-Г-Б-А-Е-К-Л, приращение длины 1 км;

3. Л-В-Б-Г-А-Е-К-Л, приращение длины 1 км;

4. Л-В-Б-А-Г-Е-К-Л, приращение длины 0 км;

5. Л-В-Б-А-Е-Г-К-Л, приращение длины 6 км;

6. Л-В-Б-А-Е-К-Г-Л, приращение длины 12 км.

В 1-ом и 4-ом варианте приращение пробега одинаково, поэтому можно выбрать любой из них. Т.к. выезд из пункта А, перепишем маршрут: А-Е-К-Л-Г-В-Б-А. Длина маршрута не изменилась, изменился лишь порядок объезда пунктов, поэтому оставляем первоначальный вариант.

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

Таблица 8 – Маршруты с уточненным порядком объезда пунктов.

Маршрут движения Загрузка, т. Длина маршрута, км
1. А-Ж-И-Н-М-Д-З-А или А-И-Н-М-Д-Ж-З-А 1,3  
2. А – Л – К – Е – Г – В – Б – А или А-Е-К-Л-Г-В-Б-А 1,4
ИТОГО 2,7

 

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