Главная Методы, методики... Эвристические методы приближенного поиска оптимальной топологии маршрута (2007, 384с., MET0033-15)

Фрагмент из кейса

Уилф Шафер, агент по закупкам компании I.XL Industries Limited. Медсин Хэт, провинция Альберта (Канада), понял, что местный экономический спад значительно...
Московская компания закупила мясо на Украине с базисом поставки DAF российско-украинская граница. Отгрузка мяса осуществлялась в рефрижераторных вагонах....

Эвристические методы приближенного поиска оптимальной топологии маршрута (2007, 384с., MET0033-15)

Font Size Larger Font Smaller Font
Рейтинг пользователей: / 0
ХудшийЛучший 
Материал из категории  Методы, методики... (логистика, транспорт)
12.09.2016 08:33

Метки (тэги, tags):

Существует несколько эвристических методов приближенного поиска оптимальной топологии маршрута.

1. Метод ближайшего соседа (Nearest Neighbor). Пункты обхода плана последовательно включаются в маршрут, причем каждый следующий должен быть ближайшим к предыдущему.

2. Метод ближайшего города (Nearest Town). На каждом шаге алгоритма к текущему множеству пунктов, уже входящих в маршрут, добавляется новый, для которого найдется ближайший к любому из них, после чего полученный маршрут заново оптимизируется по выбранному критерию.

3. Метод самого дешевого включения (Most Cheap Inclusion). Алгоритм аналогичен предыдущему, только включение нового пункта производится по принципу минимального увеличения стоимости (длины) маршрута.

 

4. Метод минимального остовного дерева (Minimum Spanning Tree). Он представляет собой три последовательно выполняемых шага. На первом для множества пунктов плана строится кратчайшее остовное дерево (с помощью алгоритма Прима, заключающегося в построении каркаса наименьшего веса графа путем его наращивания за счет присоединения ребра с наименьшим весом, только один конец которого принадлежит фрагменту каркаса). На втором в построенном графе выделяется маршрут минимальной длины, который проходит через каждый пункт не менее 1 раза. На третьем из последовательности перемещения исключаются все пункты, повторно вошедшие в маршрут. Полученная топология является искомым приближением решения «задачи коммивояжера» и образует допустимый маршрут.

 

Эвристические методы перечислены в порядке повышения качества приближенного решения и, соответственно, увеличения вычислительной трудоемкости. Каждый из них обладает своими плюсами и минусами. Наилучшее решение для конкретных исходных данных может быть найдено в результате последовательного применения, а затем выбора того варианта, который отвечает вашим требованиям. В качестве критерия оптимальности могут быть выбраны пробег, время на маршруте, грузооборот, количество задействованного транспорта (либо их комбинация). В системах планирования подбор оптимального метода чаще всего происходит без участия оператора, который может регулировать данный процесс, лишь оценивая результаты планирования и изменяя критерии оптимальности. Программные продукты данного класса имеют разные интерфейсы, но принципы их функционирования приблизительно одинаковы. В отделе планирования должен быть как минимум один сотрудник, квалификация которого достаточна для работы с электронными справочниками и определения коэффициентов расчетной скорости движения автотранспорта в зависимости от погодных условий (на его рабочем месте можно повесить таблицу с утвержденным перечнем вариантов «погода/коэффициент»). В соответствии с заранее определенной периодичностью менеджер запускает процесс планирования и выводит на печать готовые маршрутные листы. Преимущества данного метода заключаются в сокращении времени планирования рейсов (на 1000 заявок в среднем затрачивается 10 минут) и формировании оптимального маршрута с использованием множества параметров, которые сложно учесть при расчете вручную. Благодаря использованию описываемого метода снижаются расходы на обслуживание автопарка (экономия пробега/расхода бензина в среднем достигает 22,5 %), сокращается штат планировщиков, повышается эффективность использования автотранспорта (сокращение парка в отдельных случаях достигает 15 %).

 

Источник: Беспалов Р. С. Транспортная логистика. Новейшие технологии построения эффективной системы доставки. — Москва : Вершина, 2007. – С. 285-286 (384 с.)


Метки (тэги, tags):



Последние похожие материалы:
Более поздние похожие материалы:

Обновлено 15.03.2017 09:12
 

Последние новости на сайте

Элеваторы для обработки зерновых культур находят широкое применение в фермерских хозяйствах, аграрных предприятиях. С их помощью...
Давайте розглянемо різні типи ламп та основні параметри, які важливо враховувати при їх...

Авторский сайт в сфере логистики Logistics-GR

Пример материалов из категории "Задачи по логистике"

Изучение метода определения срока (точки) замены транспортного средства, основанного на точном учете затрат на ремонт в...
Чэн Тау Ханг (Cheng Tau Hang) заметил, что спрос на продукт, поставляемый его компанией, постоянен и составляет 500 единиц в месяц....

Facebook-страница

Фрагмент из задачи

Определить площадь для складирования 500 т антрацита. Насыпной вес антрацита равен = 0,9 - 1,1 т/м3, а угол естественного откос = 45°. Принять =...
Удельные затраты потребителя на содержание запасов соответственно равны 0.4; 0.32; 0.28 денежных единиц. Годовое потребление...

 

Группа на Linkedin

(более 4000 участников)

Группы на Facebook

 

Узнать о проекте Logistics-GR

 youtube-канал  

 

Результаты тестов

Последние результаты
<-->Стоит ли Вам выбирать профессию менеджера по логистике? 64.00 %
<->(Лог-М) Тема 10. Складська логістика (10 тест.завдань) 40.00 %
<->(Log) Test 01. Warehouse and Logistics (10 tests) 90.00 %
Перейти к тестам
Проект работает
15 years, 0 months, 23 days.
Исходные данные к расчету: расстояния между грузовыми пунктами: = 15 км; = 9 км, = 19 км; = 17 км; = 10 км. Нулевые пробеги равны, т. е. = 5...
Небольшой магазин имеет 10 категорий продуктов; затраты и годовой спрос на них показаны в таблице. Проведите ABC-анализ этой...
Установить срок доставки угля между портами, если расстояние между ними равно = 470 миль. Скорость судна на этой линии = 350...
Определить целесообразность применения тягача или автомобиля, если грузоподъемность каждого из них — 5 т, техническая скорость...
Среди огромного разнообразия методов и моделей управления запасами на практике применяется достаточно ограниченное их количество, в основном те модели,...
К строительным грузам в настоящее время относят различные материалы, конструкции, детали, технологическое оборудование, а также грузы, которые возникают в...
Рассмотрим показатели оценки качества логистического обслуживания. Измерение уровня качества при анализе и синтезе систем логистического обслуживания...
Транспортні роботи, виконувані внутрішньозаводським транспортом, можна згрупувати за такими напрямами: - доставка палива, сировини, матеріалів,...
Deloitte & Touche Fantus разработала список факторов, которые отрасли высоких технологий учитывают при принятии решений о местах размещения своих...
International Business Systems — самый крупный международный продавец программного обеспечения, применяемого для управления цепями поставок. Ее акции...
Каждый книжный магазин имеет структуру (или, по крайней мере, должностное лицо), организующую логистический процесс закупок. В Торговом доме (ТД)...
Логистика как наука, позволяющая рационализировать, направлять и ускорять материальные и иные экономические потоки, находит все большее применение в...

Logistics-GR - теория и практика логистики и транспорта

Copyright © 2009 - 2024. При использовании материалов сайта - гиперссылка обязательна. All Rights Reserved. По всем вопросам обращаться - email