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

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

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

Таблица 8.10

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

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

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

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

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

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

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

Таблица 8.11

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

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

Таблица 8.12

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

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

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

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

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

Получаем:

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

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

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

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

Таблица 8.13

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 8.14

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

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

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

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

Таблица 8.15

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

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

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

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

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

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

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

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

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

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

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

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

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

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