Задача аптымізацыі перавозак грузаў з падхватам і дастаўкай (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]