Problem kineskog poštara
Problem kineskog poštara, logistički problem iz svakodnevnog života, rješava se u teoriji grafova. Sličan je problemu trgovačkog putnika.[1]
Rješava ga se tako što se pokušava naći šetnju kojom će se samo jednom proći kroz svaki brid na grafu, učinivši to na najkraći mogući način, koristeći se usmjerenim ili neusmjerenim grafom.[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 vremenu 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 kod planiranja ruta autobusnog javnog prijevoza, školskih autobusa, vozila za skupljanje smeća, vozila za čišćenje ulica, vozila za čišćenje snijega, šišanje trave oko autoceste, ispitivanje dalekovoda i dr. Kod organiziranja javnog autobusnog prijevoza, tvrtka određuje mjesto autobusne postaje kao vrh i cestu kao brid u ruti autobusa. Primjenom teorije grafova izabire optimalnu rutu kojom svodi potrošnju goriva na najmanju moguću i da pritom u što manje moguće vremena svaku cestu "pokrije" barem jednom.[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.)