Álmos, Attila (2017) Általánosított profitfüggvény és oszlopgenerálás az utazó szerelő típusú problémákra. MA/MSc thesis, BCE Közgazdaságtudományi Kar, Matematikai Közgazdaságtan és Gazdaságelemzés Tanszék.
|
PDF
- Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
438kB |
Abstract
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.
Item Type: | MA/MSc thesis |
---|---|
Uncontrolled Keywords: | utazó ügynök probléma, utazó szerelő probléma, egészértékű lineáris programozás, szétválasztás és beárazás, oszlopgenerálás, címkebeállító algoritmus, traveling salesman problem, traveling repairman problem, integer linear programming, branch-and-price, column generalization, label setting algorithm |
Subjects: | Mathematics. Econometrics Economics |
ID Code: | 10206 |
Specialisation: | Gazdaság-matematikai elemző |
Deposited On: | 09 Nov 2017 13:57 |
Last Modified: | 09 Nov 2017 14:18 |
Repository Staff Only: item control page