Az utazó ügynök probléma

Abstract

Dolgozatomban arra tettem kísérletet, hogy sokrétű képet adjak az utazó ügynök feladatnak nevezett matematikai problémáról. A probléma azért különleges, mert megfogalmazása viszonylag könnyű, bárki számára megérthető, ugyanakkor matematikai szempontból a megoldása különösen időigényes, ezért az operációkutatási irodalomban megjelenő, újonnan kifejlesztett algoritmusokat gyakran az utazó ügynök feladaton „tesztelik”. Szakdolgozatomban bemutatom a problémát, annak variációit, a rá illeszkedő matematikai modelleket, és a megoldási módszerek jelentős részét. A dolgozatban nagy hangsúlyt fektetek a feladat gyakorlati alkalmazásának illusztrálására is. Emellett olyan szemszögből is vizsgálom a kérdést, hogy milyen teljesítményt nyújt az emberi agy a feladat megoldásában. A dolgozat célja elsősorban, hogy széleskörű betekintést nyújtson az utazó ügynök problémával kapcsolatos irodalomba, és bizonyítsa az olvasó számára, hogy a probléma a gyakorlati életben is sokszor felmerül. Ezen kívül igyekeztem a témához kapcsolódó érdekesebb modellekre, módszerekre és eredményekre is kitérni, ahol erre lehetőségem adódott. Munkám zárófejezetében egy esettanulmányt elemzek, mely egy finn városban az idősek számára történő melegétel-kiszállítást mutatja be, valamint vizsgálja az optimalizálás különböző feltételek melletti költségcsökkentő hatását. Az elkészült mű nagy része gráfelméleti és bonyolultságelméleti ismereteket tételez fel. A fontosabb fogalmakat azonban a függelékben röviden definiálom.