Izvorni znanstveni članak

https://doi.org/10.7305/automatika.2014.01.580

Optimizacija usmjeravanja vozila primjenom višestrukih poboljšanja u lokalnom pretraživanju

Juraj Fosin orcid.org/0000-0002-3176-5239 ; Department of Intelligent Transportation Systems, Faculty of Transport and Traffic Sciences, University of Zagreb Vukelićeva 4, HR-10000 Zagreb, P.O. Box 170, Croatia
Tonči Carić orcid.org/0000-0001-8564-4304 ; Department of Intelligent Transportation Systems, Faculty of Transport and Traffic Sciences, University of Zagreb Vukelićeva 4, HR-10000 Zagreb, P.O. Box 170, Croatia
Edouard Ivanjko ; Department of Intelligent Transportation Systems, Faculty of Transport and Traffic Sciences, University of Zagreb Vukelićeva 4, HR-10000 Zagreb, P.O. Box 170, Croatia

Sažetak

Kombinatoričke optimizacije na grafu pojavljuju se u mnogim aplikacijama u praksi. Jedan od najviše proučavanih kombinatoričkih optimizacijskih problema je problem usmjeravanja vozila. Ukoliko se optimizacija usmjeravanja vozila poveže sa suvremenim u vozila ugrađenim sustavima navigacije i nadgledanja voznog parka moguće je postići značajne uštede u troškovima dostave. U ovom radu je predložen novi mehanizam odabira smjera lokalnog pretraživanja zasnovan na višestrukim poboljšanjima za rješavanje kapacitivnog problema usmjeravanja vozila. Predloženi novi mehanizam je implementiran kao dio mehanizma odabira smjera lokalnog pretraživanja u algoritmu iterativnog lokalnog pretraživanja. Prošireni algoritam iterativnog lokalnog pretraživanja je provjeren na 4 vrlo velika optimizacijska problema sa stvarnim podacima iz Hrvatske (skup od 7.065 kupaca i 236 dostavnih vozila) i na standardnim testnim skupovima. Stvarni testni podaci dobiveni su od jedne velike hrvatske logističke tvrtke. U radu je napravljena usporedba između mehanizama odabira smjera lokalnog pretraživanja zasnovanih na prvom i najboljem poboljšanju te predloženog mehanizma poboljšanja lokalne pretrage. Usporedba je napravljena prema prijeđenom putu, broju pomaka lokalnog pretraživanja i vremenu izračuna. Dobiveni rezultati pokazuju ubrzanje u vremenu izračuna za 29 puta u usporedbi sa prvim smjerom poboljšanja lokalne pretrage te 9 puta u usporedbi sa najboljim smjerom poboljšanja lokalne pretrage bez značajnijih degradacija u kvaliteti dobivenog rješenja.

Ključne riječi

VRP; CVRP; iterativno lokalno pretraživanje; višestruka poboljšanja

Hrčak ID:

125607

URI

https://hrcak.srce.hr/125607

Datum izdavanja:

16.7.2014.

Podaci na drugim jezicima: engleski

Posjeta: 3.152 *