Главная | Обратная связь

Пример решения задачи маршрутизации

В качестве примера одной из задач маршрутизации рассмотрим задачу отыскания маршрута движения автомобиля, осуществляющего развозку некоторого вида груза из некоторого базового пункта по нескольким пунктам, связанным между собой автомобильными дорогами. Пусть число таких пунктов равно n и c_ij – расстояние от пункта i до пункта j, i,j = , где 0 соответствует базовому пункту. В каждый пункт с номером ( ) автомобиль должен побывать ровно один раз, и после развозки всех грузов ему необходимо вернуться в базовый пункт.

Задача состоит в определении порядка посещения автомобилем пунктов с номерами ( ) так, чтобы суммарное расстояние, проходимое автомобилем, было минимальным.

Для математической формулировки рассмотренной задачи вводятся переменные x_ij, которые могут принимать следующие значения:

если автомобиль из пункта с номером i переезжает в пункт с номером j;

в противном случае,

где i, j = , i ≠ j.

Следующая система соотношений образует математическую модель и отражает закономерность функционирования системы развозки грузов по n пунктам из базового пункта:

((8)

((9)

 

 

((10)

где U_i и U_j – произвольные вещественные значения.

Условия (8) - (9) исключают циклы (петли) на маршруте, поскольку приезд автомобиля в каждый пункт и выезд из каждого пункта происходит ровно один раз. Условие (10) не допускает расщепления замкнутого из n+1 звеньев маршрута автомобиля на несколько замкнутых маршрутов меньшего числа звеньев. В качестве целевой функции в рассмотренной задаче выступает транспортная работа автомобиля, которая подлежит минимизации:

((11)

 

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

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

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

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

Для внутригородской перевозки необходимо определить время на движение автомобиля с грузом (t_грi) и без груза (t_хi) на i-ом участке, время на погрузку у j-ого поставщика (t_пj) и на разгрузку у l-ого потребителя(t_рl), включающие время ожидания погрузки и разгрузки соответственно. Сумма всех составляющих дает время в наряде (T_н) :

T_н = ∑t_пj + ∑t_грi + ∑t_рl + ∑t_хi (12)

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

T_н = ∑t_пj + ∑t_грi + ∑t_рl + ∑t_х + ∑η_j + ∑ψ_l (13) (13)

где η_j – случайная составляющая, учитывающая обеденные (технологические) перерывы j-ого поставщика;

ψ_l - случайная составляющая, учитывающая обеденные (технологические) перерывы l-ого потребителя.

Включение составляющих η_j и ψ_l обусловлено возможными пересечениями, частичными накладками составляющих перевозочного процесса и времени обеденных (технологических) перерывов поставщика или потребителя. Так, например, погрузка автомобиля у поставщика не будет выполняться, если на момент прибытия оставшееся время до обеда меньше самого времени погрузки или если автомобиль прибыл во время обеденного перерыва. Аналогичные простои, связанные с технологическими (обеденными) перерывами, могут возникнуть и в пункте разгрузки.

При международной перевозке общее время нахождения автомобиля в рейсе определяется по следующей формуле:

((14)

 

где t_i,i+1 – время движения между i-м и (i+1)-м пунктами;

τ_j – время оформления таможенных документов в j-м пункте;

Θ_k - время погрузки, разгрузки и складирования в k-ом пункте;

A, B, C – количество участков движения автомобиля, пунктов таможенного оформления и пунктов погрузки-разгрузки соответственно.

Формула (14) расчета времени в рейсе не учитывает специфику международных перевозок: во-первых, ограничением режима труда и отдыха водителя или экипажа согласно ЕСТР; во-вторых, запретами (ограничениями) на движение большегрузных автомобилей по территории некоторых европейских стран в выходные и праздничные дни; в-третьих, необходимостью проведения ремонтно-профилактических воздействий, в частности, устранением отказов, а также другими причинами простоя на линии, например, поверками дорожной полицией нагрузок на оси, которые входят в период производственной деятельности водителя в течение рабочего дня, иной, чем управление автомобилем.

Таким образом, формула (14) для общей продолжительности рейса должна быть откорректирована с учетом вышеуказанных факторов и представлена в виде:

((15)

 

где φ_i – случайная составляющая, отражающая увеличение времени рейса для проведения ремонтно-профилактических воздействий и других причин;

ψ_m – случайная составляющая, отражающая ограничения связанные с ЕСТР;

η_n – случайная составляющая, отражающая запреты на движения большегрузных автомобилей;

D, E, F –число случаев простоя автомобиля с учетом указанных факторов, соответственно.

Рассчитанное значение времени рейса позволяет определить гарантированный срок доставки груза потребителю.

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

Особенностью расчета времени рейса и в наряде по формулам (13) и (15) являются нелинейность, из-за ограничений, связанных с ЕСТР, режимом работы складов и т.д., и случайного характера временных составляющих перевозочного процесса.

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

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

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

Для иллюстрации предложенного алгоритма рассмотрим пример.

Из пунктов a₁ и a₂ необходимо доставить груз в пункты b₁ – b₁₅ в требуемом количестве (табл. 19). Согласно алгоритму (рис. 8) на втором этапе определяется схема доставки. В соответствии с предложенной в табл. 18 классификацией при доставке груза используется схема "многие – ко – многим".

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

 

 

Таблица 19