Задача №801 (формирование маршрута перевозок с помощью алгоритма Свира)

Вы – специалист отдела логистики сети розничных магазинов в г. Барнауле. Вы занимаетесь составлением списка маршрутов доставки груза со склада в магазины сети. Магазины на карте показаны номерами от 1 до 100.

Груз доставляется машинами с грузоподъемностью 15 тонн по тарифу 35 рублей за километр.

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

К задаче прилагается таблица, в которой указано, сколько товаров ежедневно нужно завозить в каждый магазин, карта (масштаб карты – в 1 сантиметре 2 километра).

Решение:

Применяем алгоритм Свира.

Находим на карте склад и произвольно чертим от местоположения склада линию. Начинаем двигать эту линию против часовой стрелки. Первым на пути это линии находится магазин №76. В этот магазин необходимо доставить 2,3 т груза, что меньше грузоподъемности грузовика (15 тонн). Продолжаем движение нашей линии. Следующий магазин, который оказывается на пути ее движения, это магазин №83, в который необходимо доставит 0,9 т груза. В сумме груз, который необходимо доставить в указанные два магазина (2,3+0,9=3,2 т), меньше грузоподъемности грузовика. Продолжаем движение линии далее против часовой стрелки. Следующий магазин – №77, в него необходимо доставить 2,2 т груза. На данный момент общий вес груза составляет 5,4 т (3,2+2,2). Продолжаем движение линии. Следующий магазин - №81, вес груза = 0,5 т. Общий вес груза на данный момент равен 5,9 т (5,4+0,5). Продолжаем движение линии. Следующий магазин – №82 с грузом 2,3 т. Общий вес груза равен 8,2 т (5,9+2,3). Следующий магазин – №86 с грузом 1,1 т. Общий объем груза – 9,3 т (8,2+1,1). Следующий магазин – №84 с грузом 1,9 т. Общий объем груза – 11,2 т (9,3+1,9). Следующий магазин – №85 с грузом 2,8 т. Общий объем груза – 14 т (11,2+2,8). Смотрим, какой магазин будет следующим и достаточно ли оставшейся грузоподъемности грузовика, чтобы доставить груз в этот магазин. Следующий магазин – №79 с грузом 1,1 т. Следовательно, доставить этот груз грузовик не сможет. Таким образом, первым маршрутом будут охвачены следующие магазины: 76, 83, 77, 81, 82, 86, 84, 85. Строим на карте наш маршрут №1:

склад – №76 – №77 – №83 – №86 – №85 – №84 – №82 – №81 – склад.

Вес перевозимого груза: 2,3 + 0,9 + 2,2 + 0,5 + 2,3 + 1,1 + 1,9 + 2,8 = 14 т.

Расстояние в см: 5,1 + 1,8 + 2,5 + 2,4 + 1,9 + 0,9 + 1,0 + 0,3 + 8,4 = 24,3 см.

Переводим расстояние в км: 24,3 * 2 = 48,6 км.

Стоимость перевозки груза: 48,6 * 35 = 1701 руб.

Формируем 2-й маршрут. Первый магазин, который оказался на линии, это магазин №79, в который необходимо доставить груз весом 1,1 т. Далее до исчерпания грузоподъемности грузовика включаем в маршрут следующие магазины: №80 (1,7 т), №78 (2,7 т), №75 (3,0 т), №87 (1,3 т), №88 (1,5 т), №89 (0,5 т), №90 (2,0 т). Строим на карте маршрут №2:

Склад – №79 – №80 – №88 – №87 – №89 – №90 – №78 – №75 – склад.

Вес перевозимого груза: 1,1 + 1,7 + 2,7 + 3,0 + 1,3 + 1,5 + 0,5 + 2,0 = 13,8 т.

Расстояние в см: 7,0 + 1,4 + 3,0 + 1,7 + 2,0 + 0,8 + 1,9 + 1,1 + 5,4 = 24,3 см.

Переводим расстояние в км: 24,3 * 2 = 48,6 км.

Стоимость перевозки груза: 48,6 * 35 = 1701 руб.

Формируем 3-й маршрут. В порядке близости к линии, двигающейся против часовой стрелки, в маршрут попали следующие магазины: №91 (2,3 т), №93 (0,9 т), №92 (0,6 т), №94 (1,8 т), №96 (2,5 т), №99 (0,8 т), №95 (1,9 т), №100 (2,2 т). Строим на карте маршрут №3:

Склад – №91 – №93 – №99 – №100 – №96 – №95 – №94 – №92 – склад.

Вес перевозимого груза: 2,3 + 0,9 + 0,6 + 1,8 + 2,5 + 0,8 + 1,9 + 2,2 = 13,0 т.

