03 AllStreets - Find optimal organisation

Dit deel bestaat uit een aantal eenvoudige stappen, die wel de nodige tijd vereisen. Soms zal het lijken alsof de computer blokkeert, maar in de console kan je zien dat dat niet zo is.

De basisgedachte is: elk kruispunt met een oneven aantal straten, bijvoorbeeld een "T", is de oorzaak van het feit dat je een stuk heen-en- weer moet lopen.

Instellingen hierbij zijn:

• "Distance Algorithm": bereken een "distance matrix" met een geschatte afstand tussen alle gele punten onderling
• "Euclidian": bereken een snelle schatting van de lengte van de gele stukken
•  "A* distance": bereken een meer nauwkeurige lengte. Kies voor deze indien het netwerk niet té groot is.
• "Iterations": aantal iteraties die worden uitgevoerd per keer. Experimenteer hiermee afhankelijk van de snelheid van je computer; in principe stopt het algoritme na 25 seconden met zoeken (deze parameter heet endTime en kan je aanpassen via "SET/SaVe/LD").
• "Groupsize": in groepjes van hoeveel gele punten de computer een betere oplossing zoekt. Zet dit niet te hoog. Deze parameter wordt niet gebruikt bij automatische optimisatie.
• "MCMC value": het algoritme zoekt betere oplossingen, maar accepteert op statistische basis soms ook slechtere oplossingen, dit om niet in lokale minima vast te lopen. Een waarde van 1.05 betekent dat oplossingen die 5% slechter zijn toch geaccepteerd kunnen worden.
• het kan helpen om deze parameter op 1.08 te laten starten en langzaam te laten zakken naar 1
• zet dit bij de laatste optimisatie op 1.00

Dingen die je kan doen:

• "Preprocess (uneven nodes and dead ends)": 
• zoekt doodlopende straten, kleurt deze oranje en verdubbelt ze (zodat ze niet meer dood lopen, maar een rondje zijn)
• zoekt kruispunten met 3-5-7... straten en kleurt deze geel
• maakt een initieel voorstel van straten die je heen en weer moet lopen, kleurt deze geel
• "Auto optimize distance": probeer de gele straten zo te organiseren dat ze samen een minimale afstand hebben. Gebruik hierbij het aangegeven aantal iteraties en een groepsgrootte van 2 tot 5
• "Find Eulerian Path": bereken al eens een route langsheen alle punten

Belangrijk! Indien er om een of andere reden na "Preprocess" geen gele punten te zien zijn, ga dan terug naar STAP2 en click op "Reset Graph to Initial State", om de grafe op te ruimen.

Best practice: gebruik vooral de "Auto optimize distance".  Na een run geeft hij volgende gegevens terug:

Length of (yellow) double streets (this/lower bound/est. best ever) 19.39 / 9.14 /19.22 km

De betekenis hiervan is:

•  9.14km = theoretische ondergrens van de minimale afstand (niet haalbaar in de praktijk)
• 19.22km = beste oplossing die ooit gevonden werd
• 19.39km = laatst gevonden oplossing

Gebruik "SNAPSHOT" om goeie oplossingen te bewaren, of bewaar regelmatig het project.

Na deze stap liggen alle straten vast, en ook alle straten die dubbel gelopen worden. In de volgende stap wordt de route bepaald, met startpunt en eventuele tussenpunten.

---

[Gemini translation]

---

This part consists of a number of simple steps, which do require some time. Sometimes it will seem as if the computer has frozen, but you can see in the console that this is not the case.

The basic idea is: every intersection with an odd number of streets, for example a "T", is the reason you have to walk a section back and forth.

Settings for this are:

• "Distance Algorithm": calculate a "distance matrix" with an estimated distance between all yellow points
• "Euclidian": calculate a fast estimate of the length of the yellow segments
•  "A* distance": calculate a more accurate length. Choose this if the network is not too large.
• "Iterations": number of iterations performed each time. Experiment with this depending on the speed of your computer; in principle, the algorithm stops searching after 25 seconds (this parameter is called endTime and can be adjusted via "SET/SaVe/LD").
• "Groupsize": the number of yellow points in a group for which the computer searches for a better solution. Do not set this too high. This parameter is not used in automatic optimization.
• "MCMC value": the algorithm looks for better solutions, but occasionally accepts worse solutions on a statistical basis to avoid getting stuck in local minima. A value of 1.05 means that solutions that are 5% worse can still be accepted.
• it can help to start this parameter at 1.08 and slowly lower it to 1
• set this to 1.00 for the final optimization

Things you can do:

• "Preprocess (uneven nodes and dead ends)": 
• finds dead-end streets, colors them orange, and doubles them (so they are no longer dead ends, but a loop)
• finds intersections with 3-5-7... streets and colors them yellow
• creates an initial proposal of streets that you have to walk back and forth, coloring them yellow
• "Auto optimize distance": try to organize the yellow streets so that they collectively have a minimum distance. Use the specified number of iterations and a group size of 2 to 5
• "Find Eulerian Path": calculate a route along all points

Important! If for some reason no yellow points are visible after "Preprocess", go back to STEP 2 and click "Reset Graph to Initial State" to clean up the graph.

Best practice: primarily use "Auto optimize distance".  After a run, it returns the following data:

Length of (yellow) double streets (this/lower bound/est. best ever) 19.39 / 9.14 /19.22 km

The meaning of this is:

•  9.14km = theoretical lower bound of the minimum distance (not reachable in practice)
• 19.22km = best solution ever found
• 19.39km = last solution found

Use "SNAPSHOT" to save good solutions, or save the project regularly.

After this step, all streets are fixed, including all streets that will be walked twice. In the next step, the route will be determined, including the starting point and any intermediate points.