Általánosított profitfüggvény és oszlopgenerálás az utazó szerelő típusú problémákra

Absztrakt (kivonat)

A szakdolgozat a kombinatorikus optimalizálás egyik népszerű fejezetébe tartozó utazó ügynök és utazó szerelő problémák közös általánosítását vizsgálja. A bevezetett problémamodell a profitfüggvények egy újonnan definiált osztályát tartalmazza. A kidolgozott megoldás az egészértékű lineáris programozáson alapul. A megközelítés a klasszikus korlátozás és szétválasztás keretébe ágyazott oszlopgenerálás módszertanát alkalmazza. A technika egyik lényeges kihívása a beárazó részfeladat megoldása. Erre az általánosított feladat sajátosságaihoz adaptált algoritmus került kidolgozásra. A futtatott tesztek alapján az így létrejött megoldás hatékonyan képes kezelni a megcélzott problémát. --- The thesis examines the common generalization of the traveling salesman and traveling repairman problems, which belongs to a popular area of combinatorial optimization. The introduced problem model contains a newly defined family of profit functions. The developed solution is based on integer linear programming. The approach applies the column generation methodology embedded within the classical branch-and-bound framework. One of the key challenges of this technique is the solution of the pricing subproblem. An algorithm adapted to the characteristics of the generalized problem has been developed. Based on the test runs this solution is able to deal effectively with the discussed problem.