Составление рациональных маршрутов

при помашинных отправках

Задача составления рациональных маршрутов особенно актуальна при перевозках массовых грузов. Целевой функцией задачи является минимизация порожних пробегов. Порядок решения такой задачи рассматриваем непосредственно на примере (табл. 13.24).

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

Например, располагая автомобилем-самосвалом ЗиЛ-4503 грузоподъемностью 4,5 т и учитывая значение коэффициента использования грузоподъемности для разных грузов (для опилок γ = 0,5, для остальных грузов γ = 1), задание на перевозки представим в виде табл. 13.25.

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

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

Оптимальный план холостых ездок можно получить, решая транспортную задачу линейного программирования относительно холостых ездок, для чего грузополучателей считают поставщиками порожнего подвижного состава, а грузо-отправителей – соответственно получателями такого подвиж-ного состава. Кроме того, под обозначениями грузоотправителей и грузополучателей указываются расстояния от них до АТП. Холостые ездки для отличия их от груженых обозначают числом в скобках. Результат решения транспортной задачи относительно холостых ездок представлен в табл. 13.26.

В эту же матрицу заносят груженые ездки, которые необходимо выполнить в соответствии с планом, составленным по заявкам грузовладельцев (см. табл. 13.25). Груженые ездки показаны курсивом (табл. 13.27).

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

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

№ 1 А₁Б₂– Б₂А₁ – 5 ездок;

№ 2 А₂Б₄– Б₄А₂ – 5 ездок;

№ 3 А₄Б₅– Б₅А₄ – 6 ездок;

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

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

Контур, представленный в табл. 13.29 (А₃Б₁–А₃Б₂–А₂Б₂–А₂Б₄–А₄Б₄–А₄Б₁–А₃Б₁), состоит из сплошных горизонтальных линий, соответствующих перевозке груза, и пунктирных вертикальных, которые соответствуют подаче порожнего подвижного состава. Минимальная загрузка по этому контуру составляет две ездки. Кольцевой маршрут № 4 формируют, соединяя последовательно по контуру пункты отправления и назначения (А₃Б₁–Б₁А₂–А₂Б₂–Б₂А₄–А₄Б₄–Б₄А₃); по этому маршруту планируют два оборота. Количество оборотов, включенных в маршрут, вычитают из загрузок в вершинах контура, после чего строят новый контур и формируют следующий кольцевой маршрут, пока не будут объединены все груженые и холостые ездки.

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

Для маршрута № 4 возможны три варианта начального пункта:

1) начальный пункт А₃, соответственно окончание маршрута в пункте Б₄, нулевой пробег при этом (см. расстояния АТП–А₃ – 7 км, Б₄–АТП – 5 км) l _н = 12 км;

2) пункты соответственно А₂, Б₁ , l _н = 32 км;

3) пункты А₄, Б₂ , l _н = 15 км.

Наименьшее расстояние в первом варианте, следовательно начальным пунктом на маршруте № 4 целесообразно принять пункт А₃, маршрут при этом будет заканчиваться в пункте Б₄.

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

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

Планирование маятниковых маршрутов

Необходимость рационального планирования маятниковых маршрутов вызвана тем, что, как показывает практика, по кольцевым маршрутам выполняется не более 20 % перевозок грузов, остальные – по маятниковым.

При планировании маятниковых маршрутов следует учитывать ряд факторов:

разная продолжительность рейсов на разных маршрутах;

ограничение продолжительности работы подвижного состава рабочим временем водителя (временем наряда);

ограничения по фронту и времени загрузки у грузовладельцев;

требования грузовладельцев по регулярности, времени отправки и доставки грузов (доставка «точно в срок») и другие.

Несмотря на кажущуюся простоту, планирование маятниковых маршрутов имеет ряд скрытых (на первый взгляд) возможностей по их оптимизации. К таким возможностям относят:

достижение максимальной производительности за счет полного использования рабочего времени;

сокращение холостых и нулевых пробегов при увязке маятниковых маршрутов.

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

Методику согласования маршрутов удобно пояснить непосредственно на примере. Исходные данные приведены в табл. 13.30.

Исходя из лимита рабочего времени за смену в 480 мин на выполнение данных перевозок потребуется как минимум 4 автомобиля, причем запас времени

Т _з = 4 · 480 – 1884 = 36 мин.

Выбор лучшего варианта проводят последовательным подбором маршрутов. Первый, наиболее простой, вариант можно составить методом уже упоминавшегося ранее (в транспортной задаче) северо-западного угла (табл.13.31).

При таком сочетании маршрутов для выполнения заданного объема работы потребуется выделить 5 автомобилей с расходом рабочего времени

Т _р = 5 · 480 = 2400 мин,

при полезном использовании Т _п = 1884 мин; из пяти выделяемых автомобилей один (№ 3) недогружен заданием на 60 мин, один (№ 4) – на 120 мин, последний же из выделяемых автомобилей загружен менее чем на 40 % рабочего времени.

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

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

