Применение математического инструментария для решения задач организации и управления городскими пассажирскими перевозками

М. Р. Караева

ПРИМЕНЕНИЕ МАТЕМАТИЧЕСКОГО ИНСТРУМЕНТАРИЯ ДЛЯ РЕШЕНИЯ ЗАДАЧ ОРГАНИЗАЦИИ И УПРАВЛЕНИЯ ГОРОДСКИМИ ПАССАЖИРСКИМИ ПЕРЕВОЗКАМИ

Аннотация

В статье определены основные этапы решения задачи, оптимизации работы городских пассажирских перевозок, выбраны критерии оценки оптимальности работы автотранспортных предприятий и отражены возможности применения генетических алгоритмов для решения поставленных задач.

Ключевые слова

Организация пассажирских перевозок, модели оптимизации, генетический алгоритм, хромосома, ген, популяция, оператор случайных изменений.

2015 № 1

M. R. Karaeva

APPLICATION OF MATHEMATICAL TOOLS TO SOLVE PROBLEMS OF ORGANIZATION AND MANAGEMENT OF URBAN PASSENGER TRANSFERS

Annotation

In article disclosed the potentialities and applications of genetic algorithms for improving the optimization process of organization and management of the passenger traffic in the conditions of big cities

Keywords

The organization of passenger traffic, models of optimization, genetic algorithm, chromosome, gene, population, randomization operator of changes.

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

В настоящее время развитие единого транспортного пространства страны, объединяющего в себе не только транспортные коммуникации, но и всю

систему технологического обеспечения для всех видов транспорта, стало необходимым условием успешного развития современной транспортной системы России. Принятая транспортная стратегия Российской Федерации на период до 2030 г. предусматривает решение целого ряда задач, в том числе: управленческих, организационно-технических, а также содержит требование обеспечения всех слоев населения качественными, своевременными и доступными транспортными услугами [3, 5].

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

• резкое увеличение пассажиропотока за счет быстрого развития города;

• усиление напряженности транспортного потока;

• повышение требований пассажиров к условиям и механизму транспортного обслуживания;

• перегруженность и недостаточность пропускной способности улично-дорожной сети;

• увеличение передвижения транспортной корреспонденции населения;

• высокий коэффициент сменяемости пассажиров;

• возрастающий технический и моральный износ подвижного состава;

• обостряющаяся конкуренция на рынке пассажирских транспортных услуг.

Под воздействием всех этих факторов для обеспечения качественных транспортных услуг населению автотранспортным предприятиям (АТП) необходимо решать следующие организационно-управленческие задачи:

• повышения надежности и безопасности перевозок в течение всего рабочего периода, с акцентом на часы пиковой нагрузки;

• обеспечения выпуска на маршруты необходимого количества подвижного состава;

• организации движения транспорта и контроля за соблюдением графиков работы автомобилей по заданным схемам маршрутов;

• использования прогрессивного подвижного состава, отвечающего современным требованиям к перевозкам пассажиров в больших городах.

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

состояний транспортной системы по обслуживанию пассажиров.

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

Другим вариантом решения задач большой размерности является применение современных методов поиска, в частности генетических алгоритмов (ГА). Главной особенностью таких алгоритмов является использование множества альтернативных решений, позволяющих выполнить поиск перспективных вариантов решений с точки зрения используемого функционала и ограничений [2].

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

Для определения адекватности рекомендуемого метода решения задачи оптимизации процесса организации и управления пассажирскими перевозками для выделенных условий перевозок

предлагается использовать следующие ограничения:

1. Количество предоставляемых

мест

Nm:

Nm < Nvm

у z — у z '

Nvm

где N z — номинальная вместимость z-го автобуса.

2. Продолжительность работы

маршрута Mr (ч):

Tr < Mr < Tr

mm max'

Tr < 6ч Tr < 16ч

J nun — • 5 -» max — 1 • где Fjmin г и ^шах г являются минимальной и максимальной продолжительностью работы маршрута соответственно.

3. Время в наряде Tn (ч):

1 min — 1 — 1 max ,

Tn > 8 ч. Tn < 12 ч.

nun ' max

Z^min n и T^max тт

где ^1Ш111 " и 1 г11" " являются минимальным и максимальным временем соответственно.

4. Прохождение автобуса а через все последующие остановки маршрута,

начиная с начальной остановки X

/ = ], к, где у — номер остановки начала движения.

5. Минимальное время пассажиро-обмена на остановочных пунктах

t% (мин):

1к - 1к ,

ше минимально разрешенного ПДД и безопасного движения и меньше максимально допустимого времени, обеспечивающего качество обслуживания:

/ = 1,А' -1 J = .

7. Количество подвижного состава на линии не должно превышать общего количества автобусов в парке:

AOT < A.

8. Максимальное время ожидания на остановке tm.

max

Для решения задач оптимизации процесса организации пассажирских перевозок предлагается использовать генетический алгоритм, адаптированный к условиям поставленной задачи. При этом необходимо рассмотреть понятия хромосомы, гена, популяции, а также операторов случайных изменений [6].

В качестве хромосомы рассматривается вариант решения задачи, состоящий из элементов решения — генов. Множество вариантов решения составляют популяцию [1, 4].

