1.1 Выбор и обоснование маршрутов движения

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

В настоящее время имеется несколько методов решения задачи маршрутизации перевозок:

· метод совмещенных матриц;

· метод таблиц связей;

· метод с применением общей задачи линейного программирования.

При решении задачи данной работы применен метод совмещенных матриц. Он состоит из следующих этапов:

· получение оптимального плана порожних ездок.

· совмещение оптимального плана порожних ездок с заданным планом перевозок и формирование маршрутов.

Для маршрутизации перевозок, согласно заказам на перевозку грузов, составляют заявочную матрицу (табл.3.2). (При составлении заявочной матрицы грузы разного класса приводят к I классу делением данного объёма перевозок грузов на соответствующий коэффициент, характеризующий классность груза), в которой записываются следующие данные:

· наименование заказчика автотранспорта.

· адрес погрузки разгрузки груза.

· наименование перевозимого груза.

· объем перевозимого груза.

Таблица 1 Планируемый годовой объем перевозок

Примечание. Далее в таблицах названия городов будут сокращены до одной заглавной буквы.

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

Таблица 2 Заявочная матрица для маршрутизации перевозок

На основании заявочной матрицы строится рабочая матрица (табл.3.3.).

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

Целесообразно располагать в табл. 3.3 поставщиков и потребителей грузов в порядке нарастания расстояний от пункта с наибольшим грузооборотом.

Таблица 3 Рабочая матрица

Решение рабочей матрицы производится следующим образом: последовательно, начиная с первой строки, отыскивается в каждой строке - минимальное и следующее за ним по величине расстояние. Разница между числами записывается в дополнительный столбец. Эта разница вносится в соответствующую клетку дополнительного столбца (табл.3.3). Аналогичные операции производятся по столбцам, и результаты расчетов вносятся в соответствующие клетки дополнительной строки матрицы.

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

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

Если полностью удовлетворена потребность потребителя, то все клетки данного столбца вычеркиваются знаком «*» и в дальнейших расчетах не используются. В дополнительном столбце ставится знак «К» - конец.

При заполнении (загрузке) клеток могут встретиться следующие случаи:

1. Одновременно удовлетворяется потребность потребителя в тоннах и полностью вывезен груз у поставщика. В данном случае вычеркиваются знаком «*» все клетки строки и столбца, соответствующих минимальному расстоянию перевозки. В клетках дополнительных граф матрицы, соответствующих данной строке и столбцу, ставится знак «К» - конец. После чего разницы между минимальными и следующими за ними расстояниями отыскиваются по всем остальным строкам и столбцам. Вычеркнутые клетки при нахождении разностей во внимание не принимаются. Если разницы изменились, то на их место ставятся новые, а старые зачеркиваются и решение продолжается в том же порядке.

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

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

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

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

V-U=C

Все потенциалы определяются следующим образом. Для одного из столбцов (отправитель) принимает потенциал «U», равным нулю. При этом целесообразно приравнивать к нулю потенциал того столбца, в котором имеется загруженная клетка с наибольшим расстоянием. Остальные потенциалы определяют по загруженным клеткам исходя из следующих формул:

Для столбцов U=V-C

Для строк V=U+C.

Таблица 4 Матрица для проверки оптимальности распределения

Примечание:

1. К определению потенциалов приступают при условии, если число загруженных клеток в матрице будет равно m+n-1, где m - число основных строк, n - число основных столбцов.

2. Если число загруженных клеток меньше числа m+n-1 то необходимо искусственно загрузить недостающее количество клеток матрицы, записывая в них 0 (нуль). В последующих расчетах эта клетка считается загруженной. Нулевая не повлияет на баланс наличия и потребности груза. Нуль следует ставить в ту клетку, которая лежит на пересечении строки и столбца, не имеющих потенциалы, со строкой или столбцом, для которых потенциалы уже определены.

3. Если число загруженных клеток больше числа m+n-1, или при неправильной загрузке клеток матрицы, то определяемые потенциалы будут неоднозначными. Для ликвидации неоднозначного потенциала строится замкнутый контур. Такое решение задачи обязательно приведет к ликвидации одной из загруженных клеток и тем самым к однозначному определению потенциала.

После определения всех потенциалов рассматривают все незагруженные клетки и среди них отыскивают такие, для которых разность между соответствующими им потенциалами будет больше расстояния, указанного в этой клетке, т.е. V-U>C. Для каждой такой клетки определяется число d=V-U-C.

Такие подсчеты производятся для всех незагруженных клеток. Рассматривая таким образом все незагруженные клетки не находим клеток с положительным значением d. Значит, получено оптимальное распределение.

Примечание: если обнаруживается положительное значение, то его покажем непосредственным в левых углах соответствующих клеток таблицы цифрами в кружках. Наличие таких клеток показывает, что распределение не является оптимальным и его можно улучшить, т.е. можно найти более лучший план перевозок. Чтобы улучшить полученный план перевозок, находят клетку с максимальным числом d в кружке и для этой клетки строят «контур». Вычисления последовательно ведут до тех пор, пока имеются клетки, где есть положительные значения d. Их отсутствие показывает, что улучшить распределение нельзя, что оно является оптимальным.

Результаты полученного решения (см. табл. 5) вносят в заявочную матрицу (табл. 2) и получают совмещенную матрицу (табл. 6). После этого приступают к составлению маршрутов.

Таблица 5 Совмещенная матрица

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

Маршрут №1 Сев. > Сим. ? > Сев. = 240 тыс. тонн

Маршрут №2 Сев. > А. ? > Сев. = 160 тыс. тонн

Маршрут №3 Сим. > Б. ? > Сим. = 10 тыс. тонн

Маршрут №4 Б. > Ф. ? > Б. = 10 тыс. тонн

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

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

Таблица 6 Получение маршрутов №5 А.> Сев.> А. = 80 тыс. тонн

№6 Б.> Ф.> Б. = 100 тыс. тонн

Таблица 7 Получение маршрута № 7 Ф.>Сим.> Б. > Ф. = 20 тыс. тонн

Таблица 8 Получение маршрута №8 Сев. > Сим. > А. >Сев. = 80 тыс. тонн

Таблица 9 Получение маршрута №9 Ф. > Сим. > А. > Ф. = 10 тыс. тонн

Таблица 10 Получение маршрута № 10 Ф. > Сим. > Б. > А. > Ф. = 120 тыс. тонн

Таблица 12 Расшифровка полученных маршрутов движения автомобилей