ОПТИМИЗАЦИЯ КОЛИЧЕСТВА АВТОТРАНСПОРТНЫХ ПАССАЖИРСКИХ СРЕДСТВ В ГОРОДСКОМ ТРАНСПОРТЕ С УЧЕТОМ ПОТЕРЬ НА ОЖИДАНИЕ
Журнал: ВЕСТНИК АСТРАХАНСКОГО ГОСУДАРСТВЕННОГО ТЕХНИЧЕСКОГО УНИВЕРСИТЕТА. СЕРИЯ: УПРАВЛЕНИЕ, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА И ИНФОРМАТИКА
№ 2
, 2018
Рубрики: МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ
Авторы:
1.
Астраханский государственный технический университет
(кандидат технических наук, доцент; директор института информационных технологий и коммуникаций)
Россия
Россия
2.
Астраханский государственный технический университет
3.
Астраханский государственный технический университет
(старший преподаватель кафедры информационной безопасности)
Россия
Россия
Тип:
Статья
Страницы:
с 7
по 16
Статус:
Опубликован
Получено:
05.04.2018
Одобрено:
25.04.2018
Опубликовано:
25.04.2018
Классификаторы:
ВАК 05.12.2013 Системы, сети и устройства телекоммуникаций
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 517.977.1
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 517.977.1
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
Язык материала:
русский
Ключевые слова:
пассажирские перевозки, транспортные средства, потери пассажиров в результате ожидания транспорта, системы массового обслуживания, суммарная интенсивность
Аннотация (русский):
Формализована задача выбора оптимального числа транспортных средств, перевозящих пассажиров, в результате чего минимизируются суммарные потери транспортной системы и всех пассажиров (где потери пассажиров выражены временем их ожидания на остановках). В качестве инструмента исследования выбран аппарат теории массового обслуживания. Введена нелинейная функция, оценивающая потери пассажиров, приведены соотношения для нахождения двух параметров, описывающих эту функцию. Получена система уравнений, описывающих возможные состояния рассматриваемой системы массового обслуживания в стационарном режиме ее функционирования. Выведены аналогичные уравнения и для случая, когда интенсивность поступления пассажиров на остановки зависит от числа пассажиров, уже ожидающих на остановках, что типично для случаев, когда имеется малое число возможных источников прибытия пассажиров на остановку, например, в районах, где сосредоточены несколько крупных промышленных объектов. Сформулирована оптимизационная задача нахождения оптимального числа транспортных средств путем минимизации суммарных потерь транспортной системы и всех пассажиров. Решение полученной задачи сведено к решению системы уравнений методом Ньютона, выбранного в качестве одного из наиболее эффективных методов решения систем уравнений, заданных аналитическими выражениями. Программная реализация приведенных в работе процедур позволит снизить количество транспортных средств, осуществляющих пассажирские перевозки, до определенного приемлемого уровня, что приведет к сокращению транспортного потока на городских дорогах.
Формализована задача выбора оптимального числа транспортных средств, перевозящих пассажиров, в результате чего минимизируются суммарные потери транспортной системы и всех пассажиров (где потери пассажиров выражены временем их ожидания на остановках). В качестве инструмента исследования выбран аппарат теории массового обслуживания. Введена нелинейная функция, оценивающая потери пассажиров, приведены соотношения для нахождения двух параметров, описывающих эту функцию. Получена система уравнений, описывающих возможные состояния рассматриваемой системы массового обслуживания в стационарном режиме ее функционирования. Выведены аналогичные уравнения и для случая, когда интенсивность поступления пассажиров на остановки зависит от числа пассажиров, уже ожидающих на остановках, что типично для случаев, когда имеется малое число возможных источников прибытия пассажиров на остановку, например, в районах, где сосредоточены несколько крупных промышленных объектов. Сформулирована оптимизационная задача нахождения оптимального числа транспортных средств путем минимизации суммарных потерь транспортной системы и всех пассажиров. Решение полученной задачи сведено к решению системы уравнений методом Ньютона, выбранного в качестве одного из наиболее эффективных методов решения систем уравнений, заданных аналитическими выражениями. Программная реализация приведенных в работе процедур позволит снизить количество транспортных средств, осуществляющих пассажирские перевозки, до определенного приемлемого уровня, что приведет к сокращению транспортного потока на городских дорогах.
Ключевые слова:
пассажирские перевозки, транспортные средства, потери пассажиров в результате ожидания транспорта, системы массового обслуживания, суммарная интенсивность
пассажирские перевозки, транспортные средства, потери пассажиров в результате ожидания транспорта, системы массового обслуживания, суммарная интенсивность
Ведение Проблема оптимизации работы городского транспортного хозяйства (прежде всего, по перевозке населения) остро стоит практически во всех крупных городах нашей страны. Эта проблема вызвана целым рядом причин, наиболее важной из которых является стремительное увеличение количества транспортных средств в крупных и средних городах за последние два десятилетия при практически неизменных пропускных возможностях городских магистралей и дорог. Научные работы и практические наработки по данной проблеме [1-3] позволили существенно снизить остроту проблемы, но, несмотря на значительные предпринятые усилия, проблема оптимизации работы городской транспортной системы остается пока не решенной. Многочисленные варианты возможного решения проблемы связаны со значительными затратами. В нашей работе рассматривается оптимизация по фактору, который не связан со сколько-нибудь значимыми затратами, а именно: рассматривается возможность уменьшения количества автотранспортных средств на дорогах города при условии, что количество оставшихся транспортных средств будет достаточным для удовлетворения потребности в пассажирских перевозках, не вызывая при этом значимого раздражения ожидающих пассажиров (формализованная реализация принципа «время - деньги»). Подобная постановка задачи рассмотрена в [4, 5]. В нашей работе рассмотрены аналогичные подходы к решению данной задачи. Таким образом, в работе рассматривается задача повышения эффективности работы городского транспорта за счет увеличения пропускной способности городских магистралей путем уменьшения количества пассажирского автотранспорта с учетом степени готовности пассажиров ожидать прибытия транспорта на остановки. Формализация задачи Как было указано выше, в основе повышения эффективности работы городского пассажирского транспорта - уменьшение количества автотранспортных единиц до некоторого приемлемого для ожидающих пассажиров уровня. Для уменьшения количества пассажирского автотранспорта достаточно увеличить интервалы движения между отдельными транспортными единицами, поступающими последовательно на остановку. В результате уменьшится общее количество поездок по каждому маршруту, что приведет к уменьшению количества выдаваемых лицензий на оказание транспортных услуг и, как следствие, уменьшению количества транспортных единиц на дорогах. Таким образом, необходимо сформировать формализованную модель, предназначенную для оптимизации интервалов движения городского пассажирского транспорта. Модель будет построена на основе методов теории массового обслуживания [6]. При формализации задачи будут использованы следующие предположения, типичные при анализе многих систем массового обслуживания. 1. Поток пассажиров, поступающих на каждую остановку, является простейшим, т. е. интервалы между прибытиями пассажиров на остановку имеют показательное распределение с заданным параметром, равным средней интенсивности поступления пассажиров. Ниже данный показатель будет разбит на отдельные группы показателей в зависимости от конечного пункта назначения. 2. Поток транспортных единиц, поступающих на каждую остановку, также является простейшим. Предположение 1 в рассматриваемой задаче достаточно адекватно отражает реальную ситуацию по следующей причине. Суммарный поток пассажиров на каждой остановке складывается из большого числа редких потоков - потоков прибытия на данную остановку каждого отдельного пассажира. В реальности в некоторых случаях пассажиры могут прибывать на остановку группами, но в общем потоке пассажиров данное событие бывает очень редко. В силу теоремы Григелиониса [7] при наложении большого числа редких потоков результирующий поток с большой точностью приближается пуассоновским, или, что то же самое, простейшим потоком. Именно данный факт и лежит в основе предположения 1. Правомочность применения предположения 2 более проблемна. Однако, как показано в [6] на примере вычислительных сетей, даже в ситуациях, когда предположение о пуассоновости характеристик, казалось бы, абсолютно неприемлемо (в указанном источнике - это узлы вычислительной сети), использование пуассоновских и неразрывно связанных с ними показательных распределений приводит к средней ошибке величиной (в среднем) порядка 10 %, что в рамках рассматриваемой задачи вполне приемлемо. Как показано в [7], процессы, удовлетворяющие предположениям 1 и 2, обладают свойством отсутствия памяти, т. е. будущее поведение этих процессов не зависит от его прошлых состояний, а зависит лишь от текущего состояния. Указанное свойство позволяет изучать поведение характеристик модели на основе диаграммы состояний, отображающей возможные текущие состояния и возможные переходы между ними. Для получения аналитических соотношений введем обозначения: - общее количество остановочных пунктов, по которым движутся транспортные средства и перемещаются пассажиры (); - количество всех маршрутов, разрешенных в городской транспортной системе (); - себестоимость одного рейса для одного транспортного средства, осуществляющего перевозки по k-му маршруту (); - индикаторная функция, принимает значение 1, если по k-му маршруту можно переехать с i-го остановочного пункта на j-й, и принимает значение 0 в противном случае (; ); - средняя интенсивность потока транспортных средств, осуществляющих перевозки по k-му маршруту (); - средняя интенсивность потока пассажиров, поступающих на i-ю остановку с намерением переехать на j-ю остановку; очевидно, и если i-я и j-я остановки не связаны транспортным маршрутом; I(t) - условная величина потерь пассажира в результате ожидания на остановке в течение времени t - эта характеристика выступает в качестве оценки степени нетерпеливости пассажира при ожидании на остановке. Обсудим возможный вид функции I(t). При малых значениях t (условно при t < 5 мин) величина I(t) должна быть мала; затем величина I(t) монотонно растет, достигая максимального значения при некотором значении t (примем его равным 30 мин), затем остается практически неизменной. Перечисленным свойствам в достаточной мере удовлетворяет класс гамма распределений вида , поэтому можно принять, что (1) Считая, что малое значение t соответствует уровню квантиля в 5 %, а большое значение t - уровню квантиля в 95 %, получаем следующую систему уравнений для нахождения параметров α и c гамма-распределения: (2) Нормирующий множитель , обеспечивающий соизмеримость потерь транспортной системы и потерь пассажиров, может быть найден на основе экспертного оценивания. Более точная его оценка требует дополнительных исследований. Таким образом, соотношения (1) и (2) позволяют однозначно определить выражение для функции нетерпеливости (по другой терминологии - функции потерь) пассажира при его ожидании на остановке. Для суммарного числа пассажиров , приходящих на i-ю остановку за единицу времени, нетрудно вывести соотношение: Одно из очевидных необходимых условий обеспечения удобства системы транспортных перевозок состоит в наличии хотя бы одного маршрута, позволяющего обеспечить перевозку пассажиров между заданными двумя остановками, если есть положительный поток пассажиров между этими двумя остановками. То есть если , то необходимо (). Введем некоторые вспомогательные характеристики. Общая интенсивность потока транспорта, поступающего на i-ю остановку и позволяющего перевезти пассажиров на j-ю остановку, равна (). Затраты всех автотранспортных средств, связанные с перевозкой пассажиров, равны (3) Таким образом, рассматриваемая задача формализована как задача теории массового обслуживания, в которой поступающий поток - это пассажиропоток на остановки, обсуживаемые транспортной системой, а обслуживающие приборы - это транспортные средства, осуществляющие перевозки пассажиров. Выведем соотношения для вероятностей состояний в рассматриваемой системе массового обслуживания (СМО). Здесь под состоянием будем понимать число пассажиров, ожидающих транспорт на данной остановке. Изучим поведение рассматриваемой СМО в стационарном режиме функционирования, когда ее вероятностные характеристики не зависят явно от времени, а все изменения в СМО происходят только за счет реализации различных случайных событий, связанных с прибытием на остановку очередного пассажира или транспортной единицы. Отметим, что практически все существующие системы при неперегруженном режиме функционирования (т. е. когда суммарная интенсивность поступлений меньше суммарной пассажироемкости транспортных средств, осуществляющих перевозки пассажиров), достаточно быстро переходят в режим, практически неотличимый от стационарного. В стационарном состоянии выполняется следующее балансовое условие: для каждой остановки в каждом состоянии средняя величина прибывающего потока пассажиров совпадает со средней величиной уезжающих пассажиров. Ниже при выводе соотношений для простоты индекс i, указывающий на номер остановки, опускается. Пусть есть вероятность того, что на остановке ждут транспорт l пассажиров. Составим диаграмму состояний системы (рис.). Диаграмма состояний системы массового обслуживания на остановке Дадим пояснения по составлению диаграммы. Кружки с числами обозначают конкретные состояния, число в кружке указывает на количество ожидающих на остановке пассажиров. Дуга со стрелкой указывает на возможный переход из одного состояния в другое; число над дугой является интенсивностью такого перехода (т. е. число переходов за единицу времени). Переход из состояния «l» в состояние «l + 1» может произойти только за счет прибытия нового пассажира на остановку, что происходит с интенсивностью . Уменьшается состояние только за счет поступления транспортной единицы на остановку; интенсивность такого перехода равна интенсивности поступления транспорта на остановку, т. е. μ. Соответствующие переходы отображены нижними дугами со стрелками справа налево с приписанным весом μ. Наличия диаграммы состояний достаточно для последующего анализа СМО. В частности, на основе диаграммы для стационарных состояний системы могут быть выписаны уравнения, связывающие эти состояния между собой. Выпишем эти уравнения. Рассмотрим произвольное состояние l системы . Среднее количество переходов в это состояние из других состояний системы ввиду связей между состояниями, представленными в диаграмме, за единицу времени составляет В силу эргодической интерпретации вероятности состояний вероятность может интерпретироваться как средняя доля времени в одной единице времени, в течение которого система находится в состоянии l. Записанное выше выражение для частоты переходов в состояние l указывает возможность этого перехода из состояния «l - 1» за счет прихода на остановку пассажира - это событие, как отмечено на диаграмме, происходит с интенсивностью . Аналогично выписывается выражение для числа выходов из состояния l, которое равно . Здесь первое слагаемое связано с прибытием нового пассажира на остановку в момент, когда там уже присутствовали l пассажиров. Второе слагаемое связано с прибытием транспорта на остановку в момент, когда на остановке находились l ожидающих пассажиров. В стационарном состоянии среднее число входов в любое состояние равно среднему числу выходов из этого состояния; приходим к следующему равенству: для всех . При l = 0 аналогично находим Поскольку при анализе охвачены все возможные состояния СМО, сумма вероятностей всех состояний равна единице; получаем следующую систему уравнений: (4) Решим систему (4). Из первого уравнения (4) находим (l > 0): (5) Из второго и третьего соотношений в системе (4) получаем: , что дает следующее выражение для нулевого состояния: . После подстановки полученного выражения в (5) находим: для всех Отметим, что полученные результаты могут быть обобщены для более общего случая, когда интенсивность поступлений пассажиров зависит от числа ожидающих, что типично для систем с малым числом источников [6] (т. е. интенсивность поступлений ). В частности, для систем с конечным числом источников [6] (т. е. когда число пассажиров, которые могут прибыть на данную остановку, ограничено) справедливы соотношения (6) Обозначив через v максимально допустимое число источников поступления пассажиров (т. е. СМО представляет собой систему с конечным числом источников), с учетом (6) выводим: . Вернемся к рассмотрению случая, когда интенсивность прихода пассажиров не зависит от текущего состояния системы. Из (5) выводим: Тогда среднее число пассажиров , ожидающих на остановках, равно . Среднее время w их ожидания найдем на основе уравнения Литтла [6]: Таким образом, получаем соотношения: (7) (8) Нахождение оптимального количества транспортных средств Полученные выше соотношения для вероятностей состояний описанной выше СМО позволяют свести решение исходной задачи к выбору количества допустимых транспортных средств на каждом из существующих маршрутов. Отметим, что поток пассажиров, которые хотят с i-й остановки доехать до j-й, также является простейшим, что обосновывается на основе совершенно тех же соображений и рассуждений, которые приведены выше для общего случая. Тогда, заменяя на , а интенсивность транспорта на , выражение (7) запишем в виде для всех Средние потери (в пассажирочасах) пассажиров, ожидающих транспорта на i-й остановке для переезда на j-ю остановку, в единицу времени равны (9) для всех Из (3) и (9) выводится следующее выражение для целевой функции Z, описывающей суммарные затраты транспортной системы, связанные с облуживанием транспортных средств, и потери времени пассажиров в результате ожидания на остановках: . Полученные соотношения позволяют следующим образом формализовать задачу нахождения оптимального количества транспортных средств (или, что аналогично, интенсивностей движения) на всех транспортных маршрутах: найти такие значения переменных, при которых целевая функция Z достигает своего минимального значения: . (10) Отметим, что знание величин позволит ввести ограничения на количество транспортных средств на каждом маршруте, чтобы их суммарная интенсивность не превышала величин на k-м маршруте. Оценим количество допустимых транспортных средств на каждом маршруте. Пусть есть длина k-го маршрута (в км), - средняя скорость движения по этому маршруту, - количество автотранспортных средств на k-м маршруте. Тогда величина интервала между последовательными моментами прибытия автотранспорта на остановку равна . Далее, при интенсивности транспорта движения автотранспортных средств на k-м маршруте, длина временного интервала между последовательными моментами прибытия транспортных средств на остановку равна . Таким образом, получаем соотношение , из которого находим следующее выражение для допустимого числа транспортных средств на k-м маршруте: (11) На основе всего вышесказанного заключаем, что решение поставленной в работе задачи сводится к нахождению решения оптимизационной задачи (10). Для решения задачи (10) воспользуемся необходимым условием экстремума для функции многих переменных [8]. Из необходимого условия Лагранжа следует, что в точке минимума частные производные целевой функции по переменным должны обращаться в нуль. Из выражения для целевой функции, приведенного в (10), выводим: в точке экстремума () выполнены соотношения для всех . Таким образом, оптимальные значения переменных () являются решениями следующей системы алгебраических уравнений с k неизвестными , удовлетворяющими условию (): (12) Решение полученной системы нелинейных уравнений (12) представляет определенные сложности при больших размерах задачи. Однако аналитичность всех входящих в уравнение выражений позволяет ограничиться кругом методов решения систем нелинейных уравнений, опирающихся на аналитические выражения. Среди указанных методов наибольший интерес представляет метод Ньютона, который имеет очень высокую скорость сходимости порядка , где N - размерность задачи. Опишем более детально необходимые выражения для нахождения решения на основе метода Ньютона [8]. Метод является рекуррентным и заключается в построении последовательности на основе следующих рекуррентных соотношений (): (13) где для обозначено (см. (12)) (): Рекуррентные соотношения (13) и являются основой предлагаемого алгоритма решения системы (12). Для практической реализации метода необходимо также указать начальные значения всех переменных. Одним из недостатков метода является высокая чувствительность к выбору начальных значений. В работе предлагаются следующие начальные значения для переменной μ: для всех , что соответствует реальной практической маргинальной ситуации, когда на каждом из имеющихся маршрутов находится ровно одно транспортное средство. При практическом внедрении данного алгоритма могут быть выбраны другие начальные значения, более точно отображающие ситуацию на конкретном объекте внедрения. Условием завершения процесса поиска оптимальных значений переменных μk является близость двух соседних значений, т. е. , где - заданная точность конечного результата. Последнее соотношение в раскрытом виде записывается следующим образом: Таким образом, процедура поиска оптимальной интенсивности транспортных средств на различных маршрутах завершена. Заключение В работе формализована задача выбора оптимального числа средств, минимизирующего суммарные потери транспортной системы и всех пассажиров, где потери пассажиров связаны с их ожиданием на остановках. В качестве инструмента исследования выбран аппарат теории массового обслуживания. Получена система уравнений, описывающих возможные состояние рассматриваемой системы. Сформулирована оптимизационная задача нахождения оптимального числа транспортных средств, ее решение сведено к решению системы уравнений. Для решения полученной системы предложен метод Ньютона как один из наиболее эффективных методов решения систем уравнений, заданных аналитическими выражениями. Программная реализация приведенных в работе процедур позволит снизить количество транспортных средств, осуществляющих пассажирские перевозки, до некоторого приемлемого уровня.
1. Герами В. Д. Методология формирования системы городского пассажирского общественного транспорта. М.: МАДИ, 2001. 313 с.
2. Курганов В. М. Ситуационное управление автомобильными перевозками: моногр. М.: Техполиграфцентр, 2003. 197 с.
3. Черкасов O. Н., Межов В. Е. и др. Математическое и программное обеспечение системы управления автотранспортными предприятиями: моногр. Воронеж: ВГУ, 2007. 338 с.
4. Султанахмедов М. А. Модель оперативного управления перевозочным процессом // Города России: проблемы строительства, инженерного обеспечения, благоустройства и экологии: сб. материалов IX Междунар. науч.-практ. конф. Пенза, 2007. С. 178-181.
5. Вельможин А. В., Гудков B. A., Миротин Л. Б. Технология организации и управление грузовыми автомобильными перевозками: учеб. для вузов. Волгоград: Политехник, 1999. 296 с.
6. Клейнрок Л. Вычислительные системы с очередями. М.: Мир, 1979. 600 с.
7. Гнеденко Б. В., Коваленко И. Н. Введение в теорию массового обслуживания. М.: Изд-во ЛКИ, 2007. 400 с.
8. Васильев Ф. П. Численные методы решения экстремальных задач. М.: Наука, 1980. 519 с.
