We vroegen jullie naar de snelste route door Cineville. En toen gingen jullie los.

Hoeveel kilometer leg je af als je wandelend/rennend/sjokkend van Leeuwarden naar Maastricht moet en onderweg alle 37 andere Cinevillesteden wil aantikken? Een simpele vraag, lastig te beantwoorden.

 

Jullie gingen er helemaal vol voor. De één stuurde een foto van een kladblokje (‘geen AI praktijken’), een ander had door deze wandeling meteen een nieuw vakantieplan voor de zomer. Er zaten leuke feitjes tussen (‘dit is ongeveer ook de afstand als je een rondje óm Nederland zou willen lopen’), maar ook grote filosofische twijfels (‘fast forward 2 uur verder voor deze Camino de Cineville. Ik zit vol met vragen over afstanden, tijd en ruimte’). We ontvingen veel felicitaties en nog meer lieve bedankjes.

 

Er zaten zeker 21 antwoorden bij die dicht bij elkaar lagen, ergens in de regio 1100 – 1250 kilometer. Maar er was er maar één Cineviller die een eigen code schreef, rekening hield met de stadsgrenzen én een heuse Cineville-wandelplaylist maakte. Gefeliciteerd, Julius! En de rest: ontzettend bedankt voor jullie creatieve inzendingen.

 

De winnaar

Julius schreef een eigen code, liet de computer nachtenlang algoritmes draaien, maakte een Cineville wandelplaylist, mailde ons een uitgebreide uitleg vol met filmreferenties en kwam met een antwoord dat nog specifieker was dan wij het zelf konden bedenken: 1100 km, gerekend vanaf de randen van iedere stad. Want met het feit dat routeplanners uitgaan van het centrum van een stad, en niet met de randen van de stad (‘tik 'm aan’), daar hadden we zelf niet eens rekening mee gehouden. Julius wint daarom 15 jaar maanden gratis Cineville.

 

Mocht je geïnteresseerd zijn in hoe Julius de afstand berekende dan staat hieronder zijn uitleg. Wow.

 

Still uit Mommy (2014)

The puzzle

I have spent the past days frantically working on a solution for your puzzle. The puzzle you described is a well-known problem in mathematics and computer science (precisely my Zone of Interest) called The Travelling Salesman Problem. There is no straightforward way to compute a solution, and the only way to truly know if your answer is the optimal solution is to try out all possible combinations of cities. However, with 39 cities, that is about 20397882081197443358640281739902897356800000000 different solutions, which would take about 101989410405987216793201408699514487 years to compute. There are however some algorithms which help you search a subset of combinations to help you find the best possible solution reasonably In Time.

 

Mapping out distances

I first started by marking the locations of all 39 Cineville cities on Google Maps. For each city, I input the walking distance to all other close by cities. I used the center of the cities as given by Google Maps as the locations to calculate The Matrix of walking distances in km. Of course, using the direct airline as a distance between cities would give a smaller final distance in the end, but I did not use that since one cannot walk through walls (only in a Dream Scenario). Also, it is important to note that you specified in the comments of the Instagram post that it is not allowed to cross the country borders. This means you cannot take the shortest route from Helmond to Maastricht, but must go along the border making this distance slightly longer.

 

 

Computing a solution

After I wrote down all the distances, I wrote some python code to compute solutions. I used the simulated annealing algorithm to find a base solution. This algorithm starts of exploring different solutions at the beginning of the search and tries to improve these solutions gradually by swapping out cities or inserting them at moving them to different points of the route later in the search. This base solution turned out to be 1170 km long. I then used another algorithm called breadth-first search to try to find similar but better solutions based on the base solution and left that running overnight. This returned an improved solution of 1162 km. That solution is:

 

Leeuwarden, Groningen, Zwolle, Enschede, Deventer, Apeldoorn, Arnhem, Zevenaar, Nijmegen, Wageningen, Houten, Utrecht, Amersfoort, Hilversum, Bussum, Amsterdam, Zaandam, Hoorn, Enkhuizen, Alkmaar, Castricum, IJmuiden, Haarlem, Leiden, Voorschoten, Den Haag, Delft, Schiedam, Rotterdam, Dordrecht, Zierikzee, Middelburg, Oostburg, Goes, Breda, Den Bosch, Eindhoven, Helmond, Maastricht.

 

Shortcuts

That is however not the end of it. I realized that to have “visited” a city, one has to only go within the city borders, not all the way to the central point of that city. In cases where the route goes one way, then turns around and goes backward, one can save kilometers by only going into the edge of the borders of the city. This allowed me to make the following adjustments:

 

Groningen: Gravenburg, Groningen: -6km

Enschede : Hengelosestraat, 7521 PB Enschede -8km

Zaandam: Witbaard / D, Kerkstraat 6, 1511 EH Oostzaan -3km

Enkhuizen: Westeinde 192, 1601 BN Enkhuizen -3km

Ijmuiden: De Noostraat/Pont Velsen, 1981 BZ IJmuiden -2km

Den Haag: Aristoteleslaan 1, 2493 ZW Den Haag -4km

Doordrecht: Zuidendijk 46, 3314 CW Dordrecht -5km

Zierikzee: Weg naar de Val 168, Zierikzee -1km

Middelburg: Mortiere III, Middelburg -2km

Oostburg: 51.339546, 3.520477, Oostburg -5km

Den Bosch: Deutersestraat 4, 5223 GV 's-Hertogenbosch -3km

Eindhoven: Koudenhoven, 5631 AH Eindhoven -5km

Helmond: Korte Brugstraat 4-2, 5706 SL Helmond -5km

Saving 52km in total.

 

 

Making the final route:

Leeuwarden, Gravenburg (Groningen), Zwolle, Hengelosestraat, 7521 PB (Enschede), Deventer, Apeldoorn, Arnhem, Zevenaar, Nijmegen, Wageningen, Houten, Utrecht, Amersfoort, Hilversum, Bussum, Amsterdam, Witbaard / D, Kerkstraat 6, 1511 EH Oostzaan (Zaandam), Hoorn, Westeinde 192, 1601 BN (Enkhuizen), Alkmaar, Castricum, De Noostraat/Pont Velsen, 1981 BZ (Ijmuiden), Haarlem, Leiden, Voorschoten, Aristoteleslaan 1, 2493 ZW (Den Haag), Delft, Schiedam, Rotterdam, Zuidendijk 46, 3314 CW (Dordrecht), Weg naar de Val 16  (Zierikzee), Mortiere III, (Middelburg), 51.339546, 3.520477 (Oostburg), Goes, Breda, Deutersestraat 4, 5223 GV (Den Bosch), Koudenhoven, 5631 AH (Eindhoven), Korte Brugstraat 4-2, 5706 (Helmond), Maastricht.

 

After Everything, the final solution takes 1110km. I visualized the route by stitching together multiple screenshots from Google Maps, as Google Maps only allows routs with 10 stops at a time. As I said before, the distance would be shorter if one only used the airline for distance, but then the solution would Stop Making Sense. And that’s the weekend, I will go back to watching movies for fun instead now.