Закрепление маршрутов за АТП

Задача определения кратчайших расстояний методом потенциалов

1. Вершина, от которой требуется определить кратчайшие расстояния, называется начальной. Начальной вершине присваивается потенциал равный 0, т.е. Р_i=0.

2. По формуле (1) определяются потенциалы всех вершин, непосредственно связанных с ней:

Р_j = Р_i + l_ij, (1)

где i,j – текущие индексы соответственно исходной и непосредственно связанной с ней вершин;

Р_i – потенциал исходной вершины, км;

Р_j – потенциал вершины, непосредственно связанной с исходной, км;

l_ij – длина звена между исходной и непосредственно связанной с ней вершинами, км.

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

4. Вершина с наименьшим потенциалом принимается за исходную, от нее вновь определяются потенциалы всех вершин, непосредственно связанных с ней.

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

Для того чтобы определить кратчайшие расстояния до всех вершин сети от другой вершины необходимо проделать заново все расчеты рассмотренным методом, приняв за начало сети выбранную вершину и присвоив ей потенциал, равный 0. Таким образом, расчеты повторяются до полного заполнения таблицы и рисунка.

Метод МОДИ.

1. Делается первоначальное закрепление потребителей за поставщиками. (способ двойного предпочтения)

2. Затем первоначальный план проверяется, он должен удовлетворять следующим условиям:

а)Число загруженных клеток должно быть равно

n+m-1,

где n- кол-во пунктов потребления,

m - кол-во пунктов отправления.

б)Отсутствие циклов, когда во всех вершинах условного контура лежат загруженные клетки.

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

В распределительную матрицу вводятся вспомогательные строка и столбец. Относительной оценкой любой клетки вместо расстояния Lij служит параметр

d_ij = l_ij - u_i - v_j. (1)

Принимая для загруженных клеток d_ij=0 и используя формулу 1 определяем числа Ui и Vj, называемые потенциалами. Для этого потенциал одной из строк Ui принимаем равным 0, его желательно установить тому отправителю, у кот имеется загруженная клетка с мах расстоянием. Потенциалы других строк и столбцов определяют по формулам:

U_i= l_ij-V_j

V_j= l_ij- U_i

Затем по потенциалам строк и столбцов определяют параметры d_ij для каждой незагруженной клетки. Отсутствие клеток где d_ij <0 означает, что получен оптимальный план закрепления потребителей за поставщиками.

4. Улучшение полученного распределения.

Если существуют клетки, в кот d_ij<0, то необходимо улучшать полученный план. Для этого выбирают такую клетку, в кот d_ij минимальное. В эту клетку перемещается загрузка, что обеспечит снижение грузооборота.Для перемещения загрузки составляется контур, где все вершины (кроме той, где d_ij <0) лежат в загруженных клетках.

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

Маршрутизация перевозок массовых грузов

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

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

1. На основании заявок на перевозки составляют матрицу.

2. Решаем эту матрицу на мин пробега с помощью метода МОДИ, получаем распределение порожних ездок автомобилей, при котором их пробег без груза будет минимальным.

3. В эту же таблицу вносят план груженых ездок(цифры в скобках), и получаем так называемую матрицу совмещенного плана.

4.Составляем маршруты. В тех клетках, где имеются 2 цифры, получаются маятниковые маршруты, количество ездок по которым равно наименьшей цифре. Запланированные на маятниковых маршрутах перевозки (завоз грузов и возврат порожних а\м) исключаем из матрицы и продолжаем составление кольцевых маршрутов. Для этого в матрице строим контуры, все вершины которых лежат в загруженных клетках, причем вершины с гружеными ездками должны чередоваться с порожними ездками.

5. Для каждого кольцевого маршрута необходимо определить коэффициент использования пробега, если b≤0.5, то такой маршрут нецелесообразен, соответствующие перевозки лучше осуществлять на маятниковых маршрутах.

Закрепление маршрутов за АТП

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

Этого можно достигнуть, определяя АТП, из кот наиболее целесообразно подавать а\м на маршруты.

 

 

		А1
		В2

 

 

Рисунок1

Рассмотрим пример выполнения перевозок по маршруту(рис 1). Предположим, что по этому мар-ту надо выполнить 1 оборот А1Б1Б1А2А2Б2Б2А1. Этот мар-т можно закрепить как за АТП-1, так и за АТП-2. Подсчитаем нулевой пробег и весь пробег без груза в обоих случаях:

Из АТП-1:

нулевой пробег L₀=7+8=15

пробег без груза L_{без гр.}=7+3+8=18

Из АТП-2:

нулевой пробег L₀=5+4=9

пробег без груза L_{без гр.}=5+13+4=22

Из данного примера видно, что несмотря на меньший нулевой пробег при подаче а\м из АТП-2, весь пробег без груза будет наименьшим при подаче а\м из АТП-1. Это связано с тем, что при подаче а\м из АТП-1 не будет выполняться последняя порожняя ездка Б2А1, кот на данном мар-те является наибольшей из порожних ездок. А\м в этом случае из Б2 возвратится в АТП-1. В случае подачи а\м из АТП-2 будет выполняться порожняя ездка Б2А1, т.е. вместо 3 км пробег без груза на маршруте составит 13 км и это не покрывается разницей в нулевых пробегах при подаче а\м из АТП-1и АТП-2. Если по этому же мар-ту будет выполняться несколько оборотов, то положение не измениться.

Это показывает, что пробег без груза по мар-ту зависит от выбора пункта начала движения по мар-ту и АТП, откуда следует подавать а\м на этот пункт. Причем наиболее целесообразный выбор связан с нахождением мин разности м\у сыммой первого и последнего нулевых пробегов при подаче а\м из АТП и расстоянием м\у первым пунктом погрузки и последним пунктом разгрузки при данном выборе АТП и начального пункта мар-та. Если имеются 2 АТП, то это означает необходимость выбора мин числа из следующих выражений:

min={(a1+b1-c1), (a2+b2-c2)},

где а- пробег а\м от АТП до первого пункта погрузки,

b-пробег а\м от последнего пункта разгрузки до АТП,

с- расстояние между первым пунктом погрузки и последним пунктом разгрузки.

 

Решение задачи коммивояжера методом "ветвей и границ"

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

1. Матрица кратчайших расстояний приводится по минимальным расстояниям по строкам. Для этого из каждого элемента строки вычитают наименьший элемент данной строк.

2. Полученная на 1 этапе новая матрица приводится по столбцам. Для этого из каждого элемента столбца вычитают наименьший элемент этого столбца.

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

4. Произвести оценку нулевых элементов. Для оценки нулевого элемента необходимо выбрать мин элемент по строке (если есть другой ноль то его) и прибавить к мин элементу по столбцу.

5. В маршрут движения коммивояжера целесообразно включить пару пунктов, соответствующих нулевому элементу с максимальной оценкой.

6. Множество "все решения" делится на два подмножества:

· включают пару пунктов

· не включают пару пунктов

7. Выбор пары пунктов обратных уже включенным в маршрут, привел бы к нарушению условий задачи (побывать в каждом пункте только по 1 разу), поэтому этот элемент блокируем, проставляя в соответствующую клетку матрицы вместо цифры знак!.

Этапы с 1 по 7 для новой матрицы повторяются.

Поделиться:

Воспользуйтесь поиском по сайту: