На правах рукописи

Сонькин Дмитрий Михайлович

МАТЕМАТИЧЕСКОЕ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ

СИСТЕМЫ ДИСПЕТЧЕРСКОГО УПРАВЛЕНИЯ ТАКСОПАРКОМ

НА БАЗЕ МУЛЬТИКАНАЛЬНЫХ НАВИГАЦИОННЫХ ТЕРМИНАЛОВ

Специальность 05.13.11 – Математическое и программное обеспечение

вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

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

Томск – 2010 2

Работа выполнена в ГОУ ВПО «Национальный исследовательский Томский политехнический университет»

Научный руководитель: доктор технических наук, профессор Погребной Владимир Кириллович

Официальные оппоненты: доктор технических наук, профессор Ехлаков Юрий Поликарпович доктор физико-математических наук, профессор Дмитриев Юрий Глебович

Ведущая организация: ОАО «Российский Институт радионавигации и времени», г. Санкт-Петербург

Защита состоится «24» декабря 2010 г. в 14 часов на заседании совета по защите докторских и кандидатских диссертаций Д 212.269.06 при ГОУ ВПО «Национальный исследовательский Томский политехнический университет»

по адресу: 634034, г. Томск, ул. Советская, 84/3.

С диссертацией можно ознакомиться в библиотеке ГОУ ВПО «Национальный исследовательский Томский политехнический университет»

по адресу: 634034, г. Томск, ул. Белинского 55.

Автореферат разослан «_» ноября 2010 г.

Ученый секретарь совета по защите докторских и кандидатских диссертаций, к.т.н., доцент М.А. Сонькин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. Роль пассажирского такси, как составной части городского транспорта, в современном городе постоянно растет: появляются новые жилые районы, повышается темп жизни, изменяются требования потребителей к персональному транспортному обслуживанию. Вместе с тем в работе пассажирского такси появился ряд дополнительных, ранее не существовавших проблем: существенно возросла плотность транспортных потоков современного города, возрос уровень требований пассажиров к оперативности и сервису обслуживания, появилась существенная конкуренция на рыке предоставления услуг городского пассажирского такси. Так, например, даже в средних по численности городах (Томск, Кемерово, Иркутск, Барнаул и других – 400-800 тыс. жителей) действуют десятки транспортных предприятий, предоставляющих услуги такси. В Новосибирске на середину 2010 года зарегистрировано более 130 предприятий городского пассажирского такси.

Автоматизация диспетчерского управления таксопарком направлена как на повышение эффективности работы самого транспортного предприятия, так и на решение социально-экономических задач города, в том числе:

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

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

Решение указанных задач направлено на повышение безопасности движения, улучшение культуры обслуживания населения, снижение стоимости перевозок, обеспечение контроля за деятельностью транспортных предприятий и закреплено рядом нормативных документов, среди которых следует выделить: Постановление Правительства РФ от 25 августа 2008 г. N 641 (Об оснащении транспортных, технических средств и систем аппаратурой спутниковой навигации ГЛОНАСС или ГЛОНАСС/GPS); Федеральный закон от 9 февраля 2007 г. N 16-ФЗ (О транспортной безопасности, с изменениями от 23 июля 2008 г., 19 июля 2009 г., 29 июня 2010 г.).

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

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

Научные основы моделирования движения транспортных средств, заложены в трудах российских и зарубежных ученых: Г.В. Болоненков, В.А.

Гудков, А.В. Вельможин, Г.Д. Линник, Э.Е. Мун, М.Е. Антошвили, Г.А.

Варелопуло, С.Ю. Либерман, И.В. Спирин, А.О. Арак, А.П. Артынов, В.В.

Скалецкий, Ю.С. Лигум, В.Н. Ембулаев, А.В. Пупышев, В. Шутый, Б.Д.

Прудовский, Г. А. Кондратьев, P. Behrhard, N. Kliwer, S. Terporter и другие.

