Problem rutiranja vozila
Problem rutiranja vozila (engl. Vehicle routing problem; VRP) je ime za čitavu klasu problema u kojima se traži optimalnaa putanja (ruta) kojom bi transportno vozilo ili više vozila obišli zadati broj gradova polazeći iz centralnog skladišta. Pod optimalnom putanjom se pre svega misli na onu sa minimalnom cenom troškova puta koji se obiđe.
Pojam problema rutiranja vozila (PRV) se javlja krajem 50-ih godina 20. veka kao centralni problem u transportu, distribuciji i logistici preduzeća. U nekim granama privrede veliki procenat cene proizvoda odlazi na transportne troškove, te se njihovom optimizacijom ukupni troškovi proizvoda mogu smanjiti od 5% do 20%.
Kompletan put koje jedno vozilo pređe polazeći iz centralnog magacina, obilazeći klijente i vrativši se u centralni magacina naziva se ruta. Deo rute čine delovi puta koje vozilo pređe prelazeći direktno od jednog klijenta do drugog naziva se putanja. Problem rutiranja vozila se može posmatrati kao specifičan problem koji kombinuje Problem trgovačkog putnika i „Problem pakiranja“.
Načini rešavanja[uredi | uredi izvor]
Načini rešavanja Problema rutiranja vozila se mogu podeliti u sledeće grupe:
- egzaktni algoritmi
- heuristički algoritmi
- metaheuristički algoritmi (mravlji algoritam, genetički algoritmi, tabu pretrage itd.)