Проблемы перевалки составляют подгруппу транспортных проблем, где перевалка разрешена. При перевалке транспортировка может или должна проходить через промежуточные узлы, возможно, с изменением вида транспорта.
Проблема перевалки уходит корнями в средневековье [ сомнительно ], когда торговля стала массовым явлением. Получение маршрута с минимальной стоимостью было основным приоритетом. Однако технологическое развитие постепенно отдавало приоритет проблемам минимальной продолжительности перевозки.
Обзор
Перегрузочный или Перевалка является пересылка из товаров или контейнеров до промежуточного пункта назначения, а затем оттуда еще одному адресату. Одна из возможных причин - смена транспортного средства во время путешествия (например, с морского транспорта на автомобильный ), известное как перегрузка . Другая причина - объединить небольшие поставки в большую партию (консолидация), разделив крупную партию на другом конце (деконсолидация). Перевалка обычно происходит в транспортных узлах . Большая часть международных перевалок также осуществляется в специально отведенных таможенных зонах , что позволяет избежать таможенных проверок или пошлин, которые в противном случае являются серьезным препятствием для эффективных перевозок.
Постановка задачи
Чтобы полностью сформулировать проблему перевалки, необходимо сделать несколько исходных предположений:
- Система состоит из m пунктов отправления и n пунктов назначения со следующей индексацией соответственно:,
- Существует один единый товар, который необходимо отправить
- Требуемое количество товара в пунктах назначения равно произведенному количеству товара, доступному в пунктах отправления.
- Транспортировка одновременно начинается в пункте отправления и возможна из любого узла в любой другой (также в пункт отправления и из пункта назначения).
- Транспортные расходы не зависят от количества груза.
- Проблема перевалки - это уникальная проблема линейного программирования (LLP), поскольку она учитывает предположение, что все источники и приемники могут одновременно принимать и распределять грузы (функционируют в обоих направлениях) [1]
Обозначения
- : время транспортировки от узла r к узлу s
- : товары, доступные в узле i
- : спрос на товар в узле (m + j)
- : фактическое количество перемещено от узла r к узлу s
Математическая постановка задачи.
Цель - минимизировать при условии:
- ; ,
- ;
- ;
Решение
Поскольку в большинстве случаев явного выражения для целевой функции не существует, Раджив и Сатья предлагают альтернативный метод . В этом методе используются две последовательные фазы для определения минимального продолжительного маршрута от исходной точки до места назначения. Первый этап готов решить задача минимизации времени , в каждом случае используя оставшиесяпромежуточные узлы в качестве перевалочных пунктов. Это также приводит к минимальной продолжительности перевозки между всеми источниками и пунктами назначения. На втором этапе необходимо решить стандартную задачу минимизации времени. Решение проблемы перевалки с минимальным временем является результатом совместного решения этих двух этапов.
Фаза 1
Поскольку затраты не зависят от отгруженного количества, в каждой отдельной задаче отгруженное количество можно нормализовать до 1 . Теперь проблема упрощена до задачи присваивания от i до m + j . Позволятьбыть 1 , если ребро между узлами г и s используется в процессе оптимизации, и 0 в противном случае. Теперь цель - определить все которые минимизируют целевую функцию:
,
такой, что
- .
Следствие
- а также нужно исключить из модели; с другой стороны, без ограничение оптимальный путь будет состоять только из петли, которые, очевидно, не могут быть допустимым решением.
- Вместо , можно записать, где M - сколь угодно большое положительное число. С этой модификацией приведенная выше формулировка сводится к форме стандартной задачи присваивания , которую можно решить с помощью венгерского метода .
Фаза 2
На втором этапе решается задача минимизации времени с m отправлениями и n направлениями без перевалки. Этот этап отличается от первоначальной установки двумя основными аспектами:
- Транспортировка возможна только из пункта отправления в пункт назначения.
- Время транспортировки от i до m + j - это сумма продолжительности оптимального маршрута, рассчитанного на этапе 1. Достойно обозначения чтобы отделить его от времен, введенных на первом этапе.
В математической форме
Цель - найти которые минимизируют
,
так что
Эту проблему легко решить с помощью метода, разработанного Пракашем . Набор необходимо разбить на подгруппы , где каждый содержать -s с таким же значением. Последовательность организован как содержит самые ценные с второй по величине и так далее. Более того, положительные факторы приоритета присваиваются подгруппам , со следующим правилом:
для всех . С помощью этих обозначений цель состоит в том, чтобы найти все которые минимизируют целевую функцию
такой, что
Расширение
Некоторые авторы, такие как Das et al (1999) и Malakooti (2013), рассматривали многоцелевую проблему перевалки.
Рекомендации
- ^ "(PDF) Проблема перевалки и ее варианты: обзор" . ResearchGate . Проверено 2 ноября 2020 .
- Р. Дж. Агилар, Системный анализ и дизайн. Prentice Hall, Inc., Энглвуд Клиффс, Нью-Джерси (1973), стр. 209–220
- HL Bhatia, K. Swarup, MC Puri, Indian J. pure app. Математика. 8 (1977) 920-929
- RS Gartinkel, MR Rao, Nav. Res. Бревно. Кварта. 18 (1971) 465-472
- Г. Хэдли, Линейное программирование, издательство Addison-Wesley Publishing Company, (1962) стр. 368–373
- PL Hammer, Nav. Res. Бревно. Кварта. 16 (1969) 345-357
- PL Hammer, Nav. Res. Бревно. Кварта. 18 (1971) 487-490
- AJHughes, DEGrawog, Линейное программирование: акцент на принятии решений, издательство Addison-Wesley Publishing Company, стр. 300–312
- HWKuhn, Nav. Res. Бревно. Кварта. 2 (1955) 83-97
- A.Orden, Management Sci, 2 (1956) 276-285.
- С.Паркаш, Тр. Индийский акад. Sci. (Математика) 91 (1982) 53-57
- К.С. Рамакришнан, OPSEARCH 14 (1977) 207-209
- CRSeshan, VGTikekar, Proc. Индийский акад. Sci. (Математика) 89 (1980) 101-102
- JKSharma, K.Swarup, Proc. Индийский акад. Sci. (Математические науки) 86 (1977) 513-518
- W.Szwarc, Nav. Res. Бревно. Кварта. 18 (1971) 473-485
- Малакути, Б. (2013). Операционные и производственные системы с множеством целей. Джон Вили и сыновья.
- Дас, С. К., А. Госвами и С. С. Алам. «Многокритериальная транспортная задача с интервалом стоимости, параметрами источника и пункта назначения». Европейский журнал операционных исследований, Vol. 117, № 1, 1999, стр. 100–112