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

Размещено на http://www.allbest.ru/

Введение

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

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

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

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

Любая компания, выйдя на определённые обороты, задумывается об автоматизации своей работы. У такого решения есть явные плюсы:

- внедрение нетривиальных алгоритмов оптимизации затрат;

- уменьшение рутинной нагрузки на сотрудников и ускорение их работы;

- создание, выравнивание и контроль планов работы.

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

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

Для достижения поставленной цели необходимо решить следующие задачи:

- провести анализ предметной области;

- определиться с функциональными требованиями к системе;

- выбрать способ реализации системы;

- подобрать необходимые инструменты для разработки;

- решить задачи, встающие при реализации той или иной функции;

- разработать интерфейс приложения;

- определить основополагающие элементы развертывания системы;

- провести технико-экономическое обоснование дипломного проекта;

- рассмотреть аспекты ее безопасности и экологичности.

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

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

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

Создаваемый программный комплекс функционирует на базе коммуникаторов с операционной системой Android. Выбор данной платформы не случаен и обоснован в проекте.

Для разработки системы использовался язык Java. Были использованы комплект разработки программного обеспечения Java Development Kit, интегрированная среда разработки Eclipse, Android SDK, включающий в себя эмулятор работы реальных устройств и плагин Android Development Tools - расширение для интегрированной среды разработки, ускоряющее и упрощающее создание и отладку приложений. Основные характеристики выбранного инструментария и его преимущества так же раскрыты в дипломном проекте.

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

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

1. Анализ предметной области

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

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

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

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

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

Определим проблемы, которые целесообразно решить по внедрении автоматизированной системы, определим их влияние на производственные процессы, а так же укажем преимущества внедрения АИС (Таблица 1, 2, 3).

Таблица 1 - Проблема планирования маршрута перевозок

Объект	Значение и характеристика
Проблема	Сложность планирования маршрута перевозок
Актер	Курьер
Следствие проблемы	Снижение скорости доставки товара, задержка выполнения заказа, потеря прибыли
Успешное решение	Автоматизация процесса поиска оптимального маршрута доставки

Таблица 2 - Проблема отсутствия визуального контроля перевозок

Объект	Значение и характеристика
Проблема	Отсутствие инструмента для визуального контроля перевозок
Актер	Диспетчер, Курьер
Следствие проблемы	Практическая невозможность отследить, где точно находится Курьер. Сложность координации.
Успешное решение	Создание АРМ диспетчера с возможностью удобного отслеживания местоположения Курьеров фирмы и мониторинга их деятельности и занятости.

Таблица 3 - Проблема затянутости отчетности курьеров

Объект	Значение и характеристика
Проблема	Затянута отчетность Курьеров перед Диспетчером
Актер	Диспетчер, Курьер
Следствие проблемы	Нерегулярный срыв планирования работ по доставке товара, увеличение времени доставки.
Успешное решение	Введение возможности быстрой установки статуса доставки, легкий доступ к централизованной телефонной книге компании

Видно, что внедрение АИС значительно увеличит качество и скорость предоставляемых услуг, создаст новые условия для развития фирмы и увеличит ее конкурентоспособность.

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

Внедряемая АИС предоставляет целый спектр возможностей:

1 упрощение работы пользователей благодаря удобному и эргономичному интерфейсу ввода данных и получения необходимой информации;

2 удобство планирования маршрута становится доступным вследствие разработанной навигационной системы;

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

4 назначение исполнителя и контроля работ прямо с рабочего места диспетчера;

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

Время, необходимое для обучения обычных пользователей - 3 рабочих дня (24 часа), для обучения продвинутых пользователей - 1 рабочий день (8 часов). Система должна быть способна поддерживать минимум 15 одновременно работающих пользователей, связанных с общей базой данных

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

2. Определение способа реализации

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

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

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

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

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

2.1 Выбор аппаратной платформы

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

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

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

В-третьих, важна поддержка стандарта GSM для оперативной организации мобильной сотовой связи и наличие GPRS-модуля для обеспечения пакетной передачи данных по протоколу TCP/IP.

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

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

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

О выборе операционной системы речь пойдет далее.

2.2 Выбор операционной системы

