Читайте также:
|
Метод Фогеля позволяет без использования ЭВМ получить оптимальный или близкий к нему результат. Решение проводится по следующему алгоритму:
- исходная матрица дополняется столбцом и строкой. Затем в каждой строке и каждом столбце матрицы находятся два наименьших элемента, и определяется абсолютная разность между ними, которая заносится соответственно разности по строке в столбец разностей, разности по столбцам – в строку разностей. Если две клетки в одной и той же строке или столбце имеют одинаковые значения, то разность для этой строки или столбца принимается равной нулю.
- выбирается наибольшая величина разности независимо от того, стоит ли она в столбце или строке разностей. В клетку с минимальным элементом в данной строке или столбце заносится максимально возможная загрузка, учитывая при этом соотношение ресурсов поставщика и спрос потребителя. Если окажется, что спрос потребителя полностью удовлетворен или ресурс поставщика полностью исчерпан, то данная строка или столбец матрицы из дальнейшего рассмотрения исключается.
- после заполнения и последующего исключения клетки матрицы разности пересчитываются, и операция повторяется вновь до тех пор, пока не будет составлен допустимый план закрепления потребителей за поставщиками.
Пробег с грузом (L г), общий пробег (L о) и транспортная работа (Р) для маятниковых маршрутов определяются по формулам:
(2)
(3)
(4)
где n, k – количество пунктов, закрепленных за грузоотправителями А и Б соответственно;
li A, lj Б – расстояние от соответствующего грузоотправителя до i -ого и j -ого грузополучателя, км;
- масса груза, перевозимая i -ому и j -ому грузополучателю соответственно, т.
В таблице 3 приведены расстояния между пунктами погрузки и пунктами разгрузки, полученные в процессе выполнения задания 2 курсовой работы.
Для исходных данных, приведенных в Приложении 1, требуется определить план доставки груза. По формуле (1) были определены расстояния между пунктами, результат приведен в табл. 1
Таблица 3
Расстояния между пунктами транспортной сети
| Пункт погрузки | Расстояние до пункта разгрузки, км | |||||||||
| А | ||||||||||
| Б |
Дополним таблицу кратчайших расстояний строкой и столбцом разностей.
В первой строке два наименьших элемента - 3 и 4, поэтому разность составит 1, во второй строке два наименьших элемента 3 и 0 (табл.3). Наибольшая величина разности, равная 7, находится в 5,6, 8, 9 и 10-м столбце. Выбираем 2-го грузоотправителя.
Таблица 4
Исходная матрица для метода Фогеля
| Пункт погрузки | Расстояние до пункта разгрузки, км | Столбец разности | |||||||||
| А | |||||||||||
| Б | |||||||||||
| Строка разностей |
Таблица 5
Матрица для метода Фогеля после исключения 6-го столбца
| Пункт погрузки | Расстояние до пункта разгрузки, км | Столбец разности | |||||||||
| А | |||||||||||
| Б | |||||||||||
| Строка разностей |
Таблица 6
Матрица для метода Фогеля после исключения 8-го столбца
| Пункт погрузки | Расстояние до пункта разгрузки, км | Столбец разности | |||||||||
| А | |||||||||||
| Б | |||||||||||
| Строка разностей |
Таблица 7
Матрица для метода Фогеля после исключения 9-го столбца
| Пункт погрузки | Расстояние до пункта разгрузки, км | Столбец разности | |||||||||
| А | |||||||||||
| Б | |||||||||||
| Строка разностей |
Таблица 8
Матрица для метода Фогеля после исключения 10-го столбца
| Пункт погрузки | Расстояние до пункта разгрузки, км | Столбец разности | |||||||||
| А | |||||||||||
| Б | |||||||||||
| Строка разностей |
Таблица 9
Матрица для метода Фогеля после исключения 5-го столбца
| Пункт погрузки | Расстояние до пункта разгрузки, км | Столбец разности | |||||||||
| А | |||||||||||
| Б | |||||||||||
| Строка разностей |
Таблица 10
Матрица для метода Фогеля после исключения 1-го столбца
| Пункт погрузки | Расстояние до пункта разгрузки, км | Столбец разности | |||||||||
| А | |||||||||||
| Б | |||||||||||
| Строка разностей |
Таблица 11
Матрица для метода Фогеля после исключения 3-го столбца
| Пункт погрузки | Расстояние до пункта разгрузки, км | Столбец разности | |||||||||
| А | |||||||||||
| Б | |||||||||||
| Строка разностей |
Таблица 12
Матрица для метода Фогеля после исключения 7-го столбца
| Пункт погрузки | Расстояние до пункта разгрузки, км | Столбец разности | |||||||||
| А | |||||||||||
| Б | |||||||||||
| Строка разностей |
Таблица 13
Матрица для метода Фогеля после исключения 4-го столбца
| Пункт погрузки | Расстояние до пункта разгрузки, км | Столбец разности | |||||||||
| А | |||||||||||
| Б | |||||||||||
| Строка разностей |
Закрепление грузоотправителей за грузополучателями отражено в таблице 14. В столбце «Итого» приведено количество груза, которое должно быть у грузоотправителя, найденное как сумма потребностей закрепленных за ним грузополучателей.
Таблица 14
Оптимальное закрепление пунктов разгрузки за поставщиками
| Пункт погрузки | Расстояние до пункта разгрузки, км | Итого | |||||||||
| А | 22,17 | ||||||||||
| Б | 6,61 | ||||||||||
| Объем груза, т. | 3,69 | 4,30 | 3,10 | 3,49 | 1,67 | 0,07 | 1,20 | 1,42 | 5,34 | 4,50 | 28,78 |
Найдем пробег с грузом, общий пробег и транспортную работу для маятниковых маршрутов.
Пробег с грузом (Lг) находится по формуле:
,
где n, k – количество пунктов, закрепленных за грузоотправителями А и Б соответственно;
liA, ljБ – расстояние от соответствующего грузоотправителя до i-ого и j-ого грузополучателя, км.
L г: (5+10+4+3+6+5+4)+(0+3+7)= 95 км
Общий пробег (Lо) находится по формуле:
L о: 2*47 = 94 км
Транспортная работа (P) находится по формуле:
, где 
- масса груза, перевозимая i-ому и j-ому грузополучателю соответственно, т.
P=(5*3,69+10*4,3+4*3,1+3*3,49+6*1,67+0*0,07+3*1,2+5*1,42+7*5,34+4*4,5)=160,42 ткм
4. Формирование маршрутов движения транспортных средств с помощью методов Свира и «ветвей и границ»
Метод Свира предполагает воображаемый луч, исходящий из точки, где расположен грузоотправитель, который постепенно вращается по (или против) часовой стрелке, "стирая" с карты изображения грузополучателей (Рис.2). В тот момент, когда сумма заказов "стертых" грузополучателей достигнет вместимости транспортного средства, фиксируется сектор, обслуживаемый одним кольцевым маршрутом. При использовании метода Свира следует учитывать, что количество пунктов включаемых в один маршрут должно быть не более пяти.
Рисунок 2. Закрепление за грузоотправителями грузополучателей с помощью метода Свира
В соответствии с нашими данными, используя метод Свира, у нас получилось, что за грузоотправителем B закреплены 5 пунктов разгрузки. За грузоотправителем А закреплены соответственно 5 пункта.
Объем груза для грузоотправителя B составляет 13,2
Объем груза для грузоотправителя A составляет 15,58
Таким образом, метод Свира предполагает использование автомобилей грузоподъемностью около 16 тонн на 1 и 2 маршруте.
Для этого подойдет грузовик Man TGA 26.460
• Грузоподъемность 16000 кг:
• Тип двигателя – Дизель
• Мощность двигателя – 240 л.с.
• Расход топлива 28 л/100 км
• Собственная масса 11000 кг
В таблице 15 представлены получившиеся маршруты и каждому маршруту представлена модель транспортного средства.
Таблица 15
| № маршрута | Грузоотправитель | Закрепленные пункты | Загруженность ТС, т | Модель ТС |
| А | 1, 2, 5, 8, 10 | 15,58 | Man TGA 26.460 | |
| В | 3, 4, 6, 7, 9 | 13,2 | Man TGA 26.460 |
Для маршрута № 1 грузоотправителя А составим матрицу кратчайших расстояний (табл.15):
Таблица 15
Матрица кратчайших расстояний для маршрута №1
(грузоотправитель А)
| Пункты маршрута | A | |||||
| A | ? | |||||
| ? | ||||||
| ? | ||||||
| ? | ||||||
| ? | ||||||
| ? |
Для решения задачи коммивояжёра воспользуемся специальным программным обеспечением, реализованным в среде программирования Borland C++. В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(A,2), (2,8), (8,1), (1,5), (5,10), (10,A),
Длина маршрута равна F(Mk) = 32
Для второго маршрута получаем матрицу:
| Пункты маршрута | B | |||||
| B | ? | |||||
| ? | ||||||
| ? | ||||||
| ? | ||||||
| ? | ||||||
| ? |
Проводя расчеты аналогичным образом для грузоотправителя B, мы получаем маршрут: (B,6), (6,9), (9,7), (7,3), (3,4), (4,B). Длина маршрута равна F(Mk) = 28
Определим значения технико-эксплутационных показателей: с грузом (L г), общий пробег (L о) и транспортная работа (Р) для развозочных маршрутов по формулам:
, где
m – количество развозочных маршрутов;
t – количество пунктов на маршруте (пункт погрузки учитывается два раза);
– пробег между соседними пунктами маршрута, км;
- суммарный объем перевозок на m-ом маршруте, т;
qs – объем груза, выгружаемый в s-ом пункте, т.
Lг = 32-4+28-0=56 км
Lo = 32+28=60 км
Транспортная работа для первого маршрута:
10*15,58+1*(15,58-4,30)+11*(15,58-4,30-1,42)+2*(15,58-4,30-1,42-3,69)+4*(15,58-4,30-1,42-3,69-1,67)= 305,88 ткм
Транспортная работа для второго маршрута:
0*13,2+7*(13,2-0,07)+9*(13,2-0,07-5,34)+5*(13,2-0,07-5,34-1,2)+3*(13,2-0,07-5,34-1,2-3,1)= 205,44 ткм
Суммарная транспортная работа: 511,32 ткм.
Результаты вычислений двумя методами представим в виде таблицы сравнения технико-эксплуатационных показателей (см. табл. 16).
Таблица 16
Сравнение технико-эксплутационных показателей
| Показатель | Пробег с грузом, км | Общий пробег, км | Транспортная работа, ткм |
| после решения транспортной задачи | 160,42 | ||
| после решения задачи маршрутизации | 511,32 |
Несложно заметить, что применение кольцевых маршрутов позволяет организовать процесс перевозки значительно эффективнее, чем при применении маятникового. Значительное снижение общего пробега и значительное увеличение транспортной работы означает, что работа транспортной системы стала эффективнее, в частности, уменьшился километраж порожних пробегов.
Дата добавления: 2015-07-12; просмотров: 210 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Расположение пунктов транспортной сети | | | Определение интервалов времени прибытия и отправления транспортных средств для каждого пункта маршрутов |