Работа с графом в ГИС ПИОМ реализована следующем образом.

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

Для работы с ребрами графа (на нашем примере - это участки улиц от перекрестка до перекрестка) создан класс TStreet. В классе инкапсулированы основные функции для работы с улицами: добавление, удаление, изменение и другие. Собственно, данные об улицах хранятся в переменной этого класса - массиве SourceData. К этим данным помимо прочего относятся и ссылки на начальный и конечный перекрестки. Таким образом, можно легко перейти от улицы к ее начальному или конечному перекрестку, а вот для перехода от перекрестка к дорогам, которые с него начинаются необходимо полностью просмотреть массив SourceData.

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

Алгоритмы поиска на графе можно описать следующим образом:

* стартовая вершина выбирается как активная;

* запускается цикл перебора всех вершин;

* определяется следующая активная вершина и запускается дальнейшая итерация цикла;

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

Разница в алгоритмах и методах поиска состоит лишь в правиле выбора следующей активной вершины. В ГИС ПИОМ реализованы следующие алгоритмы поиска на графах:

1) поиск в глубину (для определения существования маршрута между двумя пунктами);

2) поиск в ширину (для определения маршрута, содержащего минимальное количество ребер графа);

3) алгоритм Дейкстры (для поиска кратчайшего пути);

4) алгоритм обхода препятствий (для быстрого поиска кратчайшего пути);

5) генетический алгоритм (для поиска оптимального многопунктового маршрута - решения задачи коммивояжера).

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

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

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

Алгоритм Дейкстры (п. 2.1) основан на методе поиска в ширину. Его особенность заключается в том, что в нем рассматриваются в качестве критерия выбора следующей активной вершины веса ребер. Иными словами, можно сказать, что активной будет выбрана та вершина, расстояние в метрах до которой от стартовой будет минимальным. Расстояние в данном случае рассчитывается как сумма весов ребер, входящих в путь от одной вершины к другой. Таким образом, данный алгоритм подходит для решения поставленной задачи поиска оптимального пути.

Алгоритм обхода препятствий (п. 2.1) является модификаций алгоритма Дейкстры. Его отличие в том, что в качестве критерия выбора следующей активной вершины в нем рассматривается не просто расстояние от стартовой вершины как сумма весов ребер, а добавляется к этой сумме еще и оценка оставшегося пути. В созданной программной реализации этого алгоритма в качестве таковой оценки берется расстояние от рассматриваемой точки до финишной по прямой. Такое улучшение позволяет в общем случае сократить количество перебираемых точек, благодаря направленности выбора следующей активной точки. Этот метод очень хорошо подходит для реализации поставленной задачи.

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

Сначала находятся оптимальные пути движения между всеми парами вершин, входящих в многопунктовый маршрут. Данный поиск производится с помощью алгоритма обхода препятствий. Причем в связи с особенностью области применения поиск для каждой пары вершин осуществляется дважды: сначала из первой вершины во вторую, а затем наоборот. Далее на основании полученных оптимальных путей строится новый граф, вершинами которого являются точки многопунктового маршрута, а ребрами - найденные пути движения. И уже на основе этого графа находится оптимальный путь с помощью генетического алгоритма (п. 2.5.3). Данный метод позволяет найти приемлемое оптимальное решение, близкое к минимальному пути.

4.4 Описание работы с системой для пользователя

Рисунок 4.3 - Диалоговое окно "Начало работы"

Создание нового проекта. При нажатии кнопки "Создать новый проект" диалогового окна "Начало работы" или при выборе пункта меню "Файл"> "Создать новый проект" открывается диалоговое окно "Свойства проекта" (рис. 4.4).

Рисунок 4.4 - Диалоговое окно "Свойства проекта"

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

1) Карта-источник. Исходная карта со схемой улично-дорожной сети города. Карта обязательно должна быть сохранена в растровом формате BMP.

2) Масштаб карты - это размер в метрах расстояния, отображаемого одним пикселем исходного BMP-файла.

3) Путь для сохранения проекта. По умолчанию программа предлагает сохранить новый проект в создаваемом подкаталоге "New" того каталога, из которого она запущена.

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

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

и редактированию информации на карте.

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

Рисунок 4.5 - Отображение карты в программе

Для изменения масштаба отображения карты необходимо покрутить колесико мыши: вперед - приближение (увеличение масштаба), назад - отдаление. Также изменить масштаб можно при помощи подменю "Вид"> "Масштаб", причем можно не только приблизить или отдалить, но и установить одно из фиксированных значений: 50 %, 75 %, 100 %, 150 %, 200 % или 300 %. Восстановить 100 % масштаб можно и нажатием колеса (средней кнопки) мыши.

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

