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

Оставшиеся грузы необходимо распределить по складской сети в Санкт-Петербурге в соответствии с индивидуальным заданием. Потребности каждого склада представить в табл. 9 (общая потребность – 57 т, является одинаковой для всех вариантов).

Таблица 9

Информация по складской сети

 

Наименование

(индивидуальное задание)

Адрес

(индивидуальное задание)

Объем поставки, т

 

1

 

 

 

2

 

 

 

3

 

 

 

4

 

 

 

5

 

 

 

Итого:

57

 

Необходимо определить рациональные маятниковые маршруты доставки потребителям, если известно:

Грузоподъемность одного транспортного средства составляет 1,5 т.

Время работы на маршруте – 9 часов в день.

Время на погрузку, разгрузку и оформление документов – 1 час.

Средняя скорость движения – 25 км/час.

Адрес автотранспортного предприятия – ул. Хрустальная, 27.

Далее представлен пример расчета параметров маршрута. В табл. 10 представлены исходные данные для примера.

Таблица 10

Пример исходных данных

Пункт отправления

Пункт назначения

Объем перевозок, т

Объем перевозок за одну поездку, т

Количество поездок

Склад на железнодорожной станции

С1

6

1,5

4

С2

5

1,5

4

С3

12

1,5

8

С4

7

1,5

5

С5

3

1,5

2

Итого

33

 

23

Этап 1. Определите расстояния между объектами логистической сети. Результаты удобно свести в табл. 11.

Таблица 11

Пример матрицы расстояний до складов, км

 

Исходный пункт

Пункт назначения

Автоколонна (А)

Склад

(С)

С1

С2

С3

С4

С5

Автоколонна

-

8

18

14

8

17

23

Склад

8

-

12

3

12

16

18

 

Этап 2. Необходимо определить затраты времени на одну поездку (пример в табл.12).

Для расчета затрат времени необходимо использовать формулу

 

 ,

 

где tc-i-c – время работы на маршруте, мин; с – индекс склада; i – индекс потребителя; lc-i – расстояние между складом и потребителем, км; li-c – расстояние между потребителем и складом, км; tпр – время, необходимое на погрузку и разгрузку, мин; V – скорость транспортного средства, км/час.

Аналогично рассчитывается время работы на маршруте, при условии возвращения в автоколонну

 

 ,

 

где tc-i-a – время работы на маршруте, мин; с – индекс склада; i – индекс потребителя; a – индекс автоколонны; lc-i – расстояние между складом и потребителем, км.; li-a – расстояние между потребителем и автоколонной, км.; tпр – время, необходимое на погрузку и разгрузку, мин; V – скорость транспортного средства, км/час.

 

Пример расчета для маршрута: Склад железнодорожной станции (далее Склад) – Склад 1

 

Результат представить в табл. 12

Таблица 12

Пример расчета затрат времени на одну поездку

Маршрут

Затраты времени, мин

Склад – С1 – Склад

118

Склад – С1 – Автоколонна

132

Склад – С2 – Склад

74

Склад – С2 – Автоколонна

101

Склад – С3 – Склад

118

Склад – С3 – Автоколонна

108

Склад – С4 – Склад

137

Склад – С4 – Автоколонна

139

Склад – С5 – Склад

146

Склад – С5 – Автоколонна

158

 

В табл. 12 строка маршрута «Склад – С1 – Склад» – означает, что транспортное средство загружается товаром на складе железнодорожной станции, едет до Склада 1, разгружается, а после этого возвращается обратно для последующей загрузки.

Строка маршрута «Склад – С1 – Автоколонна» означает, что транспортное средство загружается товаром на складе предприятия, едет до Склада 1, разгружается, а после этого возвращается в Автоколонну и больше в этот день не возит товар.

Этап 3. Составляем исходную рабочую матрицу (табл. 13).

Таблица 13

Пример исходной матрицы

Пункт назначения

Расстояние до автоколонны, км

Расстояние до склада, км

Разность расстояния, км

Количество необходимых поездок

С1

18

12

6 (18-12)

4

С2

14

3

11

4

С3

8

12

-4

8

С4

17

16

1

5

С5

23

18

5

2

 

Наименьшую оценку (-4) имеет пункт назначения Склад 3, а наибольшую оценку (11) Склад 2. Это означает, что начальным пунктом маршрута будет Склад 2, и весь рабочий день транспортное средство будет отвозить грузы в этот склад и лишь последняя поездка будет на Склад 3, откуда автомобиль поедет в автоколонну. Это необходимо для минимизации порожнего пробега.

 

Маршрут номер 1 для одного автомобиля: Автоколонна – Склад – Склад 2 – Склад – Склад 3 – Автоколонна. Известно, что время работы на маршруте составляет 9 часов в день (540 мин). Если автомобиль обслужит Склад 3 и вернется оттуда в автоколонну, он затратит 108 мин (табл. 12). Следовательно, на обслуживание Склада 2 остается 432 мин (540-108).

Если время на поездку на Склад 2 и обратно составляют 74 мин, то в этот пункт автомобиль сможет сделать 5 поездок. Но по условиям задачи необходимо лишь 4.

Таким образом, маршрут этого транспортного средства на рабочий день включает 4 поездки на Склад 2 и одну на Склад 3 (результаты представлены в табл. 18).

 

Этап 4. Определяем новую исходную матрицу (табл.14).

Таблица 14

Исходная матрица

Пункт назначения

Расстояние до автоколонны, км

Расстояние до склада, км

Разность расстояния, км

Количество необходимых поездок

С1

18

12

6

4

С3

8

12

-4

7

С4

17

16

1

5

С5

23

18

5

2

 

Наибольшую оценку разности расстояния имеет Склад 1, а наименьшую Склад 3.

 

Маршрут номер 2 для одного автомобиля: Автоколонна – Склад – Склад 1 – Склад – Склад 3 – Автоколонна. Известно, что время работы на маршруте составляет 9 часов в день (540 мин). Если автомобиль обслужит Склад 3 и вернется оттуда в автоколонну, он затратит 108 мин. Следовательно, на обслуживание Склада 1 остается 432 мин (540-108).

Если время на поездку на Склад 1 и обратно составляют 118 мин, то в этот пункт автомобиль сможет сделать 4 поездки. Полученный маршрут представлен в табл. 18

Этап 5. Определяем новую исходную матрицу (табл. 15).

Таблица 15

Исходная матрица

Пункт назначения

Расстояние до автоколонны, км

Расстояние до склада, км

Разность расстояния, км

Количество необходимых поездок

С3

8

12

-4

6

С4

17

16

1

5

С5

23

18

5

2

 

Наибольшую оценку разности расстояния имеет Склад 5, а наименьшую Склад 3.

 

Маршрут номер 3 для одного автомобиля: Автоколонна – Склад – Склад 5 – Склад – Склад 3 – Автоколонна. Известно, что время работы на маршруте составляет 9 часов в день (540 мин). Если автомобиль обслужит Склад 3 и вернется оттуда в автоколонну, он затратит 108 мин. Следовательно, на обслуживание Склада 1 остается 432 мин.

 Если время на поездку на Склад 5 и обратно составляют 146 мин, то в этот пункт автомобиль сможет сделать 2 поездки. После двух поездок останется еще 140 минут. Это позволит совершить еще одну поездку в пункт 4.

Полученный маршрут представлен в табл. 18

 

Этап 6. Определяем новую исходную матрицу (табл. 16)

Наибольшую оценку разности расстояния имеет Склад 4, а наименьшую Склад 3.

                                                                  

 

                                                                   Таблица 16

Исходная матрица

Пункт назначения

Расстояние до автоколонны, км

Расстояние до склада, км

Разность расстояния, км

Количество необходимых поездок

С3

8

12

-4

5

С4

17

16

1

4

 

Маршрут номер 4 для одного автомобиля: Автоколонна – Склад – Склад 4 – Склад – Склад 3 – Автоколонна. Известно, что время работы на маршруте составляет 9 часов в день (540 мин). Если автомобиль обслужит Склад 3 и вернется оттуда в автоколонну, он затратит 108 мин. Следовательно, на обслуживание Склада 4 остается 432 мин. Это позволит автомобилю сделать 3 поездки.

Полученный маршрут представлен в табл. 18

 

Этап 7. Определяем новую исходную матрицу (табл. 17).

Таблица 17

Исходная матрица

Пункт назначения

Расстояние до автоколонны, км

Расстояние до склада, км

Разность расстояния, км

Количество необходимых поездок

С3

8

12

-4

4

С4

17

16

1

1

 

Наибольшую оценку разности расстояния имеет Склад 4, а наименьшую Склад 3.

 

Маршрут номер 5 для одного автомобиля: Автоколонна – Склад – Склад 4 – Склад – Склад 3 – Автоколонна.

Полученный маршрут представлен в табл. 18

 

 

 

Таблица 18

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

Маршрут

Показатели маршрута

Количество поездок

Объем перевозок, т

Количество автомобилей, шт.

Время работы, мин

1

Склад – Склад 2 - Склад

4

5,0

1

296

Склад – Склад 3 - Автоколонна

1

1,5

108

Итого

5

6,5

1

404

2

Склад – Склад 1 - Склад

4

6,0

1

472

Склад – Склад 3 - Автоколонна

1

1,5

108

Итого

5

7,5

1

580

3

Склад – Склад 5 - Склад

2

3,0

1

292

Склад – Склад 4 – Склад

1

1,5

137

Склад – Склад 3 - Автоколонна

1

1,5

108

Итого

4

6,0

1

537

4

Склад – Склад 4 – Склад

3

4,5

1

411

Склад – Склад 3 - Автоколонна

1

1,5

108

Итого

4

6,0

1

519

5

Склад – Склад 4 – Склад

1

1,0

1

137

Склад – Склад 3 – Склад

3

4,5

1

354

Склад – Склад 3 – Автоколонна

1

1,5

1

108

Итого

5

7,0

1

599

Итого

23

33

5

2639

 

 


 

РАСПРЕДЕЛЕНИЕ ПОТРЕБИТЕЛЕЙ ПО СКЛАДСКОЙ СЕТИ

В ходе работы над курсовым проектом грузы были распределены между складами (табл. 9). Далее необходимо прикрепить выбранные вами магазины к складам, для организации дальнейших поставок. Всего в течение месяца будет необходимо развести по магазинам следующий объем грузов (табл.19).

Таблица 19

Адреса магазинов в Санкт-Петербурге

 

 

Наименование

Адрес

Объем поставки, т

1

Данные о магазинах берутся из табл. 6

6

2

16

3

10

4

17

5

8

Прикрепление потребителей (магазинов) к складам осуществляется с применением методов линейного программирования.

 

Постановка задачи.

Имеется 5 поставщиков (склады логистической сети), располагающих определенным количеством продукции (табл. 9), и 5 потребителей (магазины), у которых есть потребность в данной продукции (табл. 19). Необходимо определить транспортные затраты на доставку груза от любого поставщика до любого потребителя и прикрепить потребителей так, чтобы суммарные транспортные расходы по доставке продукции поставщикам были минимальными.

 

Этап 1. Определяем транспортные затраты. Затраты на транспортировку зависят от расстояния от склада до потребителя. Стоимость перевозки одной тонны груза на один километр составляет 50 руб/т. Предположим, что расстояние от Склада 1 до Магазина 1 составляет 24 км, тогда стоимость доставки одной тонны груза составит 1200 руб.

Информацию о расстояниях необходимо определить самостоятельно, используя ресурс http://maps.google.ru/. Результаты расчета стоимости доставки груза представить в виде табл. 20.

 

Для построения экономико-математической модели введем обозначения: i – номер поставщика (i = 1,…,m), m – количество поставщиков (в курсовом – 5);  j - номер потребителя (j = 1,…,n), n – количество поставщиков (в курсовом – 5); Ai – ресурсы i-го поставщика, т.е. количество груза, которое поставщик может поставить потребителям (табл.9), т; Вj – потребность в продукции  j-го потребителя (табл. 19), т; Cij – транспортные расходы по доставке одной тонны груза от i-го поставщика j-му потребителю, руб./т.; Xij – количество продукции, поставляемой от i-го поставщика j-му потребителю, т. Эта величина неизвестна и подлежит определению.

Таблица 2

Транспортные расходы по доставке одной тонны груза от i-го поставщика j-му потребителю

           Потребитель

 

Поставщик

Магазин 1

Магазин 2

Магазин 3

Магазин 4

Магазин 5

Склад 1

1200

1300

1700

2500

2900

Склад 2

1500

1600

500

2000

2800

Склад 3

800

900

850

1200

2900

Склад 4

1900

1500

1300

1700

2900

Склад 5

700

1300

1800

2100

2200

 

Экономико-математическая модель должна содержать целевую функцию, системы ограничений и условия неотрицательности переменных. В рассматриваемой задаче необходимо свести к минимуму транспортные расходы

 

 

где Cij – транспортные расходы по доставке одной тонны груза от i-го поставщика j-му потребителю, руб./т.; Xij – количество продукции, поставляемой от i-го поставщика j-му потребителю, т.

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

 

 .

 

Второе заключается в том, что по оптимальному плану количество продукции каждому потребителю должно соответствовать его потребности

 

 .

 

Наконец, в модели указывается условие не отрицательности переменных

 

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

Этап 1. Составление исходного плана. Для составления исходного плана воспользуемся приемом, который называется «метод северо-западного угла». Согласно этому методу заполнение таблицы следует начинать с левого верхнего квадрата и с позиции этого квадрата сравнить ресурсы первого поставщика (15 т) и потребности первого потребителя (6 т), выбрать меньшее из них и записать в данный квадрат, которые теперь называется «загруженным» (табл. 22). Это означает, что потребности первого потребителя удовлетворены. Затем необходимо подвинуться вправо и сравнить оставшиеся у первого поставщика ресурсы (15 – 6 = 9) и потребность второго потребителя (16), записав меньшую цифру в ячейку первой строки второго столбца, передвинуться вниз, т.к. ресурсы первого поставщика закончились, а потребность второго потребителя еще не удовлетворена. Так, двигаясь шаг за шагом, получаем исходный план.

Таблица 21

Исходные данные

Потребители

М1

М2

М3

М4

М5

Ресурсы поставщиков Ai, т

Поставщик

     Vj

Ui

V1

V2

V3

V4

V5

C1

U1

X11

1200

X12

1300

X13

1700

X14

2500

X15

2900

15

 

 

 

 

 

C2

U2

X21

1500

X22

1600

X23

500

X24

2000

X25

2800

6

 

 

 

 

 

C3

U3

X31

800

X32

900

X33

850

X34

1200

X35

2900

9

 

 

 

 

 

C4

U4

X41

1900

X42

1500

X43

1300

X44

1700

X45

2900

18

 

 

 

 

 

C5

U5

X51

700

X52

1300

X53

1800

X54

2100

X55

2200

9

 

 

 

 

 

Потребность Bj, т

6

16

10

17

8

57

 

Таблица 22

Исходный план прикрепления потребителей к поставщикам

Потребители

М1

М2

М3

М4

М5

Ресурсы поставщиков Ai, т

Поставщик

     Vj

Ui

 

 

 

 

 

C1

 

6

1200

9

1300

 

1700

 

2500

 

2900

15

 

 

 

 

 

C2

 

 

1500

6

1600

 

500

 

2000

 

2800

6

 

 

 

 

 

C3

 

 

800

1

900

8

850

 

1200

 

2900

9

 

 

 

 

 

C4

 

 

1900

 

1500

2

1300

16

1700

 

2900

18

 

 

 

 

 

C5

 

 

700

 

1300

 

1800

1

2100

8

2200

9

 

 

 

 

 

Потребность Bj, т

6

16

10

17

8

57

 

Этап 2. Проверка исходного плана. Необходимо проверить исходный план на соответствие следующим условиям:

Число «загруженных» клеток в таблице должно быть на единицу меньше суммы чисел поставщиков и потребителей, в рассматриваемом примере 9 (5 + 5 – 1), т.е. условие соблюдено.

Не должно быть ни одного занятого квадрата, который оказался бы единственным в строке и столбце таблицы, т.е. условие соблюдено.

 

Этап 3. Проверка на оптимальность. Для осуществления проверки исходного плана на оптимальность необходимо рассчитать потенциалы Ui и Vj. Эти потенциалы определяются только для «загруженных» ячеек. Сумма индексов Ui и Vj должна быть равна транспортным издержкам соответствующих ячеек. В этом примере U1 + V1 = 1200; U1 + V2 = 1300; U2 + V2 = 1600; U3 + V2 = 900; U3 + V3 = 850; U4 + V3 = 1300; U4 + V4 = 1700; U5 + V4 = 2100; U5 + V5 = 2200.

 

Индексы определяем следующим образом:

1)       принимаем U1 = 0 (так всегда);

2)       из первого уравнения получаем V1 = 1200 – 0 = 1200;

3)       из второго уравнения получаем V2 = 1300 – 0 = 1300;

4)       точно также, решая все уравнения, определяем потенциалы для всех потребителей и поставщиков (табл. 23).

 

Далее для «незагруженных» ячеек рассчитывается  (в табл. 23 рассчитанные значения представлены курсивом).

Полученные значения , как правило, отличаются от значений Cij (транспортные расходы). Если во всех «незагруженных» ячейках соблюдается неравенство , то план считается оптимальным. В рассматриваемом примере есть ячейки, в которых это неравенство не соблюдается, а значит, план не является оптимальным.

 

 

 

Таблица 23

Исходный план прикрепления потребителей к поставщикам с рассчитанными значениями потенциалов

Потребители

М1

М2

М3

М4

М5

Ресурсы поставщиков Ai, т

Поставщик

     Vj

Ui

1200

1300

1250

1650

1750

C1

0

6

1200

9

1300

1250

1700

1650

2500

1750

2900

15

 

 

 

 

 

C2

300

1500

1500

6

1600

1550

500

1950

2000

2050

2800

6

 

 

 

 

 

C3

- 400

800

800

1

900

8

850

1250

1200

1350

2900

9

 

 

 

 

 

C4

50

1250

1900

1350

1500

2

1300

16

1700

1700

2900

18

 

 

 

 

 

C5

450

1650

700

1750

1300

1700

1800

1

2100

8

2200

9

 

 

 

 

 

Потребность Bj, т

6

16

10

17

8

57

 

 

Этап 4. Улучшение исходного плана. Это происходит путем перемещения поставки в «незагруженную» ячейку, в которой  В нашем примере это квадрат С2-М3 (1550 – 500 = 1050). В случае если разность окажется одинаковой для нескольких ячеек, следует выбрать любую ячейку произвольно.

Итак, в рассматриваемом примере поставка должна быть перемещена в квадрат С2-М3. Перемещения производятся в определенном порядке с тем, чтобы не были нарушены условия, выраженные в приведенных выше уравнениях. Для этого образуем связку, т.е. замкнутую ломаную линию, состоящую из вертикальных и горизонтальных отрезков, таким образом, чтобы одной из вершин образованного многоугольника был квадрат, куда производится перемещение, а остальные вершины находились в «загруженных ячейках». В табл. 2 представлен такой многоугольник.

После образования связи свободному квадрату и связанным с ним «загруженным» ячейкам присваиваются поочередно знаки « + » и « – », начиная со свободного квадрата.

 

Таблица 24

Перемещение поставки в квадрат С2-М3

 

 

Среди тех квадратов, которые отмечены знаком « – », выбираем наименьший объем поставки (6 т.). Именно этот объем подлежит перемещению из квадратов со знаком « – » в квадраты со знаком « + ».  В результате получен новый план (табл. 25).

Таблица 25

Скорректированный план прикрепления потребителей к поставщикам

Потребители

М1

М2

М3

М4

М5

Ресурсы поставщиков, Ai, т

Поставщик

     Vj

Ui

 

 

 

 

 

C1

 

6

1200

9

1300

 

1700

 

2500

 

2900

15

 

 

 

 

 

C2

 

 

1500

 

1600

6

500

 

2000

 

2800

6

 

 

 

 

 

C3

 

 

800

7

900

2

850

 

1200

 

2900

9

 

 

 

 

 

C4

 

 

1900

 

1500

2

1300

16

1700

 

2900

18

 

 

 

 

 

C5

 

 

700

 

1300

 

1800

1

2100

8

2200

9

 

 

 

 

 

Потребность Bj, т

6

16

10

17

8

57

Повторяем описанные выше шаги. Результат представлен в табл. 26

Таблица 26

План прикрепления потребителей к поставщикам с рассчитанными значениями потенциалов

Это решение также не является оптимальным, следовательно, необходимо его улучшить путем перенесения поставок в свободные ячейки (в ячейку С5-М1). Результат представлен в табл. 27

Таблица 27

Скорректированный исходный план прикрепления потребителей к поставщикам

Потребители

М1

М2

М3

М4

М5

Ресурсы поставщиков Ai, т

Поставщик

     Vj

Ui

 

 

 

 

 

C1

 

5

1200

10

1300

 

1700

 

2500

 

2900

15

 

 

 

 

 

C2

 

 

1500

 

1600

6

500

 

2000

 

2800

6

 

 

 

 

 

C3

 

 

800

6

900

3

850

 

1200

 

2900

9

 

 

 

 

 

C4

 

 

1900

 

1500

1

1300

17

1700

 

2900

18

 

 

 

 

 

C5

 

1

700

 

1300

 

1800

 

2100

8

2200

9

 

 

 

 

 

Потребность Bj, т

6

16

10

17

8

57

 

Проверим его на оптимальность (табл. 28).

Таблица 27

План прикрепления потребителей к поставщикам с рассчитанными значениями потенциалов

Потребители

М1

М2

М3

М4

М5

Ресурсы поставщиков Ai, т

Поставщик

     Vj

Ui

1200

1300

1250

1650

2750

C1

0

5

1200

10

1300

1250

1700

 1650

2500

2750

2900

15

 

 

 

 

 

C2

-750

450

1500

550

1600

6

500

 900

2000

2000

2800

6

 

 

 

 

 

C3

- 400

800

800

6

900

3

850

 1250

1200

2350

2900

9

 

 

 

 

 

C4

50

1250

1900

  1350

1500

1

1300

17

1700

2800

2900

18

 

 

 

 

 

C5

- 500

1

700

800

1300

750

1800

 1150

2100

8

2200

9

 

 

 

 

 

Потребность Bj, т

6

16

10

17

8

57

 

Полученное решение является оптимальным, так как для всех ячеек соблюдается неравенство .

загрузка...