Завдання оптимізації перевезень вантажів з підхопленням і доставкою (VRPPD)

1. Перевезення вантажів з підхопленням і доставкою А навіщо ще одна програма оптимізації? Головні...
2. (Опис програми VrpPd)

Перевезення вантажів з підхопленням і доставкою

А навіщо ще одна програма оптимізації?

Головні переваги програми VrpPd

VrpPd може знаходити близькі до оптимального вирішення різних завдань планування маршрутів транспортних засобів - CVRP, VRP, VRPPD, PDPTW з тимчасовими вікнами або без, з різнорідним парком транспорту, з одним або декількома депо. Програма планує маршрути таким чином, що вона мінімізує число відвідувань клієнтів, якщо це можливо (або може не робити цього), планує маршрути з поверненням для повторного завантаження / розвантаження якщо це необхідно, може планувати маршрути в режимах обмежень на порядок завантаження - "останній завантажений - перший вивантажено "- (LIFO) або (FIFO), враховує транспортну роботу тр.средства при оптимізації - це додаткова економія.

Програма побудована на основі мого оптимізатора, за допомогою якого були встановлені рекорди в оптимізації - дивіться, наприклад The Pickup and Delivery Problem with Time Windows (PDPTW) / Li & Lim benchmark / 600 customers (Shobb) .

VrpPd дуже проста в установці і використанні - просто скопіювати два файли в будь-яку папку на комп'ютер під керуванням Ms Windows де встановлений Ms.Net фреймворк версії не нижче 4.5.2 - практично будь-який комп'ютер під управлінням OS Windows. Всі дані програма зберігає в файлі Ms Access - у вас немає потреби підтримувати великі і складні бази даних і її легко інтегрувати з іншими програмами. Програма так само має вбудовану підтримку імпорту даних з простих текстових файлів і може отримувати інформацію з Google Maps.

Дуже добре распараллелівать роботу - чим більше є процесорних ядер - тим швидше работает.Ето важливо якщо вирішуються великі завдання. >

(Опис програми VrpPd)

Завдання перевезення вантажів з підхопленням і доставкою (англійська абревіатура VRPPD - Vehicle routing problem with pickup and delivery) можна описати таким образом.Есть список пунктів між якими потрібно перевезти вантажі з врахуванням вантажопідйомності транспортного засобу і при цьому оптимізувати маршрут використовуючи ті чи інші критерії.

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

Може бути варіант з обмеженнями по розвантаженню транспортного засобу - наприклад розвантаження за принципом - вантаж, який завантажений останнім - вивантажується першим (так званий LIFO - last in first out принцип) або FIFO - перший завантажений, перший вигружен.Ето потрібно, наприклад, в тих випадках, коли завантаження здійснюється через задні двері транспортного средства.Еслі планувати маршрут за принципом LIFO - то не потрібно буде перевантажувати вантажі, які потрібно доставити пізніше - при цьому економиться час на розвантаження, хоча довжина маршруту може бути трохи більше.

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

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

Можливі обмеження транспортних засобів - за вантажопідйомністю, набору властивостей, обсягом, максимальному пробігу і максимальній кількості виконуваних замовлень - останні два обмеження потрібні, щоб збалансувати маршрути в разі декількох транспортних засобів - тобто одному транспортному засобу буде спланований дуже довгий маршрут з дуже великою кількістю операцій навантаження \ розвантаження, а всі інші транспортні засоби не використовуватимуться.

Це, так звана, NP - повна задача, тобто вона не вирішується простим перебором варіантів вже при досить невеликій кількості замовлень на перевезення вантажів. У моїй програмі використовується один з кращих методів пошуку рішення - так звана LNS (large neighborhood search) евристика разом з "імітацііей відпалу".

У програмі також передбачена інтеграція з - Google Maps - геокодування і отримання матриці відстаней і часу між пунктамі.Лібо матриця відстаней і часу може бути введена вручну.

Кілька скріншотів:

Відстані і час між пунктами задати таким же чином як в "Задачі комівояжера в місті" , Потім задається список різнорідних машин:

Для кожного транспортного засобу вантажопідйомність, максимальний обсяг, максимальний пробіг та обмеження на кількість замовлень по маршруту. Визначається так само пункт початку маршруту і встановлюється ознака, чи є маршрут кільцевим. Можливе обмеження на навантаження - без обмежень, LIFO або FIFO. Час початку - кінця роботи. Набір властивостей, якщо потрібно щоб конкретні замовлення виконувалися певними тр. засобами. (Властивості для замовлення, які потрібні для його виконання - можуть бути задані для кожного конкретного замовлення.)

Далі описується список замовлень на перевезення.

Запускається оптимізація, потрібно почекати протягом деякого часу, при натисканні на кнопку "Stop" програма припиняє роботу і виходить рішення. (Можна подивитися-отримати інші рішення подвійним кліком на відповідний рядок навіть в процесі оптимізації).

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

Приклади знайдених маршрутів (маршрути для кожного транспортного засобу) - в нормальному and LIFO режимах оптимізації.

Передбачені окремі тимчасові вікна для операцій навантаження, розвантаження, і для кожного транспортного засобу окремо.

Однією з унікальних особливостей VrpPd є те, що вона оптимізує не тільки відстань, але і обсяг транспортної роботи. Подивіться на картинку справа.Я спробую навести дуже простий приклад. У нас є депо D і два клієнта "A" і "B" .Ми повинні доставити їм 30 і 100 одиниць вантажу відповідно, одним транспортним засобом і повернутися в депо.Расстоянія показані на зображенні. Якщо ми сплануємо маршрут "D-> A-> B-> D" або "D-> B-> A-> D" відстань, пройдену транспортним засобом буде одним і тим же - 110. Але, якщо маршрут буде "D- > A-> B-> D ", ми будемо везти 100 одиниць вантажу для" B "на відстань 80, і 30 одиниць вантажу для" A "на відстань 50, а якщо ми сплануємо маршрут" D-> B-> A- > D "ми перевеземо 100 одиниць вантажу для" B "тільки на відстань 30, а для" A "- всього 60. Таким чином, немає різниці в відстані, але значно більше робота транспортного засобу - воно везе важкий вантаж на більшу відстань. Більшість програм це не враховують. VrpPd завжди це учітивает.Ето може дати значний економію палива.

Щоб протестувати програму, були вирішене A-n80-k10 і G-n262-k25 відомі приклади CVRP завдання. CVRP - окремий випадок VRPPD коли всі замовлення на перевезення вантажів - з депо до клієнтів. Для тестування часових вікон, я вирішив кілька відомих CVRPTW прикладів - наприклад, пожет подивитися тут , Знайдено кілька детальних рішень до VRPTW (Shobb) .

Тестову версію програми ви можете завантажити з англійської сторінки .

© 2018 Якщо у вас є питання, пропозиції або ви зацікавлені у вирішенні таких завдань - Пишіть на [email protected]