«Программный модуль формирования маршрутов транспортных средств на базе эволюционного алгоритма»

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

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

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

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

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

• Обзор и анализ задач маршрутизации и методов их решения;

• Разработка основных процедур эволюционного алгоритма для решения задач маршрутизации;

• Проектирование модуля для формирования маршрутов

транспортных средств;

• Реализация программного модуля;

• Проведение вычислительных экспериментов и анализ результатов.

• Traveling Salesman Problem (Задача коммивояжера) — задача коммивояжера относится к разряду известных задач комбинаторной оптимизации, главной целью которой является поиск наилучшего маршрута путем прохождения всех указанных пунктов минимум один раз и обязательным возвратом в начальный пункт. Если грузоподъёмность С транспортного средства не ограничена (является достаточной), то задачу VRP сводят к множественной задаче коммивояжера — Multiple Traveling Salesman Problem. Задача решается путем добавления к исходному графу k-1 (k-количество маршрутов) копий нулевой вершины и её рёбер (между этими копиями рёбра отсутствуют) [2].

• Bin Pacing Problem (Задача о рюкзаке) — задача о рюкзаке является NP-полной задачей комбинаторной оптимизации. Своё название получила от главной цели — упаковать как можно больше вещей в рюкзак с учётом ограничения вместимости. Решение задачи равнозначно решению задачи VRP, однако расстояния принимаются равными нулю. Таким образом, эффективность решений будет равнозначна [3].

Наиболее исследованными вариантами задач маршрутизации с дополнительными ограничениями и вариациями являются:

• Задача маршрутизации с ограниченной грузоподъёмностью — условием задачи является ограниченность грузоподъёмности транспортных средств;

• Задачи маршрутизации с ограничением по времени — условием задачи является обслуживание заказчиков в определенное время («временное окно»);

• Задача маршрутизации с нескольким депо — задача основана на наличии нескольких «депо» для обслуживания заказчиков;

• Задача маршрутизации с возвратом товара — данная задача основана на преимуществе возвратов некоторых товаров в депо;

• Задача маршрутизации с возвратом товаров — задача построена подобно предшествующей, однако возврат товаров осуществляется только после того как все товары из депо будут доставлены заказчикам;

• Задача маршрутизации с разным транспортом — в данной задаче обслуживание заказчиков может осуществляться одновременно несколькими машинами;

• Периодическая маршрутизация — условием является доставка товара в течение нескольких дней;

• Задача маршрутизации со случайными данными — в данной задаче компоненты могут иметь случайное поведение;

• Задача маршрутизации с возможностью дозагрузки — в задаче есть вероятность дозагрузки транспортного средства на маршруте.