Организация автомобильных перевозок (основа)

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

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

Один из методов решения задачи приведен в качестве примера [Геронимус Б.

Л. Экономико -математические методы в планировании на автомобильном транспорте. – М.: Транспорт, 1972. , с. 16–24].

Пусть необходимо определить кратчайшие расстояния от вершины 1 до всех остальных, показанных на рис. 9.6. Из схемы следует, что известно расстояние до вершины 1 (оно равно нулю) и от первой вершины до смежных с ней вершин (2, 3 и 6).

Вершина 4 также имеет связь с вершиной 1, но эта связь односторонняя, поэтому от вершины 1 с вершиной 4 связи нет.

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

Вершина 1 начальная, расстояние до нее равно нулю, ее считают в первой группе;

вершинам 2, 3 и 6 предшествует вершина 1, расстояния до них соответственно 3, 2 и 8

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

предшествующей вершины для них пока также нет, проставляем 0.

Таблица 9.1

Расчет кратчайших расстояний (этап 1)

Из расстояний до вершин второй группы наименьшее – до верши-ны 3, эту вершину из второй группы можно перевести в первую, кратчайшее расстояние до нее r3 = 2.

На следующем этапе определяют вершины, смежные с вершиной 3: это вершины

1, 2, 4, 5. Вершина 1 входит в первую группу, ее во внимание не принимают.

Расстояния до остальных вершин определяют по формуле

111

Вершина 2 уже во второй группе, расстояние до нее больше, чем записано в табл.

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

Таблица 9.2

Расчет кратчайших расстояний (этап 2)

Из вершин второй группы (2, 4, 5, 6) кратчайшее расстояние до вершины 2; ее переводят в первую группу, расстояние до нее r2 = 3.

Далее начинается следующий этап по определению вершин, смежных с вершиной

2, и расстояний до них. Результаты последующих расчетов приведены в табл. 9.3 – 9.6.

Таблица 9.3

112

Таблица 9.5

Расчет кратчайших расстояний (этап 5)

В последней таблице (табл. 9.6) указаны кратчайшие расстояния от всех вершин до вершины 1 и номера предшествующих вершин. По данным этой таблицы можно определить кратчайший маршрут, перебирая последовательно предшествующие вершины. Из всех вершин наиболее удалена от начальной вершина 7, ей предшествует вершина 8, затем вершины 6, 4, 3, 1. Таким образом, кратчайший путь от вершины 1 к

вершине 7 проходит через вершины 3, 4, 6, 8. Кратчайшие маршруты показаны на рис.

9.7.

Рис. 9.7. Кратчайшие пути от вершины 1

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

В табл. 9.7 показан первый шаг расчета: смежные с вершиной 1 вершины 2, 3, 6,

потенциалы их соответственно П2 = 3, П3 = 2, П6 = 8.

Таблица 9.7

113

Минимальное значение потенциала у вершины 3 (выделен курсивом П3 = 2);

вершину 3 переводим в первую группу, смежные с ней вершины – 2, 5, 4; определяем их потенциалы и сравниваем с уже определенными ранее.

Потенциал вершины 2 П2 = 7; ранее его определили (П2 = 3), следовательно,

значение потенциала П2 = 7 во внимание не принимаем.

Значения потенциалов П5 = 8 и П4 = 4 заносим в строку вершины 3 (табл. 9.8).

8 больше, чем П3 = 2 в строке вершины 1; его во внимание не принимаем (табл. 9.9).

Таблица 9.9

Расчет потенциалов (этап 3)

После этого вновь определяем вершину с наименьшим потенциалом (П4 = 4),

переводим вершину 4 в первую группу и процесс повторяется. Результат расчета приведен в табл. 9.10.

Кратчайшие расстояния до всех вершин определены.

114

8.3.Задачи маршрутизации при перевозках

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

Ранее (тема 6) указывалось, что при составлении маршрутов возможны разные подходы к закреплению автомобилей на маршрутах:

в случае, когда автомобили (группы автомобилей) закрепляются за поставщиками, работа организуется, как правило, по маятниковым маршрутам (l г = l х),

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

0,5

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

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

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

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

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

115

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

Например, располагая автомобилем-самосвалом ЗиЛ-4503 грузоподъемностью 4,5

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

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

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

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

116

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

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

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

Таблица 9.26

Оптимальный план холостых ездок

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

Груженые ездки показаны курсивом (табл. 9.27).

117

Таблица 9.27

Совмещенная матрица

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

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

В данном примере можно формировать маятниковые маршруты:

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

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

№3 А4Б5– Б5А4 – 6 ездок;

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

118

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

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

119

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

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

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

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

3)пункты А4, Б2 , l н = 15 км.

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

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

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

120