Оптимізація логістичних маршрутів із використанням генетичного алгоритму

Автори

Відомості

Гітіс В.Б.

канд. техн. наук, доцент Донбаська державна машинобудівна академія

veniamin.gitis@gmail.com

Васильєв О.О.

здобувач другого (магістерського) рівня вищої освіти Донбаська державна машинобудівна академія

alexvasilev162k@gmail.com

Презентація

Анотація. У роботі розглядається оптимізація маршрутів транспортування з обмеженнями на місткість транспортних засобів з метою мінімізації загальної відстані при дотриманні обмежень. Математична модель враховує вузли, транспортні засоби, їх місткість і попит клієнтів. Для отримання оптимального рішення використано генетичний алгоритм. Алгоритм дозволяє знижувати логістичні витрати, забезпечуючи ефективне використання ресурсів і зменшення часу на доставку.

Логістика є невід’ємною частиною ефективного функціонування торгових компаній. У сучасних умовах ринку мінімізація витрат на транспортування продукції та оптимізація маршрутів доставки стають найважливішими факторами, що визначають конкурентоспроможність бізнесу.

Однією з ключових задач є проблема маршрутизації транспортних засобів, яка полягає у визначенні найкращого способу доставки товарів клієнтам з урахуванням багатьох обмежень. Ця задача належить до класу NP-складних проблем, що робить застосування точних алгоритмів неефективним за великих обсягів даних.

Метою роботи є створення математичної моделі для оптимізації маршрутів з урахуванням місткості транспортних засобів (Capacitated Vehicle Routing Problem, CVRP). Для вирішення задачі CVRP було обрано генетичний алгоритм, який надає системі гнучкості, необхідної для адаптації до реальних умов.

Математична модель оптимізації логістики заснована на варіації задачі маршрутизації транспортних засобів з урахуванням обмежень на місткість [1].

Вхідними даними моделі є:

Множина вузлів V = {0,1,2,…,n), де вузол 0 є депо, а вузли {1,2,…,n} – клієнти.
Множина ребер E = { (i,j) | i,j ∈ V, i ≠ j} представляє шляхи між вузлами.
Відстань dij між кожною парою вузлів i та j.
Кількість транспортних засобів K.
Місткість кожного транспортного засобу Q.
Попит qi для кожного клієнта i, де q0 = 0 (попит депо дорівнює 0).

Визначимо змінну xkij, яка дорівнює 1, якщо транспортний засіб k проїжджає шляхом з вузла i до вузла j, інакше 0.

Метою оптимізації є мінімізація загальної пройденої відстані всіма транспортними засобами:

$m i n \sum (k = 1)^{K} ▒ \sum (i \in V) ▒ \sum (j \in V) ▒ 〖 d_{i} j x_{i} j^{k} 〗$

Система обмежень буде мати вигляд:

$\sum (j \in V) x_{i} j k = 1, \forall i \in V_{0}, \forall k = 1, \dots, K$

$@∑(j∈V)▒x_ijk =∑(j∈V)▒x_jik ,&∀i∈V,∀k=1,…,K$

$(j∈V_0)▒x_0j^k =1,&∀k=1,…,K$

$∑(i∈V_0)▒x_i0^k =1,&∀k=1,…,K$

$∑(i∈V)▒q_(i∑(j∈V)▒x_ijk ) ≤Q,&∀k=1,…,K$

$x_ijk∈\{0,1\},&∀i,j∈V,∀k=1,…,K$

Для задачі CVRP фітнес-функція генетичного алгоритму може бути визначена як загальна довжина маршрутів із штрафом за перевищення місткості транспортних засобів [2]:

$f (C) = \sum_{(} v = 1)^{V} ▒ (\sum_{(} i = 0)^{(} | R_{v} | - 1) ▒ d (r_{i}, r_{(} i + 1)) + α m a x (0, \sum_{(} i = 1)^{(} | R_{v} | - 1) ▒ q_{(} r_{i}) - Q))$

де V – кількість транспортних засобів; Rv – маршрут транспортного засобу V; d(ri,ri+1) – відстань між вузлами ri та ri+1; qri – попит у вузлу ri; Q – місткість транспортного засобу; α – штрафний коефіцієнт за перевищення місткості.

Література

Laporte G. The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms. European Journal of Operational Research. 1992. № 59. С. 345-358. URL: http://dx.doi.org/10.1016/0377-2217(92)90192-C.
Prins C. A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research. 2004. Т. 31, №12. С. 1985-2002. URL: https://doi.org/10.1016/S0305-0548(03)00158-8.