Designing optimal transport routes using open-source software

Abstract

Vehicle routing plays a major role in the industry, primarily in companies that organize the transport of goods to end-users. The theoretical background of the vehicle routing problem has been known for many years and it has been the basis for developing a lot of commercial software solutions. However, in practice, there is a barrier in the form of the lack of affordable software solutions. The difficult access to quality and reliable spatial data relating to the road network is also a limitation. This paper looks into the possibilities of applying open source software to solve this NP-difficult problem. The free spatial data from OpenStreetMap, a joint project of the virtual community, was used as a basis for modeling the graph of the road network. The experiment was carried out over the data on vehicles and users of the specific retail chain and relates to the territory of Serbia.

Rutiranje vozila ima veliku ulogu u industriji, prvenstveno u kompanijama koje se bave organizovanjem transporta dobara do krajnjih korisnika. Teorijska pozadina problema rutiranja vozila je već dugi niz godina poznata i na osnovu nje je razvijeno mnoštvo komercijalnih softverskih rešenja. Međutim, u praksi se javlja prepreka u vidu nedostatka pristupačnih softverskih rešenja. Ograničenje predstavlja i otežan pristup kvalitetnim i pouzdanim prostornim podacima koji se odnose na putnu mrežu. U radu su ispitane mogućnosti primene softvera otvorenog koda za rešavanje ovog NP-teškog problema. Kao osnova za modelovanje grafa mreže saobraćajnica, uzeti su slobodni prostorni podaci OpenStreetMapa, udruženog projekta virtualne zajednice. Eksperiment je izvršen nad podacima o vozilima i korisnicima jednog trgovinskog lanca i odnosi se na područje Srbije.