Операционная система Symbian, безоговорочно лидирующая на рынке до 2010 года в настоящее время почти полностью утратила свои позиции. Сперва Sony Ericsson объявил о прекращении использования Symbian, чтобы сосредоточиться на выпуске устройств под управлением Android. Следом за ним Samsung прекращает поддержку Symbian и переходит на использование Android, Windows Phone 7 и Bada, ОС собственной разработки.

Весной 2011 года сама Nokia объявила о том, что Windows Phone 7 станет ключевой платформой для смартфонов, однако компания не планирует отказываться от платформы Symbian и станет поддерживать мобильную платформу Symbian «по меньшей мере» до 2016 года.

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

Apple iOS (до 2010 года известная как iPhone OS) мобильная операционная система, разработанная американской компанией Apple на основе Mac OS X первоначально для iPhone, а затем расширена для поддержки таких мобильных устройств, как Apple iPod, iPad и Apple TV и в настоящее время динамично развивается.

Разработка приложений для iOS ведется в среде XCode, который поддерживает языки C, C++, Objective-C, Objective-C++, Java, AppleScript, Python и Ruby с различными моделями программирования.

Apple не лицензирует iOS для установки на стороннее оборудование, а цена коммуникатора iPhone в России достаточно велика. Этот факт безусловно сильно затруднит внедрение автоматизированной системы, разработанной для iOS с финансовой точки зрения. Поэтому данная ОС так же не была выбрана.

Набирающая некоторую популярность операционная система Windows Phone 7 обладает рядом недостатков, среди которых необходимо выделить отсутствие встроенной поддержки баз данных. SQL Server Compact не включен в состав WP7. Также не включены SQLite или любые другие сторонние СУБД. Отсутствует так же поддержка межпроцессного взаимодействия (IPC) и нет поддержки сокетов.

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

Операционная система Android - портативная (сетевая) операционная система для коммуникаторов, планшетных компьютеров, цифровых проигрывателей, наручных часов. Изначально разрабатывалась компанией Android Inc., которую затем купила Google. Впоследствии Google инициировала создание альянса Open Handset Alliance (OHA), который сейчас и занимается поддержкой и дальнейшим развитием платформы. 

Доли рынка, которые занимали операционные системы в определенные кварталы, можно узнать из рисунка 1 и таблицы 4.

Рисунок 1 - Доли рынка операционных систем для смартфонов

Таблица 4 - Доли рынка операционных систем для смартфонов

Квартал	Android	iOS	Symbian	Microsoft	Bada	RIM	Other
2007 Q4	0%	5,20%	62,30%	11,90%	0%	12,90%	20,60%
2008 Q1	0%	4,60%	49,50%	10,40%	0%	13,10%	35,50%
2008 Q2	0%	2,80%	57,50%	12,10%	0%	15,40%	27,60%
2008 Q3	0,60%	13,10%	50,30%	11,20%	0%	18,20%	24,80%
2008 Q4	1,10%	10,60%	46,50%	12,20%	0%	19,70%	29,60%
2009 Q1	1,60%	10,50%	48,80%	10,20%	0%	19,70%	28,90%
2009 Q2	1,80%	13,00%	51,00%	9,30%	0%	20,50%	24,90%
Окончание таблицы 4
2009 Q3	3,40%	17,00%	44,20%	7,90%	0%	19,00%	27,50%
2009 Q4	7,60%	16,20%	44,70%	7,90%	0%	20,60%	23,60%
2010 Q1	9,60%	15,30%	44,20%	6,80%	0%	19,30%	24,10%
2010 Q2	17,20%	14,20%	41,20%	5,00%	0,90%	16,10%	21,50%
2010 Q3	25,30%	16,60%	36,30%	2,80%	1,10%	17,50%	17,90%
2010 Q4	31,10%	16,10%	32,90%	3,40%	1,30%	11,60%	15,20%
2011 Q1	36,00%	16,80%	27,40%	3,60%	1,70%	10,90%	14,50%
2011 Q2	43,40%	18,20%	22,10%	1,60%	1,90%	9,70%	12,80%
2011 Q3	52,50%	15,00%	16,90%	1,50%	2,20%	8,90%	11,90%
2011 Q4	56,90%	18,90%	11,70%	1,90%	2,10%	8,70%	8,50%