Научно-методическим основам современных информационных технологий на базе сетей ЭВМ и телекоммуникаций для задач диспетчерского управления посвящены труды В.А. Поначугина, В.И. Рассоха, Е.В. Бондаренко и других.

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

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

Задачи для достижения поставленной цели.

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

2. Исследование существующих подходов к организации систем мониторинга и управления различными транспортными средствами.

3. Адаптация принципов построения систем мониторинга труднодоступных и подвижных объектов для задач диспетчерского управления таксопарком.

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

5. Разработка алгоритмов:

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

• динамической пакетизации навигационной, системной и производственной информации для основного и резервных каналов связи;

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

6. Программная реализация разработанных алгоритмов.

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

Научная новизна.

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

2. Модернизирован алгоритм Куна для определения максимального паросочетания «Автомобиль - Заказ» путем использования «жадного»

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

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

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

Основные положения, выносимые на защиту.

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

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

3. Комбинированный алгоритм динамической пакетизации навигационной, системной и производственной информации на основе дельтакодирования и бинарного преобразования позволяет уменьшить общий объем передаваемых данных (в соответствии с полученными аналитическими зависимостями) и сформировать данные для передачи по резервным каналам связи.

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

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

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

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

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

Реализация результатов работы.

Разработанные алгоритмы использованы при создании программных модулей для следующих систем:

• информационно – телекоммуникационная система диспетчерского управления таксопарком «АГАТ» (внедрена в диспетчерских службах таксопарков «Мой город» и «Зеленоглазое такси», г. Новосибирск);

• бортовой комплекс подвижного объекта системы мониторинга лесопожарной обстановки «ЯСЕНЬ-БКПО» (внедрен в «Центральной базе авиационной охраны лесов «Авиалесоохрана», г. Пушкино Московской области);

• аппаратно-программный комплекс визуализации, подготовки и передачи гидрометеорологической информации от подвижных объектов «АПКМЕТЕО-К»;

• Госконтракт № П2396 «Создание интеллектуальных систем навигации и управления» в рамках ФЦП «Научные и научно-педагогические кадры инновационной России» 2009–2013 гг.

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

Информационно – телекоммуникационная система «АГАТ» используется для автоматизации работы диспетчерских служб двух таксопарков г.

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

Кроме того, алгоритм динамической пакетизации навигационной, системной и производственной информации на основе дельта-кодирования и бинарного преобразования программно реализован и включен в состав бортового комплекса подвижного объекта системы мониторинга лесопожарной обстановки (ИТС «ЯСЕНЬ-БКПО») для Центральной базы авиационной охраны лесов «Авиалесоохрана», г. Пушкино Московской области.

Практическая ценность работы подтверждается актами внедрения.

Автор выражает благодарность специалистам ООО «ИНКОМ»

(г.Томск) за помощь при внедрении результатов диссертационных исследований.

Личный вклад автора.

1. Постановка задач исследования и разработка концепции алгоритмического и программного обеспечения ИТС «АГАТ» выполнены автором совместно с заместителем директора ГК «Мой город» Рыдкиным Е.М.

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

3. Разработка параметрического подхода к формированию и передаче данных от подвижных объектов выполнена автором совместно с Шкуратовым А.В., Миньковым А.С.

4. Разработка нового способа и комбинированного алгоритма динамической пакетизации навигационной, системной и производственной информации на основе дельта-кодирования и бинарного преобразования выполнены автором совместно с Шкуратовым А.В., Саврасовым Ф.В.

5. Модернизация алгоритма Куна для определения максимального паросочетания «Автомобиль - Заказ» путем использования «жадного» алгоритма на этапе формирования базового паросочетания выполнена лично автором.

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

Апробация работы. Основные результаты диссертационной работы докладывались на следующих конференциях:

• Всероссийских научно-технических конференциях студентов, аспирантов и молодых ученых «Молодежь и современные информационные технологии» (г. Томск, 2006, 2007, 2008 г.);

