Исследование методов и информационных моделей для оптимизации маршрутов при решении логистических задач

 

Из таблицы  7 видно, что необходимым функционалом обладает метод ветвей и границ и метод Литтла. Именно их я выбрал для дальнейшей реализации.

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

Предлагаемая  целевая функция должна содержать  следующие параметры:

 

1  Запасы на складе;

2  Стоимость перевозки;

3  Объем перевозки;

4  Оптимальная длина маршрута;

 

2.1 Постановка задачи оптимизации маршрутов при решении логистических задач

 

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

1 Маршрут должен быть замкнутым, то есть водитель должен вернуться в тот пункт, из которого он начал движение;

2  Каждый склад водитель должен посетить точно один раз, то есть надо обязательно обойти все склады, при этом не побывав ни на одном складе дважды [32].

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

Существует  метод решения этой задачи, который  дает оптимальное решение. Это метод  ветвей и границ или алгоритм Литтла. Тип задачи – задача коммивояжера.

Если  считать склады клиентов вершинами  графа, а коммуникации (i,j) – его дугами, то требование нахождения минимального пути, проходящего один и только один раз через каждый склад, и возвращения обратно, можно рассматривать как нахождение на графе гамильтонова контура минимальной длины [33].

 

2.2 Математическая  модель задачи оптимизации маршрутов  при решении логистических задач

 

Опишем  математическую модель для оптимизации  маршрутов при решении логистических задач. Введем систему обозначений:

1 N - число городов.

2  , i, j=1..N - матрица затрат, где Ci j  - затраты на переход из i-го города     в j-й. 

3  - матрица переходов с компонентами.

4  = 1, если коммивояжер совершает переход из i-го города в j-й

    = 0, если не совершает перехода,

где i, j = 1..N.

 

Задача  коммивояжера может быть сформулирована как целочисленная введением  булевых переменных , если маршрут включает переезд из склада  i непосредственно на склад j и в противном случае [34-35]. Тогда можно задать математическую модель задачи, то есть записать целевую функцию(1) и систему ограничений(2)-(4):

(1)

Условия (2) – (4) в совокупности обеспечивают, что каждая переменная равна или нулю, или единице [35]. При этом ограничения (2), (3) выражают условия, что водитель побывает на каждом складе один раз в него прибыв (ограничение (2)), и один раз из него выехав (ограничение (3)).

Однако  этих ограничений не достаточно для  постановки задачи коммивояжера, так  как они не исключают решения, где вместо простого цикла, проходящего  через n вершин, отыскиваются 2 и более отдельных цикла (подцикла), проходящего через меньшее число вершин. Поэтому задача, описанная уравнениями (2) – (4) должна быть дополнена ограничениями, обеспечивающими связность искомого цикла [36-37].

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

, где  , и (5)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. РАЗРАБОТКА ПРОЕКТА ПРОГРАММНО-МЕТОДИЧЕСКОГО КОМПЛЕКСА ДЛЯ ОПТИМИЗАЦИИ МАРШРУТОВ ПРИ РЕШЕНИИ ЛОГИСТИЧЕСКИХ ЗАДАЧ

 

3.1 Анализ бизнес-процесса «Оптимизация маршрутов при решении логистических задач»

 

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

 

 Таблица  8 – Выходы и потребители бизнес-процесса

 

Таблица 9 – Входы и поставщики бизнес-процесса

 

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

 

Таблица 10 – Условия начала и окончания бизнес-процесса системы совершенствования презентационных систем

Приведем  функциональную декомпозицию на основе SADT технологии.

Для построения SADT диаграммы необходимо выделить перечень активностей ПО.

Основной  активностью ПП будет «Оптимизация маршрутов при решении логистических задач».

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

 На рисунке 1 представлена ​​контекстная SADT-диаграмма нулевого уровня

 

      

 

 

 

 

 

 

 

 

 

     Рисунок  5 - ​​Контекстная SADT-диаграмма нулевого уровня

Описание SADT – диаграммы нулевого уровня в таблице 11.

Таблица 11 – Описание SADT – диаграммы нулевого уровня

 

Описание SADT-диаграммы первого уровня представлены в таблице 12 .

 

Таблица 12 – Описание SADT-диаграммы первого уровня