Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

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

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Оптимизация кольцевых развозочных маршрутов




 

Решение подобных задач рассмотрим на следующем примере развозки товаров. В соответствии с заказами потребителей городская овощная база обязуется обеспечить доставку овощей и фруктов согласно схеме, представленной на рис. 8.8. При этом известно, что удовлетворение потребностей соответствующих потребителей, которые отражены в табл. 8.10, будет осуществляться посредством автотранспорта грузоподъемностью 4 т. Требуется найти m замкнутых путей l 1, l 2,…, l k,…, l m из единственной общей точки К, чтобы выполнялось следующее условие:

 

Рис. 8.8. Схема взаимного размещения овощной базы и потребителей: К – овощная база; М-М12 – потребители

 


Таблица 8.10

Потребности заказчиков в овощах и фруктах

Пункт назначения Потребность, т Пункт назначения Потребность, т
М1 М2 М3 М4 М5 М6   М7 М8 М9 М10 М11 М12  

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

I. Рассмотрим алгоритм реализации метода математического моделирования.

1. Строится кратчайшая сеть, которая связывает товарную базу и все пункты назначения без замкнутых контуров, начиная с пункта, который находится на минимальном расстоянии от товарной базы (в нашем случае – пункт М5) (рис. 8.9). Далее сеть строится таким образом, чтобы

 

Рис. 8.9. Кратчайшая сеть, связывающая овощную базу и пункты назначения

 

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

2. По каждой ветви сети, начиная с пункта, наиболее удаленного от товарной базы К (считая по кратчайшей связующей сети - это пункт М10), группируются пункты на маршруты с учетом количест­ва ввозимого груза и грузоподъемности (вместимости) развозочного автотранспорта. При этом сумма грузов по группируемым пунктам маршрута должна быть равной грузоподъемности автомобиля или немного меньше ее, а общее количество автомобилей - минимально необходимым (табл. 8.11).

Таблица 8.11

Предварительные маршруты объезда пунктов назначения

№ маршрута Пункт назначения Потребность в продукции, т
     
  М10  
М12  
  Итого: 4
  М11  
М9  
М6  
М4  
  Итого: 4
  М4  
М8  
  Итого: 4
  М7  
М3  
М2  
  Итого: 4
  М2  
М1  
М5  
  Итого: 4

Определяют рациональный порядок объезда пунктов каждого маршрута (на примере маршрута №). Для этого строится таблица-матрица, где по диагонали размещаются пункты, которые включаются в маршрут, и начальный пункт К, а в соответствующих клетках – кратчайшее расстояние между ними согласно рис. 8.8 (табл. 8.12).

Таблица 8.12

Таблица-матрица маршрута №2

Номер строки К        
Сумма   М11 М9 М6 М4

Начальный маршрут строим для трех пунктов матрицы, которые имеют наибольшие размеры сумм, показанных в строке (37; 35; 33), т.е. пункты К, М11, М4. Для включения последующих пунктов вы1­бираем из оставшихся пункт, имеющий наибольшую сумму, – это пункт М6 (сумма 29), определяем, между какими пунктами его следует включить, – К и М11, М11 и М4, М4 и К.

Чтобы это выяснить, для каждой пары пунктов необходимо найти размер приращения маршрута по формуле

где С – расстояние, км; i – индекс включаемого пункта; k – индекс первого пункта из пары; р – индекс второго пункта из пары.

При включении пункта М6 между первой парой пунктов К и М11 определяем размер приращения ΔКМ11 при условии, что i-М6, k-K, р-M11

Получаем:

Таким же образом определяем приращения ΔМ11М4=0; ΔМ4К=2. Так как ΔМ11М4= min, пункт М6 должен располагаться между пунктами М11 и М4 (К-М1164-К). Используя этот метод, определяем, между какими пунктами должен располагаться пункт М9. После проведенных расчетов получаем следующий порядок объезда пунктов-потребителей предварительного маршрута №2: К-М91164-К.

