Skip to ContentSkip to Navigation
Over onsNieuws en agendaNieuwsberichten

Proefschrift: 'Beter zoeken met BnB'

08 februari 2007

Als de code van een cijferslot zoek is, kan het alleen geopend worden door alle cijfercombinaties langs te gaan. In het slechtste geval is de laatste combinatie de juiste. Echter, als de code uit tien cijfers bestaat, moeten tien miljard mogelijkheden bekeken worden. De zogenaamde 'NP-lastige' problemen in het proefschrift van Marcel Turkensteen zijn vergelijkbaar met het 'cijferslotprobleem'. Ook bij deze problemen is het aantal mogelijkheden buitensporig groot.

Cijferslot
Cijferslot

De kunst is derhalve om de zoekruimte op een slimme manier af te tasten. Bij de Branch and Bound (BnB) methode wordt dit gedaan door de zoekruimte op te splitsen in kleinere deelgebieden. Turkensteen past de BnB methode onder andere toe bij het handelsreizigersprobleem, waarbij een kortste route door een verzameling plaatsen bepaald moet worden. Dit probleem is in algemene vorm nog steeds niet opgelost. De economische gevolgen kunnen groot zijn: zo staat nog steeds niet vast of bijvoorbeeld een routeplanner vrachtwagens optimaal laat rondrijden. De huidige BnB-methoden worden in dit proefschrift met name verbeterd door niet naar de kosten van een verbinding te kijken, maar naar de kostentoename als een verbinding niet gebruikt wordt: de boventolerantie.

 

Curriculum vitae
Marcel Turkensteen (Tolbert, 1979) studeerde econometrie in Groningen. Het onderzoek werd uitgevoerd bij de afdeling Marketing en SOM. Turkensteen promoveert op 15 februari 2007 (13.15 uur) tot doctor economische wetenschappen in de bij prof.dr. G. Sierksma. De titel van het proefschrift is: Advanced analysis of branch and bound algorithms.

Laatst gewijzigd:31 januari 2018 11:51
printOok beschikbaar in het: English

Meer nieuws

  • 14 juni 2018

    Bringing Physical Internet to life

    Van maandag 18 tot vrijdag 22 juni vindt het vijfde internationale Physical Internet congres (#IPIC2018) plaats in Groningen. De Rijksuniversiteit Groningen organiseert dit congres samen met de logistieke sector. Meer dan 250 wetenschappers en vertegenwoordigers...

  • 11 juni 2018

    Een nieuw tijdperk voor organisationele relaties | Oratie David Langley | Dinsdag 19 juni

    Nieuwe, veelbelovende internet-afhankelijke technologieën zoals digital fabrication, internet of things, blockchain en distributed artificial Intelligence worden steeds populairder. Prof. David Langley geeft in zijn oratie een toelichting op zijn ideeën...

  • 08 juni 2018

    Lara Lobschat wint MOA Insights Scientist Award

    Lara Lobschat heeft de MOA Insights Scientist Award gewonnen. De universitair docent Marketing kreeg de prijs voor haar proefschrift over online communicatie. Vanwege de praktische relevantie kreeg ze voor haar onderzoek eerder een ‘early career grant’...