По умолчанию на карте отображаются только векторные данные, хранящиеся в БД проекта. При выборе меню "Вид" > "Параметры отображения" > "Показывать исходную карту", карта-источник будет отображаться как подложка для векторной карты (рис. 4.6, б).

а б

Рисунок 4.6 - Отдельное отображение только векторной карты (а) и совместное с картой-источником (б)

Перемещение по карте осуществляется простым перетаскиванием с удерживаемой нажатой левой кнопкой мыши.

Итак, рассмотрим редактирование карты. Для этого нужно сначала переключиться в соответствующий режим работы: меню "Режим работы" > "Редактирование" > "Улицы, перекрестки".

1) Создание дороги.

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

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

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

При создании дороги следует учесть то, что направление движения на создаваемом отрезке дороги совпадает с порядком его создания: от начального перекрестка к конечному.

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

2) Редактирование информации об отрезке дороги.

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

3) Удаление отрезка дороги.

Для удаления необходимо сначала выбрать отрезок дороги (навести на него курсор мыши), затем вызвать контекстное меню и выбрать пункт "Удалить улицу".

4) Изменение перекрестков.

Для выравнивания отрезков дорог можно легко перемещать существующие перекрестки по карте. Для этого наведите курсор мыши на окончание отрезка дороги (на перекресток), при этом он выделится красным маркером, а при щелчке на нем подсветка станет зеленой. Теперь можно, нажав на нем левую кнопку мыши, перемещать его перетаскиванием в новое положение.

5) Удаление перекрестков.

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

И при этом их характеристики совпадают (эта одна и та же улица), то перекресток удаляется, а отрезки дорог сливаются в один. Если же нет, то вместе с перекрестком удаляются все дороги, примыкающие к нему.

Поиск оптимального маршрута движения. Для поиска маршрута движения нужно сначала перейти в соответствующий режим: меню "Режим работы" > "Поиск маршрута" > "Маршрут старт-финиш".

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

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

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

Рисунок 4.7 - Оптимальный маршрут

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

Поиск оптимального многопунктового маршрута. Для поиска многопунктового маршрута движения нужно сначала перейти в соответствующий режим: меню "Режим работы" > "Поиск маршрута" > "Многопунктовый маршрут". Далее необходимо установить его точки (минимум 4). Точки устанавливаются двойным щелчком в нужном месте карты. При этом они также связываются с ближайшим перекрестком. Для удаления точки нужно дважды щелкнуть на ней. После нажатия кнопки "Найти маршрут" определяется оптимальный путь и отображается на карте жирными черными линиями.

Дополнительно тонкими черными линиями отображаются альтернативные пути движения (рис. 4.8).

Рисунок 4.8 - Оптимальный многопунктовый маршрут

Работа с результатами поиска. Самым простым из направлений дальнейшего развития ГИС ПИОМ является увеличение количества данных, полученных в результате поиска оптимального маршрута: расчет дополнительных параметров, формирование отчетов и их экспорт в различные форматы для дальнейшей обработки.

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

Дополнительные критерии оптимизации. При добавлении дополнительных атрибутов дорог и формировании на их основе критериев поиска можно получить множество различных и интересных перспектив развития и применения ГИС ПИОМ. Можно рассмотреть несколько вариантов дополнительных атрибутов.

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

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

3) Время движения. Этот критерий аналогичен критерию длины пути. Однако длина отрезка дороги и среднее время проезда по нему не всегда пропорциональны. Есть участи дорог с ограниченной скоростью движения, есть участки, где движение затруднено плотным потоком и постоянно возникающими пробками. А бывает и наоборот - строят специальные "разгрузочные" дороги, скорость движения по которым выше среднегородской скорости [17].

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

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

Или, если представить, что узлы - это города, а ребра графа - это линии авиаперелетов между ними, то получается, что этот граф будет представлять собой схему авиаперелетов в пределах страны, или между странами. Оптимизация маршрутов требуется и в этой деятельности. Не секрет, что прямые авиаперелеты возможны не во всех направлениях, зачастую приходится лететь с пересадкой, а то и двумя. В этих случаях можно найти множество вариантов перелета и выбрать из них оптимальный будет достаточно трудоемко. Ведь в критерий оптимальности могут входить достаточного много параметров: стоимость перелета, время полета, время ожидания следующего рейса, компания-авиаперевозчик, тип самолета, качество обслуживания (наличие в самолете мест повышенной комфортности), качество пересадочного пункта и другие. Разработанная ГИС ПИОМ (при незначительной модификации и добавлении требуемых исходных данных) может легко учесть все эти параметры, их проанализировать и выдать оптимальный по заданному критерию результат.

Можно найти еще множество вариантов практического применения разработанной ГИС ПИОМ при небольшой модификации в каждом конкретном случае.

Глава 5. Социальная значимость работы

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

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

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

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

Заключение

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

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

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

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

Размещено на Allbest.ru