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

На правах рукописи УДК 62-50

0И4603228 ЧЖО МЬО ХАН

ПЛАНИРОВАНИЕ РАСПИСАНИЯ И УПРАВЛЕНИЕ ДВИЖЕНИЕМ ПАССАЖИРСКОГО ТРАНСПОРТА С ИСПОЛЬЗОВАНИЕМ МОДЕЛИРУЮЩЕЙ СРЕДЫ

Специальность 05.13.01 «Системный анализ, управление и обработка информации» (информатика, управление и вычислительная техника)

АВТОРЕФЕРАТ

Диссертации на соискание ученой степени кандидата технических наук

- з июн 2010

Москва-2010

004603228

Работа выполнена на кафедре "Системы автоматического и интеллектуального управления" Московского авиационного института (государственного технического университета).

Научный руководитель: доктор технических наук, профессор

заслуженный деятель науки РФ Лебедев Георгий Николаевич

Официальные оппоненты: доктор технических наук, профессор

Певзнер Леонид Давидович доктор технических наук, профессор Шумилов Юрий Юрьевич

Ведущая организация:

Московский государственный университет путей сообщения (МИИТ)

Защита диссертации состоится "07" июня 2010 г. в -^о часов на заседании диссертационного совета Д 212.125.11 в Московском авиационном институте (государственном техническом университете) по адресу: 125993, г. Москва, А-80, ГСП-З, Волоколамское шоссе, д. 4, заседаний Ученого Совета МАИ.

С диссертацией можно ознакомиться в библиотеке МАИ. Автореферат разослан "^'^010 года.

Д 212.125.11, к.т.н., доцент

Ученый секретарь диссертационного совета

Горбачев Ю.В

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

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

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

К числу особенностей решаемых задач относятся:

- необходимость составления многомерных маршрутов для нескольких ТС, причем в отличие от задачи коммивояжера в некоторых оживленных остановках необходимо прибытие ТС более, чем один раз;

- при составлении графика движения ТС необходимо учесть различные статистические данные о скорости накопления очередей пассажиров на разных остановках;

- начальные и конечные пункты движения для каждого ТС могут не совпадать друг с другом.

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

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

- решить задачу маршрутизации движения заданного числа ТС так, чтобы пассажиры на каждой остановке была обслужены заданное число раз:

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

В данной работе на защиту выносятся следующие основные положения:

1. Эвристический алгоритм многомерной маршрутизации безопасного движения нескольких ТС при обслуживании заданного множества остановок в городском районе.

2. Численный алгоритм параметрической оптимизации моментов выхода в рейс нескольких ТС по выбранным маршрутам для обеспечения максимальной прибыли пассажирских перевозок.

3. Результаты моделирования на ЭВМ, подтверждающие эффективность предложенных алгоритмов.

Научная новизна полученных результатов состоит в следующем.

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

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

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

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

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

Достоверность полученных результатов обусловлена, во-первых, использованием научно-обоснованных численных поисковых методов параметрической оптимизации и линейного программирования, и во-вторых, подтверждается результатами моделирования на ЭВМ, показавшими повышение доходности на 20-30% пассажирских перевозок за счет предложенного подхода.

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

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

1. Известно общее число единиц N городского транспорта -автобусов (рис.1)

2. Заданы координаты х0,у0 (начального) и х^ ук (конечного) пунктов маршрута движения каждого автобуса.

3. Задана конфигурация улиц, зданий (список х^, ул, х12, у2,... в виде прямоугольников) и х^у^ (в виде центральных точек и радиуса круга)

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

5. По одному маршруту в рейс выходит один автобус.

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

7. Скорости движения автобусов V постоянны, известны и одинаковы.

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

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

Требуется:

1. Определить расстояния безопасного движения в городском квартале между каждой парой пунктов и тем самый

определить матрицу IV расстояний между пунктами.

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

3. Сформировать математическую модель оценки дохода и затрат на движение автобусов в виде параметрического критерия.

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

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

6. Показать эффективность предложенного подхода путем моделирования на ЭВМ.

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

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