• IX Международной научно-практической конференции “Исследование, разработка и применение высоких технологий в промышленности" (г. Санкт-Петербург, 2010 г.);

• VII Всероссийской научно-практической конференции-конкурсе «Технологии Microsoft в теории и практике программирования» (г.

Томск, 2010 г.).

• Международной научно-практической конференции «Интеллектуальные информационные системы для труднодоступных и подвижных объектов»

(г. Томск, 2010 г.).

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

• Диплом 11 Межрегиональной специализированной выставки-ярмарки «Средства и системы безопасности. Антитеррор» в конкурсе "Сибирские Афины" за разработку информационно-телекоммуникационной системы автоматизации диспетчерского управления городским автопарком такси (ИТС «АГАТ») (ОАО ТМДЦ «ТЕХНОПАРК», г. Томск, 2009 г.);

• Медаль Всероссийской выставки-ярмарки «Итеграция-2010» в конкурсе "Сибирские Афины" за разработку системы диспетчерского управления транспортом (ОАО ТМДЦ «ТЕХНОПАРК», г. Томск, 2010 г.);

• Диплом специализированной выставки «Электроника-Транспорт 2010»

(ВВЦ, г. Москва, 2010 г.).

Публикации. По теме диссертационной работы опубликовано научных работ, в том числе 3 статьи в изданиях, рекомендованных ВАК для опубликования результатов диссертаций. Получено 2 свидетельства о регистрации программ для ЭВМ.

Структура и объем работы. Диссертационная работа включает:

введение, четыре главы, заключение, список литературы из 106 наименований, 9 приложений. Общий объем диссертации составляет 175 страниц машинописного текста. Работа содержит 45 рисунков, 15 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

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

Большинство систем в качестве основного канала связи используют радиоканал в голосовом режиме. Для подавляющего большинства систем он также является единственным каналом связи, что накладывает ряд ограничений: количество абонентов на одном канале 50-70; возможны искажения при передаче информации; время доведения информации высоко.

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

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

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

Системы мониторинга таксопарков, по своей сути, являются иерархически распределенными системами реального времени. Поэтому, при разработке новой системы данного класса целесообразно использовать известные методы построения распределенных систем мониторинга подвижных и труднодоступных объектов, предложенных в работах ученых Томского политехнического университета и специалистов ООО «ИНКОМ». Данные принципы адаптированы и развиты применительно к построению системы диспетчерского управления таксопарком (рис. 1) с учетом специфики объектов такого рода.

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

Принцип 2. Интеграция центров диспетчерского управления таксопарками – позволят связать отдельные элементы в одну систему.

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

Принцип 4. Совмещение работы систем передачи данных для подвижных объектов – повышает надежность доведения информации и управляемость всей системой.

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

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

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

Рис. 1. Адаптация принципов построения систем мониторинга Информация, передавая с мобильных терминалов делится на три категории: навигационную, системную и производственную. Анализ информации необходимой к передаче от автомобилей такси в ДЦ показал, что основной объем информации (более 85%), составляют навигационные данные о маршруте движения и о текущем местоположении автомобилей такси. Оставшаяся часть – это различного рода системная и производственная информация.

Для уменьшения частоты передачи данных с сохранением возможности оперативного обмена информацией применен «параметрический» подход к формированию данных. Основная идея данного подхода заключается в фиксации данных не с заданным жёстким временным интервалом, а по превышению ряда настраиваемых управляющих значений параметров. В качестве таких параметров P выделены: tm – суточный маяк; tmp – периодический маяк; s – пройденное расстояние; u – угол поворота; vmax – превышение скорости; kin – вход в контрольную точку/зону; kout – выход из контрольной точки/зоны; kline – прохождение контрольной линии ; aj – срабатывание датчика; bk – сообщение – по инициативе водителя отправляется производственная информация (ответ/запрос/подтверждение). Введя для каждого параметра P приоритет срочности, соответствующие данные могут быть: немедленно отправлены в центр сбора данных; зафиксированы и отправлены в центр сбора данных с ближайшим пакетом по интервалу передачи данных; зафиксированы и сохранены в энергонезависимой памяти терминала.

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

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

