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

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

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

Обзор

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

Формулировка проблемы

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

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

Обозначения

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

Математическая постановка задачи

Цель – минимизировать $\sum \limits _{i=1}^{m}\sum \limits _{j=1}^{n}t_{i,j}x_{i,j}$ подлежит:

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

Решение

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

Этап 1

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

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

такой, что

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

Следствие

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

Этап 2

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

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

В математической форме

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

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

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

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

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

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

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

такой, что

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

Расширение

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

Ссылки

• Р. Дж. Агилар, системный анализ и проектирование. Prentice Hall, Inc. Энглвуд Клиффс, Нью-Джерси (1973), стр. 209–220.
• HL Bhatia, K. Swarup, MC Puri, Indian J. pure appl. Математика. 8 (1977) 920-929
• Р.С. Гартинкель, М.Р. Рао, нав. Рез. Бревно. Кварта. 18 (1971) 465-472
• Дж. Хэдли, Линейное программирование, издательство Addison-Wesley Publishing Company, (1962), стр. 368–373.
• ПЛ Хаммер, нав. Рез. Бревно. Кварта. 16 (1969) 345-357
• ПЛ Хаммер, нав. Рез. Бревно. Кварта. 18 (1971) 487-490
• А.Дж.Хьюз, Д.Э.Гравог, Линейное программирование: акцент на принятии решений, издательство Addison-Wesley Publishing Company, стр. 300–312.
• Х.В.Кун, нав. Рез. Бревно. Кварта. 2 (1955) 83-97
• А.Орден, Наука управления, 2 (1956) 276-285.
• С.Паркаш, Учеб. Индийский акад. наук. (Математические науки) 91 (1982) 53-57
• К. С. Рамакришнан, OPSEARCH 14 (1977) 207-209.
• С. Р. Сешан, В. Г. Тикекар, Учеб. Индийский акад. наук. (матем. наук) 89 (1980) 101-102
• Дж.К.Шарма, К.Сваруп, Proc. Индийский акад. наук. (Математические науки) 86 (1977) 513-518
• В. Шварц, нав. Рез. Бревно. Четверть. 18 (1971) 473-485
• Малакути, Б. (2013). Операции и производственные системы с множеством целей. Джон Уайли и сыновья.
• Дас, С.К., А. Госвами и С.С. Алам. «Многокритериальная транспортная задача с интервальными параметрами стоимости, источника и пункта назначения». Европейский журнал операционных исследований, Vol. 117, № 1, 1999, стр. 100–112.