OPTIMIZATION OF QUANTITY OF PASSENGER TRANSPORT FACILITIES IN URBAN TRANSPORT SUBJECT TO WAITING LOSS
Journal: VESTNIK OF ASTRAKHAN STATE TECHNICAL UNIVERSITY. SERIES: MANAGEMENT, COMPUTER SCIENCE AND INFORMATICS
№ 2
, 2018
Rubrics: MATHEMATICAL MODELING
Authors:
1.
Astrakhan State Technical University
(Candidate of Sciences in Technology, Assistant Professor; Head of the Institute of Information Technologies and Communications)
Russian Federation
Russian Federation
2.
Astrakhan Technical State University
3.
Astrakhan Technical State University
(Senior Lecturer of the Department of Information Security)
Russian Federation
Russian Federation
Type:
Article
Pages:
from 7
to 16
Status:
Published
Received:
05.04.2018
Accepted:
25.04.2018
Published:
25.04.2018
Subject area:
VAC 05.12.2013 Системы, сети и устройства телекоммуникаций
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 517.977.1
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 517.977.1
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
Language:
Russian
Keywords:
passenger transportation, vehicles, passenger loss while waiting for transport, queuing systems, minimization of total losses
Abstract (English):
The paper focuses on formalizing the task of choosing the optimal number of public transport for minimizing total losses of the transport system and all passengers (where passenger loss is expressed by their waiting time at the stations). As for the research tool, the queuing theory apparatus was chosen. There was introduced a nonlinear function that estimates passenger loss, given the relations for finding two parameters describing the function. A system of equations describing possible states of the queuing system under consideration in the stationary mode of its operation has been obtained. Similar equations are derived for the case when the rate of passengers arriving to the stations depends on the number of passengers already waiting at the stations, which is typical for cases where there are a small number of possible sources of passenger arrival to the station, e.g. in industrial districts of the cities.The optimization problem of finding the optimal number of vehicles is formulated by minimizing the total losses of the transport system and all passengers. The solution of the problem obtained is reduced to solving the system of equations using Newton method as one of the most effective methods for solving systems of equations defined by analytic expressions. Software implementation of the procedures given in the work will reduce the number of vehicles for passenger transportation to a certain acceptable level, thereby reducing the amount of traffic on urban roads.
The paper focuses on formalizing the task of choosing the optimal number of public transport for minimizing total losses of the transport system and all passengers (where passenger loss is expressed by their waiting time at the stations). As for the research tool, the queuing theory apparatus was chosen. There was introduced a nonlinear function that estimates passenger loss, given the relations for finding two parameters describing the function. A system of equations describing possible states of the queuing system under consideration in the stationary mode of its operation has been obtained. Similar equations are derived for the case when the rate of passengers arriving to the stations depends on the number of passengers already waiting at the stations, which is typical for cases where there are a small number of possible sources of passenger arrival to the station, e.g. in industrial districts of the cities.The optimization problem of finding the optimal number of vehicles is formulated by minimizing the total losses of the transport system and all passengers. The solution of the problem obtained is reduced to solving the system of equations using Newton method as one of the most effective methods for solving systems of equations defined by analytic expressions. Software implementation of the procedures given in the work will reduce the number of vehicles for passenger transportation to a certain acceptable level, thereby reducing the amount of traffic on urban roads.
Keywords:
passenger transportation, vehicles, passenger loss while waiting for transport, queuing systems, minimization of total losses
passenger transportation, vehicles, passenger loss while waiting for transport, queuing systems, minimization of total losses
Ведение Проблема оптимизации работы городского транспортного хозяйства (прежде всего, по перевозке населения) остро стоит практически во всех крупных городах нашей страны. Эта проблема вызвана целым рядом причин, наиболее важной из которых является стремительное увеличение количества транспортных средств в крупных и средних городах за последние два десятилетия при практически неизменных пропускных возможностях городских магистралей и дорог. Научные работы и практические наработки по данной проблеме [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. Gerami V. D. Metodologiya formirovaniya sistemy gorodskogo passazhirskogo obschestvennogo transporta. M.: MADI, 2001. 313 s.
2. Kurganov V. M. Situacionnoe upravlenie avtomobil'nymi perevozkami: monogr. M.: Tehpoligrafcentr, 2003. 197 s.
3. Cherkasov O. N., Mezhov V. E. i dr. Matematicheskoe i programmnoe obespechenie sistemy upravleniya avtotransportnymi predpriyatiyami: monogr. Voronezh: VGU, 2007. 338 s.
4. Sultanahmedov M. A. Model' operativnogo upravleniya perevozochnym processom // Goroda Rossii: problemy stroitel'stva, inzhenernogo obespecheniya, blagoustroystva i ekologii: sb. materialov IX Mezhdunar. nauch.-prakt. konf. Penza, 2007. S. 178-181.
5. Vel'mozhin A. V., Gudkov B. A., Mirotin L. B. Tehnologiya organizacii i upravlenie gruzovymi avtomobil'nymi perevozkami: ucheb. dlya vuzov. Volgograd: Politehnik, 1999. 296 s.
6. Kleynrok L. Vychislitel'nye sistemy s ocheredyami. M.: Mir, 1979. 600 s.
7. Gnedenko B. V., Kovalenko I. N. Vvedenie v teoriyu massovogo obsluzhivaniya. M.: Izd-vo LKI, 2007. 400 s.
8. Vasil'ev F. P. Chislennye metody resheniya ekstremal'nyh zadach. M.: Nauka, 1980. 519 s.