Операционная система Android обладает целым рядом преимуществ [13]:

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

Во-вторых, система полностью универсальна. Android OS можно устанавливать и на смартфоны, и на карманные компьютеры, и даже на телефоны (в облегчённом виде).

Это одна из наиболее удобных и практичных мобильных операционных систем, используемых в современном мире и ее настройка очень проста.

Популярность операционной системы Android стала следствием того, что ведущие компании мобильных телефонов, например, HTC, Motorola, Samsung Electronics, и многие другие производители стали использовать Android на своих смартфонах.

Преимуществом Android от Google также является так же и то, что новая версия Android запускается почти каждые 3 месяца. Обновление телефона новыми версиями помогает пользователям наслаждаться более качественными услугами.

2.2.1 Особенности архитектуры ОС Android

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

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

Архитектуру Android принято делить на четыре уровня [1]:

- уровень ядра;

- уровень библиотеки среды выполнения;

- уровень каркаса приложений;

- уровень приложений.

На рисунке 2 показаны основные компоненты операционной системы и их взаимодействие между собой.

Рисунок 2 - Архитектура операционной системы Android

Ядро Android основано на ядре Linux версии 2.6, но сама система Android не является Linuх-системой в чистом виде, имеет некоторые отличия и содержит дополнительные расширения ядра, специфичные для Android, - свои механизмы распределения памяти, взаимодействие между процессам и и др.

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

Основные компоненты уровня ядра:

- драйвер межпроцессного взаимодействия (IPC Driver);

- драйвер управления питанием (Android Power Management);

- набор драйверов для оборудования, входящего в состав мобильного устройства.

«Выше» ядра, как программное обеспечение промежуточного слоя, лежит набор библиотек (Libraries), предназначенный для обеспечения важнейшего базового функционала для приложений. То есть именно этот уровень отвечает за предоставление реализованных алгоритмов для вышележащих уровней, поддержку файловых форматов, осуществление кодирования и декодирования информации (в пример можно привести мультимедийные кодеки), отрисовку графики и многое другое. Библиотеки реализованы на C/C++ и скомпилированы под конкретное аппаратное обеспечение устройства, вместе с которым они и поставляются производителем в предустановленном виде.

Перечислим некоторые из них:

- Surface Manager - в ОС Android используется композитный менеджер окон, наподобие Compiz (Linux), но более упрощенный. Вместо того чтобы производить отрисовку графики напрямую в буфер дисплея, система посылает поступающие команды отрисовки в закадровый буфер, где они накапливаются вместе с другими, составляя некую композицию, а потом выводятся пользователю на экран. Это позволяет системе создавать интересные бесшовные эффекты, прозрачность окон и плавные переходы.

- Media Framework - библиотеки, реализованные на базе PacketVideo OpenCORE. С их помощью система может осуществлять запись и воспроизведение аудио и видео контента, а также вывод статических изображений. Поддерживаются многие популярные форматы, включая MPEG4, H.264, MP3, AAC, AMR, JPG и PNG.

- SQLite - легковесная и производительная реляционная СУБД, используемая в Android в качестве основного движка для работы с базами данных, используемыми приложениями для хранения информации.

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

- LibWebCore - библиотеки известного шустрого браузерного движка WebKit, используемого также в десктопных браузерах Google Chrome и Apple Safari.

- SSL - библиотеки для поддержки одноименного криптографического протокола. Libc - стандартная библиотека языка C, а именно её BSD реализация, настроенная для работы на устройствах на базе Linux. Носит название Bionic.

На этом же уровне располагается Android Runtime - среда выполнения. Ключевыми её составляющими являются набор библиотек ядра и виртуальная машина Dalvik. Библиотеки обеспечивают большую часть низкоуровневой функциональности, доступной библиотекам ядра языка Java.

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

Уровнем выше располагается Application Framework, иногда называемый уровнем каркаса приложений. Именно через каркасы приложений разработчики получают доступ к API, предоставляемым компонентами системы, лежащими ниже уровнем. Кроме того, благодаря архитектуре фреймворка, любому приложению предоставляются уже реализованные возможности других приложений, к которым разрешено получать доступ. В базовый набор сервисов и систем, лежащих в основе каждого приложения и являющихся частями фреймворка, входят [2]:

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

