Wie bezorgt de krant het snelst in Manhattan?

door Huibert Spoorenberg
Stel je voor: er wonen 120 abonnees van De Telegraaf in Manhattan. Hun appartementen zijn willekeurig verspreid over het raster van streets en avenues van dat deel van New York. Er is één distributiepunt en vier bezorgers. Bedenk dan maar eens de ideale bezorgroutes, waarbij de kranten in een zo kort mogelijke tijd in de bus belanden. De Computer Management Group (CMG) maakte er in samenwerking met de TUE en De Telegraaf een wedstrijd van. Een puzzel als voorbeeld van toegepaste wiskunde en informatica. Hoe eenvoudig de opdracht ook klinkt, zo complex is de oplossing. Het is, net als het klassieke handelsreizigersprobleem, een geval van discrete optimalisering. Maar nu is het nog lastiger, omdat je ook nog moet beslissen wèlke krantenjongen wèlke abonnees van kranten voorziet. De oplossing wordt dus niet één route die alle ‘klanten’ verbindt, maar meer een soort spin met vier poten. Elke oplossing geeft overigens een bovengrens op de minimale bezorgtijd. Maar bij een bepaald bezorgplan heb je het optimum en het is de bedoeling om dat te vinden. Het gebruik van computers is toegestaan, maar zelfs als er maar zestig kranten bezorgd hoefden te worden zijn er al meer verschillende routes mogelijk dan dat er zich atomen in het heelal bevinden. De bedenkers van de puzzel hebben zelf uiteraard een oplossing, maar niemand kan bewijzen dat het niet beter kan. Bij de huidige stand van zaken in de wiskunde is dit soort problemen namelijk nog altijd niet oplosbaar.
Het idee voor de wedstrijd is eigenlijk uit nood geboren. Omdat de universitaire uitstroom aan wiskundigen en informatici zo gering is, kampt CMG al langere tijd met een personeelstekort: voor 300 arbeidsplaatsen zijn slechts 200 afgestudeerden beschikbaar. Daarom besloot het bedrijf een leuke puzzel te verzinnen om de interesse in de studie Wiskunde en Informatica enigszins te verhogen. Wat ook weer in het belang van de TUE is. De makers willen daarom jaarlijks een dergelijke wedstrijd uitschrijven. Met hun medewerkers bedachten de TUE-hoogleraren Emile Aarts en Jan Karel Lenstra dit jaar het bezorgprobleem en CMG zocht contact met een krant die mee wilde werken. Het werd De Telegraaf, die de wedstrijd op 7 september publiceerde. Op die dag verscheen het probleem tevens op het World Wide Web. Vast staat dat veel mensen zich er het hoofd over aan het breken zijn: scholieren (individueel en klassikaal), studenten, echte professionals en hobbyende gepensioneerden. Er zijn in vier categorieën hoofdprijzen van fl. 5000,- te winnen. Voor de beste oplossing, de beste scholier, de beste schoolklas en de beste professional (werkenden op het gebied van onderzoek en ontwikkeling van Wiskunde en Informatica). Onder de vermelding ‘Whizzkids ‘96’ kunnen oplossingen tot 22 oktober opgestuurd worden aan: Lubbers & Dijk, Notarissen; Postbus 53040; 1007 RA Amsterdam. Informatie is te verkrijgen bij CMG NL, Laan van Kronenburg 14; 1183 AS Amsterdam, of bij prof. Jan Karel Lenstra, HG 9.31, of via http://www.cmg.nl/manhattan/index.html.