Оптимизация маршрутов перевозок в компании ООО Массив

Июль 23, 2022

Главная
Экономика
Оптимизация маршрутов перевозок в компании ООО Массив

Содержание

2. , ООО мебельная фабрика "М А С С И В" занимается производством и продажей мебели. Предприятие
3. Цель дипломной работы – повышение эффективности деятельности компании ООО «Массив» на базе формирования оптимальных маршрутов перевозки
4. Постановка задачи исследования Определить оптимальный маршрут движения транспортного средства, цель которого состоит в том, чтобы посетить
5. Математическая модель Известно: N - число пунктов, Di j, i, j=1..N - матрица расстояний, где Di
6. Методы решения задачи коммивояжера Метод полного перебора Метод ветвей и границ Жадные алгоритмы Метод минимального остовного
7. Алгоритм метода ветвей и границ Рассматривается задача в виде: Алгоритм ветвей и границ основан на следующих
8. 3.Пересчет оценок. Если G1 G2, то Поэтому, разбивая в процессе ветвления подмножество G’ G на непересекающиеся
9. Программные средства для решения задачи коммивояжера Математические программные системы Специальные программы Программный комплекс «МАРШРУТ» (МГТУ им.
11. Контрольные расчеты на реальных данных компании ООО «Массив» Исходные данные
12. Результат эксперимента №1 Протяженность оптимального маршрута 188,6 км. Уфа Войкова 1-Иглино Ленина 2а-Чишмы Революционная 19-Уфа Менделеева
13. Результат эксперимента №2 Протяженность оптимального маршрута 711,6 км. Уфа Войкова1-Янаул Ленина 18а-Янаул Победы 88а-Янаул Советская2-Янаул Советская6-Бирск
14. Результат эксперимента №3 Протяженность оптимального маршрута 627,6 км. Уфа Войкова1-Ишимбай Жуковского 1а-Ишимбай Губкина 31-Ишимбай Левый берег
15. Длины маршрутов до и после применения программы
16. Влияние программы на затраты:
18. Скачать презентацию

Слайд 2

,
ООО мебельная фабрика "М А С С И В" занимается производством и продажей

мебели. Предприятие является
серийным производителем в Республике
Башкортостан стульев и столов из массива
и шпона березы . Предлагает широкий
ассортимент продукции для комплектации
помещений различного назначения.
Компания OOО «Массив» имеет несколько собственных торговых точек, а так же продукцию компании можно приобрести у партнеров фирмы.

Слайд 3

Цель дипломной работы – повышение эффективности деятельности компании ООО «Массив» на

базе формирования оптимальных маршрутов перевозки мебели.

Задачи:

Слайд 4

Постановка задачи исследования Определить оптимальный маршрут движения транспортного средства, цель которого

состоит в том, чтобы посетить все заданные объекты за кратчайший срок (с наименьшими затратами). Данную задачу можно представить как задачу о коммивояжере

Постановка задачи
Имеется N городов, которые должен обойти коммивояжер с минимальными затратами. При этом на его маршрут накладывается два ограничения:
маршрут должен быть замкнутым, то есть коммивояжер должен вернуться в тот город, из которого он начал движение;
в каждом из городов коммивояжер должен побывать точно один раз, то есть надо обязательно обойти все города, при этом, не побывав ни в одном городе дважды.

Слайд 5

Математическая модель
Известно: N - число пунктов, Di j, i, j=1..N - матрица расстояний,

где Di j - расстояние из i-го пункта в j-й. Найти: Xi j - матрицу переходов с компонентами: Xi j = 1, если коммивояжер совершает переход из i-го пункта в j-й, Xi j = 0, если не совершает перехода,
где i, j = 1..N и i≠j. Функция цели - суммарная протяженность маршрута F, которую необходимо минимизировать, запишется в следующем виде: Ограничения: Условия прибытия в каждый пункт и выхода из каждого пункта только по одному разу выражаются следующими равенствами:
, j = 1..N , i = 1..N Для обеспечения непрерывности маршрута вводятся дополнительно N переменных Ui≥0 (i = 1..N ) и N2 дополнительных ограничений: Ui - Uj + N ⋅ Xi j ≤ N-1, i, j = 1..N, i ≠ j.

Слайд 6

Методы решения задачи коммивояжера
Метод полного перебора
Метод ветвей и границ
Жадные алгоритмы
Метод минимального

остовного дерева

Алгоритм «ближайшего
соседа»

Алгоритм «k-ближайших
соседей»

Алгоритм «муравьиной
колонии»

Генетические
алгоритмы

Алгоритм Прима

Алгоритм Борувки

Слайд 7

Алгоритм метода ветвей и границ
Рассматривается задача в виде:
Алгоритм ветвей и

границ основан на следующих построениях:
1. Вычисление оценки. Пусть G' G, тогда φ(G') называется нижней
оценкой, если для любого х є G' выполняется неравенство f(x) ≥ φ(G').
2.Ветвление (разбиение множества G на подмножества). Положим
и разобьем множество на r1
непересекающихся подмножеств

Для K-го множества разбиение будет
Данную процедуру разбиения можно представить в виде дерева

Слайд 8

3.Пересчет оценок. Если G1 G2, то
Поэтому, разбивая в

процессе ветвления подмножество G’ G на непересекающиеся подмножества
будем предполагать, что φ(G1’) ≥ φ (G’), причем хотя бы для некоторых номеров выполняется φ( ) ≥ φ (G’).
4.Вычисление планов (допустимых решений). Если на шаге ветвления
с номером k известен план , на шаге с номером (k + 1) — план и если
, то план забывается и вместо него сохраняется план
Наилучшее из полученных допустимых решений принято называть рекордом.
5.Признак оптимальности. Пусть G = . Тогда план является
оптимальным, т.е. , если выполняется условие
Если признак оптимальности выполнен, то решение закончено.

Слайд 9

Программные средства для решения задачи коммивояжера
Математические программные системы
Специальные программы
Программный комплекс
«МАРШРУТ»

(МГТУ им. Баумана)

Программа нахождения
оптимального маршрута
перевозок (УГАТУ, каф. ВМК)

Слайд 10

Слайд 11

Контрольные расчеты на реальных данных компании ООО «Массив»
Исходные данные

Слайд 12

Результат эксперимента №1
Протяженность оптимального маршрута 188,6 км.
Уфа Войкова 1-Иглино Ленина 2а-Чишмы

Революционная 19-Уфа Менделеева 21-Уфа Индустриальное шоссе 4а-Уфа Кольцевая 65/1-Уфа Войкова1

Слайд 13

Результат эксперимента №2
Протяженность оптимального маршрута 711,6 км.
Уфа Войкова1-Янаул Ленина 18а-Янаул Победы

88а-Янаул Советская2-Янаул Советская6-Бирск 8 марта 1г-Бирск Мира 1г-Бирск Коммунистическая 172-Нефтекамск Карла Маркса 9-Нефтекамск Комсомольский проспект 28-Нефтекамск Победы4-Уфа Войкова 1

Слайд 14

Результат эксперимента №3
Протяженность оптимального маршрута 627,6 км.
Уфа Войкова1-Ишимбай Жуковского 1а-Ишимбай Губкина

31-Ишимбай Левый берег 4-Стерлитамак Ивлева 12-Стерлитамак Коммунистическая 51-Стерлитамак Лазурная 13-Стерлитамак Глинки 11-Стерлитамак Гоголя 111-Стерлитамак Ленина 2б-Салават Октябрьская 56/9-Салават Уфимская 8б-Салават Ленина 20/18-Салават Салавата Юлаева 31-Кумертау Станционная 13/1-Уфа Войкова 1

Слайд 15

Длины маршрутов до и после применения программы

Слайд 16

Оптимизация маршрутов перевозок в компании ООО Массив

Содержание

,ООО мебельная фабрика "М А С С И В" занимается производством и продажей

Цель дипломной работы – повышение эффективности деятельности компании ООО «Массив» на

Постановка задачи исследования Определить оптимальный маршрут движения транспортного средства, цель которого

Математическая модельИзвестно: N - число пунктов, Di j, i, j=1..N - матрица расстояний,

Методы решения задачи коммивояжераМетод полного перебораМетод ветвей и границЖадные алгоритмыМетод минимального

Алгоритм метода ветвей и границРассматривается задача в виде: Алгоритм ветвей и

3.Пересчет оценок. Если G1 G2, то Поэтому, разбивая в

Программные средства для решения задачи коммивояжераМатематические программные системыСпециальные программыПрограммный комплекс «МАРШРУТ»

Контрольные расчеты на реальных данных компании ООО «Массив»Исходные данные

Результат эксперимента №1Протяженность оптимального маршрута 188,6 км.Уфа Войкова 1-Иглино Ленина 2а-Чишмы

Результат эксперимента №2Протяженность оптимального маршрута 711,6 км.Уфа Войкова1-Янаул Ленина 18а-Янаул Победы

Результат эксперимента №3Протяженность оптимального маршрута 627,6 км.Уфа Войкова1-Ишимбай Жуковского 1а-Ишимбай Губкина