Файл: Воркут А.И. Автомобильные перевозки партионных грузов учеб. пособие.pdf

Вычеркиваем прежнее значение /3 = 4,2 и записываем его новое значение 1'ъ = 2,4.

Для пятого и шестого столбца

//^ 1ц .

Врезультате внесенных изменений получаем табл. 25. Так как при внесении изменений // и lt могут только

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

116

Для клеток (3, 5) и (3, 6) условие оптимальности на­ рушено. Вносим изменение

4 = 4 + 4—5 = 3,6,

4 — 4 ~Ь 4—6 = 4,8.

Получаем табл. 26, в которой проверяем на оптималь­ ность заполненные клетки 5 и 6 столбца, не находящиеся на пересечении, соответственно с 5-й и 6-й строками. Такая клетка одна (5, 6)

4 — 4 ~ 4 2 > 4-6-

Вносим изменение

4 = 4 + 4—6 == 4,8.

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

117

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

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

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

Pi Р* Р3 Р5 Ре*

длина которого составит 4,2 км.

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

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

§ 6. РАСЧЕТЫ РАЦИОНАЛЬНЫХ РАЗВОЗОЧНЫХ МАРШРУТОВ НА ЭВМ

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

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

118

«

Набор пунктов продолжается до тех пор, пока не нару­ шится условие

"з

2 gpi “С <7-

г=1

После выполнения этого условия набор для данного мар­ шрута прекращается.

Параллельно с набором пунктов в маршрут определяют порядок объезда пунктов. Для определения последователь­ ности объезда пунктов могут быть использованы различные алгоритмы, например метод последовательного включения пунктов, рассмотренный в § 3 этой главы.

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

Ниже излагается программа, разработанная в вычисли­ тельном центре Главмосавтотранса [4]. Она состоит из двух частей (подпрограмм), первая из которых вычисляет функцию набора пунктов в маршруты, а вторая на основе вычислений в первой части подбирает пункты в маршруты исходя из грузоподъемности подвижного состава и времени нахождения автомобиля в наряде, и одновременно опреде­ ляет порядок объезда пунктов.

Программа состоит из шести зон, две из которых с ис­ ходными данными меняются.

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

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

119

Таблица 28

Пример решения задачи развоза мелких партий грузов

грузоподъемности автомобилей; количество автомобилей по каждому из возможных типов;

время простоя автомобилей под погрузкой и вы­ грузкой на 1 т груза и дополнительное время на каждый заезд; время нахождения автомобилей в наряде для одно­

сменных (обычно 7 ч), двухсменных, полуторосменных автомобилей.

Основные параметры программы: Общее число пунктов п •< 802,

Число пунктов завоза на маршруте п3 < 40, Число типов подвижного состава /V < 7.

Время работы программы в минутах, можно принять как

( = 1,2п + т,

120