Остаются маршруты продолжительностью 120 мин – 2 ездки и 180 мин – 4 ездки. Их целесообразно совмещать с расчетом:

Т_н = 120 + 2 · 180 = 480,

то есть одна ездка продолжительностью 120 мин и две ездки продолжительностью 180 мин.

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

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

А _э = 4 (min).

Минимизация холостых и нулевых пробегов

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

Задание на перевозку приведено на рис. 13.9. В течение смены из пункта А в пункт В₁ необходимо выполнить 12 ездок, в пункт В₂ – 50 ездок. За смену один автомобиль может выполнить по маршруту АВ₁ 3 оборота и по маршруту АВ₂ – 5 оборотов.

Для выполнения перевозок на каждом маршруте потребуется выделить подвижной состав:

на маршрут АВ₁ А _м1 = 12 / 3 = 4 авт.;

на маршрут АВ₂ А _м2 = 50 / 5 = 10 авт.

Пробег при выполнении перевозок будет следующим:

на маршруте АВ₁ l _г = 12 · 24 = 288 км,

l _н,х = 4 · (18 + 24 · 2 + 8) = 296 км;

на маршруте АВ₂ l _г = 50 · 10 = 500 км,

l _н,х = 10 · (18 + 10 · 4 + 24) = 820 км.

Коэффициент использования пробега

β = (288 + 500) / (288 + 500 + 296 + 820) = 0,418.

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

Решая данную задачу, получаем оптимальный план порожних ездок (табл. 13.34).

Полученное распределение порожних ездок показывает, что в АТП должно вернуться 12 автомобилей из пункта В₁ и 2 автомобиля из пункта В₂. Следовательно, все порожние ездки из пункта В₂ следует выполнять в пункт А.

Для выполнения этих условий работу подвижного состава следует организовать следующим образом: направить 12 автомобилей на маршрут АВ₂; после выполнения по нему по 4 оборотов последнюю ездку назначить в пункт В₁, после чего возвратить подвижной состав в АТП.

По маршруту АВ₁ будут выполнены все необходимые ездки, на маршруте АВ₂ останется выполнить 2 ездки:

n _е2 = 50 – (12 · 4) = 2.

Для этого потребуется использовать еще один автомобиль.

При выполнении перевозок таким образом суммарный непроизводительный пробег

L _н,х = 12 · (18 + 4 · 10 + 8) + 1 · (18 + 1 · 10 + 24) = 842 км.

Коэффициент использования пробега в таком случае

β = (288 + 500) / (288 + 500 + 842) = 0,483,

что на 15,5 % выше, чем в первом случае.

Оптимизация мелкопартионных перевозок грузов

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

Мелкопартионные перевозки, как правило, выполняются при транспортном обслуживании предприятий торговли и бытовом обслуживании населения.

Особенности мелкопартионных перевозок:

значительные затраты времени на передачу грузов и погрузочно-разгрузочные работы, часто большие, чем на движение;

низкие техническая и эксплуатационная скорости на маршрутах, проходящих, как правило, по загруженным магистралям в густозаселенных местах;

высокие требования к качеству перевозок: гарантия своевременной доставки («точно в срок»), сохранность грузов;

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

Задачи планирования мелкопартионных перевозок относят к классу задач дискретной оптимизации, так как теоретически возможно перебрать все варианты решений и выбрать лучший из них. Однако, если учесть, что задача объезда 10 пунктов на маршруте будет иметь более 3,5 млн. решений, естественно, такой подход к решению задачи нереален.

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

Один из таких способов, разработанный английскими специалистами Кларком и Райтом и поэтому известный как метод Кларка – Райта, применяется для решения задач мелкопартионных перевозок с одним отправителем или получателем. В данном методе используется метод функций «выгоды».

«Выгода» появляется от объединения двух маятниковых маршрутов в один кольцевой в случае, если соблюдается условие (рис. 13.10)

∆l = l ₁ + l ₂ – l ₁₂ > 0.

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

Пример. Объемы завоза и вывоза грузов, расстояния от грузоотправителя до получателей и между ними представлены в табл. 13.35. Для перевозки может быть использован подвижной состав вместимостью 240 и 160 единиц груза.

В соответствии с заданием перевозки необходимо выполнить на 9 маршрутах; суммарный пробег от пункта 0, являющегося в данном случае грузоотправителем, до всех других пунктов (1–9), являющихся пунктами доставки, составит 228 км.

В случае объединения маршрутов, например первого (0–1–0) и второго (0–2–0), возможный эффект

∆l = 10 + 4 – 8 = 6 км.

Эффект от объединения всех маршрутов попарно занесем в табл. 13.36.

Кроме того, в таблицу добавим столбец, обозначающий признак маршрута: цифра 2 обозначает, что данный пункт включен в маятниковый маршрут вида 0–i–0; цифра 1– пункт включен в кольцевой маршрут, причем данный пункт является первым или последним пунктом доставки кольцевого маршрута (центральный пункт, в нашем случае 0 в развозочно – сборном маршруте не учитывается); цифра 0 обозначает, что данный пункт является внутренним пунктом кольцевого маршрута и его нельзя использовать для объединения маршрутов.

