Investigation of Capacitated Vehicle Routing Algorithms

Abstract

The main aim of Master Thesis is to perform extensive capacitated vehicle routing problem algorithms analysis and suggest an open source implementation. The aim is achieved by performing a capacitated vehicle routing problem algorithms analytical review, architectural review of best performing HGSADC algorithm and creating an open source implementation. Finally, two computational benchmarks of an implemented open source algorithm are presented comparing results to the original HGSADC version and other open-source CVRP algorithms. The thesis consists of 39 pages of text without appendixes, 15 figures, 2 tables, 50 reference entries, 1 appendix

Magistro baigiamojo darbo tikslas - ištirti transporto priemonių galimybes įvertinančio maršruto sudarymo algoritmo (angl. Capacitated Vehicle Routing Problem; CVRP) tobulinimo galimybes, pasiūlyti ir ištirti algoritmo modifikacijas. Iškeltiems uždaviniams įvykdyti buvo atlikta analitinė CVRP algoritmų apžvalga, išanalizuota efektyviausio dabartinio metodo HGSADC architektūra ir sukurta jį įgyvendinanti atvirojo kodo implementacija. Atlikti eksperimentiniai bandymai lyginant sukurtą algoritmą tiek su HGSADC autoriaus skelbiamais rezultatais, tiek su kitais atvirojo kodo CVRP algoritmais. Sukurtas algoritmas rodo geriausius rezultatus tarp atvirojo kodo CVRP algoritmų, tačiau ženkliai atsilieka nuo rezulatų, skelbiamų HGSADC straipsnyje. Darbo apimtis: 39 psl. teksto be priedų, 15 iliustr., 2 lentelės, 50 bibliografinių šaltinių, 1 priedas.