В опорном блоке находится дата и время начала формирования пакета (DT), служебная информация о навигационных данных (SS) и координаты опорной точки (Y, X).

Содержимое дельта блока N состоит из заголовка подблока (PB N), смещения времени относительно предыдущего блока/подблока (TO N, TOD N.1, TOD N.2, TOD N.3), смещения координат относительно предыдущего блока/подблока (SS N, YO N.1, YO N.2, XO N.1, XO N.2), описания событий произошедших в указанный момент времени (EvC N, EvID N.1-EvID N.M, EvD N.1-EvD N.M), дополнительно присоединенных данных (bED N, EDid N, ED N).

Отношение размера пакета (пакетов) к объему полезной передаваемой информации приведено на рис. 3, где: H- объем полезной передаваемой информации; L – размер пакета; h1 – объем полезной передаваемой информации, при котором размеры пакетов графиков I и II равны l1; h2 – объем полезной передаваемой информации, при котором размер пакета графика II меньше размера графика I на величину l2.1-l2.2.

Рис. 3. Отношение размера пакета к объему передаваемой информации На графике I отображена ситуация, когда для передачи данных не используются никакие алгоритмы сжатия. Размер передаваемых пакетов растет линейно и напрямую зависит от объема полезной передаваемой информации. На малых объемах информации такой подход обеспечивает хорошую экономичность за счет отсутствия «лишних» данных. На графике II приведен пример использования комплексного алгоритма динамической пакетизации. На малых объемах информации он имеет больший размер, в связи с добавлением системных полей. С ростом объема полезной передаваемой информации размер пакета увеличивается нелинейно, и отношение длины пакета к объему полезной передаваемой информации уменьшается.

В реальных условиях, наиболее распространена ситуация h2, когда выгода от использования второго подхода перекрывает его недостатки до точки h1.

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

Блок схема работы алгоритма приведена на рис. 4.

В приведенной структуре показано, что пакет не имеет явных ограничений на длину (количество подблоков), поэтому ее необходимо ограничивать основываясь на наступлении приоритетного события (например tm, tmp, bk, достижения пакета определенного размера и др.). Размеры подблоков зависят от заложенной размерности полей EvC N, EDid N, EvID N.M.

В диссертации разработана обобщенная структура программного обеспечения системы диспетчерского управления таксопарком.

Рис. 4. Блок схема комбинированного алгоритма динамической пакетизации В третьей главе система такси рассматривается как система массового обслуживания (СМО). Приводится описание разработанного алгоритма распределения заказов на обслуживание автомобилями такси.

Служба такси, по своей сути, это система массового обслуживания, где потребность клиента в перемещении является заявкой на обслуживание, а автомобиль такси – обслуживающим аппаратом.

Рассмотрим дисциплину обслуживания заявок в таксопарке. Таксопарк, как система массового обслуживания, состоит из j линий (каналов), где j = 1, n, которые могут одновременно принимать заявки. В любой момент времени канал Kj находится в одном из двух состояний – занят либо свободен. В некоторый момент времени в таксопарк диспетчеру поступает заявка на обслуживание. Обслуживание заявки продолжается некоторое время, после чего канал освобождается и готов к приему следующей заявки. Заявки образуют поток – последовательность с некоторым чередованием моментов их появления во времени. Понятно, что заявки имеют разный приоритет и накладывают различные требования на обслуживание. Если в требуемый момент времени имеется свободный обслуживающий аппарат (автомобиль такси), то заявка принимается к обслуживанию. В случае если все обслуживающие аппараты заняты, запрос продолжает оставаться в системе. Таким образом, рассмотренная СМО - система с ожиданием, в которой имеется накопитель практически бесконечной ёмкости для хранения поступивших требований, при этом ожидающие заказы образуют очередь.

