Математическое и программное обеспечение системы диспетчерского управления таксопарком на базе мультиканальных навигационных терминалов тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Сонькин, Дмитрий Михайлович

• Сонькин, Дмитрий Михайлович
• кандидат технических наук
• 2010

Оглавление диссертации кандидат технических наук Сонькин, Дмитрий Михайлович

ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ.

ВВЕДЕНИЕ.

1 ИССЛЕДОВАНИЕ СУЩЕСТВУЮЩИХ СИСТЕМ МОНИТОРИНГА И УПРАВЛЕНИЯ ТРАНСПОРТОМ.

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

1.2 Основные задачи диссертации.

1.3 Исследование существующих подходов и систем.

1.3.1 Автоматизация службы такси.

1.3.2 Автоматизация городского пассажирского транспорта.

1.3.3 Автоматизация спецтранспорта.

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

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

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

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

2.1.1 Разработка алгоритма интеграции центров диспетчерского управления таксопарками.!.

2.1.2 Комбинированный алгоритм динамической пакетизации* навигационной, служебной и производственной информации.

2.2 Построение программного обеспечения системы диспетчерского' управления таксопарком.

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

3 РАЗРАБОТКА СПОСОБА АВТОМАТИЗАЦИИ РАСПРЕДЕЛЕНИЯ ЗАКАЗОВ НА ОБСЛУЖИВАНИЕ АВТОМОБИЛЯМИ ТАКСИ.

3.1 Система диспетчерского управления такси как система массового обслуживания.

3.1.1 Обоснование возможности рассмотрения системы^диспетчерского управления такси как системы массового обслуживания

3.1.2 Анализ информационных потоков реального таксопарка.

3.2 Разработка общего алгоритма распределения заказов.

3.2 Формализация и математическая постановка задачи оптимального распределения заказов между водителями такси.

3.3 Разработка алгоритма оптимального назначения заказов автомобилям такси.

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

3.3.2 Поиск оптимального распределения заказов Венгерским методом .96 3.5 Выводы по главе 3.

4 ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ ДИССЕРТАЦИОННЫХ ИССЛЕДОВАНИЙ.

4.1 Программный модуль «Блок расчета стоимости поездки».

4.2 Программная реализация метода распределения заказов такси.

4.2.1 Особенности программной реализации модуля «Алгоритм Куна».

4.2.2 Особенности программной реализации модуля «Венгерский метод»

4.3 Программная реализация Блока формирования документов.

4.4 Верификация программного обеспечения.

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

Введение диссертации (часть автореферата) на тему «Математическое и программное обеспечение системы диспетчерского управления таксопарком на базе мультиканальных навигационных терминалов»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• ■ Медаль Всероссийской выставки-ярмарки «Итеграция-2010» в конкурсе

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

• Диплом специализированной выставки «Электроника-Транспорт 2010» (ВВЦ, г. Москва, 2010 г.).

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

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

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Сонькин, Дмитрий Михайлович

4.4 Выводы по главе 4

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

4.4.2 Разработанный программный модуль «Блок расчета стоимости поездки» позволяет учитывать различные тарифные планы при расчете стоимости поездки, что позволяет его использовать для любого таксопарка.

4.4.3 Время формирования месячных (годовых) отчетов документов «Поступающие заказы», «Статистика по работе водителей», «Статистика по работе диспетчеров» составляет не более 1,5 минут и удовлетворяет требованиям заказчиков. л

4.4.4 Программные модули («Order», «SyncDB», «DinamicPack», «Поступающие заказы», «Статистика по работе водителей», «Статистика по работе диспетчеров» и «Блок расчета стоимости поездки»), разработанные в рамках диссертационного исследования, подтвердили работоспособность и эффективность предложенных алгоритмов и используются в составе системы диспетчерского управления таксопарком.

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Сонькин, Дмитрий Михайлович, 2010 год

1. Дажин В. Маршрутные такси и транспортная политика // Автомобильный транспорт. 2002. №10. С. 14-16.

2. Ефремов И.С. Теория городских пассажирских перевозок. М.: Высшая школа, 1980. 535 с.

3. Калантаров Г.С. Совершенствование работы автобусов на городских маршрутах во внепиковые периоды (на примере города Москвы) : автореф. дис. канд. техн. наук. М., 1994. 20 с.

4. Каплан Э.Т. Совершенствование методов диспетчерского оперативного управления. Алма-Ата: Минавтотранс КазССР,' 1984. С. 20-23.

5. Касаткин Ф.П. Организация перевозочных услуг и безопасность транспортного процесса. М.: Академический Проект, 2005. 352 с.

6. Катулев, А.Н. Современный синтез критериев в задачах принятия решений. М.: Радио и<связь, 1992. 120 с.

