Телефон: +7 (383)-202-16-86

Статья опубликована в рамках: XXXVII Международной научно-практической конференции «Научное сообщество студентов XXI столетия. ТЕХНИЧЕСКИЕ НАУКИ» (Россия, г. Новосибирск, 24 декабря 2015 г.)

Наука: Информационные технологии

Скачать книгу(-и): Сборник статей конференции

Библиографическое описание:
Муравьев В.В., Кулагин И.Н., Столбовой Д.А. РАЗРАБОТКА ПРОГРАММЫ ДЛЯ ПРОКЛАДКИ ОПТИМАЛЬНОГО МАРШРУТА ПО КОМПЛЕКСНОМУ КРИТЕРИЮ ЭФФЕКТИВНОСТИ // Научное сообщество студентов XXI столетия. ТЕХНИЧЕСКИЕ НАУКИ: сб. ст. по мат. XXXVII междунар. студ. науч.-практ. конф. № 10(36). URL: http://sibac.info/archive/technic/10(36).pdf (дата обращения: 10.07.2020)
Проголосовать за статью
Конференция завершена
Эта статья набрала 0 голосов
Дипломы участников
У данной статьи нет
дипломов


РАЗРАБОТКА  ПРОГРАММЫ  ДЛЯ  ПРОКЛАДКИ  ОПТИМАЛЬНОГО  МАРШРУТА  ПО  КОМПЛЕКСНОМУ  КРИТЕРИЮ  ЭФФЕКТИВНОСТИ


Муравьев  Владислав  Витальевич


студент  2  курса,  кафедра  «Автоматика  и  управление  в  технических  системах»,  СамГТУ, 
РФ,  г.  Самара


Кулагин  Иван  Николаевич


студент  2  курса,  кафедра  «Автоматика  и  управление  в  технических  системах»,  СамГТУ, 
РФ,  г.  Самара


Столбовой  Дмитрий  Александрович


студент  2  курса,  кафедра  «Автоматика  и  управление  в  технических  системах»,  СамГТУ, 
РФ,  г.  Самара


Е-mail:  tot.kto.1997@mail.ru


Тычинина  Юлия  Александровна


научный  руководитель,  канд.  техн.  наук,  доцент  СамГТУ, 
РФ,  г.  Самара


 


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


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


Дорожную  сеть  можно  представить  в  виде  ориентированного  взвешенного  графа  G(V,E),  где  V  –  это  множество  вершин  в  количестве  mE  –  множество  ребер  в  количестве  n,  каждому  ребру  поставлено  в  соответствии  некоторое  число    (вес).  Вершинам  графа  соответствуют  перекрестки  на  улицах  города,  то  есть  места  дорожной  сети,  где  имеются  возможности  выбора  дальнейшего  маршрута  поездки.  Ребрам  графа  соответствуют  участки  дорог  между  двумя  вершинами.


Из  теории  графов  известно,  что  кратчайшим  путем  из  вершины  a  в  вершину  b  будет  называться  путь  P=(V1,  V2,  …,  Vk),  длиной  kгде  V1=aVk=b,  который  имеет  минимальное  значение  суммы    [2].  В  данной  работе  предлагается  ввести  для  каждого  ребра  несколько  весов,  каждый  из  которых  характеризует  один  из  факторов  важных  для  пользователя.  Например,  можно  в  качестве  веса    рассматривать  длину  j-го  ребра,    –  качество  дорожного  покрытия  соответствующего  участка,  выраженного  в  относительных  единицах  по  десятибалльной  шкале  (0  –  непроходимая  дорога,  10  –  идеальное  дорожное  покрытие),    –  загруженность  j-го  участка  дороги  по  десятибалльной  шкале  (0  –  пустая  дорога,  10  –  движение  парализовано).  Пользователь  может  задать  не  только  начальный  и  конечный  пункт  назначения,  но  и  свои  приоритеты  при  оптимизации  движения  в  виде  весовых  коэффициентов  ,  таким  образом,  чтобы  +,  например  набор  введенных  коэффициентов:    означает,  что  пользователя  в  первую  очередь  (на  60%)  интересует  минимизировать  пройденное  расстояние,  во  вторую  очередь  (на  30  %)  избежать  пробок,  а  в  последнюю  очередь  качество  дорожного  покрытия.


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


 


  (1)


 


В  результате  данной  работы  с  помощью  Microsoft  Visual  Studio  была  написана  программа  нахождения  оптимального  по  смешанному  критерию  эффективности  маршрута  между  двумя  пунктами.  Программа  предусматривает  ввод  количества  вершин  графа,  а  также  три  матрицы  весов  ребер,  отображающих  физическую  длину  ребер,  качество  дороги  на  данном  участке  и  его  загруженность.  Ребра  графа  могут  быть  как  ориентированными  (дороги  с  односторонним  движением),  так  и  неориентированными.  Далее  вводятся  коэффициенты  приоритета  пользователя  .  После  ввода  исходных  данных  программа  визуализирует  граф,  рассчитывает  результирующую  матрицу  смежности  с  учетом  трех  исходных  матриц  весов  и  коэффициентов  приоритета.  На  следующем  этапе  пользователь  указывает  начальную  и  конечную  вершину  маршрута,  на  основе  этих  данных  программа  находит  оптимальных  путь  с  использованием  алгоритма  Дейкстры  [2],  выводит  его  стоимость  и  выделяет  маршрут  на  графическом  представлении  графа.  На  рисунке  1  представлено  главное  окно  программного  интерфейса,  которое  служит  для  ввода  исходных  данных.  В  данном  примере  коэффициенты  приоритета  расставлены  таким  образом,  что  при  выборе  траектории  учитывается  только  длина  пройденного  пути,  а  остальные  факторы  не  рассматриваются  ().  Кратчайший  путь  отображается  во  вспомогательном  окне  визуализации  графа  (рисунок  2).  На  рисунках  3–4  показан  пример  работы  программы  при  коэффициентах  приоритета  пользователя  ()  и  других  пунктах  отправки  и  назначения.


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


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


 



Рисунок  1.  Окно  программы  для  ввода  исходных  данных


 



Рисунок  2.  Графическое  представление  результата  поиска  маршрута  1-2


 



Рисунок  3.  Окно  программы  для  ввода  исходных  данных


 



Рисунок  4.  Графическое  представление  результата  поиска  маршрута  0-6


 


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


 


Список  литературы:

  1. Автоматическая  трассировка  маршрутов  на  электронной  карте  [Электронный  ресурс]  –  Режим  доступа  –  URL:  http://www.pocketgis.biz  (дата  обращения  19.12.2015). 
  2. Алексеев  В.Е.,  Таланов  В.А.  Графы.  Модели  вычислений.  Структуры  данных:  учеб.  пособие.  Нижний  Новгород:  Издательство  Нижегородского  университета,  2005.  –  307  с.
  3. Mapquest  route  planner  [Электронный  ресурс]  –  Режим  доступа.  –  URL:  http://www..com/routeplanner:Find  the  shortest  path  from  A  to  B  to  Z  (дата  обращения  19.12.2015).
Проголосовать за статью
Конференция завершена
Эта статья набрала 0 голосов
Дипломы участников
У данной статьи нет
дипломов

Комментарии (8)

# Алексей 29.12.2015 00:00
Недурно! По мере прочтения возникали свои идеи по поводу реализации поставленной задачи, удивительно, но через пару-тройку строк встречал свои же идеи в этом тексте :)
# Владислав 30.12.2015 00:00
Алексей, спасибо за отзыв!
# Сараев Михаил 30.12.2015 00:00
Задача очень актуальна. На сколько можно судить, это первая версия и, надеюсь, данный проект будет расширяться и уточняться. Хотелось бы узнать, проходили ли обсуждения с преподавателями ВУЗа, которые очень хорошо знают теорию графов? Возможно, это позволит улучшить алгоритм, найти дополнительные критерии, проверки. Я бы посоветовал, в частности, Лукиных В.А., у него был очень хороший курс по данному предмету.<br />В описании есть опечатка: вес w2j - качество дорожного покрытия; w3j - загруженность. При этом коэффициенты C2 - загруженность, С3-качество покрытия. Надеюсь,что в алгоритме не так.<br />По поводу приведенного описания веса покрытия "0 – непроходимая дорога, 10 – идеальное дорожное покрытие" - получается что минимальное значение (то есть самое удачное) будет по непролазной дороге. Если перевести это в область других критериев- то еще непроходимая дорога должна быть максимально загружена. Скорее всего для непроходимых участков, закрытых участков нужно вводить некий максимальный вес, чтобы он никогда не попадал в минимальные показания.<br />Возник вопрос по поводу коэффициента: не согласен, что при отсутствии интереса к определенному критерию его коэффициент должен быть равен 0. Это опять же ведет к минимизации,а значит я могу задать так,что программа предложит мне путь через непроходимый участок. Скорее всего,необходимо учитывать участвующие критерии, остальные же исключать из расчета.<br />По представленным графическим материалам хотелось бы внести предложение - сделать итоговый вид окна с графами в формате "городских улиц", то есть как в описании - вершины графов - перекрестки, ребра-улицы. Сейчас визуально улиц нет, а задача решается для них. Так как авторы сами предлагают ввод доп. критериев, рассмотреть вариант формирования "типового набора" критериев и общего алгоритма. При работе пользователь должен будет сам решить, что из предложенного ему интересно, и формировать итоговую проверку для графа на основании выбранных критериев.
# Владислав 30.12.2015 00:00
Михаил, спасибо за столь развернутый комментарий. В описании алгоритма и вправду есть опечатка, но в самой реализации программы все правильно. Что касается интерфейса он будет дорабатываться. Остальные предложения мы обсудим с соавторами.
# Надежда 30.12.2015 00:00
Каким образом планируется в дальнейшем осуществить привязку графа к карте местности? Как это будет выглядеть со стороны пользователя?
# Владислав 30.12.2015 00:00
Надежда, карта местности будет загружается из внешнего файла, после чего пользователь сам будет отмечать вершины и ребра графа на карте.
# Елена 03.01.2016 00:00
Актуальная задача, но только в том случае, на мой взгляд, если решение доведено до реального практического результата.<br /><br />Поэтому интересным было бы рассмотрение вопросов <br />1) формирования и оценки корректности шкал приведенных для примера (и возможно дополнительных) критериев<br />2) оценки и актуализации веса ребер уже реального графа - той же дорожной карты (пробки и длина пути - понятно, а вот как быть с непредсказуемо изменяющейся в течение года, а иногда и в течение недели и дня, проходимостью?)<br />3) возможности практической реализации мобильного приложения для конечного пользователя.<br /><br />И еще вопрос: как быть, если все критерии для пользователя одинаково важны и важны прям на 100%???
# Владислав Муравьев 04.01.2016 00:00
Елена, спасибо за ваш отзыв. Если для пользователя важны все критерии, то он может сделать одинаковые коэффциенты приоритета т.е. 0,33.В таком случае будет найден оптимальный маршрут при учете всех критериев.Остальные предложения мы рассмотрим с соавторами.

Оставить комментарий

Форма обратной связи о взаимодействии с сайтом