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

Заказ №38652

Задача 14 Деловая игра «Разработка кольцевых маршрутов движения автотранспорта»

Вариант 1 Сущность метода. Разработка кольцевых маршрутов представляет собой комбинаторную задачу, для решения которой возможно применение различных математических и эвристических методов. В частности, данная задача может быть решена методом, известным как алгоритм Свира, или алгоритм дворника-стеклоочистителя. Суть алгоритма Свира заключается в том, что полярная ось, подобная щетке дворника-стеклоочистителя, начинает вращаться против (или по) часовой стрелки, «стирая» при этом с координатного поля изображенные на нем магазины – потребители материального потока. Как только сумма заказов «стертых» магазинов достигнет вместимости транспортного средства, фиксируется сектор, обслуживаемый одним кольцевым маршрутом, и намечается путь объезда потребителей. Построение следующего сектора начинается лишь после того, как в рассматриваемом секторе будет получен допустимый кольцевой маршрут. Формирование кольцевых маршрутов завершается при полном обороте луча. Требуется: на основании задания, используя алгоритм Свира: а) разработать маршруты и составить графики доставки заказанных товаров в магазины района; б) рассчитать размер расходов, связанных с доставкой товаров; в) выполнить анализ разработанной схемы доставки. Исходные данные Номер магазина Размер заказа, коробок Номер магазина Размер заказа, коробок 1 9 16 45 2 39 17 33 3 25 18 41 4 22 19 38 5 25 20 25 6 26 21 13 7 29 22 35 42 8 25 23 14 9 17 24 37 10 41 25 21 11 31 26 17 12 35 27 24 13 25 28 25 14 37 29 29 15 27 30 45 Решение Для решения задачи используется координатная сетка (см. рис. 1). На ней точками обозначены магазины – потребители материального потока. В правой, нижней от магазина клетке – его номер. В середине района находится распределительный склад – точка 0. Установим исходящий из точки 0 воображаемый луч в горизонтальное положение (луч пересечет магазин 29) и начнем вращать его по часовой стрелке, формируя загрузку автомобиля товарами. Для магазина № 29 в автомобиль укладывают 29 коробок. Далее в поле луча попадает магазин № 30, для которого грузят 45 коробок. Продолжая движение луча, захватываем заказ магазина № 1 – 9 коробок. Далее захватываем заказ магазина № 3 – 25 коробок. Общее количество груза в машине Р = 108 коробок показывает, что формирование маршрута завершено, так как грузовместимость автомобиля не позволит выполнить следующий заказ.