7. Кривошеенко Ю.В. Организация оперативного управления движением городских автобусов, с учетом закономерностей прибытия пассажиров на остановочные пункты : автореф. дис. канд. техн. наук. М., 1982. 20 с.

8. Крупник В.Ш. Совершенствование технологии составления расписаний движения городского пассажирского транспорта с целью повышения эффективности его работы : дис. канд. техн. наук. М., 1980.

9. Лопатин А.П. Моделирование перевозочного процесса на городском пассажирском транспорте. М.: Транспорт, 1985. 144 с.

10. Лохов А. Совершенствование управления^ городским пассажирским транспортом // Автотранспортное предприятие. 1999. № 12. С. 10-13.

11. Макаров И.П. Автоматизация управления городским транспортом. М.: Транспорт, 1981. 152 с.

12. Мильнер Б.З. Системный подход к организации управления. М.: Экономика, 1983. 224 с.

13. Обыденов А.П. Совершенствование системы управления автотранспортным предприятием. М.: Транспорт, 1992. 195 с.

14. Постолит А. Повышение эффективности пассажирских перевозок при использовании комплексного бортового оборудования // Автомобильный транспорт. 2005. №4. С. 38-41.

15. Спирин И.В: Организация и управление пассажирскими автомобильными перевозками. М.: Академия, 2003. 400 с.

16. Тарасик В.П. Эффективность интеллектуального управления городским автобусом // Автомобильная промышленность. 2002. №11. С 22-25.

17. Хрущев М.В. Составление оптимальных схем. автобусных маршрутов в городах с использованием ЭЦВМ «Урал-2» // Организация и экономика автомобильного транспорта. М.: Транспорт, 1970. С. 119-133.

18. Либерман С Ю Исследование и разработка методов рациональной организации движения автобусов на городских маршрутах: автореф. дис. канд. техн. наук. М.: 1979.

19. Hibbs J. Transport policy: The myth of integrated planning. London: The institute of economic affairs, 2000. 111 pp.

20. Rybak J. Salzburg: öffentlicher Verkehr Wird teurer // SLP. 2007. №2.

21. Breitinger E. Die Lieblinge des Publikuns // OMNIBUS. 2003. №3.

22. Kliewer, N. Effizienr erhohen im OPNV Optimierung des Fahrzeugeinsatzesem öffentlichen Personennahverkehr. // OR News. 2007. №7.

23. Terporter, S. Ein neues Verfahren zur Kombination von Mehrfahrgast-taxi und OPNV. Das KOMET-SYSTEM. Dussburg: Univ. Duss-burg-Essen, Fachgebiet Verkehrswegen und Verkehrsbau, 2004.143 pp.

24. Мун Э.Е., Рубец А.Д. Оптимизация перевозок пассажиров маршрутными такси. М.: Транспорт, 1986. 136 с.

25. Пассажирские автомобильные перевозки: учеб. для вузов / В:А. Гудков и др.. М.: Горячая линия Телеком, 2004. 448 с.

26. Плетнева Н.Г., Лукинский В.В., Пластуняк И.А. Моделированиепроизводственных процессов на транспорте: учеб. пособие. СПб.: СПбГИЭУ, 2003. 110 с.

27. Рюгер 3. Эксплуатация городского пассажирского транспорта. М.: Транспорт, 1977. 208 с.

28. Селин B.C. Проблемы организации транспортного обслуживания населения города в рыночных условиях хозяйствования: монография. Краснодар: КубГТУ, 2002. 232 с.

29. Спирин И.В. Резервирование в управлении хозяйственными системами (на примере транспорта). М.: ИКЦ «Академкнига», 2003. 199 с.

30. Фишельсон М.В. Транспортная планировка городов: учеб. пособие: М.: Высшая школа, 1985. 239 с.

31. Линник, Г.Д. Разработка эффективного процесса оперативного управления маршрутного автобуса : автореф. дис. канд. техн. наук. Волгоград: ВГТУ, 2000. 16 с.

32. Аррак, А. Социально-экономическая эффективность пассажирских перевозок. Таллин: Ээсти раамат, 1984. 216 с.

33. Оптимизация городских автобусных перевозок. / М.Е. Антошвили и др.. М.: Транспорт, 1985. 102 с.

34. Организация городских автобусных перевозок с применением математических методов и ЭВМ. / М.Е. Антошвили и др.. М.: Транспорт, 1974. 104 с.

35. Варелопуло, Г.А. Организация движения и перевозок. М.: Транспорт, 1990. 208 с.

36. Рева В.М., Лигум Ю.С, Вайншток М.А., Сотников В.Е. Управление пассажирским автотранспортом: справочное пособие. Киев: Техника, 1985. 167 с.

37. Шутый В. АРМ работника производственной службы АТП // Автомобильный транспорт. 1988. № 9. С. 48-49.

38. Лихтик М.С., Прудовский Б.Д. Изучение грузопотоков при планировании и39.40,41.