ВЫПУСКНАЯ РАБОТА МАГИСТРА

Тема : Методы и алгоритмы поиска оптимального пути перемещения агентов по территориально-распределенным торговым точкам

Содержание

Цели и задачи

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

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

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

  • расстояние между торговыми точками;
  • время, затраченное на поездку;
  • тип местности;
  • расход топлива;
  • направление движения по дорогам (однонаправленное, двунаправленное).

Основными задачами являются:

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

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

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

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

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

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

Планируемые практические результаты

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

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

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

  • контроля перемещения агентов;
  • временной оптимизации - больше посещенных торговых точек за то же рабочее время.

Обзор исследований и разработок по теме:

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

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

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

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

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

Математические методы решения задачи

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

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

После получения маршрута необходимо нанести его на карту местности, с указанием посещаемых торговых точек как пунктов остановки агента. Для решения поставленной задачи необходимо получить географические координаты путей между торговыми точками, то есть координаты магистралей, улиц, домов, которые агент обязан посетить. После получения таких данных можно подключать алгоритмы поиска оптимальных маршрутов по имеющимся координатам. Математически город можно представить как граф, то есть упорядоченная пара G: = (V,E), для которой выполнены следующие условия:

  • V это множество вершин или узлов,
  • E это множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами[1,2,4].

В действительности вершины V представляют собой перекрестки, пересечения дорог, ребра E - объединяющие их участки дорог. Эта схема применима не только в масштабе города, но и по сути сети дорог страны. Таким образом, для решения задачи следует использовать алгоритмы на графах, позволяющие найти оптимальный путь через набор вершин.

На рисунке приведен схематичный вид неориентированного графа с шестью вершинами, в качестве которых выступают перекрестки и семью ребрами, в качестве которых выступают дороги, соединяющие перекрестки (рисунок 1).


Рисунок 1. Неориентированный граф с шестью вершинами и девятью рёбрами.

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

Схема функционирования системы (иначе говоря, архитектура) представлена на рисунке 2.

Иллюстрация работы подсистемы
Рисунок 2. Процесс функционирования подсистемы, иллюстрирующий получение и обработку информации. Анимация состоит из 4 кадров с задержкой в 50мс между кадрами; задержка для повторного воспроизведения составляет 250мс; количество циклов воспроизведения не ограничено; объем 87кБ.

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

  • алгоритм поиска A*;
  • алгоритм Дейкстры;
  • поиска кратчайших путей алгоритм Флойда;
  • генетический алгоритм;
  • муравьиный алгоритм.
  • нейронные сети модели Хопфилда.

Заключение

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

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

  • Лорьер Ж.-Л. Системы искусственного интеллекта / Пер. с фр. и ред. В. Л. Стефанюка. — М.: Мир, 1991. — С. 238—244. — 20 000 экз. экз. — ISBN 5-03-001408-X
  • Рассел С. Дж., Норвиг, П. Искусственный интеллект: современный подход = Artificial Intelligence: A Modern Approach / Пер. с англ. и ред. К. А. Птицына. — 2-е изд.. — М.: Вильямс, 2006. — С. 157—162. — 3000 экз. экз. — ISBN 5-8459-0887-6
  • Нильсон Н. Искусственный интеллект: методы поиска решений = Problem-solving Methods in Artificial Intelligence / Пер. с англ. В. Л. Стефанюка; под ред. С. В. Фомина. — М.: Мир, 1973. — С. 70 — 80.
  • Dechter, R., Pearl, J. Generalized best-first search strategies and the optimality of A* // Journal of the ACM. — 1985. — Т. 32. — № 3. — С. 505 — 536.
  • Hart P. E., Nilsson, N. J., Raphael, B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths // IEEE Transactions on Systems Science and Cybernetics SSC4. — 1968. — № 2. — С. 100 — 107.
  • Hart P. E., Nilsson, N. J., Raphael, B. Correction to «A Formal Basis for the Heuristic Determination of Minimum Cost Paths» // SIGART Newsletter. — 1972. — Т. 37. — С. 28 — 29.
  • Pearl J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. — Addison-Wesley, 1984. — ISBN 0-201-05594-5
  • Ананий В. Левитин Глава 3. Метод грубой силы: Задача коммивояжера // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Algorithms. — М.: «Вильямс», 2006. — С. 159-160. — ISBN 0-201-74395-7
  • Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1
  • В.И. Мудров Задача о коммивояжере. — М.: «Знание», 1969. — С. 62.

При написании данного автореферата магистерская работа еще не завершена. Дата окончательного завершения работы: 1 декабря 2010 г. Полный текст работы и материалы по теме могут быть получены у автора или его научного руководителя после указанной даты.