Составление маршрутов движения транспорта

Составление кольцевых маршрутов в первом прибли­жении может осуществляться методом, известным как ал­горитм Свира или алгоритм дворника-стеклоочистителя (рис. 48). Зададим положение потребителя материального потока в полярной системе координат. Полюс системы — точку 0, разместим в месте дислокации распределительно­го склада. Выберем первоначальное, нулевое, положение полярной оси φ =0. Положение потребителя определяется расстоянием от центра и углом φ , который образован полярной осью, т.е. лучом, исходящим из точки 0 и направ­ленным на потребителя.

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

На кольцевые маршруты кроме ограничений по вмес­тимости могут накладываться дополнительные требования, например, ограничения по времени. Если окажется, что время движения по определенному кольцевому маршруту больше допустимого, необходимо этот сектор уменьшить, увеличив соответственно соседний сектор. Необходимые уменьшения сектора выполняются и при наличии других ограничений.

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

Транспортная задача

Транспортная задача – это задача прикрепления поставщика к потребителям.

Имеется m поставщиков определенного вида продукции. Максимальные объемы возможных поставок заданы и равны соответственно a_i при i = 1,2, … m, Эта продукция используется n потребителями. Объемы потребностей заданы и равны соответственно b_j при j = 1,2, … n. Стоимость перевозок единицы продукции от поставщика к потребителю известна и равна c_ij Требуется установить такие объемы перевозок х_ij, от каждого поставщика к потребителю, чтобы суммарные затраты на перевозки были минимальными и потребности всех потребителей были бы удовлетворены.

Математическая модель этой задачи такова:

∑∑х_ij, c_ij → min

b_j

b_j

b_j

_j

_j

_m

_потреб

_постав

x_ij,p_ij

с_ij

с_ij

с_ij

x_ij

x_ij

a_i

u_i

_i

с_ij

с_ij

с_ij

x_ij

x_ij

x_ij

a_i

u_i

_i

с_ij

с_ij

c_ij

x_ij

x_ij

a_i

x_ij

u_i

_n

v_i

v_i

v_i

i- поставщик

j –потребитель

a_i- запас на поставку

b_j –потребность в поставке

x_ij- партия поставки

c_ij- стоимость доставки

B –базисная клетка

u_i-потенциал поставщика(строки)

v_j – потенциал потребителя (столбца)

p_ij – потенциал поставки (клетки)

n – колическтво поставщиков

m –количество потребителей

Алгоритм решения.

1. первичное распределение.

   1. Проверка на закрытость (открытость) задачи. (закрытый тип - Сумма объемов поставки должна быть равна сумме потребностей.)

   2. распределить грузы методом северо-западного угла или методом наименьшей стоимости.

   3. подсчитать стоимость доставки по полученному графику.

2. проверка на оптимальность.

   1. Проверка на выражденность m+n- 1 = B выражен , а если базисных клеток меньше то невыражден. Вводим дополнительную клетку с нулевой поставкой.

   2. Зададимся нулевым потенциалом.

   3. Подсчитаем потенциалы строк и столбцов.

   4. Подсчитаем потенциалы клеток и проверим на оптимальность.

   5. если оптимальный то считаем затраты если не оптимальный то строим цикл переноса

3. построение цикла переноса.

   1. Определяем клетку где разница потенциала клетка и стоимость наименьшая

   2. Строим цикл переноса, при этом кол-во + и – должно быть одинаковое в каждом столбце и в каждой строке.

   3. Производим перераспределение на минимальную величину объема поставки попавшего в цикл переноса.

Проверяем на оптимальность