Рис.2. Пример деления на ячейки городского квартала Каждая ячейка согласно этому методу имеет свои вершины и ребра. Поиск траектории начинается с исходного пункта, при этом на каждом шаге из полученного графа исключаются вершины, которые находятся внутри препятствия, а также ребра, которые имеют пересечение с заданными препятствиями. В результате модификации диаграмма Вороного обеспечивает нахождение безопасного пути между препятствиями до тех пор, пока траектория не попадет в ячейку, содержащую конечную остановку. Так как в каждой ячейке её вершина равноудалена от ребер, найденный путь является наиболее безопасным в окружении препятствий. В то же время в простых ситуациях этот путь является также кратчайшим или, строго говоря, близким к нему. Предварительное моделирование на ЭВМ процедуры определения траектории между двумя остановками подтвердило эти свойства. Примеры определения матрицы расстояний между 9 пунктами с учетом имеющихся препятствий представлены таблицей 1.

Таблица.¡. Пример матрицы расстояний между пунктами маршрутов

П1 П2 ПЗ П4 П5 П6 П7 П8 П9

П1 0 00 00 3 00 оо 00 00 00

П2 04 0 ОО со 5 оо 10 00 00

ПЗ СО оо 0 оо оо 3 оо ОО ОО

П4 оо 00 оо 0 6 3 оо 00 00

П5 оо 5 оо 6 0 7 оо 6 00

П6 оо 00 3 00 7 0 00 00 7

П7 00 10 00 6 00 оо 0 00 оо

П8 оо оо ОО 00 6 оо оо 0 7

П9 00 оо 00 оо оо 7 00 7 0

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

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

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

Рис.3. Пример выбора четырех маршрутов движения при обслуживании 14 пассажирских остановок.

А2к АЗк

А1в

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

попавших в него остановок. Тогда, вычислив заранее расстояние 5 по

прямой между начальным А и конечным А.к пунктами, можно оценить

степень изломанности маршрута через отношение у, а эффективность

маршрута, планируемого более совершенным последующим алгоритмом Дейкстры, можно оценить через приоритет Я..

(!)

г

J

В частности, с помощью формулы (1) потенциальные возможности 4 транспортных средств в примере на рис .3.20 дают такой ответ: 111=0.7; Я2=5; Я3=4; 114=5.

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

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

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

Для формирования критерия предварительно была выбрана экспоненциальная формула дохода с1к от пассажиров при появлении на одной И-гой остановке двух автобусов у и /.

Рис.4. Структурная схема модифицированного алгоритма многомерной

маршрутизации

1-е

\

(2)

где с10 - заданный доход от максимального числа пассажиров, V- известная средняя постоянная скорость автобуса на трассе, а - показатель скорости появления числа пассажиров на остановке, где г^ и гы - расстояния до Ь-гой остановки от начала маршрута для .¡-го и ¡-го автобусов соответственно, т. и - ненулевые моменты начала выезда автобусов } и / в рейс,

подлежащие выбору. В частности, при г. = г(. = 0 автобусы выходят на трассу одновременно.

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

гы ~ гь, = А^у; от, - количество станций, куда }-ый автобус приехал

позже; nJ- количество станций, куда j-ый автобус приехал первым; /у-

количество станций, куда автобусы приходят одновременно, либо интервал между двумя автобусами невелик; А - некоторый временной интервал

Дг.

движения определяющий условия если -д < —- < д , то ¡-ый автобус и у-ый

дГу

автобус пришли одновременно, если — < -д, то у-ый автобус пришел

V

Ч

вторым, если — > д, тоу'-ый автобус пришел первым.(см. рис.5)

V

_/-ыи автобус

Рис.5. Представление дискретного варианта интервалов движения

Тогда формулу дохода Б. ддя] -го автобуса можно представить в общем виде:

1 л.

1-е

1-е

+ ^•¿[1-^] (3)

где к1,к_к1 - коэффициенты достижения различных доходов на остановках трех типов. Заметим, что время задержки ^ входит в слагаемые формулы (3) с разными знаками, т.к. в первом случае выгодно отправляться в рейс позже, а во втором случае раньше других автобусов.

дгу

Проведя дальнейшие упрощения и допустив, что при — > о значение

V

А^ Дгу &гу

— = 2Д , а при — < о значение — = -д, и при К = к = 1; к =0.5 , получим V V V ...

при учете членов второго порядка в ряде Тейлора следующее приближенное выражение при Д > г - г, .

