Источник: http://science.ncstu.ru/conf/past/2010/sc-potential/theses/mtransp/27.pdf/file_download
Математическая модель движения транспортных потоков [1-3] позволяет упрощенно, но с приемлемой точностью моделировать движение автотранспортных средств по улично-дорожной сети.
Основополагающей при разработке модели являлась гипотеза о распределении интервалов по времени между подряд идущими автомобилями по закону Эрланга k-го порядка. Проведенные экспериментальные исследования подтвердили эту гипотезу при интенсивности по одной полосе движения до 300 авт /ч и значении k=2.
Время движения по данному маршруту улично-дорожной сети складывается из времени движения между двумя соседними перекрестками и времени, теряемом у перекрестка на ожидание возможности продолжить движение в требуемом направлении (задержки у перекрестка). Вся улично-дорожная сеть города, как обычно, может быть представлена в виде ориентированного графа, вершинами которого являются перекрестки. При программной реализации в среде DELPHI это может быть карта населенного пункта, нанесенная на форму, с помеченными при помощи кнопок перекрестками. При активации кнопки переменным присваиваются названия пересекающихся улиц.
Необходимую для расчетов информацию об улично-дорожной сети конкретного населенного
пункта предлагается хранить в двух связанных таблицах базы данных, структура которых
представлена ниже.
Структура таблицы Streets базы данных MSAccess:
1) № - номер квартала (дуги графа) в улично-дорожной сети, соединяющего перекрестки I и II;
2) S1 и S2 – пересекающиеся улицы, образующие перекресток I (вершину I графа);
3) S3 и S4 – пересекающиеся улицы, образующие перекресток II (вершину II графа);
4) Control – наличие светофорного регулирования;
5) Priority – главная или второстепенная улица;
6) Length – длина квартала;
7) Col – количество полос для движения;
8) IntA1, IntA2 и т.д. – интенсивность по полосам в направлении А;
9) IntВ1, IntВ2 и т.д. – интенсивность по полосам в направлении В;
10) A left, A right – возможность поворотов при движении в направлении А;
11) B left, B right - возможность поворотов при движении в направлении В.
Структура таблицы Intersections базы данных MSAccess:
1) № - совпадает с номером квартала, соединяющего перекрестки I и II в таблице Streets;
2) S1 и S2 – пересекающиеся улицы, образующие перекресток I (вершину I графа);
3) IntC line1, IntC line2 и т.д. – интенсивность по полосам в направлении С улицы, пересекающей
перекресток I;
4) IntD line1, IntD line2 и т.д. – интенсивность по полосам в направлении D улицы, пересекающей
перекресток I.
Для решения задачи отыскания кратчайшего маршрута между двумя пунктами мы будем
использовать алгоритм, предложенный Е. Декстроем. Он представляет собой итерационную
процедуру, в которой каждой вершине присваивается метка – либо постоянная и при этом
показывающая «расстояние» от этого узла до выделенного, либо временная, где это «расстояние»
оценивается сверху.
Каждой дуге графа соответствует число L(x, y) – «длина» дуги, если вершины не соединены
дугой, то L(x, y)=~. Требуется найти кратчайший путь, соединяющий данные вершины s и t.
В ходе выполнения алгоритма окрашивают вершины и дуги графа и вычисляют величины d(x),
равные кратчайшему пути из вершины s в вершину х, включающему только окрашенные вершины.
В нашем случае L(x, y) – время движения от перекрестка х до перекрестка y с учетом задержки
на перекрестке х.
Запрос в базу данных в приведенном ниже алгоритме удобно выполнить в виде отдельной
процедуры. Также в качестве отдельных процедур рекомендуется оформить определение показателей
эффективности организации движения на регулируемом и нерегулируемом перекрестках [2].
Необходимые для работы программы данные будут храниться в двух массивах записей: MPlus
(данные о перекрестках, имеющих постоянные метки) и MMinus (данные о перекрестках, имеющих
временные метки). Поля записей следующие:
Str1 – улица, по которой совершалось движение до данного перекрестка;
Str2 – улица, пересекающая Str1;
TimeCr – время движения d(x) до данного перекрестка от начальной точки маршрута;
Trassa - перечень пройденных перекрестков.
В списке констант введем постоянную величину XXL=1000 000 000.
Алгоритм определения оптимального пути между двумя точками населенного пункта:
1-й шаг. Задаем начало и конец маршрута нажатием соответствующих кнопок на карте
населенного пункта. Перекресток – начало пути заносим в массив MPlus под номером n=0 и в массив
MMinus под номером 4n.
2-й шаг. Выбираем из базы данных все перекрестки, смежные с перекрестком № n, и заносим в
массив MMinus данные о них под номерами (4n+1), (4n+2), (4n+3). В таблице Streets базы данных
обязательно есть соответствующая строка, если перекрестки x и y соседние, и содержатся данные о
том, разрешено ли движение из x в y .
Если такая строка отсутствует, то L(x, y)=XXL. Если строка есть, но движение в этом
направлении запрещено, то L(x, y)= XXL..
3-й шаг. Рассчитываем время движения от перекрестка № n до всех смежных с ним, не
занесенных в массив MPlus.
4-й шаг. Выбираем минимальный элемент в поле MMinus.TimeCr и заносим данные о
соответствующем перекрестке в массив MPlus под номером (n+1). Из массива MMinus данные об
этом перекрестке удаляем.
5-й шаг. Повторяем шаги 2 – 4 до тех пор, пока перекресток № (n+1) в массиве MPlus не совпадет
с концом маршрута. Если перекресток № (n+1) в массиве MPlus совпал с концом маршрута, то
расчеты заканчиваем.
6-й шаг. Выводим на экран массив MPlus – список перекрестков, через которые пролегает
кратчайший маршрут между двумя данными точками населенного пункта.
Апробация данного алгоритма показала его адекватность. Его использование позволит
выбирать оптимальный маршрут движения с учетом «пробок».