Для решения поставленной задачи и построения хромосомы в качестве входных параметров были использованы:

- время начала движения каждого автобуса на линии;

- условный номер остановки начала движения;

- количество совершаемых рейсов за время в наряде;

- количество подвижного состава на линии.

С учетом этих параметров предложенная хромосома А будет иметь вид:

где tk — время, отведенное для остановки по графику на £-той остановке.

6. Время перемещения автобуса между остановками должно быть боль-

A = (а1 р1 ^уЬ, а & ,5* ,уЬ, Г2,3

мz z 57 --z _ z г .L.z z ч

а Р ,5 »У7,2, -7г,у ' 'Уг-1,к,к-1)

3 Yi,j ,-,Yi-1,k v v v

Yi,j ,—,f i-1,k

Так, ген а

несет ин-

=

формацию о количестве рейсов; ген р^ = ,Р1>ЫД1^ )

определяет начало движения у-го автобуса в минутах за Ы-й рейс V = 1, г где г — количество автобусов на маршруте за время в наряде; ген б^ =

определяет начало движения у-го автобуса в минутах за Ы-й рейс V = 1, г где г — количество автобусов на маршруте за время в наряде. Гены

_ (1 1 1 УМ \

<1,2 -I /1,2,1' /1,2,2' /1,2,3

\

7+1,3 )-•

у v, N = ( lyV, N lvv, N IV 1 у,1 +1 =( /Л +1,1, /Л +1,2, /

J,

V, N ( ' V, N

У к-1, к = ( /к-1, к ,1,

'Я-Г к ,з

представляют собой векторы временных интервалов прохождения участков маршрута у-м автобусом Ы-го рейса, где

I = 1к.

Ген

задает место начала движения у-го автобуса, V = 1, г, где 2 — количество автобусов на маршруте за время в наряде.

Сравнение хромосом осуществляется следующим образом: из анализируемой популяции Р = .., ТА,..., лучшей считается хромосома с наименьшими нарушениями ограничений, а среди хромосом с равными нарушениями выбирается хромосома с большим значением целевой функции ^ ( ' А) .

Таким образом, получена структура хромосомы, которая представляет собой закодированный вариант движения автобуса по маршруту за время в наряде. Каждая хромосома характеризу-

ется величиной нарушения ограничений и значением целевой функции.

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

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

Условием остановки вычисления целевой функции является достижение максимального количества итераций Ыитер. При этом производится выбор из популяции наилучшего решения. Это решение представлено в виде хромосомы Р , у которой значение целевой функции является наилучшим среди всех хромосом текущей популяции. Таким образом, достигается рациональное решение, к основным итогам которого можно отнести:

• определение оптимального количества подвижного состава, выпускаемого на линию за сутки;

• выявление оптимального количества подвижного состава на линии в часы пик;

• составление оптимального расписания для каждого автобуса по дням недели;

• уточнение дорожной ситуации в текущий момент времени;

• оперативная корректировка расписания движения автобуса в каждый момент времени в зависимости от дорожной ситуации;

• корректировка скорости движения автобуса в зависимости от условий движения;

• установление причины сбоя графика движения;

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

Библиографический список

1. Курейчик, В. В., Курейчик, В. М. Об управлении на основе генетического поиска // Автоматика и телемеханика. — 2001. — № 10.

2. Минкин, Ю. И., Петров, А. И. Самоорганизующийся генетический алгоритм // Известия РАН. Теория и системы управления. — 2001. — № 3.

3. Миротин, Л. Б., Курганов, В. М., Лебедев, А. Информационно-логистическое управление городским пассажирским транспортом // Бизнес и логистика - 2000 : сб. материалов Московского междунар. логистического форума. — М., 2000.

4. Ракитянская, А. Б., Ротштейн, А. П. Генетический алгоритм диагно-

стики на основе нечетких отношений // Известия РАН. Теория и системы управления. — 2001. — № 5.

5. Спирин, И. В. Перевозки пассажиров городским транспортом : справ. пособие. — М. : Академкнига, 2004.

6. Титов, И. В. Совершенствование экономических методов управления пассажирской автотранспортной организацией : автореф. дис. ... канд. эконом. наук. — М., 2012.

Bibliographic list

1. Kureichik, V. V., Kureichik, V. M. On the control based on genetic search // Automation and Remote Control. — 2001. — № 10.

2. Minkin, Yu. I., Petrov, A. I. Self-organizing genetic algorithm // Izvestiya of Russian Academy of Sciences. Theory and Control Systems. — 2001. — № 3.

3. Mirotin, L. B., Kurganov, V. M., Lebedev, А. Logistics Information Management urban passenger transport // Business and Logistics - 2000 : materials of Moscow Intern. Logistics Forum. — M., 2000.

4. Rakityanskaya, A. B., Rothstein, A. P. Genetic algorithm based on fuzzy diagnosis relations // Izvestiya of Russian Academy of Sciences. Theory and Control Systems. — 2001. — № 5.

5. Spirin, I. V. Transportation of passengers by bus : reference. — M. : Akad-emkniga, 2004.

6. Titov, I. V. Improving economic governance passenger road transport operators : author. dis. ... cand. economy science. — M., 2012.