Проблема перевалки

Для проверки этой статьи нужны дополнительные цитаты . Помогите улучшить эту статью , добавив ссылки на надежные источники . Неподтвержденные материалы могут быть оспорены и удалены. Найти источники:  «Проблема перевалки» – новости  · газеты  · книги  · ученый  · JSTOR ( январь 2021 г. ) ( Узнайте, как и когда удалять это сообщение )

Задачи перевалки образуют подгруппу транспортных задач, где перевалка разрешена. При перевалке транспортировка может или должна проходить через промежуточные узлы, возможно, меняя виды транспорта.

Проблема перевалки берет свое начало в средневековье ^{[ сомнительно – обсудить ]} , когда торговля начала становиться массовым явлением. Получение маршрута с минимальной стоимостью было главным приоритетом. Однако технологическое развитие медленно отдавало приоритет проблемам транспортировки с минимальной продолжительностью.

Перевалка или транспогрузка — это отправка товаров или контейнеров в промежуточный пункт назначения, а затем оттуда в еще один пункт назначения. Одной из возможных причин является смена транспортного средства во время поездки (например, с морского транспорта на автомобильный транспорт ), известная как перевалка . Другая причина — объединение небольших партий в большую партию (консолидация) с разделением большой партии на другом конце (деконсолидация). Перевалка обычно происходит в транспортных узлах . Большая часть международной перевалки также происходит в обозначенных таможенных зонах , что позволяет избежать необходимости таможенных проверок или пошлин, которые в противном случае являются серьезным препятствием для эффективной транспортировки.

Для полной формулировки задачи перевалки необходимо сделать несколько начальных предположений:

• Система состоит из m пунктов отправления и n пунктов назначения, имеющих следующую индексацию :${\displaystyle i=1,\ldots ,м}$${\displaystyle j=1,\ldots ,n}$
• Существует один однородный товар, который необходимо отгрузить
• Требуемое количество товара в пунктах назначения равно произведенному количеству, имеющемуся в пунктах происхождения.
• Транспортировка одновременно начинается в исходных пунктах и ​​возможна из любого узла в любой другой (как в исходный пункт, так и из пункта назначения)
• Транспортные расходы не зависят от отгружаемого количества.
• Задача перевалки грузов является уникальной задачей линейного программирования (ЗЛП), поскольку она предполагает, что все источники и приемники могут как получать, так и распределять грузы одновременно (функционировать в обоих направлениях) ^[1].

• ${\displaystyle t_{r,s}}$: время транспортировки от узла r до узла s
• ${\displaystyle a_{i}}$: товары, доступные в узле i
• ${\displaystyle b_{m+j}}$: спрос на товар в узле (m+j)
• ${\displaystyle x_{r,s}}$: фактическое количество, перемещенное из узла r в узел s

Цель состоит в том, чтобы свести к минимуму :${\displaystyle \sum \limits _{i=1}^{m}\sum \limits _{j=1}^{n}t_{i,j}x_{i,j}}$

• ${\displaystyle x_{r,s}\geq 0}$; , ${\displaystyle \forall r=1\ldots m}$${\displaystyle s=1\ldots n}$
• ${\displaystyle \sum _{s=1}^{m+n}{x_{i,s}}-\sum _{r=1}^{m+n}{x_{r,i}}=a_{i}}$; ${\displaystyle \forall i=1\ldots m}$
• ${\displaystyle \sum _{r=1}^{m+n}{x_{r,m+j}}-\sum _{s=1}^{m+n}{x_{m+j,s}}=b_{m+j}}$; ${\displaystyle \forall j=1\ldots n}$
• ${\displaystyle \sum _{i=1}^{m}{a_{i}}=\sum _{j=1}^{n}{b_{m+j}}}$

Поскольку в большинстве случаев явное выражение для целевой функции не существует, Раджив и Сатья предлагают альтернативный метод . Метод использует две последовательные фазы для выявления маршрута с минимальной длительностью от исходных пунктов до пунктов назначения. Первая фаза стремится решить задачу минимизации времени, в каждом случае используя оставшиеся промежуточные узлы в качестве пунктов перевалки. Это также приводит к минимальной длительности транспортировки между всеми источниками и пунктами назначения. Во время второй фазы необходимо решить стандартную задачу минимизации времени. Решение задачи минимизации времени перевалки является совместным результатом решения этих двух фаз.${\displaystyle n\cdot m}$${\displaystyle n+m-2}$

Поскольку затраты не зависят от отгруженного количества, в каждой отдельной задаче можно нормализовать отгруженное количество до 1. Теперь задача упрощается до задачи назначения от i до m+j . Пусть будет 1, если ребро между узлами r и s используется во время оптимизации, и 0 в противном случае. Теперь цель состоит в том, чтобы определить все , которые минимизируют целевую функцию:${\displaystyle x'_{r,s}=1}$${\displaystyle x'_{r,s}}$

