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