Методы оптимизации кольцевых развозочных маршрутов
Решение подобных задач рассмотрим на следующем примере развозки товаров. В соответствии с заказами потребителей городская овощная база обязуется 24.06.2012 г. обеспечить доставку овощей и фруктов согласно схеме представленной на рисунке 6.4. При этом известно, что удовлетворение потребностей соответствующих потребителей, которые отражены в таблице 6.8, будут осуществляться посредством автотранспорта грузоподъемностью 4 тонны. Требуется найти m замкнутых путей l1, l2, …, lk, …, lm из единственной общей точки К, чтобы выполнялось следующее условие:
Рисунок 6.4 – Схема взаимного размещения овощной базы и потребителей: К – овощная база; М1– М12 – потребители
Таблица 6.8 – Потребности заказчиков в овощах и фруктах
Подчеркнем, что существует несколько методов решения подобных задач: математического моделирования, графический и комбинированный. І. Рассмотрим алгоритм реализации метода математического моделирования. 1. Строится кратчайшая сеть, связующая товарную базу и все пункты назначения без замкнутых контуров, начиная с пункта, который отстоит на минимальном расстоянии от товарной базы (в нашем случае это пункт М5) (рисунок 6.5). Далее сеть строится таким образом, чтобы совокупный путь, соединяющий все пункты назначения и товарную базу (овощную базу К), был минимальный.
Рисунок 6.5 – Кратчайшая сеть, связующая овощную базу и пункты назначения
2. Затем по каждой ветви сети, начиная с пункта, наиболее удаленного от товарной базы К (считая по кратчайшей связующей сети – это пункт М10), группируются пункты на маршруты с учетом количества ввозимого груза и грузоподъемности (вместимости) развозочного автотранспорта. При этом сумма грузов по группируемым пунктам маршрута должна быть равной или немного меньше грузоподъемности автомобиля, а общее число автомобилей – минимально необходимым (таблица 6.9).
Таблица 6.9 – Предварительные маршруты объезда пунктов назначения
3. Определяется рациональный порядок объезда пунктов каждого маршрута (на примере маршрута № 2). Для этого строится таблица-матрица, в которой по диагонали размещаются пункты, включаемые в маршрут, и начальный пункт К, а в соответствующих клетках – кратчайшее расстояние между ними согласно рисунку 6.4 (таблица 6.10). Таблица 6.10 – Таблица-матрица маршрута № 2
Начальный маршрут строим для трех пунктов матрицы, имеющих наибольшие размеры сумм, показанных в строке (37; 35; 33), то есть пункты К, М11, М4. Для включения последующих пунктов выбираем из оставшихся пункт, имеющий наибольшую сумму – это пункт М6 (сумма 29), и определяем, между какими пунктами его следует включить – К и М11, М11 и М4, М4 и К. Чтобы это решить, для каждой пары пунктов необходимо найти размер приращения маршрута по следующей формуле:
где С – расстояние, км; i – индекс включаемого пункта; k – индекс первого пункта из пары; p – индекс второго пункта из пары.
При включении пункта М6 между первой парой пунктов К и М11 определяем размер приращения ∆ КМ11 при условии, что i – М6, k – К, p – М11. Получаем:
Таким же образом определяем приращения ∆ М11М4 = 0; ∆ М4К = 2. Так как ∆ М11М4 = min, следовательно, пункт М6 должен располагаться между пунктами М11 и М4 (К–М11–М6–М4–К). Используя этот метод, определяем, между какими пунктами должны располагаться пункт М9. После проведенных расчетов получаем следующий порядок объезда пунктов-потребителей предварительного маршрута № 2: К–М9–М11–М6–М4–К. Важно подчеркнуть, что движение по полученному кольцевому маршруту можно осуществлять в двух направлениях: начиная обслуживание с пункта М9 или с пункта М4. Пути движения в обоих направлениях будут равны между собой (32 км), однако различными будут транспортные работы. Так, транспортная работа для направления движения с начальным пунктом М9 будет равна 59 т-км (7км·4т + +3км·3т + 10км·2т + 2км·1т), тогда как для направления движения с начальным пунктом М4 – соответственно 63 т-км (10·4 + 2·3 + 7·2 +3·1) (см. рисунок 6.4). Следовательно, более рациональным будет направление движения по маршруту с начальным пунктом М9, так как при этом будет проделана меньшая транспортная работа. Аналогичные расчеты проводятся для оставшихся маршрутов № 1, № 3, № 4 и № 5. 4. Составляется сводная маршрутная ведомость (таблица 6.11).
Таблица 6.11 – Сводная маршрутная ведомость
Анализ таблицы 8.13 показывает, что совокупный пробег пяти автомобилей на пяти маршрутах в соответствии с проведенными оптимизационными расчетами согласно методу математического моделирования составляет 139 км.
Анализ алгоритма и порядок оптимизации кольцевых развозочных маршрутов указывает на высокую трудоемкость расчетных работ, что не позволяет в должной мере использовать подобный подход на практике. Данный факт обуславливает необходимость применения представленного ниже алгоритма.
|