${\displaystyle T_{i,m+j}=\sum _{r=1}^{m+n}\sum _{s=1}^{m+n}{t_{r,s}\cdot x'_{r,s}}}$,

такой что

• ${\displaystyle \sum _{s=1}^{m+n}{x'_{r,s}}=1}$
• ${\displaystyle \sum _{r=1}^{m+n}{x'_{r,s}}=1}$
• ${\displaystyle x'_{m+j,i}=1}$
• ${\displaystyle x'_{r,s}=0,1}$.

• ${\displaystyle x'_{r,r}=1}$и должны быть исключены из модели; с другой стороны, без ограничения оптимальный путь состоял бы только из петель типа -, что, очевидно, не может быть допустимым решением.${\displaystyle x'_{m+j,i}=1}$${\displaystyle x'_{m+j,i}=1}$${\displaystyle x'_{r,r}}$
• Вместо можно записать, где M — произвольно большое положительное число. С этой модификацией формулировка выше сводится к форме стандартной задачи о назначениях , которую можно решить венгерским методом .${\displaystyle x'_{m+j,i}=1}$${\displaystyle t_{m+j,i}=-M}$

На втором этапе решается задача минимизации времени с m пунктами отправления и n пунктами назначения без перевалки. Этот этап отличается от исходной установки двумя основными аспектами:

• Транспортировка возможна только из пункта отправления в пункт назначения.
• Время транспортировки от i до m+j представляет собой сумму длительностей, полученных по оптимальному маршруту, рассчитанному на этапе 1. Стоит обозначить его как , чтобы отделить его от времени, введенного на первом этапе.${\displaystyle t'_{i,m+j}}$

Цель состоит в том, чтобы найти , какие минимизируют${\displaystyle x_{i,m+j}\geq 0}$

${\displaystyle z=max\left\{t'_{i,m+j}:x_{i,m+j}>0\;\;(i=1\ldots m,\;j=1\ldots n)\right\}}$,
такой что

• ${\displaystyle \sum _{i=1}^{m}{x_{i,m+j}}=a_{i}}$
• ${\displaystyle \sum _{j=1}^{n}{x_{i,m+j}}=b_{m+j}}$
• ${\displaystyle \sum _{i=1}^{m}{a_{i}}=\sum _{j=1}^{n}{b_{m+j}}}$

Эту проблему легко решить с помощью метода, разработанного Пракашем . Набор необходимо разбить на подгруппы , где каждая содержит -s с одинаковым значением. Последовательность организована так, что содержит самые большие значения , вторые по величине и так далее. Кроме того, подгруппам назначаются положительные факторы приоритета по следующему правилу:${\displaystyle \left\{t'_{i,m+j},i=1\ldots m,\;j=1\ldots n\right\}}$${\displaystyle L_{k},k=1\ldots q}$${\displaystyle L_{k}}$${\displaystyle t'_{i,m+j}}$${\displaystyle L_{k}}$${\displaystyle L_{1}}$${\displaystyle t'_{i,m+j}}$${\displaystyle L_{2}}$${\displaystyle M_{k}}$${\displaystyle \sum _{L_{k}}{x_{i,m+j}}}$

${\displaystyle \alpha M_{k}-\beta M_{k+1}=\left\{{\begin{array}{cc}-ve,&if\;\alpha <0\\ve,&if\;\alpha >0\end{array}}\right.}$

для всех . При такой записи цель состоит в том, чтобы найти все , которые минимизируют целевую функцию${\displaystyle \бета}$${\displaystyle x_{i,m+j}}$

${\displaystyle z_{1}=\sum _{k=1}^{q}{M_{k}}\sum _{L_{k}}{x_{i,m+j}}}$

такой что

• ${\displaystyle \sum _{i=1}^{m}{x_{i,m+j}}=a_{i}}$
• ${\displaystyle \sum _{j=1}^{n}{x_{i,m+j}}=b_{m+j}}$
• ${\displaystyle \sum _{i=1}^{m}{a_{i}}=\sum _{j=1}^{n}{b_{m+j}}}$
• ${\displaystyle \alpha M_{k}-\beta M_{k+1}=\left\{{\begin{array}{cc}-ve,&if\;\alpha <0\\ve,&if\;\alpha >0\end{array}}\right.}$

Некоторые авторы, такие как Дас и др. (1999) и Малакути (2013), рассматривали многокритериальную задачу перевалки.

• RJ Aguilar, Системный анализ и проектирование. Prentice Hall, Inc. Энглвуд Клиффс, Нью-Джерси (1973) стр. 209–220
• HL Bhatia, K. Swarup, MC Puri, Indian J. pure appl. Math. 8 (1977) 920-929
• RS Gartinkel, MR Rao, Nav. Res. Log. Quart. 18 (1971) 465-472
• Г. Хэдли, Линейное программирование, Addison-Wesley Publishing Company, (1962) стр. 368–373
• PL Hammer, Nav. Res. Log. Quart. 16 (1969) 345-357
• PL Hammer, Nav. Res. Log. Quart. 18 (1971) 487-490
• AJHughes, DEGrawog, Линейное программирование: акцент на принятии решений, Addison-Wesley Publishing Company, стр. 300–312
• HWKuhn, Журнал морских исследований, квартал 2 (1955) 83-97
• А.Орден, Наука управления, 2 (1956) 276-285
• С.Паркаш, Proc. Indian Acad. Sci. (Math. Sci.) 91 (1982) 53-57
• CS Рамакришнан, OPSEARCH 14 (1977) 207-209
• CRSeshan, VGTikekar, Proc. Indian Acad. Sci. (Math. Sci.) 89 (1980) 101-102
• Дж. К. Шарма, К. Сваруп, Proc. Indian Acad. Sci. (Math. Sci.) 86 (1977) 513-518
• В.Шварц, нав. Рез. Бревно. Кварта. 18 (1971) 473-485
• Малакути, Б. (2013). Операционные и производственные системы с множественными целями. John Wiley & Sons.
• Дас, СК, А. Госвами и СС Алам. «Многоцелевая транспортная задача с интервальными параметрами стоимости, источника и назначения». Европейский журнал операционных исследований, том 117, № 1, 1999, стр. 100–112