Таким образом, службу такси можно разделить на две взаимосвязанные СМО. Первая СМО отвечает за прием заявок на обслуживание, где линиями (каналами) обслуживания являются диспетчера. Вторая СМО отвечает за распределение поступивших заявок между автомобилями такси.

Для службы такси характерно то, что процесс функционирования такой системы представляется в виде последовательности отдельных фаз обслуживания, выполняемых различными устройствами. Причем соблюдается порядок, в соответствии с которым каждое последующее устройство (канал обслуживания) приступает к обслуживанию запроса только тогда, когда работа предыдущего устройства с данным запросом закончена. Процесс оказания транспортной услуги можно условно разбить на несколько фаз: принятие диспетчером заказа по телефону, назначение автомобиля такси, который будет обслуживать данный вызов, выезд автомобиля такси и оказание транспортной услуги. В общем виде функционирование системы представлено на рис. 5, где D1-Dn - диспетчеры, а A1-Am – автомобили такси.

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

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

Рис. 5. Схема службы такси как системы массового обслуживания Задачу автоматизации процесса распределения заказов на обслуживание заказов клиентов такси между автомобилями таксопарка целесообразно представить в виде двудольного графа G=(Z,A), где Z={z1,…,zn} – множество поступающих заказов, A={a1,…,am} – множество автомобилей такси, готовых их выполнить, а Y={yij}; i = 1,n ; j = 1,m – множество ребер, связывающих вершины из множества Z c вершинами множества A (рис. 6 а)).

Рис. 6. Представление задачи распределения поступающих заказов Следует отметить, что в общем случае каждый из заказов может быть принят и выполнен любым автомобилем такси. Это соответствует случаю, когда каждая вершина zi Z может быть связана со всеми вершинами множества A, т. е. коэффициент инцидентности iZ каждой вершины zi находится в диапазоне 0 iZ m. Аналогично каждый автомобиль такси с различной эффективностью может обслужить любой поступивший заказ, т. е. каждая вершина a j A может быть связана со всеми вершинами множества Z, и соответственно коэффициент инцидентности jA каждой вершины aj находится в диапазоне Каждому ребру из множества Y может быть поставлен в соответствие интегральный критерий эффективности ki, j K. При этом ki, j = f (ki1, j, ki2, j..., kipj ), где p– число локальных весовых коэффициентов, таких как: удаленность от места назначения, тип автомобиля, процент выполнения дневного плана, тип клиента и др. Таким образом, при распределении заказов необходимо из всего множестn m росочетаний (заказ-автомобиль), которая в наилучшей степени удовлетворяла бы заданному интегральному критерию эффективности K. Иначе говоря, необходимо таким образом распределить полученные заказы между автомобилями такси, что бы достичь максимальной эффективности F при их выполнении (рис.

6 б)):

где ki, j – интегральный критерий эффективности, учитывающий p весовых локальных коэффициентов для i-го водителя при выполнении j-го заказа; xi, j – элемент искомой матрицы назначений (матрицы неизвестных), n- количество автомобилей, m- количество заказов.

Для решения этой задачи предложен следующий алгоритм:

Шаг 1. Формирование двудольного графа G=(Z,A), где Z = {z1,..., zn } – множество поступающих заказов и A = {a1,..., am } – множество автомобилей такси, готовых их выполнить.

Шаг 2. Определение стратегии распределения заказов в соответствии с оперативной ситуацией: S = f ( s1, s2, si, sk ), где факторы si определяют текущую загрузку, соотношение между количеством автомобилей и количеством заказов, общую размерность графа G и др. Если выбрана стратегия 1, то выполняется Шаг 3, в противном случае Шаг 6.

Шаг 3. Расчет локальных критериев эффективности, соответствующим ребрам графа G.

Шаг 4. Преобразование графа G в граф G '. Целью преобразования является уменьшение мощности множества вершин Z или вершин множества A по критерию min(m,n).