В табл. 13.36 все маршруты маятниковые (еще не объединены), поэтому признак маршрутов для всех пунктов – 2.

Анализируя матрицу выигрышей, приходим к заключению, что максимальную выгоду, равную 27, можно получить, объединяя маршруты 0–4–0 и 0–6–0 и маршруты 0–4–0 и 0–9–0. При объединении первой пары маршрутов (0–4–0 и 0–6–0) суммарное количество груза по ввозу 75 + 95 = 170 ед., по вывозу 45 + 30 = 75 ед.

Следовательно, на данный маршрут следует назначать автомобиль грузоподъемностью 240 единиц, но следует помнить, что он при этом недогружен (240 – 170 = 70 ед. груза). Количество ввозимого и вывозимого груза проставляем в соответствующих столбцах напротив пунктов 4 и 6; признаком маршрута для этих пунктов становится 1, так как пункты являются первым или последним пунктом на маршруте; маршруту присвоим номер 1 (табл. 13.37).

Далее рассмотрим возможность объединения маршрута 0–9–0 с полученным 0–4–6–0, так как в этом случае «выгода» будет максимальной (выгода от объединения маршрутов 0–4–0 и 0–9–0 равна 27). Для объединенного маршрута ввоз составит 230 ед., вывоз 85 ед., то есть перевозку на маршруте можно выполнить автомобилем грузоподъемностью 240 ед.. Пункт 4 становится внутренним пунктом маршрута (к нему присоединяем маршрут 0–9–0), поэтому присваиваем ему признак 0, а пункту 9 присваиваем признак 1 (табл. 13.38).

При последующем рассмотрении матрицы выигрышей можно объединить маршруты 0–7–0 и 0–8–0, после чего к маршруту 0–7–8–0 присоединить маршрут 0–5–0, присвоить маршруту 0–7–8–5–0 номер 2, затем объединить маршруты 0–2–0 и 0–3–0, присвоить маршруту 0–2–3–0 номер 3, маршрут 0–1–0 остается маятниковым, так как при присоединении его к любому из сформированных маршрутов количество груза превышает грузоподъемность подвижного состава.

Окончательный вариант объединения маршрутов представлен в табл. 13.39.

Таким образом, получены 4 маршрута организации перевозок:

маршрут № 1 – 0–6–4–9–0, загрузка на развоз 230 ед., сбор груза – 85 ед.;

маршрут № 2 – 0–7–8–5–0, загрузка на развоз 210 ед., сбор груза – 50 ед.;

маршрут № 3 – 0–2–3–0, загрузка на развоз 140 ед., сбор груза – 80 ед.;

маршрут № 4 – 0–1–0, маятниковый, загрузка на ввоз 110 ед., сбор груза – 25 ед.

Пробег при выполнении перевозок по объединенным маршрутам будет следующим: № 1 – 54 км, № 2 – 31 км, № 3 – 16 км, № 4 – 20 км, всего – 121 км, что на 107 км меньше, чем при выполнении перевозок по маятниковым маршрутам.

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

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

Один из наиболее простых методов решения такой задачи – метод сумм.

В качестве примера определим оптимальный вариант объезда пунктов маршрута 0–6–4–9–0. Для этого построим матрицу кратчайших расстояний между пунктами маршрута (табл. 13.40), в итоговой строке которой проставим сумму расстояний по каждому столбцу.

По итоговой строке выбираем три пункта, имеющих наибольшие суммы в итоговой строке; в нашем случае это пункты 0, 6, 9. Они образуют кольцевой маршрут 0–6–9–0, в который необходимо вставить пункт со следующей максимальной суммой в итоговой строке. В данном примере это пункт 4, но его необходимо вставить между пунктами на маршруте так, чтобы увеличение расстояния перевозок было минимальным.

Увеличение длины маршрута находят по формуле

(13.16)

где i, j – пункты, между которыми предполагается вставить

новый пункт в маршрут;

k – вставляемый в маршрут пункт;

l _ik, l _kj, l _ij – расстояния между соответствующими пунктами.

Увеличение длины маршрута 0–6–9–0, если вставить дополнительно пункт 4, будет следующим:

∆l ₀₆ = l ₀₄ + l ₄₆ – l ₀₆ = 15 + 4 – 16 = 3,

∆l ₆₉ = l ₆₄ + l ₄₉ – l ₆₉ = 4 + 11 – 15 = 0,

∆l ₉₀ = l ₉₄ + l ₄₀ – l₉₀ = 11 + 15 – 23 = 3.

Минимальное увеличение длины маршрута определяет место вставки нового пункта в маршрут; в нашем примере это вставка пункта 4 между пунктами 6 и 9, при этом ∆l = 0. Следовательно, целесообразно назначить маршрут 0–6–4–9–0.