Введение, Модель и метод расчета - Определение кольцевых маршрутов наименьшей суммарной стоимости с двух баз методом фиктивных узлов и веток
Одним из ключевых вопросов логистики является выбор оптимальных кольцевых маршрутов передвижения материальных потоков, которые могут минимизировать стоимость доставки товара потребителям. Их определение при доставке товара с нескольких баз представляется довольно сложной задачей дискретной оптимизации, которая рассмотрена лишь для некоторых частных случаев. Обзор некоторых подходов к ее решению приведен, например, в [1]. Из них наибольший интерес представляет использование метода ветвей и границ (ВиГ), так как он является точным по сравнению со всеми другими. Он основан на глобальном поиске решения и, следовательно, обладает способностью избежать "ловушек" при применении методов локальной оптимизации. Его возможности постоянно расширяются [2]. Разработан усовершенствованный алгоритм ВиГ, позволяющий посещать пункты разгрузки товара несколько раз [3]. Следует заметить, что для неполного транспортного графа он может иметь вырождение решения [4].
Модель и метод расчета
Постановка задачи заключается в следующем. Базы Б1 и Б2 расположены в противоположных наиболее удаленных концах транспортной сети. Известна матрица стоимости переезда между вершинами транспортного графа. Грузоподъемность не ограничена. Требуется найти кольцевые маршрута движения с каждой базы минимальной суммарной стоимости.
Решение состоит из двух основных этапов. На первом этапе находим оптимальные кольцевые маршруты из условия, чтобы их суммарная стоимость была наибольшей. Для этого решаем задачу коммивояжера, используя метод фиктивных узлов и ветвей [3].
Алгоритм вычислений на первом этапе заключается в следующем.
1. В исходной матрице заменяем стоимость каждой ветви приведенной ее величиной
, (1)
Где:
- наибольшее значение стоимости в исходной таблице.
- 2. Вводим внешние фиктивные узлы в вершины, дублирующие базы. 3. Соединяем базы и фиктивные узлы со смежными вершинами ориентированными дугами. При этом их направление противоположное. 4. Соединяем базы и дублирующие фиктивные узлы четырьмя фиктивными ветвями: Ф1-Ф3 и Ф3-Ф2, Б2-Ф4 и Ф4-Б1, чтобы получился замкнутый круг. Их длина принимается не менее минимальной величины хорды в рассматриваемой базе. Принципиальная схема организации двух колец представлена на рис. 1.
Рис. 1. Схема ввода внешних фиктивных узлов
Кольцевой маршрут фиктивный узел
- 5. Составляем расчетную матрицу стоимости с учетом введенных внешних фиктивных узлов. 6. Выполняем операции приведения по строкам и столбцам с помощью наименьших их элементов. 7. Производим оценку элементов матрицы. 8. Удаляем из матрицы ветвь с наибольшей оценкой и блокируем движение в обратном направлении. Получаем новую матрицу меньшего размера. 9. Создаем фиктивные матрицы и, вводя в матрицу вычеркнутые строку и столбец. 10. Выполняем над матрицами, и операции, описанные в пунктах 6-9 до тех пор, пока последняя вычеркиваемая ветвь не станет очевидной.
Оптимальная схема маршрута устанавливается из сравнения всех возможных полученных рациональных вариантов.
На втором этапе решается задача коммивояжера по критерию минимальной стоимости отдельно каждого полученного кольца. Затем путем обмена смежными вершинами между двумя маршрутами выполняется улучшение решения. Применение разработанной методики рассмотрим на следующем примере.
Пример. Исходная матрица стоимости представлена в табл. 1, где максимальное ее значение составляет 8 единиц. Базы Б1 и Б2 расположены в вершинах 1 и 11, соответственно.
Таблица 1 Исходная матрица стоимости
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
1 |
3 |
2 |
1 |
3 | |||||||||
2 |
3 |
1 |
8 |
6 |
4 |
2 | |||||||
3 |
2 |
1 |
2 |
3 |
5 |
5 | |||||||
4 |
1 |
2 |
4 |
7 | |||||||||
5 |
8 |
3 |
8 |
6 |
4 |
5 |
6 |
7 | |||||
6 |
6 |
5 |
4 |
8 |
6 |
3 |
3 |
6 | |||||
7 |
5 |
7 |
6 |
4 |
2 | ||||||||
8 |
6 |
3 |
4 |
7 |
5 |
7 | |||||||
9 |
4 |
3 |
7 |
5 |
2 |
6 | |||||||
10 |
6 |
2 |
5 |
6 | |||||||||
11 |
7 |
5 |
6 |
7 | |||||||||
12 |
3 |
4 |
5 |
7 | |||||||||
13 |
2 |
6 |
2 |
7 |
2 | ||||||||
14 |
7 |
6 |
7 |
2 |
В табл. 2 представлена расчетная матрица после применения формулы (1) и ввода внешних фиктивных узлов и ветвей. Приведем краткие результаты расчета табл. 2 по вышеизложенному алгоритму.
Таблица 2 Расчетная матрица стоимости
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
Ф1 |
Ф2 |
Ф3 |
Ф4 |
1 |
5 |
6 |
7 |
5 | |||||||||||||
2 |
7 |
0 |
2 |
4 |
6 |
5 | |||||||||||
3 |
7 |
6 |
5 |
3 |
3 |
6 | |||||||||||
4 |
6 |
4 |
1 |
7 | |||||||||||||
5 |
0 |
5 |
0 |
2 |
4 |
3 |
2 |
1 | |||||||||
6 |
2 |
3 |
4 |
0 |
2 |
5 |
5 |
2 | |||||||||
7 |
3 |
1 |
2 |
4 |
6 | ||||||||||||
8 |
2 |
5 |
4 |
1 |
3 |
1 | |||||||||||
9 |
4 |
5 |
1 |
3 |
6 |
2 | |||||||||||
10 |
2 |
6 |
3 |
2 | |||||||||||||
11 |
1 | ||||||||||||||||
12 |
4 |
3 |
1 |
5 | |||||||||||||
13 |
6 |
2 |
6 |
1 |
6 | ||||||||||||
14 |
1 |
2 |
1 |
6 | |||||||||||||
Ф1 |
5 | ||||||||||||||||
Ф2 |
1 |
3 |
2 |
1 | |||||||||||||
Ф3 |
1 | ||||||||||||||||
Ф4 |
5 |
В процессе решения были получены два кольцевых маршрута с максимальной суммарной стоимостью. Если отбросить введенные начальные и расчетные фиктивные узлы, то получаются следующие схемы движения: 1-12-13-5-2-5-6-7-4-7-3-1 и 11-10-8-9-14-11 (рис. 2). Заметим, что вершины 5 и 7 посещаются дважды. Маршруты имеют восемь смежных вершин: 5, 6, 7, 8 , 9, 10, 13 и 14.
Рис. 2. Определение кольцевых маршрутов на первом этапе
Переходим ко второму этапу и рассматриваем все комбинации сочетаний при обмене их между маршрутами. В результате решения задачи находим две оптимальные схемы движения: 1-4-3-2-3-5-12-1, стоимостью 16 единиц и 11-10-7-8-6-9-13-14-11, стоимостью 29 единиц (рис. 3). Заметим, что вершина 3 посещается дважды.
Рис. 3. Оптимальные маршруты.
Похожие статьи
-
Таким образом, разработана методика нахождения кольцевых маршрутов с двух баз снабжения с использованием метода фиктивных узлов и ветвей....
-
Расчет цепи, Расчет методом контурных токов, В результате получаем матрицу: - Расчет параметров цепи
В заданной схеме (рис. 1.) необходимо определить токи в ветвях, напряжения на сопротивлениях, и соответствующие этим сопротивлениям номинальные значения...
-
Введение - Анализ транспортных логистических систем
В настоящее время не существует однозначного определения понятия "логистика". Во многих источниках используется следующее определение: Логистика -...
-
Расчеты по определению удельных равнодействующих сил необходимы для построения диаграммы удельных сил, действующих на поезд при различных движения: в...
-
Аналитический Метод применим только при линейных нагрузках. Графический Метод применим Для любых нагрузок (линейных или нелинейных), и отличается...
-
Определение маршрута перевозки - Расчет основных показателей параметров обслуживания пассажиров
Маршрутом называется регламентированный путь следования подвижного состава при выполнении перевозок. Маятниковым называют такой маршрут, при котором путь...
-
Метод построен на конформных преобразованиях (раздел теории функции комплексного переменного). Суть метода заключается в существовании двух систем...
-
С 1 км=С Мат +С Раб +С Мех +С Нак +С Нил +С Пр (3.1.1) Где С Мат - затраты труда на материалы; Сраб - зарплата рабочих Смех - расходы на эксплуатацию...
-
Объем, виды и способы ремонтных работ определяются экспертом в зависимости от характера, степени повреждения и состояния (коррозионного разрушения)...
-
Целью выполнения курсовой работы является закрепление знаний полученных ранее освоенных дисциплин и использование их при проектировании механического...
-
Определение сметной стоимости строительства узла коммутации - Передача дискретных сообщений
При определении денежных и материальных затрат на строительство или реконструкцию сооружений электрической связи на стадии проектного задания...
-
Введение - Выбор оптимального варианта отфрахтования судна и составление проекта чартера
Судно оферта груз чартер Цель работы - закрепление и расширение знаний, приобретенных при изучении курса, развитие навыков расчета элементов рейса и...
-
Совершенствование алгоритма планирования маршрутов автотранспортной доставки мелкопартионных грузов В работах [1]; [2] дана содержательная постановка...
-
Порядок выполнения работы, Модель транспортной задачи - Оперативное планирование перевозок грузов
Порядок исполнения работы представлен на рис. 2.1. Рис. 2.1. Порядок выполнения курсовой работы Модель транспортной задачи При решении...
-
Введение - Особенность перевозки грузов и пассажиров на транспорте
В общем виде задача выбора схемы автобусных маршрутов в городах формулируется следующим образом. Имеется транспортная сеть - улицы города, по которым...
-
Задача8 Чему равна пропускная способность канала связи, описанного следующей матрицей: ? Решение Найдем безусловные вероятности источника и приемника:...
-
Определение пиковых токов - Расчет системы электрооборудования пассажирского вагона
Пиковые токи - это максимальные токи, возникающие в процессе нормальной эксплуатации электрооборудования при включении мощных потребителей....
-
А) сумма средств, полученная от реализации изготовленной продукции Б) разница между расходами и прибылью В) стоимость производственной программы Г) сумма...
-
Инвентарный парк локомотивного депо, , лок, определяется по формуле [4] , (2.14) Где - парк в распоряжении депо, лок; - парк вне распоряжения депо лок, ,...
-
Пост по ТР трансмиссии автомобиля ЗиЛ-ММЗ-554 Основные виды работ: Разборка, дефектация, замена негодных деталей, сборка, регулировка. Режим работы: 800...
-
Далее необходимо рассчитать диаметр оси навески стабилизатора. Для выполнения требования равнопрочности ось будет выполнена трубчатого сечения с...
-
Цель и метод расчета, состав теплопоступлений В данном курсовом проекте цель теплотехнического расчета эксплуатационная, поскольку по результатам этого...
-
Самосвал автомобиль экскаватор уклон Согласно варианту 12 исходными данными для определения сопротивления копания грунта бульдозером являются: марка...
-
Введение - Оптимизация маршрутов автотранспортной доставки продукции компаний
Перед любой крупной компанией, работающей в условиях крупного города, и, соответственно, имеющей в своем распоряжении множество складских помещений,...
-
Перевозки автомобильным транспортом включают в себя грузовые и пассажирские перевозки. Классификация грузов отражает те их свойства, которые определяют...
-
Задание 1 Определите среднее расстояние перевозки lСр на основании следующих данных: Q1= 20 тыс. т; Q2 = 40 тыс. т; Q3 = 30 тыс. т; Q4= 10 тыс. т; l1 =...
-
Расчет электрической емкости представляет весьма сложную физико-математическую задачу. В инженерной практике используются справочные данные, готовые...
-
Таблица 8 ИТОГО: Стоимость узлов и деталей: 60 006,98 Процент к стоимости запчастей (на мелкие детали) (%): 2,00 Стоимость узлов и деталей с учетом...
-
В соответствии с Приложением 3 Методических рекомендаций для судебных экспертов "Исследование автомототранспортных средств в целях определения стоимости...
-
В соответствии с п. п. 4.4. Методических рекомендаций для судебных экспертов "Исследование автомототранспортных средств в целях определения стоимости...
-
Ц3=0 I1+ I2 - I3=0 I3+ I4 - I5=0 I1=(ц3 - ц1)*Y1 Y1= 1/Z1=0,1-0,2j I2=(ц3 - ц1)*Y2 Y2= 1/Z2=0,1912-0,0889j I3=(ц1 - ц2+e1)*Y3 Y3= 1/Z3=0,0688-0,2293j...
-
Графоаналитический метод по выбору типа и определения числа автобусов по часам суток. Для перевозки пассажиров могут быть использованы автобусы различных...
-
В качестве исходных данных берем граф: Рис. 4 Исходный граф Используя приложение "Microsoft Excel" вводим исходные данные, отражающие расстояние между...
-
Наименование и марка материала Сумма (руб.) Примечание 1. Материалы, необходимые дляоформлениядокументации 300 Все необходимые материалы принимаются за...
-
Расчет оптимального маршрута движения
Задание на лабораторную работу Задание: Транспортная сеть города и расстояние между соседними пунктами известны (рис.1). Требуется определить кратчайшее...
-
Введение - Расчет основных показателей параметров обслуживания пассажиров
Основными задачами субъектов осуществляющих пассажирские перевозки являются: - полное удовлетворение потребностей населения в пассажирских автомобильных...
-
Длина маршрута 362 км, время в пути 6 ч., остановки на маршруте: Вышний Волочек, Валдай. Стоимость билета 975 руб. Время отправления 11.45 ежедневно...
-
Количество рабочих человек, Р СП, определяется по формуле ,(2.2) Где Ф СП - годовой фонд времени списочного рабочего, при нормальных условиях труда. Ф...
-
В данной работе необходимо выполнить расчет произвольно взятой сети и найти наиболее оптимальный из двух вариантов. Исходными данными являются план...
-
В данном варианте работы не рассматривается вариант определения экономии от сокращения сроков поставки скоропортящихся грузов ввиду отсутствия таковых....
Введение, Модель и метод расчета - Определение кольцевых маршрутов наименьшей суммарной стоимости с двух баз методом фиктивных узлов и веток