Шаг 5. Решение задачи оптимального распределения заказов (множество вершин Z) между водителями такси (множество вершин A) Венгерским методом. Переход на Шаг 7.

Шаг 6. Решение задачи максимального распределения заказов (множество вершин Z) между водителями такси (множество вершин A) модернизированным алгоритмом Куна.

Шаг 7. Формирование двудольного графа G ' ' = ( Z ' ', A' ' ) по критерию отказа водителей от выполнения заказа, где A' ' A множество водителей, отказавшихся от выполнения заказа, а Z ' ' Z – заказы, на выполнение которых пришел отказ от водителей.

Шаг 8. Формирование нового графа G с учетом ограничений, накладываемых графом G ' ' (Шаг 1) или прекращение работы.

В результате выполнения предложенного алгоритма в каждый дискретный момент времени ti формируется искомое множество паросочетаний P.

Множества A' и Z ', а также множества A' ' (нераспределенные автомобили) и Z ' ' (нераспределенные заказы) переходят для рассмотрения в момент времени ti+1.

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

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

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

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

Основными компонентами разработанного по результатам диссертационного исследования программного обеспечения для системы диспетчерского управления таксопарком «АГАТ» являются:

- модуль «Order» оперативного распределения заказов между автомобилями такси;

- модуль «SyncDB» динамической синхронизации оперативных данных для резервного управления и перераспределения заказов локальных диспетчерских центров таксопарков на основе экспресс-анализа информационных потоков;

- модуль «DinamicPack» динамической пакетизации навигационной, системной и производственной информации для основного и резервных каналов связи.

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

Приведены результаты исследования эффективности разработанных алгоритмов по таким показателям как: вычислительная сложность;

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

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

Рис. 7. Графики зависимости времени нахождения требуемого паросочетания Для комбинированного алгоритма динамической пакетизации данных приведены результаты загрузки центрального процессора мультиканального навигационного терминала «МОБИС-Т» в обычном режиме и во время работы алгоритма; приведены результаты построения кривых зависимости К (коэффициента сжатия) от различных входных условий (формата навигационного блока, размера навигационного пакета, частоты фиксации данных и др.);

Опыт эксплуатации системы диспетчерского управления таксопарком «АГАТ» показал высокую эффективность разработанных программных модулей. Скорость работы диспетчерской службы возрастает в 1,5-2,1 раза (в зависимости от конфигурации системы), что доказывает эффективность разработанных алгоритмов.

Пример экранной формы приема заказа и назначения автомобиля такси системы диспетчерского управления таксопарком «АГАТ» приведен на рис. 8.

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

Рис. 8. Форма приема заказа и назначения автомобиля такси Основные результаты работы:

1. Разработаны новые алгоритмы обработки данных для системы диспетчерского управления таксопарком:

• алгоритм динамической синхронизации оперативной информации в базах данных локальных таксопарков;

• алгоритм комбинированной динамической пакетизации навигационных, системных и производственных данных;

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

2. Проведено тестирование эффективности разработанных алгоритмов.

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

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

4. Программные модули «Order», «SyncDB», и «DinamicPack», реализующие предложенные в диссертационной работе алгоритмы, включены в состав системы диспетчерского управления таксопарком «АГАТ».

5. Программный модуль «DinamicPack», включен в состав бортового комплекса подвижного объекта системы мониторинга лесопожарной обстановки (ИТС «ЯСЕНЬ-БКПО»).

6. Система диспетчерского управления таксопарком «АГАТ» внедрена в двух таксопарках г. Новосибирска.

7. Бортовой комплекс подвижного объекта системы мониторинга лесопожарной обстановки (ИТС «ЯСЕНЬ-БКПО») внедрен в ФГУ «Центральная база авиационной охраны лесов «Авиалесоохрана», г. Пушкино Московской области.

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

Публикации по теме диссертации:

В изданиях, рекомендованных ВАК:

1. Шамин А.А., Сонькин Д.М. Оценка пропускной способности систем пакетной передачи данных с «пульсирующей» загрузкой канала связи.

Вычислительные технологии. – Том 12, Спец. выпуск 1. – Новосибирск:

Институт вычислительных технологий СО РАН, 2007. – С. 29–33.

2. Сонькин Д.М. Адаптивный алгоритм распределения заказов на обслуживание автомобилями такси // Известия Томского политехнического университета. – 2009. – Т. 315. – № 5. – С. 65-69.

3. Сонькин Д.М., Саврасов Ф.В., Шкуратов А.В., Миньков А.С. Унификация форматов данных при взаимодействии с терминалами такси // Известия Томского политехнического университета. – 2010. – Т. 317. – № 5.

Свидетельства о регистрации программ:

4. Сонькин М.А., Котельников Р.В., Обухов М.О., Шкуратов А.В., Белов В.В., Комлев А.Н., Печерская Е.И., Семыкин С.В., Сонькин Д.М., Антонов В.А.

Подсистема мониторинга лесопожарной обстановки на основе аппаратнопрограммного комплекса контроля местоположения воздушных судов и других подвижных объектов в режиме реального времени // Свидетельство о государственной регистрации программы для ЭВМ, №2007614629. – 2007.

5. Сонькин М.А., Печерская Е.И., Тогидний Р.Л., Добродеева П.С., Назмутдинов Р.Б., Шкуратов А.В., Сонькин Д.М., Миньков А.С.

Специальное программное обеспечение аппаратно-программного комплекса визуализации, подготовки и передачи гидрометеорологической информации (АПК-МЕТЕО-К) // Свидетельство о государственной регистрации программы для ЭВМ, №2010612830. – 2010.

Публикации в других изданиях:

6. Сонькин М.А., Сонькин Д.М., Критерии формирования аппаратнопрограммного кластера для передачи оперативных данных из труднодоступных объектов // Молодежь и современные информационные технологии: Сборник трудов IV Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых. – Томск, 2006. – С.

405–406.

7. Сонькин Д.М., Сонькин М.А. Оптимизация процедур формирования выходных документов в информационных системах на основе SQL – сервера// Молодежь и современные информационные технологии: Сборник трудов V Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых. – Томск, 2007. – С. 264–265.

8. Сонькин Д.М., Семыкин С.В., Сонькин М.А. Система мониторинга и управления транспортными средствами с использованием нескольких типов каналов связи // Молодежь и современные информационные технологии:

Сборник трудов V Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых. – Томск, 2007. – С. 448–450.

9. Белов В.В., Сонькин Д.М. Некоторые задачи автоматизации городского такси с использованием микропроцессорных терминалов // Молодежь и современные информационные технологии: Сборник трудов VI Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых. – Томск, 2008. – С. 18–19.

10. Сонькин Д.М., Семыкин С.В. Адаптивный конвертер данных переменной структуры // Молодежь и современные информационные технологии:

Сборник трудов VI Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых. – Томск, 2008. – С. 71–72.

11. Сонькин Д.М. Способ программной интеграции автоматизированных информационно-телекоммуникационных систем с центром обслуживания звонков // VII Всероссийская научно-практическая конференция-конкурс «Технологии Microsoft в теории и практике программирования». – Томск, 12. Сонькин Д.М. Особенности программного обеспечения системы диспетчерского управления такси // IX Международная научнопрактическая конференция “Исследование, разработка и применение высоких технологий в промышленности". – Санкт-Петербург, 2010. – Т.3. – С. 146-149.

13. Сонькин Д.М., Саврасов Ф.В., Шкуратов А.В., Миньков А.С.

Универсальный интерфейс для аппаратно-программной платформы мобильных объектов систем мониторинга и управления транспортом // Материалы международной научно-практической конференции «Интеллектуальные информационные системы для труднодоступных и подвижных объектов». – Томск, 2010.