«¿[г-Д + г - г -0.5-а-(2Д + т -г )'] + £[д + г - г - 0.5-а ■ (Д + т - г )'] в • «/ 1.1

+т£|л-г-.-0-5-а-(г\-г-/)'] (4)

Также понадобится формула оценки дохода при линеаризации выражения (4), и при т1 = тк = г, = 0,когда автобусы выходят в рейс одновременно, получим

О , ,

—^=(2-т +и)-Д + г (и,-„) + 0,5/,|г| (5)

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

когда автобусы приходят на остановку одновременно и один их них уходит далее в рейс пустым. Поэтому желательно «развести» их в разные стороны

любым путем, увеличивая |г.|.

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

Далее в главе 4 приведены формулы для предварительной идентификации параметров А и а, входящих в критерии (4) и (5), если есть конкретные примеры получения прибыли в реальных условиях обслуживания пассажиров. Вначале уточним параметр Д, характеризующий средний интервал времени между моментами прибытия двух автобусов на одну остановку. Если для у'-того автобуса число таких остановок с пересекающимся маршрутами равно £ , то оценка д есть средняя величина

. 4г,|Дг.(й)|

*=1 V • ь

1

Считая значения д для каждого автобуса одинаковыми, получим формулу

- 1 ЛГ 1 ^ I , Л = (6)

Значение л,дг (А) могут быть найдены, из исходных данных. Например, воспользуемся при г = г = о, данными таблицы 2, для которой N=8; ь =7, л = ь =5,1 = ь = /. = 6,/ =2 =3, а значения Д/- являются элементами

I 3 ) > < « ' 7 ( !/

этой таблицы. Тогда получим, что д « 6.2 мин.

Теперь перейдем к оценке показателя скорости а увеличения очереди пассажиров в двух случаях, когда этот показатель одинаков и когда возможны два значения ах и аг, (а2>а,) для обычных остановок и в оживленных перекрестках соответственно. Тогда воспользуемся линеаризованной моделью (5) оценки прибыли для ^того автобуса, и при г = г; = 0 определим с её

помощью параметр в первом случае

-

(1 • Д-(2-й, +т ,+0,5-1 )

о у 1 1 ' 1 '

где пртп1. легко определяются из таблицы 2. Поэтому интересующий нас показатель а равен 1 Д, £>

« =----(7)

И-с1о-АТ* 2п1+т1+0,5Л

Например, для данных таблицы 2 и заданных значений дохода DJ значение а = .

Во втором случае, если остановки неравноценны, то тогда можно получить соответствующие оценки

Д..ЦУДЛ . (8)

с1 К Р Р -Р Р Р Р -Р Р

"о 1Ч1гк Г1к Гг 1 1\]12к 'и'и

После идентификации нужных параметров критерия с его помощью проводится оптимизация расписания движения автобусов, проводимая в три этапа. На первом этапе при поиске экстремума важно начальное множество выбираемых параметров т/,_/=У..Лг, определяющие окрестность последующих уточнений. В качестве первого приближения воспользуемся формулой (4), обладающей тем достоинством, что условия максимума дохода сводится к решению линейных алгебраических уравнений, и кроме того, в опорной точке производится выбор всех параметров одновременно.

Используя условия экстремума при а1= а2=а , продифференцируем выражение (4), чтобы получить простую систему линейных уравнений.

т, 1 -гу(юу+яу+/у ) + £>,+][>,=(-Иу+Иу-/у)— = (9)

/=1 у=1 Л

Система уравнений (9) позволяет найти начальное приближение. Рассмотрим применение данного подхода на примере. Пусть дано расписание движения 8 ТС в виде матрицы, представленной в таблице.2 для случая одновременного выезда автобусов в рейс.

Таблица 2 - Матрица интервалов времени между приходом автобусов

на остановки.

00 -7 +6 -6 +8 +9 +1 +10

+7 00 -8 +2 -9 +6 00 00

-6 +8 00 -9 +2 +10 -2 00

+6 -2 +9 00 +7 -6 00 +8

-8 +9 -2 -7 со 00 +2 00

-9 -6 -10 +6 00 00 +8 -7

-1 00 +2 00 -2 СО 00 00

-10 00 00 -8 оо -7 00 00

Данные этой таблицы позволяют составить систему уравнений (9), которой для данного примера соответствует таблица(З). В результате решения данного примера опорной точке соответствует вектор

^ ±1 +з.

'а'аг'а'ог'а'а'аг'а'*

Таблица 3 - Система линейных уравнений.

Т1 Ь Тб ч (п-т-1)/а

-7 1 1 1 1 1 1 1 -30

1 -5 1 1 1 1 0 0 -10

1 1 -6 1 1 1 1 0 -20

1 1 1 -6 1 1 0 1 -40

1 1 1 1 -5 0 1 0 -10

1 1 1 1 0 -6 1 1 20

1 0 1 0 1 0 -3 0 -30

1 0 0 1 0 1 0 -3 30

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

определить приоритет м для случая, когда выбор времени выезда автобуса в

рейс обеспечит наибольший прирост, в виде следующей априорной оценки

Mj = ntj -rtj +lj (10)

На третьем этапе при численном поиске учтем:

- для каждого транспортного средства анализируется три возможных варианта моментов выхода в рейс - г. = 0,т. = т,т. = -г;

- составляющие дохода от одновременного прибытием двух автобусов учтем более строго при детальной зависимости от |z\| в трех дискретных

вариантах - г = -г,0, +г.

- наряду с доходом учтем затраты на эксплуатацию транспортных

средств.

Тогда можно получить следующие оценки, введя обозначения: S- затраты на эксплуатацию одного автобуса при движении/мин; Р - затраты на эксплуатацию руб/мин водителя; ш = r(s + Р) - общие затраты во время рейса одного автобуса

ДЯ/ = Р |г | - затраты в период простоя одного автобуса.

Величину прибыли для трех случаев можно определить по формулам Я. (г = 0) = D (г = 0)-Я/ = а-Д-</(ет + 2л + 0.5/ )-(S + р)- Г (11)

Я (г > 0) = D (т =г)-Ш -ДЯ/ =

, , (12) = а-Д-</(т +2п +0.5lj)-(S + р)-Т + т-[а■di(mi +0.51, - л )-р\

Я (г < 0) = D (г = -г)-Ш -ДЯ/

' ' J J ' , , (13)

= a-Adl(mj+2nj+0.5lj)-(S + p)-T + T-[a-dt(n-m+0.Sli) + pj

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

обозначив т. = х. - у. , где 0 < xJ < г, 0 < у < т - неотрицательные

переменные.

Я=Я +Ф |г| + £г =(Ф + Е )■ х +(Ф - Е )■ у = П +Сх +С у

! ч1 J I Jl J J J 11^1 ]' ^ J •J I 1 /у

где я = я (г = 0) соответствует формуле (11), с и С являются коэффициентами линейной формы критерия, а и Е равны Ф = d (а -I + а I )- р

'г'/ ' Л ^ м (14)

Е, = d. La, \m„ ~n J + a, - «„ )1

Тогда возможны три альтернативы у выбора параметров х/ и у ■ у = 1. х. = г; =0

7 = 2. х = у = 0 или л: = у. -т (15)

Г = 3. = 0; у. = т

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

движения вычисляются значения Ф , Е , а затем коэффициенты С и С .

Определение соответствующей альтернативы при Ф < о осуществляется по следующим правилам.

у = з (г = -г) при Ф + Е < 0, Ф - Е > 0

у = 2 (г = +г) при Ф1 + Е1 > 0, Ф - Е - любая (16)

У = 1 (г = 0) при Ф + Я < 0, Ф - £ < 0 Графическое преставление выбора альтернатив представлено на рис.6.

Рис.6. Графическое представление выбора варианта принятия решения В работе на примерах показано, что если на первом этапе оптимизации после первого попытки в опорной точке общий доход вырос на 15-20%, то последующее улучшение с найденным порядком координатного поиска составило около 10%. Поэтому поиск можно не продолжать, считая эффект от оптимизации достигнутым.

В конце главы 4 дается описание численного алгоритма приближенного составления расписания движения автобусов. Блок-схема этого алгоритма представлена на рис.7.

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

Идентификация параметров а и Л накопления очереди пассажиров по форыуам (6-Я)

*

Формирование ибшщы первоначальных интервалов движения автобусов т таблицы расстояний между остановками

Формироазинс системы ли и ей лих уравнении поиска (9) и определение опорной ючкн

1

/ и /

______________ !

*

Опр елсл с ни с п р к о р н гс I а ТС при выборе направления покоординатного поиска по формуле (10)

/ ^ /

/ ^ / _*_

| 11оКООр4ИИ31МЫЙ числимый лоне* __т яомешоа шеа » рейс

Выбор ыыеряаишы у с иомомы» линейного (|р01раммир0вання по условиям ( 14 н!5 )

._I_

1 Вычисление максимальной прибыли но формуле (14-16)

т_

/ 1 = /

1 Конец

Рис.7. Блок-схема алгоритма численной оптимизация моментов выезда

автобусов в рейс

Результаты опорного решения задачи в данном примере представлены

на рис.8, при следующих числовых данных: с/0=100 руб., Д=5 мин, а=0,1

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

Рис.8. Общий доход в зависимости от номера ТС Нижний график соответствует исходному варианту в случае одновременного выезда в рейс 8 автобусов, средний график показывает улучшенное значение доходов в опорной точке, для которой поправки выбраны одновременно при решении линейных уравнений (9). Верхний график иллюстрирует конечный результат при координатном поиске, свидетельствующих об повышении доходов в целом на 20-^25% от оптимизации. Таким образом, результаты моделирования подтвердили правильность предложенного подхода.

Заключение

На основании проведенных исследований можно сделать следующие

выводы:

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

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

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

маршрут с потенциальным включением большего числа остановок при априорно наименьшей кривизне.

4. Найдена структура эвристического алгоритма многомерной маршрутизации с учетом особенностей движения автобусов в городском районе.

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

6. Моделирование на ЭВМ показало, что в целом оптимизация выбора маршрутов и расписания движения автобусов позволит повысить эффективность пассажирских перевозок на 20^25% .

Список опубликованных работ

1. Лебедев Г.Н., Мирозян JI.A., Михайлин Д.В., Чжо Мьо Хан. "Нейросетевая система планирования и управления одиночными и групповыми действиями беспилотных летательных аппаратов", отчет по НИР,МАИ,2006.-64с.

2. Галютин В.Б., Лебедев Г.Н., Тин Пхон Чжо, Чжо Мьо Хан. "Применение прямых и обратных задач линейного программирования при оптимизации планирования работы наземного и воздушного транспорта", Труды международной научно-технической конференции «Проблемы автоматизации и управления в технических системах», Пенза: Изд-во ПГУ, 2009. Стр 262-264.

3. Галютин В.Б., Галютина O.A., Чжо Мьо Хан. "Использование технологии программируемых интегральных схем (ПЛИС) для реализации иерархических нейроструктур принятия решений", Сборник трудов VI научно-практической конференции «Технологии, научно-техническое и информационное обеспечение в образовании, экономике и производстве региона», МГУТУ, Вязьма, 2007.

4. Галютин В.Б., Чжо Мьо Хан. "Иерархическая нейроструктура принятия решения на основе технологии ПЛИС", //Известия РАН. Математическое моделирование. М.,2007.

5. Галютин В.Б., Галютин O.A., Чжо Мьо Хан. "Планирование движения транспортных средств с использованием моделирующей среды", Сборник трудов "XVII международного научно-технического семинара «Современные технологии в задачах управления, автоматики и обработки информации»", г. Алушта, СПБ.:ГУАП, 2008 г.,286с. стр 8.

и обработки информации»", г. Алушта, СПБ.:ГУАП, 2008 г.,286с. стр 8.

6. Галютин В.Б., Лебедев Г.Н., Чжо Мьо Хан, " Планирование расписания движения пассажирского транспорта с использованием компьютерных моделирующих средств и линейного программирования" "Вестник компьютерных и информационных технологий", город: изд-во, «Машиностроение» 2009 г. №12., стр 9-16.

7. Галютин В.Б., Лебедев Г.Н., Чжо Мьо Хан, "Планирование расписания движения ТС с использованием моделирующей среды и линейного программирования", Труды IX Всероссийской научно-технической конференции «Повышение эффективности средств обработки информации на базе математического моделирования»", г. Тамбов, Сборник трудов Изд-во «ВВАИУРЭ(ВИ)», 2009 г., стр 265273.

8. Галютин В.Б., Лебедев Г.Н., Чжо Мьо Хан, "Планирование расписания движения пассажирского транспорта с использованием компьютерных средств оптимизации и методов линейного программирования", Сборник трудов "Научная сессия ГУАП", С.Петербург, 2009 г., стр 129-132.

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

ТРАНСПОРТА. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ.

§1.1. Актуальность работы.

§ 1.2. Цель диссертационной работы, её научная новизна, достоверность и практическая ценность.

§ 1.3. Научная новизна и практическая ценность работы, её достоверность.

§ 1.4. Общая постановка задачи.

§1.5. Выводы по главе 1.

ГЛАВА 2. РАЗРАБОТКА АЛГОРИТМА ОПРЕДЕЛЕНИЯ ТРАЕКТОРИИ ДВИЖЕНИЯ ОДНОГО ТС МЕЖДУ ДВУМЯ ОСТАНОВКАМИ С УЧЕТОМ ОГРАНИЧЕНИЙ ПРОЕЗДА В ГОРОДЕ.

§2.1. Постановка задачи построения траектории проезда автобуса между двумя остановками в городском квартале.

§2.2. Описание алгоритма определения множества допустимых точек траектории проезда с помощью метода Вороного (диаграмма

Вороного).

§2.3. Выбор траектории проезда между двумя остановками по критерию минимального пути.

§2.4. Моделирование на ЭВМ алгоритма определения траектории движения ТС, проходящий через выбранное множество допустимых точек.

§2.5 Выводы по главе 2.

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

§3.1. Анализ известных алгоритмов маршрутизации и выбор метода

Дейкстры для определения оптимального маршрута.

§3.1.1. Метод ветвей и границ.

§3.1.2. Метод ближайшего соседа.

§3.1.3. Волновой алгоритм.

§3.1.4. Алгоритм поиска в глубину (ширину).

§3.1.5. Алгоритм Беллмана-Форда.

§3.1.6. Алгоритм Дейкстры.

§3.1.7. Алгоритм Джонсона.

§3.1.8. Алгоритм Флойда-Уоршелла.

§3.2. Модификация алгоритма Дейкстры для задачи многомерной маршрутизации.

§3.3. Выводы по главе 3.

ГЛАВА 4. ОПРЕДЕЛЕНИЕ ГРАФИКА ДВИЖЕНИЯ ТС ПО ЗАДАННЫМ МАРШРУТАМ, ОБЕСПЕЧИВАЮЩЕГО МАКСИМАЛЬНУЮ ПРИБЫЛЬ.

§4.1 Постановка задачи оптимизации составления расписания.

§4.2. Формирование параметрического критерия оценки дохода от пассажирских перевозок.

§4.3. Идентификация параметров критерия оценки прибыли пассажирских перевозок при одновременном выезде транспортных средств.

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

§4.5. Уточненное субоптимальное решение задачи на базе линейного программирования.

§4.6. Описание численного алгоритма приближенного решения задачи составления расписания.

§4.7. Оценка эффективности предложенного алгоритма с помощью моделирования на ЭВМ.

§4.8 Выводы по главе 4.

§1.1. Актуальность работы.

Задачи маршрутации и планирования расписания движения по маршруту нескольких транспортных средств (ТС) с целью повышения эффективности их использования являются актуальными для различных видов пассажирского транспорта. [1,5,45] При известных маршрутах движения и пунктах их пересечения возникает задача выбора таких интервалов движения между ТС, чтобы некоторый критерий эффективности принимал оптимальное значение. В качестве такого критерия в данной работе принята максимальная прибыль с учетом затрат на эксплуатацию ТС. Это позволит не тратить лишние ресурсы (топливо), уменьшить другие затраты (время, зарплата), увеличить число обслуживаемых пассажиров, садящихся на остановках и приобретающих билеты за проезд [3,14,18,37,45].

Однако заранее неизвестны как некоторые параметры этого критерия, так и то, что задача составления расписания не имеет точного аналитического решения, которое зачастую принимается экспертом за счет опыта и навыков о том, как стоит изменить интервалы движения в заданные пункты маршрута. Известные трудности возникают и при выборе маршрутов движения группы ТС.[5,9,33]

Для преодоления первой трудности возникает целесообразность воссоздания критерия затрат по отдельным примерам получения прибыли, для того чтобы использовать критерий в окончательной форме в общем случае. [4,6]

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

Третья задача выбора маршрута движения транспортных средств является оптимизационной задачей, часто возникающей на практике. Она может быть сформулирована следующим образом: для некоторой группы пунктов с заданными расстояниями между ними требуется найти кратчайшие маршруты группы ТС с посещением каждого города один или несколько раз и с возвращением в исходную точку. Было доказано[24,26,28], что эта задача принадлежит большому множеству задач, называемых «МР-полными» (недетерминистски полиномиальными). Для ЫР-полных задач не известно лучшего метода решения, чем полный перебор всех возможных вариантов, и, по мнению большинства математиков, маловероятно, чтобы лучший метод был когда-либо найден. [56] Так как такой полный поиск практически неосуществим для большого числа городов, то эвристические методы используются для нахождения приемлемых, хотя и неоптимальных решений.

В основе составления расписания лежат элементы общей теории расписаний. Технологию разработки расписания следует воспринимать не только как трудоемкий технический процесс, содержащий объект автоматизации с использованием ЭВМ, но и как акцию оптимального управления. Таким образом, это - проблема разработки оптимальных расписаний движения ТС. [42,49]

Задачу составления расписания не стоит рассматривать только как некую программу, реализующую функцию составления расписания на начальном этапе, на которой ее (программы) использование и заканчивается. Экономический эффект от более эффективного использования ТС может быть достигнут в результате работы по управлению интервалами между ними. Расписание здесь является лишь инструментом такого управления, и для наиболее полного его использования необходимо, чтобы программа сочетала в себе не только средства для составления оптимального расписания, но и средства для поддержания его оптимальности в случае изменения некоторых входных данных, которые на момент составления расписания считались постоянными. Многокритериальность этой задачи и сложность объекта, для которого строится математическая модель, обуславливает необходимость серьезного математического исследования объекта для увеличения функциональных возможностей алгоритмов составления расписаний без значительного усложнения модели и, как следствие, увеличения объемов используемой памяти и времени решения задачи. [24,25,35,36]

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

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

§4.8 Выводы по главе 4

В результате проведенных исследований можно сделать следующие выводы:

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

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

-ранжировать транспортные средства по их значимости получения прибыли;

-провести покоординатное дискретное уточнение времен выхода автобусов в рейс.

2.Полученые результаты моделирования подтвердили правильность предложенного подхода, и показали, что при принятых допущениях улучшение эффективности транспортных перевозок достигает 2СН-25%.

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

Рис. 4.6. Полная структурная алгоритма маршрутизации и планирования движения нескольких ТС

ЗАКЛЮЧЕНИЕ

На основании проведенных исследований можно сделать следующие выводы:

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

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

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

4. Найдена структура эвристического алгоритма многомерной маршрутизации с учетом особенностей движения автобусов в городском районе.

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

6. Моделирование на ЭВМ показало, что в целом оптимизация выбора маршрутов и расписания движения автобусов позволит повысить эффективность пассажирских перевозок на 2(К25% .

1. А. Ахо, Д. Хопкрофт, Д. Ульман. Структуры данных и алгоритмы. М.: «Вильяме», 2000.

2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоримов. -М.: Мир, 1979.

3. Банди Б. Методы оптимизации: Вводный курс. М.: Радио и связь, 1988.

4. Васильев Ю.Л., Ветухновский Ф.Я., Глаголев В.В. и др. Дискретная математика и математические вопросы кибернетики. М.: Наука, 1974.

5. Васильева Е.М., Игудин Р.В., Лившиц В.Н. и др. Оптимизация планирования и управления транспортными системами М. «Транспорт», 1987.

6. Вентцель Е.С. Введение в исследование операций. Изд-во «Советское радио», 1964.

7. Верж К. Теория графов и ее применения. М.: ИЛ, 1962.

8. Вирт Н. Систематическое программирование. М.: Мир, 1978.

9. Гасс С. Линейное программирование. -М.: Физматгиз, 1961.

10. Гладков Л.А., Курейчик В.М., Курейчик В.В. Основы теории алгоритмов: Учебное пособие по курсу «Математическая логика и теория алгоритмов». — Изд-во ТРТУ, 2002.

11. Глушков В. М., Летичевский A.A. Теория дискретных преобразователей // Избр. Вопр. Алгебры и логики. Новосибирск: Наука, 1973.

12. Глущков В. М., Цейтлин Г.Е., Ющенко Е. Л. Алгебра, языки, программирование. Киев: Наук, думка, 1985.

13. Гришанин Ю.С., Лебедев, Г.Н., Липатов A.B., Степаньянц Г.А. Теория оптимальных систем. — М.: Изд-во МАИ, 1999.

14. Гроссман И., Магнус В. Группы и их графы. М.: Мир, 1971.

15. Емеличев В.А., Мельников О.И. и др. Лекции по теории графов. М.: Наука, 1990.

16. Еремин И.И., Астафьев H.H. Введение в теорию линейного и выпуклого программирования. -М.: Наука, 1976.

17. Ермаков С.М., Жиглявский A.A. Математическая теория оптимального эксперимента. -М.: Наука, 1987.

18. Зуховицкий С.И., Авдеева Л.И. Линейное и выпуклое программирование. — М.: Наука, 1964.

19. Клини С. Введение в метаматематику. М.: ИЛ, 1957.

20. Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ. -М.: «Вильяме», 2006.

21. Куратовский К., Мостовский А. Теория множеств. М.: Мир, 1970.

22. Курош А.Г. Теория групп. М.: Наука, 1967.

23. Лавров И. А., Максимова Л. Л. Задача по теории множеств, математической логике и теории алгоритмов. М.: Наука, 1975.

24. Левитин A.B. Алгоритмы: введение в разработку и анализ. М.: «Вильяме», 2006.

25. МакКоннелл Д. Основы современных алгоритмов. — М.: Техносфера, 2004.

26. Малков В.П., Маркина М.В. Поэтапная параметрическая оптимизация. Учебное пособие. Н.Новгород: Издательство Нижегородского университета, 1998. 142 с.

27. Марков А. А., Нагорный H. М. Теория алгоритмов. М.: ФАЗИСТ, 1996.

28. Морз Ф.М., Кимбелл Д.К. Методы исследования операций Изд-во «Советское радио», 1956.

29. Ope О. Теория графов. М.: Наука, 1980.

30. Плохотников К.Э. Вычислительные методы. Теория и практика в среде MATLAB: курс лекций. Учебное пособие для вузов. М.: Горячая линия-Телеком, 2009.

31. Пономарев В.Ф. Дискретная математика для инженеров. Учебное пособие для вузов. М.: Горячая линия-Телеком, 2009.

32. Понтрягин Л.С., Болтянский В.Г., Гамкрелидзе Р.В., Мищенко Е.Ф. Математическая теория оптимальных процессов. Физматгиз, 1961.

33. Ромакин М.И. Элементы линейной алгебры и линейного программирования. Изд-во «Высшая школа», 1963.

34. Солодовников А. Введение в линейную алгебру и линейное программирование. -М.: Просвещение, 1966.

35. Стенбринк П. Оптимизация транспортных сетей. М. «Транспорт», 1981.

36. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. -М.: Наука, 1986.

37. Таха X. Введение в исследование операций. М.: Мир, 1985.

38. Уилсон Р. Введение в теорию графов. М.: Мир, 1977.

39. Ф.Препарата, М.Шеймос. Вычислительная геометрия: Введение. М.: Мир, 1989.45. форд JI.P., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.

40. Френкель А., Бар-Хиллел И. Основания теория множеств. М.: Мир, 1966.

41. Харрари Ф. Теория графов. М.: Мир, 1973.

42. Харрари Ф., Палмер Э. Перечисление графов. М.: Мир, 1977.

43. Эльсгольц Л.Э. Дифференциальные уравнения и вариационное исчисление. — М.: Наука, 1969.

44. Юдин Д.Б., Гольштейн Е.Г. Линейное программирование. Физматгиз, 1963.51. http://ru.wikiDedia.org/wiki/Алгоритм Дейкстры

45. Dijkstra Е. W. A note on two problems in connexion with graphs. // Numerische Mathematik. V. 1 (1959), pages 269-271.53. http://ru.wikipedia.org/wiki/MeTQд ветвей и границ54. http://ru.wikipedia.org/wiki/Алгоритм поиска А*

46. Ravindra К. Ahuja, Kurt Mehlhorn, James В. Orlin and Robert E. Tarjan. Faster Algorithms for the Shortest Path Problem. Journal of the ACM, 37:213-223, 1990.