2.4 Формирование путей передвижения пассажиров на маршрутной сети (кратчайших путей на графе беспересадочных поездок)

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

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

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

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

В то же время единственность выбранного пути существует, как правило, только в субъективном восприятии пассажира и может трактоваться исключительно в геометрическом смысле. Реальный участник движения при наличии альтернативных попутных маршрутов в разные дни для поездки выбирает и разные маршруты - проще говоря, садится в первый подошедший. Таким образом, субъективно единственному пути на маршрутном графе соответствует пучок путей. Напомним, что маршрутным графом принято называть объединение графов, соответствующих сетям всех видов ОПТ, дополненное дугами посадок и пересадок.

На первый взгляд, достаточно построить кратчайшие пути на маршрутном графе. Однако при ближайшем рассмотрении такой подход оказывается неприемлемым в силу следующего обстоятельства. Каждому пути на маршрутном графе соответствует стратегия вида: “От пункта А до пункта В на маршруте Х, далее - на маршруте ...”.Реальной же стратегии пассажира более соответствует “От пункта А до пункта В на маршрутах Х1 или Х2 или Х3 ..., далее на Y1 или Y2...”. Более того, при построении пути на маршрутном графе возникает существенная ошибка при вычислении длины пути, источник которой ясен из следующего простого примера. Пусть два пункта на сети связаны двумя маршрутами, время проезда одинаково - например, 10 минут, интервал тоже одинаков- например, 8 минут. На маршрутном графе связи между этими двумя пунктами будут соответствовать два пути, отражающих поездки по каждому маршруту, и длина каждого пути будет равна 10+8/2 = 14 минут. Реальное же время ожидания подходящего маршрута будет оцениваться величиной 2 минуты, а общее время поездки 12 минут. Еще хуже ситуация, если на одном из маршрутов интервал увеличится до, например, 12 минут. Поездке по такому маршруту будет соответствовать путь длиной 16 минут, который вообще не выберется в качестве кратчайшего. То же произойдет и при снижении скорости на одном из маршрутов - он выпадает из пучка кратчайших путей. Реальный же пассажир, безусловно, будет использовать такие маршруты, что приведет к сокращению времени по сравнению с псевдократчайшими 14-ю минутами.

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

В предлагаемой модели длины ребер ГБП задаются в соответствии с выражениями (2.35)-(2.37).

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

С учетом сказанного необходимо отметить еще одно преимущество ГБП перед маршрутным графом: он имеет существенно меньшую размерность, и кратчайшие пути на нем строятся с меньшими затратами вычислительных ресурсов.

Для построения кратчайших путей на ГБП предлагается использовать алгоритм кругового расширения, который и реализован в АРМ МАРС.