- Контент-провайдеры (Content Providers), управляющие данными, которые одни приложения открывают для других, чтобы те могли их использовать для своей работы.

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

- Менеджер Оповещений (Notification Manager), благодаря которому все приложения могут отображать собственные уведомления для пользователя в строке состояния.

- Менеджер Действий (Activity Manager), который управляет жизненными циклами приложений, сохраняет данные об истории работы с действиями, а также предоставляет систему навигации по ним.

- Менеджер Местоположения (Location Manager), позволяющие приложениям периодически получать обновленные данные о текущем географическом положении устройства.

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

На вершине программного стека Android лежит уровень приложений (Applications). Сюда относится набор базовых приложений, который предустановлен на ОС Android. Например, в него входят браузер, почтовый клиент, программа для отправки SMS, карты, календарь, менеджер контактов и многие другие. Список интегрированных приложений может меняться в зависимости от модели устройства и версии Android. И помимо этого базового набора к уровню приложений относятся в принципе все приложения под платформу Android, в том числе и разрабатываемая система.

2.3 Выбор средств разработки и тестирования

Выбор устройств-коммуникаторов в качестве аппаратной основы для реализации проекта и Android OS в качестве операционной системы в значительной степени обусловил и то, какой инструментарий будет использоваться для разработки и тестирования приложений.

2.3.1 Язык Java

Система разрабатывалась на объектно-ориентированном языке Java, разработанном компанией Sun Microsystems, которая в данный момент приобретена корпорацией Oracle. Выбор данного языка был сделан по ряду соображений.

Программы на языке Java транслируются в байт-код, выполняемый виртуальной машиной (Java Virtual Mashine) - программой, обрабатывающей байтовый код и передающей инструкции оборудованию как интерпретатор.

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

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

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

Система Java создавалась объектно-ориентированной с самого начала. Объектно-ориентированная парадигма во многом наиболее удобна при создании программного обеспечения.

Нужно отметить, что существует возможность разрабатывать программы и на C/C++ (с помощью Native Development Kit), и на Basic (с помощью Simple) и с использованием других языков. Также можно создавать собственные программы с помощью конструкторов приложений, таких как App Inventor.

2.3.2 Java Development Kit 

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

Java Development Kit (JDK) - бесплатно распространяемый корпорацией Oracle Corporation комплект разработчика приложений на языке Java, включающий в себя стандартные библиотеки классов Java, примеры, документацию, различные утилиты и исполнительную систему Java (JRE).

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

Все современные интегрированные среды разработки приложений на Java, такие, как NetBeans IDE, Sun Java Studio Creator, IntelliJ IDEA, Borland JBuilder, Eclipse, опираются на сервисы, предоставляемые JDK. Большинство из них для компиляции Java-программ используют компилятор из комплекта JDK. Поэтому эти среды разработки либо включают в комплект поставки одну из версий JDK, либо требуют для своей работы предварительной инсталляции JDK на машине разработчика.

2.3.3 Интегрированная среда разработки Eclipse

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

Eclipse - наиболее полно документированная, свободная и доступная интегрированная среда разработки для Java. Eclipse также очень проста в изучении. Это делает Eclipse очень привлекательной IDE для разработки приложений под Android;

Компания Google выпустила плагин для Eclipse - Android Development Tools, который позволяет создавать Android-пpoeкты, компилировать их, и, что очень важно, использовать эмулятор мобильного ycтpoйcтвa для запуска и отладки приложений.

Плагин Android Development Tools для Eclipse автоматически создает необходимую структуру Android пpoeктa и устанавливает требуемые параметры настройки компилятора.

2.3.4 Android SDK

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

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

Dalvik Debug Monitor Service (DDMS) - интегрированный с Dalvik, стандартной виртуальной машиной платформы Android, этот инструмент позволяет управлять процессами на эмуляторе или устройстве, а также помогает в отладке приложений.

3. Функциональные требования к системе

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

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

- определить общие границы и контекст моделируемой предметной области;

- сформулировать общие требования к функциональному поведению проектируемой системы;

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

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

