hrvatski

Metaheurističke metode rješavanja problema usmjeravanja vozila s vremenskim prozorima

Problem usmjeravanja vozila (eng. Vehicle Routing Problem, kratica VRP) predstavlja težak kombinatorni problem sa kojim se svakodnevno susreću tvrtke koje skupinom vozila obavljaju dostavu ili prikupljanje tereta na više geografski udaljenih lokacija. Skupinom vozila ograničenih kapaciteta potrebno je posjetiti skup lokacija i obaviti iskrcaj/ukrcaj zadane količine tereta, pri čemu vozila polaze iz skladišta i vraćaju se u skladište nakon obavljenog posluživanja. Problem usmjeravanja vozila s vremenskim prozorima (eng. Vehicle Routing Problem with Time Windows, kratica VRPTW) proširenje je osnovnog VRP problema u kojem svaka lokacija ima definiran vremenski prozor unutar kojeg posluživanje mora započeti. Rješavanje ovog problema podrazumijeva pronalazak rješenja sa minimalnim brojem potrebnih vozila i rutama po kojima će ukupna prevaljena udaljenost biti minimalna. Zbog kompleksnosti problema, egzaktne metode rješavanja primjenjive su samo na problemima manjih dimenzija, dok se kod problema većih dimenzija moraju primijeniti heurističke ili metaheurističke metode koje ne jamče pronalazak optimalnog rješenja, ali relativno brzo mogu pronaći rješenja zadovoljavajuće kvalitete. Posebno učinkovite su metaheurističke metode zasnovane na idejama iz prirode poput simuliranog kaljenja, genetskog algoritma i algoritma mravlje kolonije. Opisan je princip rada navedenih metoda kao i njihove različite inačice i proširenja. Implementirani algoritmi testirani su na standardnim testnim problemima, a ostvareni rezultati uspoređeni sa rezultatima drugih autora. Algoritmi su primijenjeni i na problemima iz prakse modeliranim na osnovu podataka prikupljenih od nekoliko hrvatskih tvrtki različitih profila i djelatnosti (dostava poštanskih pošiljaka, dostava tiskovina, dostava farmaceutskih proizvoda, dostava pekarskih proizvoda i dostava robe široke potrošnje). Opisana je metodologija rješavanja u praksi uz pomoć geografskog informacijskog sustava i vektorskog zemljovida koji je nužan za mjerenje stvarnih prometnih veličina poput cestovnih udaljenosti i vremena putovanja, te je prikazan prototip programskog rješenja koje se može primijeniti u tvrtkama kao alat za planiranje dostave. Rezultati dobiveni rješavanjem praktičnih problema pokazali su da je troškove dostave moguće značajno smanjiti primjenom opisane metodologije i metaheurističkih metoda rješavanja.

problem trgovačkog putnika; TSP; problem usmjeravanja vozila; VRP; problem usmjeravanja vozila s vremenskim prozorima; VRPTW; metaheurističke metode; genetski algoritam; simulirano kaljenje; optimizacija kolonijom mravi; kombinatorička optimizacija; praktični problemi usmjeravanja vozila

nije evidentirano