Welkom bij WHIZZKIDS '96

Hier vind je informatie over de Whizzkids wiskunde puzzle 1996. Dit is een puzzel wedstrijd gesponsord door CMG (consultants in informatie technologie) en werd gepubliceerd in de Telegraaf, eind september 1996. Het probleem is bedacht door Jan Karel Lenstra en Emile Aarts, hoogleraren aan de Technische Universiteit Eindhoven.

Aan deze wedstrijd mocht iedereen meedoen, op enkele evidente uitzonderingen na. Er waren speciale prijzen te verdienen door de beste scholier en beste schoolklas. Er is een aparte categorie voor professionals.

Het probleem

Ten tijde van de publicatie was een volledige beschrijving voorhanden bij CMG. Het probleem bestaat uit het verzinnen van een leveringsplan waarin door vier krantenjongens bij 120 abonnees de krant wordt bezorgd. Die kranten worden bij een centraal depot opgehaald en van daaruit brengen de joingens de krant rond. Bedoling is de LAATSTE KRANT ZO VROEG MOGELIJK te bezorgen. Als tweede criterium wordt de GEMIDDELDE BEZORGTIJD PER ABONNEE zo laag mogelijk gehouden. Voor een gemakkelijke beschrijving van de afstanden is het leveringsprobleem gesitueerd in Manhattan. Vanwegew het stratenpatroon is het eenvoudig de lokatie van een abonnee te geven met (x,y) coordinaten. Bovendien is het gemakkelijk uit te rekenen hoever twee abonnees van elkaar liggen. Een numeriek overzicht is te vinden in overzicht van abonnees en depot.

Oplossingen

We hebben meer dan 900 oplossingen binnengekregen. Een 14 jarige scholier heeft daarbij de professionals weten te verslaan!!! En wel met een papier-en-potlood methode. De beste oplossing werd gevonden door een groep Eindhovense studenten, die daarvoor veel computer kracht hebben gebruikt. Ze vonden een leverschema met lengte 1183 en een kortste gemiddelde levertijd. Het schijnt ze wel slapeloze nachten te hebben opgeleverd. Een verslag van hun wederwaardigheden vind je in sleepless nights. Een oplossing gelijk aan die van de studenten is weergegeven in het volgende plaatje:

met de vier routes gegeven door:

0 83 84 89 86 96 104 109 105 106 98 102 101 95 88 87 93 94 112 97 92 90 79 56 51 49 42 37 21 18

0 73 69 61 55 50 44 45 36 34 25 30 31 27 32 35 43 41 28 23 24 22 17 15 13 10 8 1 6 5 2

0 81 72 60 65 68 67 70 75 78 80 76 66 64 63 62 57 59 58 54 53 48 47 39 40 26 38 33 14

0 85 91 114 113 115 120 118 117 119 116 108 110 111 107 100 103 99 82 77 74 71 52 46 29 20 19 16 9 11 12 3 4 7

Merk op dat dit niet noodzakelijk het best mogelijke antwoord is. We kunnen slechts bewijzen dat een oplossing met een lengte korter dan 1160 niet mogelijk is. Er is dus nog een marge van 2 procent.

Je hoeft een computer niet alleen te laten "stampen". Je kunt hem ook gebruiken om een strategie gebaseerd op menselijk inzicht te ondersteunen. Diego Lont (ook een informatica student) heeft met collega-studenten een beslissingsondersteunend systeem gemaakt waarmee je de routeverdeling kunt manipuleren. Daarbij worden de oplossingkarakteristieken automatisch bijgewerkt. Je vindt het in de java applet.

We hopen dat ieder plezier heeft gehad van de puzzel. Wie wil kan nog werken aan een OPEN VRAAG. Er is een beloning van 5000 GULDEN voor diegene die met een oplossing aankomt die strict KORTER is dan 1183 of die BEWIJST dat zo'n oplossing niet kan bestaan.

Update: it has been shown by Bill Cook et al that the best solution submitted is the true optimum solution, both for a min-max of 1183, as well as the minimum average delivery time 558.81667. A full description is found in David Applegate, William Cook, Sanjeeb Dash, Andre Rohe, (2002) Solution of a Min-Max Vehicle Routing Problem. INFORMS Journal on Computing 14(2):132-143. Online version.

This page was modified last on: December 23, 1997,
by Cor Hurkens (wscor@win.tue.nl)