Суть диаграммы вариантов использования состоит в следующем. Проектируемая система представляется в виде множества сущностей или актеров, взаимодействующих с системой с помощью вариантов использования. При этом актером (actor) или действующим лицом называется любая сущность, взаимодействующая с системой извне. Это может быть человек, техническое устройство, программа или любая другая система, которая может служить источником воздействия на моделируемую систему так, как определит сам разработчик [11]. Вариант использования служит для описания сервисов, которые система предоставляет актеру. Диаграмма вариантов использования может дополняться пояснительным текстом, который раскрывает смысл или семантику составляющих ее компонентов.

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

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

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

Проектируемая система состоит из двух частей.

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

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

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

Итак, система представляет собой совокупность мобильных устройств, оснащенных АРМ Курьеров, объединенных в единое целое через АРМ Диспетчера (рисунок 3, таблица 5).

Рисунок 3 - Общая структура АИС

Таблица 5 - Реестр основных компонентов системы

Код	Наименование	Формулировка
К	АРМ Курьера	Автоматизированное рабочее место курьера функционирует на базе коммуникатора с ОС Android и позволяет производить расчет оптимального маршрута, оценивать необходимое время прохождения маршрута. Обеспечивается обмен информацией с АРМ Диспетчера
M	АРМ Диспетчера	Автоматизированное рабочее место диспетчера функционирует на ПК, позволяет вести мониторинг состояния перевозок по карте. Обеспечивается обмен информацией с АРМ Клиента.

Теперь более детально определим функциональные требования к клиентской части системы (рисунок 4, таблица 6).



Рисунок 4 - Диаграмма прецедентов для клиентской части системы, размещаемой на коммуникаторах с ОС Android (АРМ Курьера)

Таблица 6 - Реестр вариантов использования для АРМ Курьера

Код	Наименование	Формулировка
KA1	Определение местоположения	Определение координат (широты и долготы) текущего местоположения и отображение их на карте.
KA2	Расчет оптимального маршрута	Расчет, построение и отображение оптимального маршрута движения от текущего местоположения до пункта назначения.
KA3	Оценка необходимого времени	Оценка времени, необходимого для прохождения оптимального маршрута.
KS1	Установка статуса состояния перевозок	Установка статуса состояния: «Свободен», «Выполняю заказ», «Аварийная ситуация», «Перерыв в работе»
Окончание таблицы 6
KD1	Редактирование реестра объектов	Меню доступа и инструментам добавления, редактирования и удаления городских объектов.
KD2	Добавление объекта	Добавление в базу данных нового объекта с указанием его наименования, категории, адреса, широты и долготы, примечаний.
KD3	Редактирование данных об объекте	Редактирование данных о географическом объекте
KD4	Удаление объекта	Удаление объекта из базы данных

Проведем декомпозицию объекта АРМ Диспетчера по выполняемым функциям (рисунок 5, таблица 7).



Рисунок 5 - Диаграмма прецедентов для стационарной, серверной части системы (АРМ Диспетчера)

Таблица 7 - Реестр вариантов использования для АРМ Курьера

Код	Наименование	Формулировка
MA1	Мониторинг состояния перевозок	Диспетчер в любой момент по интерактивной карте может отследить, где в данный момент находится тот или иной курьер, свободен он или занят
Окончание таблицы 7
MP1	Управление курьерами	Отсюда диспетчер получает возможность просматривать список курьеров, зарегистрированных в системе, а так же редактировать, изменять, удалять и просматривать информацию о них.
MP2	Добавление курьера	Добавление в базу данных нового курьера, ввод необходимой информации и характеристик
MP3	Редактирование данных о курьере	Корректировка данных о курьере
MP4	Удаление курьера	Удаление курьера из базы данных
MP5	Просмотр сведений о курьере	Просмотр основных сведений о курьере, хранящихся в базе данных

4. Разработка проекта

4.1 Обзор и решение ключевых задач

4.1.1 Определения текущего местоположения

