Содержание к диссертации
Введение
Глава 1. Особенности городской дорожно-транспортной системы 10
1.1. Обзор существующих методик 12
1.2. Выводы 14
Глава 2. Моделирование пассажиропотоков 15
2.1. Задача определения показателей подвижности населения 15
2.2. Модель системы с пассажиропотоками 16
2.3. Модель системы для небольшого количества остановок 19
2.4. Модель системы, состоящей из десяти остановок 23
2.5. Программная реализация вычисления характеристик пассажиропотоков в транспортных системах 25
2.6. Выводы и перспективы 26
Глава 3. Моделирование потоков общественного транспорта 28
3.1. Модель системы с общественным транспортом 29
3.2. Оптимизация работы общественного транспорта 31
3.2.1. Формирование исходных данных о транспортной системе 32
3.2.2. Особенности построения алгоритма для поиска равновесного решения 38
3.2.3. Численная реализация алгоритма поиска равновесного решения 40
3.3. Примеры оптимизации работы общественного транспорта 42
3.4. Выводы и перспективы 49
Глава 4. Моделирование транспортных потоков 50
4.1. Задача распределения транспортных потоков 50
4.2. Модель транспортной сети 51
4.3. BPR-функция задержки потока 54
4.4. BPR-функция задержки потока для системы из трех маршрутов 61
4.5. Выводы 67
Глава 5. Конкуренция среди сервисов, предоставляющих дополнительные услуги
5.1. Задача определения равновесных цен на примере парковочного сервиса 69
5.2. Модель системы с дополнительными сервисами 70
5.3. Модель с фиксированным значением pi, / = 1, 2 71
5.3.1. Симметричный случай 72
5.3.2. Несимметричный случай 75
5.3.3. Численные эксперименты 78
5.4. Модель с гибким значением pi, і = 1, 2 81
5.4.1. Имитационная модель системы 85
5.4.2. Численные эксперименты, практическое применение 86
5.5. Выводы 89
Глава 6. Парадокс Браесса в транспортных системах 90
6.1. Задача поиска парадокса Браесса на городских дорогах 91
6.2. Модель системы E-net 92
6.3. Динамическое пользовательское равновесие 94
6.4. Особенности определения парадокса Браесса 99
6.5. Парадокс Браесса в модели E-net 100
6.6. Пример появления парадокса на городских дорогах 105
6.7. Поиск парадокса Браесса для модели с новой дорогой 106
6.8. Пример появления парадокса для модели с новой дорогой 111
6.9. Выводы 112
- Программная реализация вычисления характеристик пассажиропотоков в транспортных системах
- Особенности построения алгоритма для поиска равновесного решения
- BPR-функция задержки потока для системы из трех маршрутов
- Численные эксперименты, практическое применение
Программная реализация вычисления характеристик пассажиропотоков в транспортных системах
Для поиска равновесных решений для K = 5, K = 10 была разработана программа по вычислению характеристик пассажиропотоков в транспортных системах. Программа позволяет получить оценку распределения входящих на каждой остановке пассажиров по последующим остановкам маршрутов на основе информации о входящих и выходящих из общественного транспорта пассажирах. Информация о пассажирах определяется путем проведения натурных наблюдений в автобусах, либо при помощи фиксации количества пассажиров специальными автоматами, установленными на входе и выходе [35].
Для получения оценки распределения пассажиропотоков разработана программа, которая состоит из двух модулей. Первый модуль позволяет генерировать экспериментальные пассажиропотоки на основе известных данных о среднем количестве пассажиров на остановках. Для K = 5, K = 10 путем проведения натурных наблюдений были получены численные значения пассажиропотоков на остановках. Для каждой остановки количество вошедших в автобус пассажиров изменяется в некоторых пределах. Так, например, для K = 10 количество вошедших в автобус пассажиров на первой остановке колеблется от 4 до 6. Количество вышедших пассажиров на каждой остановке также изменяется в некоторых пределах, например, для второй остановки (на первой остановке никто не выходит) этот предел составляет от 2 до 3. Аналогичная ситуация складывается на всех остановках. На основании заданных пределов для каждой остановки программа генерирует экспериментальные значения пассажиропотоков, при этом распределение пассажиропотоков на каждой остановке равномерное, различными для остановок являются только отрезки, на которых задается это распределение. Количество необходимых экспериментов определяет пользователь. Все полученные экспериментальные значения пассажиропотоков записываются в текстовый файл формата .txt. В файле данные по каждому эксперименту представлены отдельной строкой. Модуль является вспомогательным и может использоваться при недостатке натурных наблюдений за пассажирами в автобусах.
Для обработки значений численных экспериментов (результатов натурных наблюдений, либо данных модуля генерации экспериментов) разработан модуль, который позволяет определить доли пассажиров и направления, по которым хотят переместиться эти доли. Поиск решения осуществляется либо при помощи метода наименьших квадратов, либо при помощи метода минимизации абсолютных величин разностей. Результат работы модуля представлен в виде таблицы, где для каждого пассажиропотока указаны начальная и конечная остановки.
На примерах для K = 5, K = 10 продемонстрирована методика определения пассажиропотоков между различными остановками. Величины пассажиропотоков найдены при помощи методов наименьших квадратов и минимизации абсолютных величин разностей.
Таким образом, использование программы позволяет делать прогнозы относительно подвижности населения. Заметим, что предложенная процедура определения пассажиропотоков легко реализуема на практике. Например, в автобусах в больших городах пассажиры входят на остановке в первую дверь и регистрируют свой билет в специальном автомате. Выход осуществляется через другие двери, где можно просто установить дополнительные фиксирующие устройства [35]. Глава 3. Моделирование потоков общественного транспорта В связи с увеличением объемов перевозок пассажиров по различным маршрутам в последнее время особенно актуальной становится задача моделирования потоков общественного транспорта. Бывает, в результате неудачной организации пассажирских перевозок между различными районами города в некоторые районы невозможно добраться только одним маршрутом или, крайне проблематично уехать из такого района в силу небольшого количества общественного транспорта. Соответственно, для пассажиров появляется проблема, связанная с большим периодом ожидания подходящего автобуса, а с другой стороны, если увеличить количество автобусов на маршруте, для транспортных операторов (перевозчиков) может появиться проблема убыточности рейсов. Поэтому необходимо всестороннее исследование проблемы. Так в работах М. Е. Антошвили, С. Ю. Либермана, И. В. Спирина, Г. А. Варелопуло, В. А. Гудкова, Л. Б. Миротина [3, 14, 17, 67] доказывается, что поиск оптимального значения интенсивности движения транспортных средств по маршрутам необходимо выполнять, учитывая интересы и транспортных предприятий, и пассажиров. В работах М. Е. Корягина и А. П. Лопатина [23, 29, 24, 25] исследуются задачи поиска оптимальных параметров, для которых при заданных потоках, дисциплине обслуживания, стоимости показатели качества функционирования системы оптимальны. Далее в работе также будет продолжено развитие этого направления с учетом дополнительного ограничения на количество одновременно перевозимых пассажиров.
Особенности построения алгоритма для поиска равновесного решения
Для описанной выше задачи затруднительно получить решение только аналитическими методами в силу большой размерности и большого количества возможных стратегий перевозчиков, поэтому далее будет представлены основные этапы алгоритма, позволяющие найти оптимальные временные интервалы и определить доходы перевозчиков.
Прежде чем перейти к поиску равновесного решения, необходимо подготовить начальные данные, в т.ч. определить, сколько всего пассажиров нужно доставить с одной остановки на другую. Методика по сбору информации о пассажиропотоках между различными остановками представлена в главе 2. Эту информацию по передвижениям пассажиров можно описать при помощи матрицы корреспонденций, так в матрице / - начальная остановка пассажира, j - конечная. Причем, размерность такой матрицы NxN.
Информацию обо всех маршрутах движения городского пассажирского транспорта также будем представлять в виде матриц. Всего таких матриц 24, размерность каждой NxN. В матрице если с остановки под номером / можно попасть в остановку под номером j, то элемент матрицы с индексами /, j примет значение 1, иначе 0. Для обратного рейса складывается аналогичная ситуация, с той лишь разницей, что индексы /, j меняются местами.
Далее для каждого перевозчика определим свою матрицу вместимости. Это необходимо, так как на различных узлах маршрута количество пассажиров, которые перевозчик может перевезти, меняется в зависимости от того сколько пассажиров уже находится в автобусе перевозчика в данный момент. Для каждого перевозчика такая матрица будет своя, в зависимости от ограничения на количество одновременно перевозимых пассажиров. Матрица представляет собой количество свободных мест на каждой остановке маршрута. Чтобы определить это количество на остановке /, необходимо знать, сколько пассажиров село на предыдущих 1–1 остановках, с намерением попасть на /+1, /+2, .. остановки.
Например, чтобы определить, сколько пассажиров перевозчик может доставить с остановки 3 на остановку 4 (см. рисунок 3.3), необходимо знать, сколько пассажиров он перевозит с остановок 1 и 2 на остановку 4, итоговую сумму необходимо вычесть из ограничения на количество одновременно перевозимых пассажиров для этого перевозчика. Полученная таким способом величина однозначно определяет ограничение для каждой остановки на количество пассажиров, которые может перевезти транспортный оператор с этой остановки. Подобным образом пассажировместимость считается для всех перевозчиков, для каждой остановки с учетом того, что не все остановки принадлежат одному маршруту.
Для поиска решения задачи используем итерационную процедуру Курно [98], т.е. на каждом этапе алгоритма последовательно (для каждого перевозчика) будем решать задачу оптимизации стратегии одного перевозчика при фиксированных стратегиях других перевозчиков.
При решении задачи одномерной оптимизации используем метод дихотомии [7]. Этот метод хорошо зарекомендовал себя в задачах одномерной оптимизации. Основное его преимущество в простоте, а также в отсутствии необходимости вычислять производные на каждом шаге, что очень затруднительно для функции минимума.
Вычислительная сложность разработанного алгоритма О(N3 ).
На основе алгоритма, описанного ранее, была разработана программа поиска оптимальных интервалов движения автобусов по маршрутам [52, 53]. Программа написана на языке Си. Программа для заданных начальных характеристик системы позволяет определять для каждого транспортного оператора оптимальные интервалы движение его автобусов так, чтобы его прибыль была максимальной, и наибольшее количество пассажиров было перевезено. Программа также предусматривает возможность поиска оптимальных временных интервалов движения автобусов и прибыли перевозчиков, если транспортная сеть города сократится и количество маршрутов, по которым автобусы осуществляют перевозку пассажиров, станет меньше. Однако в таком случае количество перевезенных пассажиров сократится. Итоговая информация представляет собой огромные массивы числовых данных, поэтому в качестве выходных результатов программа формирует три файла с расширением txt. В файлы заносится информация относительно всех перемещений пассажиров. В файл bus_stops1.txt записывается информация о суммарном количестве пассажиров на каждой остановке. Для каждого перевозчика в программе предусмотрена детализация его маршрута по прямому и обратному направлениям. Для каждой остановки фиксируется информация о количестве вошедших и вышедших из автобуса пассажиров, эта информация заносится в файл come_leave.txt. Также для каждого перевозчика программа записывает в файл profit.txt информацию по оптимальным интервалам движения автобусов и возможную прибыль, если перевозчики не будут отклоняться от равновесных стратегий.
Полученную из файлов числовую информацию удобно рассматривать в виде графиков и таблиц. Так как эта информация периодически меняется в силу увеличения или уменьшения пассажиропотоков, изменения стоимости проезда, сокращения количества перевозчиков и т.д., было разработано приложение, которое формирует таблицы и рисует графики на основе полученных в программе файлов (bus_stops1.txt, come_leave.txt., profit.txt). С помощью Visual Basic for Application в среде Microsoft Office Excel было реализовано приложение, которое обрабатывает файлы данных. Эти данные распределяются между тремя вкладками приложения. Первая вкладка содержит общую справочную информацию о перевозчиках (номера автобусов, стоимость проезда, протяженность маршрута, информацию по затратам), а также информацию об оптимальных интервалах движения автобусов и возможных доходах перевозчиков. Для сравнения в справочной информации о перевозчиках приведены данные по фактическим интервалам движения автобусов по данным городских порталов [48, 61]. Также на первой вкладке размещена информация по общему количеству пассажиров на всех остановках, по суммарному количеству приехавших на остановку пассажиров, и суммарному количеству уехавших с остановки пассажиров для каждой остановки. По данным из таблиц формируются графики, которые наглядно демонстрируют пассажиропотоки на остановках. Вторая вкладка содержит детализацию информации относительно маршрутов перевозчиков. Для каждого маршрута в виде таблице представлена информация по каждой остановке в прямом и обратном направлениях. Для остановки в таблице представлена информация по количеству вошедших и вышедших из автобуса пассажиров. Для наглядности информация по каждому маршруту представлена также и в виде графика. Для каждого маршрута формируются два графика: один для прямого рейса, второй для обратного рейса.
Третья вкладка содержит детализацию информации относительно прибыли перевозчиков. В таблице для каждого перевозчика представлена информация по доходам и расходам, итоговой прибыли перевозчиков и количеству перевезенных ими пассажиров в состоянии равновесия. На основе данных о доходах и расходах перевозчиков формируется диаграмма.
На рисунках 3.5 – 3.11 (см. приложение 1) представлены экранные снимки работы различных компонентов программного комплекса.
Таким образом, представленный программный комплекс позволяет не только находить оптимальные интервалы движения автобусов в существующей дорожной сети города, но также и формирует статистические данные, которые позволяют более детально исследовать ситуацию на рынке пассажирских перевозок. Отметим, что если количество маршрутов сокращается, но по остальным маршрутам никаких изменений не происходит, программный комплекс также может использоваться, а для маршрутов, которые перестали существовать, достаточно задать нулевую вместимость автобусов, которые осуществляли перевозку пассажиров по этим маршрутам.
BPR-функция задержки потока для системы из трех маршрутов
Рассмотрим в качестве примера участок транспортной сети г. Петрозаводска, который соединяет микрорайоны Древлянка и Центр (рисунок 4.1). Найдем для такой транспортной сети функции задержек на маршрутах.
На рисунке 4.1 представлены основные маршруты, по которым можно добраться с Древлянки в Центр. Путепровод, соединяющий улицу Гоголя и Лососинское шоссе, закрыт на ремонт, поэтому Лососинское шоссе практически не влияет на формирование маршрутов и транспортных потоков. Найдем для каждого маршрута функцию задержки, а также определим в каком случае существует конкурентное равновесие и ситуация социального оптимума.
В таблице 4.1 представлены численные характеристики маршрутов, изображенных на рисунке 4.1. Численные характеристики были получены путем проведения натурных экспериментов для определения времени путешествия по маршрутам, а также при помощи интерактивной карты [22], которая позволяет вычислять расстояния между объектами.
Для определения пропускной способности каналов на маршрутах была проведена серия экспериментов для каждого маршрута. Для маршрута № 1 результаты экспериментов представлены в таблице 4.2.
На основе экспериментальных значений методом наименьших квадратов было получено значение c1 . Аналогичным образом были получены значения c2 , c3 . Полученные характеристики пропускной способности на маршрутах представлены в таблице 4.3. Для найденных характеристик пропускной способности на маршрутах рассмотрим, какие маршруты будет использовать транспортный поток, состоящий из 10, 100 и 1000 автомобилей.
Задача состоит в том, чтобы для ситуации конкурентного равновесия и системного оптимума, определить, как распределяется транспортный поток по маршрутам, а также при каких значениях c1 , c2 , c3 этот поток использует все маршруты.
Для поиска величин транспортных потоков на маршрутах была разработана программа в среде Microsoft Office Excel на языке Visual Basic for Application [8], которая обрабатывает табличные данные и определяет количество маршрутов, по которым пойдет поток, а также границы значений c1, c2 , c3 , при переходе через которые транспортный поток идет по большему количеству маршрутов.
В таблицах 4.4, 4.5 представлена информация о равновесных потоках, а также значениях c1 , c2 , c3 , в зависимости от которых поток идет по различным маршрутам. Рассмотрим в качестве примера участок транспортной сети г. Петрозаводска, который соединяет микрорайоны Древлянка и Центр (рисунок 4.1). Найдем для такой транспортной сети функции задержек на маршрутах. На рисунке 4.1 представлены основные маршруты, по которым можно добраться с Древлянки в Центр. Путепровод, соединяющий улицу Гоголя и Лососинское шоссе, закрыт на ремонт, поэтому Лососинское шоссе практически не влияет на формирование маршрутов и транспортных потоков. Найдем для каждого маршрута функцию задержки, а также определим в каком случае существует конкурентное равновесие и ситуация социального оптимума.
В таблице 4.1 представлены численные характеристики маршрутов, изображенных на рисунке 4.1. Численные характеристики были получены путем проведения натурных экспериментов для определения времени путешествия по маршрутам, а также при помощи интерактивной карты [22], которая позволяет вычислять расстояния между объектами.
Для определения пропускной способности каналов на маршрутах была проведена серия экспериментов для каждого маршрута. Для маршрута № 1 результаты экспериментов представлены в таблице 4.2.
На основе экспериментальных значений методом наименьших квадратов было получено значение c1 . Аналогичным образом были получены значения c2 , c3 . Полученные характеристики пропускной способности на маршрутах представлены в таблице 4.3. Для найденных характеристик пропускной способности на маршрутах рассмотрим, какие маршруты будет использовать транспортный поток, состоящий из 10, 100 и 1000 автомобилей. Задача состоит в том, чтобы для ситуации конкурентного равновесия и системного оптимума, определить, как распределяется транспортный поток по маршрутам, а также при каких значениях c1 , c2 , c3 этот поток использует все маршруты. Для поиска величин транспортных потоков на маршрутах была разработана программа в среде Microsoft Office Excel на языке Visual Basic for Application [8], которая обрабатывает табличные данные и определяет количество маршрутов, по которым пойдет поток, а также границы значений c1, c2 , c3 , при переходе через которые транспортный поток идет по большему количеству маршрутов. В таблицах 4.4, 4.5 представлена информация о равновесных потоках, а также значениях c1 , c2 , c3 , в зависимости от которых поток идет по различным маршрутам.
Численные эксперименты, практическое применение
Рассмотрим несколько примеров, демонстрирующих работу программы, описанной в предыдущем разделе.
Рассмотрим систему, в которой пропускная способность первого сервиса// 15 польз./час, второго //2 = 11 польз./час. Стоимость единицы времени пребывания системе С = 2 у.е., а награда пользователя R = 3 у.е.
В данном случае условие: R — выполнено, поэтому можно приступить к поиску решения. Доходы провайдеров для таких значений параметров представлены в таблице 5.3. 87 Всего в систему прибыли 21 пользователь. Из них были обслужены - 16; 5 пользователей остались необслуженными и покинули систему. Полученные результаты показывают, что действительно, провайдеры могут бороться за назначение цен так, чтобы при этом не потерять спрос на свои услуги. Рассмотрим еще один пример. Допустим, что в систему не прибыло ни одного пользователя. Соответственно провайдеры не получат прибыли. На следующем примере продемонстрирована такая ситуация. Посмотрим, как изменятся стоимости услуг сервисов а также их доходы при уменьшении характеристик системы, т.е. jux = 1 польз./час, ju2 = 13 польз./час. При этом значения R и С останутся прежними. Результат для изменившихся характеристик системы представлен в таблице 5.4. Всего в систему поступило – 0 пользователей. Из них, обслуженных пользователей – 0, необслуженных пользователей – 0. Действительно, может случиться, что система простаивает, соответственно и провайдеры не получают доходы. Пример 5.5. Рассмотрим систему, в которой пропускная способность первого сервиса //, = 36 польз./час, второго ju2 = 42 польз./час. Стоимость единицы времени пребывания системе по-прежнему С = 2 у.е., а награда пользователя R = 3 у.е. Определим, как теперь изменятся доходы сервисов. Как и ранее условие: R — выполнено, поэтому в таблице 5.5 представлено решение для такой системы. В данном случае в силу высокой скорости обслуживания пользователей доходы парковщика незначительны.
Полученные практические результаты можно применять не только для транспортных сетей, но и, например, для компьютерных сетей при проектировании различных сервисов на веб-сервере. В таком случае, если пользователю нужно воспользоваться каким-либо сервисом на сервере, ему необходимо заплатить за право доступа на веб-сервер, за время пребывания в системе и непосредственно за необходимый ему сервис.
Полученные выше результаты показывают, что провайдеры действительно могут конкурировать за назначение цен так, чтобы пользователи не покинули систему, и доходы провайдеров возросли. При этом для различных ценовых ситуации определено, каким образом выбор пользователей зависит от стоимости услуг провайдеров. Также найдены равновесные цены для провайдеров и соответственно их доходы. Проведено сравнение полученных результатов с моделью без конкуренции, и, кроме того, подтверждено, что появление второго сервиса выгодно пользователям и не выгодно первому сервису. В задачах оптимизации транспортных сетей важно также учитывать, что добавление новых дорог в существующей транспортной сети может ухудшить характеристики системы [50, 54, 60]. Такое явление называется парадокс Браесса [84, 96, 99]: добавление альтернативных путей к некоторой сети при независимом («эгоистическом») распределении нагрузки на ее элементы может уменьшать эффективность ее работы. Парадокс Браесса может появляться в различных системах, так Роугарден и Вэлиант показали, что данный парадокс с большой вероятностью наблюдается в случайных графах, т.е. в случайно построенных дорожных сетях [105]. В немецком г. Штутгарте после инвестиций в дорожную сеть в 1969 г. ситуация на дорогах не улучшилась, пока не была закрыта для движения секция недавно построенной дороги. В Сеуле в Южной Корее после удаления автомобильного пути как части проекта восстановления ручья Чонгечон стала заметна неэффективность кольцевой дороги вокруг города. В 1990 году в США закрытие 42-й авеню в Нью-Йорке позволило сократить перегрузку на дорогах [47].
Самое очевидное решение парадокса – удаление дополнительного элемента сети и возвращение к ее прежней структуре. Такой метод использовался в работах [92, 101], где вычислялись характеристики добавляемого канала, чтобы гарантированно избежать возникновения парадокса Браесса. Более сложная задача: анализ существующих сетей на наличие парадокса Браесса и удаление парадоксального элемента сети. Такая задача пока что не решена, поскольку не известен алгоритм, который позволял бы однозначно устанавливать указанный элемент, или, что равносильно, устанавливать оптимальную конфигурацию сети. Однако для частных случаев возможно найти решение. В работах [32, 70] исследуется вопрос проявления и обнаружения парадоксальных элементов в равновесных ситуациях для модели Вардропа.
