Problem trgovačkog putnika
Problem trgovačkog putnika, logistički problem iz svakodnevnog života, rješava se u teoriji grafova. Sličan je problemu kineskog poštara.[1]
Rješava ga se tako što se pokušava naći šetnju kojom će se barem jednom proći kroz svaki vrh na grafu te se vratiti na početni vrh, učinivši to na najkraći mogući način, koristeći se usmjerenim ili neusmjerenim grafom. Mogu biti zadane i udaljenosti među vrhovima, pa se traži i da je ukupna prijeđena udaljenost najmanja.[1]
Usporedba je s poštarom koji se kreće ulicama (u matematičkom modelu to je graf) te ima zadaću dostaviti pošiljke u svaku kuću (vrhovi dotičnog grafa), u najkraćem veremenu te se vratiti u poštu (polaznu točku). Poštar želi potrošiti što manje vremena, truda i novca da bi izvršio svoju zadaću, upotrijebivši najkraću rutu.[1]
Primjena je npr. kod planiranja ruta i redoslijeda prijevoza robe od skladišta do trgovina.[1]
Izvori
- ↑ 1,0 1,1 1,2 1,3 math.e, hrvatski matematički elektronički časopis Maja Fošner i Tomaž Kramberger: Teorija grafova i logistika br. 14, ISSN ISSN 1334-6083 (pristupljeno 23. prosinca 2019.)