Расстояние в см: 8,8 + 1,3 + 3,7 + 0,9 + 3,0 + 1,3 + 1,0 + 0,5 + 8,2 = 28,7 см.

Переводим расстояние в км: 28,7 * 2 = 57,4 км.

Стоимость перевозки груза: 57,4 * 35 = 2009 руб.

Формируем 4-й маршрут. В порядке близости к линии, двигающейся против часовой стрелки, в маршрут попали следующие магазины: №98 (2,9 т), №97 (1,3 т), №74 (1,1 т), №72 (1,3 т), №71 (0,8 т), №66 (1,4 т), №65 (1,3 т), №67 (2,3 т), №73 (1,5 т). Строим на карте маршрут №4:

Склад – №98 – №97 – №66 – №65 – №67 – №71 – №72 – №73 – №74 – склад.

Вес перевозимого груза: 2,9 + 1,3 + 1,1 + 1,3 + 0,8 + 1,4 + 1,3 + 2,3 + 1,5 = 13,9 т.

Расстояние в см: 10,3 + 1,6 + 1,6 + 0,9 + 1,7 + 2,3 + 2,6 + 1,3 + 0,6 + 1,9 =24,8 см.

Переводим расстояние в км: 24,8 * 2 = 49,6 км.

Стоимость перевозки груза: 49,6 * 35 = 1736 руб.

Формируем 5-й маршрут. В порядке близости к линии, двигающейся против часовой стрелки, в маршрут попали следующие магазины: №64 (2,2 т), №63 (2,1 т), №62 (2,3 т), №68 (1,6 т), №70 (0,5 т), №61 (2,4 т), №60 (2,2 т), №69 (0,8 т). Строим на карте маршрут №5:

Склад – №64 – №63 – №61 – №60 – №62 – №68 – №69 – №70 – склад.

Вес перевозимого груза: 2,2 + 2,1 + 2,3 + 1,6 + 0,5 + 2,4 + 2,2 + 0,8 = 14,1 т.

Расстояние в см: 10,5 + 1,2 + 2,0 + 1,2 + 3,0 + 3,5 + 1,6 + 0,7 + 4,4 =28,1 см.

Переводим расстояние в км: 28,1 * 2 = 56,2 км.

Стоимость перевозки груза: 56,2 * 35 = 1967 руб.

Формируем 6-й маршрут. В порядке близости к линии, двигающейся против часовой стрелки, в маршрут попали следующие магазины: №59 (1,0 т), №50 (1,9 т), №58 (0,4 т), №51 (2,1 т), №57 (0,5 т), №52 (1,9 т), №49 (1,6 т), №53 (2,3 т), №47 (2,1 т). Строим на карте маршрут №6:

Склад – №59 – №58 – №57 – №53 – №47 – №49 – №50 – №51 – №52 – склад.

Вес перевозимого груза: 1,0 + 1,9 + 0,4 + 2,1 + 0,5 + 1,9 + 1,6 + 2,3 + 2,1 = 13,8 т.

Расстояние в см: 10,1 + 1,2 + 1,0 + 3,2 + 1,4 + 1,8 + 1,8 + 0,3 + 0,7 + 4,3 = 25,8 см.

Переводим расстояние в км: 25,8 * 2 = 51,6 км.

Стоимость перевозки груза: 51,6 * 35 = 1806 руб.

Формируем 7-й маршрут. В порядке близости к линии, двигающейся против часовой стрелки, в маршрут попали следующие магазины: №54 (1,5 т), №56 (2,5 т), №55 (1,7 т), №45 (0,7 т), №43 (1,7 т), №7 (1,2 т), №44 (1,0 т), №12 (2,2 т), №48 (1,5 т). Строим на карте маршрут №7:

Склад – №54 – №56 – №7 – №12 – №55 – №48 – №45 – №44 – №43 – склад.

Вес перевозимого груза: 1,5 + 2,5 + 1,7 + 0,7 + 1,7 + 1,2 + 1,0 + 2,2 + 1,5 = 14,0 т.

Расстояние в см: 10,1 + 1,7 + 2,7 + 2,4 + 0,6 + 2,2 + 2,0 + 0,5 + 1,0 + 5,9 = 29,1 см.

Переводим расстояние в км: 29,1 * 2 = 58,2 км.

Стоимость перевозки груза: 58,2 * 35 = 2037 руб.

Формируем 8-й маршрут. В порядке близости к линии, двигающейся против часовой стрелки, в маршрут попали следующие магазины: №9 (2,4 т), №13 (1,3 т), №46 (1,3 т), №6 (0,7 т), №11 (1,0 т), №2 (1,5 т), №5 (0,4 т), №1 (3,0 т), №10 (2,1 т). Строим на карте маршрут №8:

Склад – №46 – №13 – №9 – №6 – №6 – №2 – №1 – №5 – №11 – №10 – склад.

Вес перевозимого груза: 2,4 + 1,3 + 1,3 + 0,7 + 1,0 + 1,5 + 0,4 + 3,0 + 2,1 = 13,7 т.

Расстояние в см: 7,9 + 2,8 + 1,9 + 0,8 + 1,5 + 0,3 + 1,7 + 1,6 + 0,6 + 11,8 = 30,9 см.

Переводим расстояние в км: 30,9 * 2 = 61,8 км.

Стоимость перевозки груза: 61,8 * 35 = 2163 руб.

Формируем 9-й маршрут. В порядке близости к линии, двигающейся против часовой стрелки, в маршрут попали следующие магазины: №3 (1,8 т), №4 (2,1 т), №41 (1,4 т), №42 (2,5 т), №16 (0,6 т), №14 (1,7 т), №8 (1,7 т), №15 (0,9 т), №17 (1,3 т), №20 (0,8 т). Строим на карте маршрут №9:

Склад – №41 – №42 – №16 – №14 – №4 – №3 – №8 – №15 – №17 – №20 – склад.

Вес перевозимого груза: 1,8 + 2,1 + 1,4 + 2,5 + 0,6 + 1,7 + 1,7 + 0,9 + 1,3 + 0,8 = 14,8 т.

Расстояние в см: 5,0 + 1,4 + 4,4 + 1,4 + 2,0 + 0,8 + 1,6 + 1,4 + 2,0 + 1,7 + 9,2 = 30,9 см.

Переводим расстояние в км: 30,9 * 2 = 61,8 км.

Стоимость перевозки груза: 61,8 * 35 = 2163 руб.

Формируем 10-й маршрут. В порядке близости к линии, двигающейся против часовой стрелки, в маршрут попали следующие магазины: №19 (2,0 т), №21 (2,4 т), №18 (2,6 т), №40 (1,1 т), №22 (1,4 т), №23 (1,7 т), №24 (1,2 т), №36 (1,6 т). Строим на карте маршрут №10:

Склад – №19 – №18 – №22 – №23 – №24 – №21 – №40 – №36 – склад.

Вес перевозимого груза: 2,0 + 2,4 + 2,6 + 1,1 + 1,4 + 1,7 + 1,2 + 1,6 = 15,0 т.

Расстояние в см: 10,2 + 2,3 + 2,9 + 0,3 + 0,7 + 1,0 +0,7 + 3,4 + 4,1 = 26,5 см.

Переводим расстояние в км: 26,5 * 2 = 53,0 км.

Стоимость перевозки груза: 53,0 * 35 = 1855 руб.

Формируем 11-й маршрут. В порядке близости к линии, двигающейся против часовой стрелки, в маршрут попали следующие магазины: №38 (1,4 т), №39 (1,2 т), №25 (0,5 т), №26 (0,7 т), №37 (2,3 т), №27 (1,4 т), №28 (2,1 т), №35 (1,3 т), №29 (1,8 т), №30 (1,3 т). Строим на карте маршрут №11:

Склад – №38 – №39 – №26 – №25 – №28 – №30 – №29 – №27 – №37 – №35 – склад.

Вес перевозимого груза: 1,4 + 1,2 + 0,5 + 0,7 + 2,3 + 1,4 + 2,1 + 1,3 + 1,8 + 1,3 = 14,0 т.

Расстояние в см: 5,2 + 0,9 + 2,9 + 1,0 + 1,8 + 2,1 + 0,8 + 1,5 + 4,3 + 1,3 + 4,0 = 25,8 см.

Переводим расстояние в км: 25,8 * 2 = 51,6 км.

Стоимость перевозки груза: 51,6 * 35 = 1806 руб.

Маршрут №12 формируем из оставшихся магазинов: №31 (2,9 т), №33 (2,3 т), №32 (0,5 т), №34 (0,9 т). Строим на карте маршрут №12:

Склад – №33 – №31 – №32 – №34 – склад.

Вес перевозимого груза: 2,9 + 2,3 + 0,5 + 0,9 = 6,6 т.

Расстояние в см: 7,5 + 3,1 + 1,2 + 3,1 + 6,4 = 21,3 см.

Переводим расстояние в км: 21,3 * 2 = 42,6 км.

Стоимость перевозки груза: 42,6 * 35 = 1491 руб.

Общая стоимость перевозки груза составляет:

1701 + 1701 + 2009 + 1736 + 1967 + 1806 + 2037 + 2163 + 2163 + 1855 + 1806 + 1491 = 22435 руб.

Исходная схема размещения склада и магазинов