Logisztikus ügynökök

Szép napot mindenkinek!

Még a múlt héten kaptam egy újabb publikációs listát, amelyet fel kell tölteni a Magyar Tudományos Művek Tárába. Mostani alanyom Földesi Péter tanár úr, aki logisztikával és az ellátási láncokkal foglalkozik, de publikációi – és rengeteg konferencia-előadása – számos részterületet érintenek. (Egy Győrben elhangzott előadást a Videotoriumon is meg lehet nézni). Közülük is egy felkeltette a figyelmemet, mert több helyen is előfordul, és még csak nem is hallottam róla: a Travelling Salesman Problem (TSP), avagy az utazó ügynök problémája. Logisztikai órákon minden bizonnyal előkerül ez a fogalom, de azért – már csak saját kíváncsiságom kielégítése érdekében is – itt egy kis összefoglaló róla.

Képzeljük el azt az ideális állapotot, hogy szabadságra megyünk / véget ért a vizsgaidőszak, és nyaralni megyünk. Majd vegyük azt az igen gyakran előforduló másik állapotot, hogy kevés a pénzünk az utazásra, és azt szeretnénk, hogy az adott keretek között a legtöbbet hozzuk ki a nyaralásból. Szóval ülünk a térkép fölött, bekarikázzuk azokat a városokat (falvakat, stb.), amelyeket fel szeretnénk keresni, de ott a probléma: minél kevesebb pénzt kelljen az utazásra költeni.

Ahhoz képest, hogy ezzel mennyien foglalkoznak heves viták közepette a családi asztal fölött (s kisebb-nagyobb sikerrel meg is oldják!), ez a feladat, mely az 1930-as évektől “utazóügynök-probléma” néven is ismert, s alkalmazza a logisztika, a számítástechnika és, meglepő módon a biológia is. Alapvetően a nehézség a nagyobb településszámnál kezdődik, hiszen a lehetőségek száma n település esetén mindig (n-1!)/2 lesz, ami már tíz település esetében is 181.440 választható megoldás, és ebből kiválasztani az optimálisat… (apropó, nem legoptimálisabb, hanem optimális!)

Nos hát ezért kutatják ennyien! 🙂

Advertisements

Vélemény, hozzászólás?

Adatok megadása vagy bejelentkezés valamelyik ikonnal:

WordPress.com Logo

Hozzászólhat a WordPress.com felhasználói fiók használatával. Kilépés / Módosítás )

Twitter kép

Hozzászólhat a Twitter felhasználói fiók használatával. Kilépés / Módosítás )

Facebook kép

Hozzászólhat a Facebook felhasználói fiók használatával. Kilépés / Módosítás )

Google+ kép

Hozzászólhat a Google+ felhasználói fiók használatával. Kilépés / Módosítás )

Kapcsolódás: %s

%d blogger ezt kedveli: