Обзор решений классической модели VRP. Особенности прокладывания маршрутов доставки заказов. Анализ полученных результатов применения реализованных алгоритмов решения задач. Использование API сторонних сервисов. Модель спроектированной базы данных.
Продвижение науки в прошлых веках позволило математически сформулировать определение проблемы и таким образом создать способ структурировать алгоритмы, подходящие для ее решения. Обобщая TSP, VRP - одна из самых известных комбинаторных проблем оптимизации, и хотя она не имеет оптимального решения, будучи NP-трудной, многие дифференцирующиеся в подходах, числе параметров и затраченных для подсчета ресурсах, алгоритмы могут быть применены, чтобы получить результаты с необходимой точностью и эффективностью. Детальное изучение моделей VRP-задач, начиная с введения термина [8], привело к увеличению разнообразия среди VRP-моделей и сужению рамок исследования и разработке алгоритмов решения для отдельных моделей. Цель исследования состоит в том, чтобы внедрить различные алгоритмы для решения VRP, переведя алгоритмы из теоретической модели в географическую карту города и оценить эффективность их работы с различными наборами реальных данных и трудностями, возникающими в сфере повседневных услуг доставки, чтобы создать приложение, применяющее реализованные алгоритмы для создания легких для чтения и применения маршрутных листов и карт доставки товаров. 2) Изучить алгоритмы и существующие подходы решения VRP-задач, выбрать несколько алгоритмов из различных классов для реализации;Общим недостатком такого теоретического типа решений в рамках поставленной в этой работе задачи разработки маршрутов доставки товаров является отсутствие возможности применить реализованные эвристики на реальных данных любой сложности, поскольку классические реализации эвристик не предполагают использование дополнительных параметров или ограничений сверх уже имеющихся в оригинальной постановке задачи VRP. Для достижения данной цели создаются наборы инструментов и библиотеки для решения сложных и насыщенных моделей VRP-задач, которые после используются для составления карт маршрутов. Дорожная библиотека маршрутизации, использующаяся как механизм для создания интерфейса GRAPHHOPPER Maps, сервиса составления маршрутов на карте. Сервис маршрутизации, позволяющий считывать данные из xls-таблиц и учитывающий многие параметры транспортных средств в насыщенных VRP-задачах для построения маршрутов на карте рис. Для достижения данной цели создаются наборы инструментов и библиотеки для решения сложных и насыщенных моделей VRP-задач, которые после используются для составления карт маршрутов.Введем функцию, подсчитывающую расстояние, пройденное автомобилем , у которой наступила очередь развозить заказ под номером r в маршрутном листе (заказ ). Наименьшее время доставки всех заказов: Введем функцию K, подсчитывающую максимальное время, потраченное каждым из курьеров для развоза всех заказов из своего маршрутного листа: В таком случае, требуется найти такой набор маршрутных листов , что , 2. Для инициализации первичного решения используется эвристический алгоритм First Fit (поиск первого подходящего) [32], заключающийся в постепенном распределении всех имеющихся заказов по маршрутным листам так, чтобы минимизировать выбранный для основного алгоритма поиска решения критерий оптимизации (наименьшее число курьеров - максимальное заполнение маршрутных листов заказами; наименьшее время доставки заказов - максимально равномерное заполнение маршрутных листов; наименьшее расстояние - минимальные расстояния между заказами в одном маршрутном листе). Поскольку Hill Climbing Algorithm всегда выбирает оптимальный шаг для текущего решения, данный алгоритм легко может завершить свою работу решением в локальном максимуме (рис. Описанные далее локальные алгоритмы оптимизации (Late Acceptance Hill Climbing Algorithm, Step Counting Hill Climbing Algorithm, Tabu Search, Simulated Annealing) являются улучшением Hill Climbing Algorithm, каждый по-своему решая проблему локальных экстремумов.В конце главы приведены особенности построения маршрутов доставки заказов в городе Москве. Также важную роль сыграли реализации API внешних систем, с которыми приложению требовалось работать, а именно Яндекс.Карты и геокодер Яндекс, имеющие реализацию как раз для вышеописанных языков. HTTP-запросы использовались для работы с методами известного API, а xml-формат использовался для работы с Excel-документами. Карт и Google Maps выяснилось, что второй сервис имеет более строгие ограничения на число запросов к функциям своего API, а также не позволяет, в отличие от Яндекс.Карт, использовать статические карты, что значительно увеличивает размер передаваемых сервисом данных, увеличивая время ответа и общее время ожидания пользователем результатов работы приложения. Итоговым выбранным стали статические карты Яндекс Карт, по ранее названным причинам представляющие собой сочетание оптимальной скорости отображения результата и приемлемые ограничения на число запросов в день (достаточное для поставленной задачи, где на день распределяется и доставляется по городу Москве не более 50 заказов) [39].Проблема разработки маршрутов доставки товаров - одна из самых сложных и востребованных логистических задач комб
Введение
Логистическое планирование доставки товаров было проблемой для человечества со времен начала потребности в транспортировке грузов в древнем мире. Современная глобализация и постоянно увеличивающееся число способов доставлять товары только усложнили принятие решения в этой области предпринимательства, создавая потребность в централизованном поиске и внедрении решения вопросов эффективности доставки для современных компаний.
Продвижение науки в прошлых веках позволило математически сформулировать определение проблемы и таким образом создать способ структурировать алгоритмы, подходящие для ее решения. VRP-задача используется для нахождения оптимального набора маршрутов для достижения всех клиентов имеющимся парком транспортных средств. Обобщая TSP, VRP - одна из самых известных комбинаторных проблем оптимизации, и хотя она не имеет оптимального решения, будучи NP-трудной, многие дифференцирующиеся в подходах, числе параметров и затраченных для подсчета ресурсах, алгоритмы могут быть применены, чтобы получить результаты с необходимой точностью и эффективностью. Детальное изучение моделей VRP-задач, начиная с введения термина [8], привело к увеличению разнообразия среди VRP-моделей и сужению рамок исследования и разработке алгоритмов решения для отдельных моделей. Общая тенденция исследования VRP сосредотачивается на более практических проблемах доставки, нежели описанных в стандартных моделях базовых параметрах [15].
Важность низких расходов на транспортировку и их последующее влияние на стоимость доставки товаров многократно увеличивают продуктивность и сбережения компании при интеграции решения VRP, тем самым искореняя все сомнения в актуальности исследования VRP, несмотря на длительность существования этой проблемы.
В рамках данной квалификационной работы была поставлена цель решить конкретную практическую проблему распределения и составления маршрутов доставки. Цель исследования состоит в том, чтобы внедрить различные алгоритмы для решения VRP, переведя алгоритмы из теоретической модели в географическую карту города и оценить эффективность их работы с различными наборами реальных данных и трудностями, возникающими в сфере повседневных услуг доставки, чтобы создать приложение, применяющее реализованные алгоритмы для создания легких для чтения и применения маршрутных листов и карт доставки товаров.
Для достижения этой цели были поставлены и решены следующие задачи: 1) Выбрать VRP-модель, описывающую поставленную задачу доставки заказов;
2) Изучить алгоритмы и существующие подходы решения VRP-задач, выбрать несколько алгоритмов из различных классов для реализации;
3) Выбрать критерии оптимизации для реализуемых алгоритмов;
4) Реализовать выбранные алгоритмы для применения их на выбранной модели;
5) Разработать программу, решающую VRP-задачу для выбранной модели при помощи реализованных алгоритмов;
6) Провести тестирование алгоритмов, сравнить и обосновать полученные результаты;
7) Разработать пользовательский интерфейс управления программой;
8) Разработать техническую документацию.
Работа организована следующим образом: в первой главе производится обзор и сравнение основных групп аналогов, решающих VRP-задачи. Во второй главе описываются классическая и выбранная VRP-модели, приводится математическая постановка решаемой задачи, а также описываются и сравниваются используемые и существующие алгоритмы решения. В третьей главе описаны особенности программной реализации разработанного приложения.
Глава 1. Решения VRP-задач
В данной главе проводится обзор и сравнение ключевых групп приложений, а также их наиболее заметных представителей, занимающихся решением VRP-задач.
Все приложения и инструменты, которые можно найти в сети Интернет, делятся на два основных типа: предназначенные для теоретического решения классической VRP-задачи и для практического решения насыщенных VRP-моделей.
1.1 Обзор решений классической модели VRP
Проекты первого типа стремятся объединить большое число известных эвристик для решения классической проблемы VRP. Эта цель достигается либо посредством создания крупных интернет-библиотек, содержащих набор эвристик и метаэвристик, либо посредством создания приложений с возможностью визуализации полученных решений на простых графических моделях VRP.
Примерами проектов первого типа являются: Библиотека, реализованная на языке C , позволяющая использовать эвристики и метаэвристики для решения классической и двух самостоятельно разработанных авторам моделей VRP, а также подключать сторонние библиотеки для создания двумерных графиков. Не предоставляет возможность проверить оптимальность выбранной эвристики [18].
Библиотека, реализованная на языке Java, позволяющая моделировать классическую задачу VRP, а также применять к ней две реализованные эвристики [24].
Библиотека, реализованная на языке Lisp, позволяющая моделировать классическую задачу VRP, а также применять к ней одну реализованную эвристику. Находится в состоянии разработки.
Библиотека, реализованная на языке Java, решающая классическую модель VRP-задачи посредством одной реализованной эвристики и позволяющая учитывать дополнительные параметры для развозимых товаров.
Библиотека, реализованная на языке С, моделирующая решение [27] классической задачи VRP.
Библиотека, позволяющая решать классическую задачу VRP посредством применения трех различных эвристик.
Примерами второго типа проектов можно назвать: Библиотека, реализованная на языках Java/Scala, предназначенная для решения сложных оптимизационных проблем, в том числе и проблему маршрутизации.
Библиотека, реализованная на языке Visual Basic и предназначенная для интеграции с Microsoft Excel, позволяющая решать задачу маршрутизации [31] для этой платформы.
Приложение, реализованное на языке Java, оптимизирующее управление бизнес-ресурсами, позволяющее в том числе решать и классическую VRP-задачу.
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
