ВВЕДЕНИЕ
ГЛАВА 1 ОБЗОР СУЩЕСТВУЮЩИХ СПОСОБОВ РЕШЕНИЯ ЗАДАЧ
МАРШРУТИЗАЦИИ ТРАНСПОРТА
1.1Описание задачи маршрутизации транспорта
1.2Алгоритмы для решения ЗМТ
1.2.1Точные алгоритмы
1.2.2Эвристические алгоритмы
1.2.3Метаэвристические алгоритмы
1.3Ограничения в задачах маршрутизации
транспорта
1.4Математическая модель задачи маршрутизации
транспорта
ГЛАВА 2 РЕАЛИЗАЦИЯ ЭВРИСТИЧЕСКОГО АЛГОРИТМА ДЛЯ РЕШЕНИЯ
ЗМТ
2.1Обоснование выбора технических
средств
2.2Исходные
данные
2.3Реализация
алгоритма
2.4Проведение вычислительного эксперимента
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЕ А. Диаграмма
классов
Каждый год спрос на транспортно-логистические услуги повышается по всему миру. В следствии этого, проблема решения задач маршрутизации транспорта становится все более актуальной и востребованной. Главная цель в рассматриваемых задачах заключается в построение маршрутов для транспортных средств, которые обслуживают заданное количество клиентов.
Количество видов задач маршрутизации транспорта является очень большим, как и алгоритмов, решающих их. Это точные, эвристические и метаэвристические алгоритмы. Т.к. задача маршрутизации транспорта является NP-трудной [26], очевидно, что точные подходы целесообразно использовать только при малоразмерных задачах. Поэтому, для решения задач маршрутизации транспорта предпочтительней и чаще всего используются эвристические алгоритмы. Они создают решения приближенные к оптимальному, но за меньшее время (по сравнению с точными методами). Еще одна особенность эвристических алгоритмов проявляется в многообразие решений, которые получаются в ходе работы алгоритма по одному и тому же примеру.
Таким образом, актуальность темы бакалаврской работы обусловлена тем, что даже при наличии большого количества уже реализованных эвристических алгоритмов, необходимо и дальше реализовывать и улучшать данные алгоритмы для поиска наилучшего результата, т.к. применение автоматизированных систем в области транспортной логистики - один из способов сэкономить ресурсы.
Данная бакалаврская работа отличается высокой практической значимостью. В ходе его создания была разработана программа, решающая задачу маршрутизации транспорта в условиях ограничений по грузоподъемности, позволяющая сделать процесс выбора оптимального пути наиболее результативным.
Объект исследования бакалаврской работы - вычислительный процесс нахождения оптимального пути эвристическим алгоритмом в условиях ограничений по грузоподъемности.
Предмет исследования бакалаврской работы - программа, определяющая оптимальный путь с помощью эвристического алгоритма для решения задачи маршрутизации транспорта.
Цель бакалаврской работы - применить эвристический алгоритм для решения задачи маршрутизации транспорта в условиях ограничений по грузоподъемности.
Для достижения цели работы необходимо решить следующие задачи:
1)программная реализация алгоритма оптимизации с помощью
эвристического алгоритма;
2)вычислительный эксперимент;
3)анализ данных вычислительного эксперимента.
Первая глава описывает задачу маршрутизации транспорта, алгоритмы, которые решают данную задачу.
Вторая глава посвящена разработке алгоритма и программе, использующая данный алгоритм с дополнительными условиями, подводятся результаты работы разработанного алгоритма.
В данной работе был рассмотрен ряд видов задачи маршрутизации транспорта, подробно описаны распространенные алгоритмы решения ЗМТ, такие как точные, эвристические и метаэвристические алгоритмы. Среди них был эвристический алгоритм перемещения, который был реализован на языке программирования Java. В качестве теста производильности использовался тест Christofides, Mingozzi and Toth. В конце работы проведен вычислительный эксперимент, в результате которого был сделан вывод, что разработанный алгоритм стремится к лучшим результатам данного теста.
В рамках бакалаврской работы все цели и задачи выполнены.
Итогом проделанной работы является:
1)изучена литература, посвященная задаче маршрутизации транспорта;
2)рассмотрены известные методы решения задачи маршрутизации транспорта;
3)проведен анализ по эвристическим алгоритмам;
4)реализован эвристический алгоритм перемещения для решения задачи маршрутизации транспорта;
5)разработана программа, способная решать задачу маршрутизации транспорта с использованием эвристического алгоритма в условиях ограничений по грузоподъемности.