Важно подчеркнуть, что движение по полученному кольцевому маршруту можно осуществлять в двух направлениях: начиная об­служивание с пункта М9 или с пункта М4. Пути движения в обоих направлениях одинаковые (32км), однако различными будут транспортные работы. Так, транспортная работа для направления движения с начальным пунктом М9 будет равна 59т-км (7км∙4т+3км∙3т+10км∙2т+2км∙1т), тогда как для направления движе­ния с начальным пунктом М4- соответственно 63т-км (10∙4+2∙3+7∙2+3∙1) (см. рис. 8.8). Следовательно, более рациональным будет направление движения по маршруту с начальным пунктом М9, так как при этом проделана меньшая транспортная работа.

Аналогичные расчеты проводятся для оставшихся маршрутов №1, 3, 4, 5.

Составляется сводная маршрутная ведомость (табл. 8.13).


Таблица 8.13

Сводная маршрутная ведомость

№ мар­шрута Последовательность выполнения маршрута Расшифровка Протяженность пути движения на маршруте, км
              К→М10→М12→К     К→М9→М11→М6→М4→К     К→М4→М8→К     К→М2→М3→М7→К   К→М5→М2→М1→К К – овощная база М10 – магазин №10 М12 – магазин №12 К – овощная база М9 – магазин №9 М11 – магазин N11 М6 - магазин №6 М4 - магазин № 4 К – овощная база М4 – магазин №4 М8 – магазин № 8 К – овощная база М2 – магазин №2 М3 – магазин №3 М7 – магазин №7 К – овощная база М5 – магазин №5 М2 – магазин №2 M1 – магазин №1              

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

Алгоритм применения метода математического моделирования с использованием GPS-навигатора

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

Формируются предварительные маршруты. При этом во внимание принимается кратчайшая сеть, полученная с помощью СРS-навигатора. Для этого по каждой ветви сети, начиная с пункта, наиболее удаленного от товарной базы, группируются пункты на маршруты с учетом количества ввозимого груза и грузоподъемности (вместимости) развозочного автотранспорта. Сумма грузов по группируемым пунктам маршрута должна быть равна грузоподъемности автомобиля или немного меньше ее, а общее количество автомобилей – минимально необходимым.

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

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

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

1. На тетрадном листе «в клетку», где отмечены координатные оси, строится карта-схема реальной зоны обслуживания с нанесением

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

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

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

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

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

 

Рис. 8.10. Группировка потребителей на маршруты согласно эффекту дворника-стеклоочистителя:

К – овощная база; М112 – потребители

 

Таблица 8.14

Предварительные маршруты объезда пунктов назначения

№ маршрута Пункт назначения Потребность в продукции, т
     
Вращение луча по часовой стрелке
  М1  
М2
М5
  Итого: 4
  М12  
М11
М9
  Итого: 4

Окончание таблицы 8.14

     
  М10  
М6
М5
  Итого: 4
  М8  
М7
М4
  Итого: 4
  М4  
М3
  Итого: 4

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

Составляют сводную маршрутную ведомость (табл. 8.15).

Таблица 8.15

Сводная маршрутная ведомость

№ мар­шрута Последовательность выполнения маршрута Расшифровка Протяженность пути движения на маршруте, км
       
      К→М5→М2→М11→К   К→М12→М11→М9→К   К→М10→М6→М5→К   К – овощная база М5 – магазин №5 М2 – магазин №2 М11 – магазин №11 К – овощная база М12 – магазин №12 М11 – магазин N11 М9 - магазин №9 К – овощная база М10 – магазин №10 М6 – магазин № 6 М5 – магазин №5      

Окончание таблицы 8.15

       
  К→М4→М8→М7→К   К→М4→М3→К К – овощная база М4 – магазин №4 М8 – магазин №8 М7 – магазин №7 К – овощная база М4 – магазин №4 М3 – магазин №3  

Таким образом, совокупный пробег пяти автомобилей на пяти маршрутах в соответствии с проведенными оптимизационными расчетами, согласно комбинированному методу, составляет 135 км, что на 4 км, или 3 %, меньше по сравнению с методом математиче­ского моделирования.

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

GPS-навигатора

1. Формируются предварительные маршруты. При этом придер­живаются первого пункта алгоритма комбинированного метода.

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

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

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

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

2. Метод математического моделирования в большинстве случаев позволяет получать оптимальный результат, если количество пунктов назначения не превышает 10. При этом его необходимо применять, если грузоподъемность (вместимость) автомобиля позволяет удовлетворять потребности всех пунктов назначения (независимо от их количества) за один оборот.

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

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

 






Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных