Презентация на тему "Тема дипломной работы –Оптимизация маршрутов перевозокв компании ООО «Массив»"

Содержание

• 
  Слайд 1
  

  Тема дипломной работы –Оптимизация маршрутов перевозокв компании ООО «Массив»

  Дипломник:. Руководитель: Курамшин Д.В. 1

• 
  Слайд 2
  

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

• 
  Слайд 3
  

  Цель дипломной работы– повышение эффективности деятельности компании ООО «Массив» на базе формирования оптимальных маршрутов перевозки мебели. Задачи: 3

• 
  Слайд 4
  

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

• 
  Слайд 5
  

  Математическая модель Известно:N - число пунктов,Dij, i, j=1..N - матрица расстояний, где Dij - расстояние из i-го пункта в j-й.Найти:Xij - матрицу переходов с компонентами:Xij = 1, если коммивояжер совершает переход из i-го пункта в j-й,Xij = 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. 5

• 
  Слайд 6
  

  Методы решения задачи коммивояжера Метод полного перебора Метод ветвей и границ Жадные алгоритмы Метод минимального остовного дерева Алгоритм «ближайшего соседа» Алгоритм «k-ближайших соседей» Алгоритм «муравьиной колонии» Генетические алгоритмы Алгоритм Прима Алгоритм Борувки 6

• 
  Слайд 7
  

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

• 
  Слайд 8
  

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

• 
  Слайд 9
  

  Программные средства для решения задачи коммивояжера Математические программные системы Специальные программы Программный комплекс «МАРШРУТ» (МГТУ им. Баумана) Программа нахождения оптимального маршрута перевозок (УГАТУ, каф. ВМК) 9

• 
  Слайд 10
  

  10

• 
  Слайд 11
  

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

• 
  Слайд 12
  

  Результат эксперимента №1 Протяженность оптимального маршрута 188,6 км. Уфа Войкова 1-Иглино Ленина 2а-Чишмы Революционная 19-Уфа Менделеева 21-Уфа Индустриальное шоссе 4а-Уфа Кольцевая 65/1-Уфа Войкова1 12

• 
  Слайд 13
  

  Результат эксперимента №2 Протяженность оптимального маршрута 711,6км. Уфа Войкова1-Янаул Ленина 18а-Янаул Победы 88а-Янаул Советская2-Янаул Советская6-Бирск 8 марта 1г-Бирск Мира 1г-Бирск Коммунистическая 172-Нефтекамск Карла Маркса 9-Нефтекамск Комсомольский проспект 28-Нефтекамск Победы4-Уфа Войкова 1 13

• 
  Слайд 14
  

  Результат эксперимента №3 Протяженность оптимального маршрута 627,6км. Уфа Войкова1-Ишимбай Жуковского 1а-Ишимбай Губкина 31-Ишимбай Левый берег 4-Стерлитамак Ивлева 12-Стерлитамак Коммунистическая 51-Стерлитамак Лазурная 13-Стерлитамак Глинки 11-Стерлитамак Гоголя 111-Стерлитамак Ленина 2б-Салават Октябрьская 56/9-Салават Уфимская 8б-Салават Ленина 20/18-Салават Салавата Юлаева 31-Кумертау Станционная 13/1-Уфа Войкова 1 14

• 
  Слайд 15
  

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

• 
  Слайд 16
  

  Влияние программы на затраты: 16

• 
  Слайд 17
  

  Для достижения поставленной цели в ходе выполнения дипломной работы были решены следующие задачи: проведен системный анализ компании ООО «Массив»; задача нахождения оптимального маршрута перевозки мебели поставлена как задача коммивояжера; осуществлен выбор метода и инструментального средства для решения задачи нахождения оптимального маршрута; проведены контрольные расчеты на реальных данных компании ООО «Массив», которые показали снижение транспортных расходов от 10% до 21%. Использование предложенного в работе программного средства позволит сократить время пробега машин, даст экономию материальных ресурсов, товар с цеха будет быстрее поступать на собственные торговые точки и к партнерам фирмы. Выводы 17