Задача получения приложением данных о текущем местоположении пользователя является отправной точкой в вопросе построения оптимального маршрута. Видится два решения этого вопроса: использование спутниковой системы навигации GPS и сетевого провайдера местоположения Android (ANLP - Android's Network Location Provider).

Несмотря на то, GPS является более точным, он работает только на улице, быстро расходуется заряд батареи, и не возвращает местоположение так же быстро, как хотят пользователи. ANLP определяет местоположение пользователя с помощью мобильных вышек и Wi-Fi сигналов. Этот способ вполне работоспособен как на открытом воздухе, так и в помещении, реагирует быстрее использует меньше энергии аккумулятора, но дает меньшую точность позиционирования. По этим причинам целесообразно использовать эти два метода в совокупности [7].

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

Вот несколько источников ошибок:

1 множественность источников определения местоположения - GPS, Cell-ID и Wi-Fi. И каждый дает свой ключ к определению местоположения пользователя. Определение того, какие данные использовать и каким доверять - это дело компромиссов в точности, скорости и экономии заряда батареи;

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

3 изменение точности - необходимо постоянно производить оценку погрешности определения нового местоположения.

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

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

Алгоритм выбора провайдера местоположения представлен на рисунке 6.

Рисунок 6 - Выбор провайдера местоположения

4.1.2 Прокладка оптимального маршрута

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

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

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

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

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

Узлы могут последовательно соединять две дуги, имеющие разные характеристики, или соединять несколько дуг в местах перекрестков, развилок и т.п. Если дороги физически проходят над одним участком местности на разных уровнях (тоннель, эстакада и т.п.), то в точке пересечения дорог на карте графа узел должен отсутствовать. С помощью набора односторонних и двусторонних дуг и узлов можно однозначно описать различные виды перекрестков, одноуровневых и многоуровневых развязок. Если на перекрестке дорог необходимо показать запрет поворота, то в этом месте дороги могут быть показаны параллельными односторонними дугами, которые имеют узлы только с теми пересекающими их дугами, на которые разрешено перестроение транспорта.

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

Операционная система Android разработана компанией Google. Поэтому логично выделить первого кандидата - картографический сервис Google Maps. Действительно, в настоящее время он очень бурно развивается. Кроме того, существуют готовые и очень удобные инструменты для создания приложений под Android с использованием Google Maps. Однако детальное изучение системы показало, что подробно сеть дорог проложена только в пределах США и стран Евросоюза. В России же в векторном формате представлены карты лишь наиболее крупных городов. Свободное редактирование так же не представляется возможным.

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

После выделения недостатков двух представленных выше картографических сервисов, выбор пал в сторону использования OpenStreetMap (дословно «открытая карта улиц»), сокращённо OSM - некоммерческий веб-картографический проект по созданию силами сообщества участников-пользователей Интернета подробной свободной и бесплатной географической карты мира.

В настоящее время проект динамично развивается и охватывает все крупные населенные пункты. Существуют удобные инструменты для добавления и редактирования картографических данных. Среди редакторов стоит в первую очередь выделить Potlatch 2, доступ к которому свободно открыт с сайта OpenStreetMap.

4.1.3 Особенности построения графа дорог в OpenStreetMap

OpenStreetMap использует топологическую структуру данных, состоящую из объектов:

- node (точка) - точка с указанными координатами;

- way (линия (путь)) - упорядоченный список точек, составляющих линию или полигон;

- relation (отношение) - группы точек, линий и других отношений, которым назначаются некоторые свойства;

- tag (тег) - пары «ключ - значение», могут назначаться точкам, линиям и отношениям.

Пример графа дорог OpenStreetMap, редактируемый в системе Potlatch2 можно видеть на рисунке 7. Можно видеть, что разные типы дорог привязываются к реальным географическим координатам. Подробнее об этом будет сказано в следующей главе.



Рисунок 7 - визуализация графа дорог в OpenStreetMap

Все возможные виды карт состоят из базовых элементов, которыми являются «точка» (node) и «путь» (way). С каждым из базовых элементов связано множество его свойств (т.н. «меток») [14].

Точка - базовый элемент в структуре данных OSM. Точка имеет параметры «широта» и «долгота». Точки используются для того, чтобы определить «линию», однако точка может являться и самостоятельным элементом карты, и использоваться для обозначения отдельного ни с чем не связанного объекта (например, телефонной будки, бара, для указания координат, к которым привязано название населённого пункта или любого интересного места. Отдельные точки (т.е. не входящие в состав линий или областей) всегда должны иметь хотя бы одно свойство.

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

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

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

Линия характеризуется свойствами, которые распространяются на линию на всём её протяжении. Например, для линии, обозначающей дорогу, такими свойствами могут являться тип и качество покрытия, допустимая скорость движения и т.п. Если при уточнении выясняется, что не все свойства линии сохраняются на всём её протяжении (например, на дороге, которой соответствует линия, имеется участок с другим типом покрытия), то линия может быть разделена на части [3].

Для того, чтобы считаться корректно определённой, линия должна иметь хотя бы одно свойство.

В OpenStreetMap нет ограничений на свойства (теги), которыми могут быть помечены элементы (Точки и Пути). Однако, выгоднее использовать некий рекомендованный набор объектов и соответствующих им тегов.

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

Таблица 8 - Типы дорог в OpenStreetMap

Значение	Описание
primary	Автомобильные дороги регионального значения
secondary	Автомобильные дороги областного значения
tertiary	Более важные автомобильные дороги среди дорог местного значения
living_street	Улицы, на которых пешеходы имеют преимущество перед автомобилями
pedestrian	Для обозначения улиц городов, выделенных для пешеходов.
track	Дороги сельскохозяйственного назначения.
path	Тропа без назначения. Беговая лыжня, велосипедный маршрут, пешеходный маршрут.
Окончание таблицы 8
footway	Пешеходные дорожки. Если по ним разрешено передвижение на велосипеде, то необходимо добавить тег bicycle=yes.
cycleway	Велодорожка. Если это дорожка и для пешеходов, можно добавить тег foot=yes.

Для описания характеристик дорог следующие теги:

- Maxspeed:practical - практически достижимая на участке дороги скорость.

- Surface - используется для более подробного описания покрытия. дороги. Этот тег позволяет учитывать, например, тот факт, что езда по грунтовым дорогам более медленная (занимает большее время).

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

Принимает такие значения, как excellent, good, intermediate, bad, horrible, impassable.

- Bicycle - тег, устанавливающий, возможность проезда велотранспорта.

- Foot - могут ли перемещаться пешеходы.

Все покрытия можно разделить на две основные группы: paved и unpaved road. В США, термин unpaved road называют разбитую дорогу. В России используется термины не грунтовая/грунтовая дорога (таблица 9).

Навигационное программное обеспечение должно учитывать, что езда по грунтовым дорогам более медленная (занимает большее время) и может быть вообще невозможна в ненастье.

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

Таблица 9 - Типы качества дорог в OpenStreetMap.

Значение	Описание	Качество покрытия
asphalt	Асфальтное покрытие	paved
cobblestone	Булыжник -- специально уложенные относительно ровными поверхностями вверх камни.	paved
concrete	Бетон. Бетонное покрытие может заливаться на месте или выкладываться железо-бетонными плитами.	paved
grass	Трава, укатанная транспортными средствами, утоптанная людьми	unpaved
gravel	Гравий -- мелкие камни с неровной поверхностью	unpaved
ground	Голая почва, специальное покрытие отсутствует.	unpaved

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

4.1.4 Поиск оптимального маршрута

Существует целый ряд алгоритмов поиска оптимального маршрута. Алгоритм поиска A* является наиболее интересным при решении задачи с большим количеством путей и вершин [22].

A* пошагово просматривает все пути, ведущие от начальной вершины в конечную, пока не найдёт минимальный. Как и все информированные алгоритмы поиска, он просматривает сначала те маршруты, которые «кажутся» ведущими к цели. От жадного алгоритма (который тоже является алгоритмом поиска по первому лучшему совпадению) его отличает то, что при выборе вершины он учитывает, помимо прочего, весь пройденный до неё путь (составляющая g(x) -- это стоимость пути от начальной вершины, а не от предыдущей, как в жадном алгоритме). В начале работы просматриваются узлы, смежные с начальным; выбирается тот из них, который имеет минимальное значение f(x), после чего этот узел раскрывается. На каждом этапе алгоритм оперирует с множеством путей из начальной точки до всех ещё не раскрытых (листовых) вершин графа («множеством частных решений»), которое размещается в очереди с приоритетом. Приоритет пути определяется по значению функции