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

На заключительном этапе в матрице всегда остается только один элемент, который может быть включен в мар­ шрут. В нашем примере это элемент А — 1 (табл. 21).

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

Таблица 21

В результате записываем рекомендуемый развозочный маршрут

Л — 1 — 3 — 2 — 4 — Л,

его длина

/л—1 ~h h—з ~h h—2 4 —4 + Ц — а — 15,9 км

на 1,5 км меньше длины маршрута Л —3—2—1—4—Л, выбранного нами ранее по кратчайшей связывающей сети

. и методом суммирования по столбцам.

§5. МОДЕЛИРОВАНИЕ ТРАНСПОРТНЫХ СЕТЕЙ

ИОПРЕДЕЛЕНИЕ КРАТЧАЙШИХ РАССТОЯНИЙ

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

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

110

Научную основу для решения этой задачи дает математи­ ческая теория графов.

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

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

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

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

I ll

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

h — h + hi

и вносим его в клетки с номером / левого столбца и верхней строки таблицы.

В силу связанности сети все числа /; и lt (i, / = 1,2, 6 ) можно найти.

* Излагается матричный вариант алгоритма Форда [27],

Таблица 24

а затем исправляем /г в соответствующем столбце.

Этот процесс повторяется до тех пор, пока для всех клеток, где lt известно, // — h < h/. Тогда числа lj и lt определяют кратчайшие расстояния от точки Рг до всех остальных.

Для заполненных клеток первого столбца (табл. 24)

114