Планирование транспортных перевозок с минимальными издержками

DOI:

Классическая транспортная задача об оптимальном плане перевозок описана в любом руководстве по математическим методам в транспортной науке. С ее постановкой и свойствами можно ознакомиться, например, в [2]. Но стоит отметить, что есть еще два фактора, которые необходимо дополнительно учитывать при планировании перевозок. Во-первых, величина непрямолинейности маршрутов, соединяющих две точки транспортной сети. Математически это значение можно рассчитать как отношение длины кратчайшего пути между этими точками к расстоянию между ними по прямой. Это значение всегда больше 1 и на реальных городских транспортных сетях может превышать 2. Разница между этой величиной и единицей, умноженная на 100 %, дает процент естественных потерь (например, в виде расхода топлива, временных затрат и т. д.) при транспортировке по данной транспортной сети. Вторым фактором является ограниченная пропускная способность дорожных участков транспортной сети. Если даже решение классической задачи дает оптимальный план транспортировки, то может сложиться ситуация, когда транспортировка в нужное время не может быть осуществлена из-за перегруженности участков сети. Задача состоит в том, чтобы составить транспортный план, в котором все транспортные потребности будут полностью удовлетворены и в то же время общие транспортные расходы достигнут своего минимума. Следует отметить, что при отсутствии ограничений на максимальную нагрузку на дорогу эта задача решается тривиально: все ij единиц груза должны перевозиться по кратчайшему пути из i в j.

1.    Постановка задачи

Дана транспортная сеть, состоящая из п узлов. Пусть G = ( Р, Е ) — плоский граф, представляющий транспортную сеть. Из пункта Р ^ ( г = 1,2,...,п) в пункт P j ( j = 1, 2 ,...,п ) необходимо доставить d^ единиц груза. Стоимость перевозки единицы груза на единицу расстояния известна и составляет с денежных единиц. Отметим, что величины d^ всегда можно считать неотрицательными числами для любых i,j .

Для каждой пары i,j Е Р определим множество Y _i j всех простых путей из i в j . Для ясности изложения пусть элементы этого множества будут пронумерованы и подчиняться правилу Y j | < | Y ij ⁺¹ | . Таким образом, y 0 ₉ есть кратчайший путь из г в j . Эти пути образуют маршруты, по которым возможны перевозки.

Если распределить d^ единиц груза по всем путям из Yij , то величина d ^ (к = = 1, 2 ,...,п^ ) равна количеству единиц груза, распределенному на перевозку по маршруту Y ?j . Среди этих величин допускаются нулевые.

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

^ pq

F ( d ) = с • ЕЕ Y ,^.                      (1)

p = q i =1

Далее для каждого ребра е графа G зададим его максимальную нагрузку 0 (e) . В качестве этой величины выступает число грузов, которое можно через него перевезти:

N (е) = Е d ‘, .                                 (2)

Y pq Э е

Требуется определить набор х величин d ^ ( i,j = 1, 2, ...,п ; к = 1, 2 ,...,п^ , удовлетворяющих условиям:

^ ij

Е = Di,, к=1

N(e) < 0(e),

Dy > 0(i, j = 1,2, ...,п; к = 1, 2, ...,nij,(5)

и таких, что линейная форма (1) достигает своего минимума.

Равенство (3) гарантирует удовлетворение всех потребностей в перевозках. Неравенство (4) гарантирует, что дороги не будут перегружены. Функционал (1) является линейным, ограничения также линейны. Следовательно, мы получаем задачу линейного программирования.

Нужно отметить, что без ограничений вида (4) задача минимизации функционала (1) решается тривиально: надо всю перевозку из пункта р в пункт q распределить на кратчайший маршрут Ypg € Ppg• Другими словами, Tpq                            Tpq

^С • К К | Y pgHg >  ^С • К | Y pg I К ^д = С • К | Y pg | ^ pg . p _ g к =1               p _ g     к =1          p _ g

2.    Алгоритм нахождения k-го по длине пути

Для решения поставленной задачи нужно уметь находить Y p +¹ при условии, что известны все члены последовательности {Y p_g}* _₀ - Искать сразу все множество Y _pg для каждой пары pq нецелесообразно из-за того, что путей может существовать слишком много, а понадобятся единицы.

Перед описанием алгоритма необходимо ввести некоторые обозначения:

• •    Ж — множество рассмотренных вершин;

• •    ^ — множество найденных путей из p в q ;

• •    п — множество новых путей из p в q ;

• •    in ( q ) = { u E V : 3 (u, q) € E } .

Алгоритм состоит из следующих шагов.

• 1.    Установить начальные значения Ж = 0 , п = 0 , ^ = {Y p_g}* _₀ .

• 2.    Найти множество вершин Q = { q'\q' Е in ( q ) ,q ' = p,q / Ж } .

• 3.    Для каждого q ' Е Q'"

  • 3.1.    Найти ^ _pg ‘ — наиболее короткий путь из p в q ' , удовлетворяющий ряду следующих условий:

• •    ^ + ⁽q ‘ , q ) / # ;

• •    ^ _pg ‘ не проходит через вершину q и вершины множества Ж .

• 3.1.1.    Если подходящие пути имеются в { Y pu } _₀ , то из них выбирается путь с наименьшим i , то есть с минимальной длиной, а затем перейти к следующей вершине множества Q .

• 3.1.2.    Найти подходящий путь из p в q ' с помощью текущего алгоритма со следующими начальными значениями:

• •    Ж = Ж + q';

• •    ^ = р \ (q‘^,q⁾\^ Э (q'^Y;

• •    п = 0.

• 3.2.    Если путь ^_pg‘ найден, то добавить к п путь ^_pg‘ + (q',q).

• 4.    Если п = 0, тогда из всех путей множества п выбрать наиболее короткий, иначе в {Yp_g}*_₀уже содержатся все возможные пути из p в q.

3.    Алгоритм построения плана оптимальных перевозок

• 1.    Найти кратчайший путь Y 0 _g из p в q V p = q . Если 3 p, q : v _pg > 0, @Y _pg , то конец алгоритма. Задача неразрешима. Существует направление, по которому необходимо перевезти груз, но не существует ни одного пути, по которому можно это сделать.

• 2.    Определить множество перегруженных ребер Е _ог)ег . Ребро е перегружено, если условие (4) не выполняется. Если E_mer = 0 , тогда мы получаем тривиальный случай, то есть перевозку v _pq единиц груза осуществлять по кратчайшему маршруту Y py V p, q . Задача решена.

• 3.    Если E _over = 0 , то необходимо разгрузить все ребра е G E _over следующим способом:

  • 3.1.    V Y p₉ : Y p₉ Э е найти новый кратчайший путь из p в q по вышеописанному алгоритму.

• 3.2.    Решить задачу линейного программирования, описанную выше. Алгоритмы решения задач линейного программирования можно посмотреть, например, в [1]. В результате решения поставленной задачи получим оптимальное распределение потоков по всем найденным путям.

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

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

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

Заключение

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