VIII Международная студенческая научная конференция Студенческий научный форум - 2016

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

Цель работы: Разработка и исследование алгоритмов построения оптимального маршрута посещения городских объектов для курьерской компании. Для успешной реализации цели работы был проведен обзор алгоритмов построения оптимального маршрута [1,4], результаты обзора занесены в Таблицу 1 - «Сравнительный анализ алгоритмов поиска оптимального пути».

Наиболее известные системы навигации:

На сегодняшний день GPS (ГЛОНАСС) - приёмники очень часто применяются с целью для определения местонахождения и скорости. Глобальную систему определения координат представляет собой GPS . Основу системы GPS составляет сеть ИСЗ (Искусственный Спутник Земли) равномерно “покрывающих” всю земную поверхность и развёрнутых в около земной орбите. С очень высокой степенью точности рассчитаны орбиты ИСЗ, координаты каждого спутника, отчего они известны в любой момент времени. В направлении Земли, радиопередатчик каждого из спутников непрерывно излучает сигналы. Эти сигналы принимает GPS-приемник, находящейся в некоторой точке земной поверхности, координаты которой нужно определить. Точные текущие координаты местоположения определяет по радиосигналам спутников GPS-приемников. В GPS - приемнике измеряется время распространения сигнала от ИСЗ и вычисляется дальность “спутник-приемник”[3].

При вычислении расстояния пользуются тем свойством, что (со скоростью света распространяется радиосигнал). Так как для определения местоположения точки необходимо знать три плоские координаты X, Y и высоту H, то в приемнике вычисляется расстояния до трех различных ИСЗ. Очевидно, что при без запросном методе радионавигации, точное определение времени распространения сигнала возможно только при наличии синхронизации временных шкал спутника и приемника[3].

После GPS, на данный момент ГЛОНАСС является второй действующей спутниковой системой в мире. По планам руководства проекта, основу системы ГЛОНАСС составляют 24 спутника на орбите Земли. Система ГЛОНАСС может определять местонахождение объекта с точностью до 3,0 м, но после перехода в рабочее состояние двух спутников системы «Луч», по планам руководства, точность сигнала ГЛОНАСС должна будет вырасти до 1 метра [2].

Глобальная навигационная спутниковая система (ГЛОНАСС). Главное отличие ГЛОНАСС от системы GPS в том, что спутники ГЛОНАСС в своём орбитальном движении не имеют синхронности с вращением Земли, это и обеспечивает им высокую стабильность. Благодаря этому в течение всего срока активного существования группировка ГЛОНАСС не требует дополнительных корректировок. Однако, срок службы спутников ГЛОНАСС заметно короче.

Бэйдоу (BDS) – Китайская навигационная система Бэйдоу (BDS)." Ссылаясь на представителя организации, занимающейся разработкой системы Бэйдоу Рана Ченгки, информационное агентство "Синьхуа, сообщило, что Китайская навигационная система Бэйдоу (BDS) начала свою работу в некоторых странах Азиатско-Тихоокеанского регионах, Индии, Монголии и Китае. Эксперты отметили, что для гражданских нужд точность позиционирования BDS не превышает 10 метров, при этом точность измерения скорости составляет 0,2 метра в секунду. Ошибка, возникающая в передаче времени от спутника находится в пределах 50 наносекунд (миллиардных долей секунды)[2].

Таблица 1

«Сравнительный анализ алгоритмов поиска оптимального пути»

Название алгоритма	Порядок	Количество операций	Путь
Алгоритм Флойда-Уоршелла	Расстояние от вершины до вершины	n3	Минимальный путь между каждой парой вершин
Алгоритм Форда-Беллмана	Расстояние от нулевой вершины до всех остальных	n * m	Минимальный путь от нулевой до всех остальных
Алгоритм Дейкстры	Расстояние от нулевой вершины до всех остальных	n2	Минимальный путь от нулевой до всех остальных
Алгоритм обхода препятствий А*	Два графа, две позиции		Минимальный путь от одной вершины до другой

Обзор был дан по самым известным и описанным алгоритмам, каждый алгоритм находит свое применение, но ни один алгоритм не может претендовать на единственно верное решение.

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

Литература:

1. Самуйлов С. В. Методика сравнительного анализа алгоритмов на примере алгоритмов последовательного поиска // Концепт. – 2014. – № 09.

2. Ревнивых С.Г. тенденции развития глобальных навигационных спутниковых систем // Гироскопия и навигация. 2012. № 3 (78). С. 3-17.

3. Урличич Ю. Инновационный потенциал будущих проектов на основе глонасс-технологий // T-Comm: Телекоммуникации и транспорт. 2011. Т. 5. № 2. С. 10-12.

4. Панкратьев Е.В., Чеповский А.М., Черепанов Е.А., Чернышев С.В. Алгоритмы и методы решения задач составления расписаний и других экстремальных задач на графах больших размерностей // фундаментальная и прикладная математика. 2003. Т. 9. № 1. С. 235-251.

3

Код для цитирования: Скопировать