2-opt, clustering, insertie: optimalisatieheuristieken ontcijferd

Waarom heuristieken?

De perfecte rit berekenen is een NP-moeilijk probleem: voorbij enkele tientallen stops kan geen computer alle combinaties testen. We zien dus af van het gegarandeerde optimum en mikken op een uitstekende, snel verkregen oplossing. Precies dat doen heuristieken. Drie families vullen elkaar aan.

1. Groeperen (clustering)

Voor we iets ordenen, verdelen we de adressen in coherente geografische clusters. Eén voertuig = één zone. Deze stap vermijdt de duurste fout: een chauffeur door de stad sturen voor één geïsoleerde stop. Clustering berekent niet de volgorde, maar bepaalt de perimeter van elke rit.

2. Lokale verbetering: 2-opt

Zodra een rit gebouwd is, verbeteren we ze. De 2-opt-methode, in 1958 voorgesteld door Croes, is de bekendste: ze verwijdert twee segmenten en verbindt ze omgekeerd. Daalt de totale afstand, dan houden we het; zo niet, ongedaan maken. Duizenden keren herhaald in een fractie van een seconde « ontwart » dit de kruisingen en streeft het naar een vloeiende rit. Een klassieker, juist omdat hij eenvoudig en bijzonder doeltreffend is.

3. Goedkoopste insertie

Hoe voeg je een nieuwe stop toe aan een al berekende rit — bijvoorbeeld een dringende bestelling die in de loop van de dag binnenkomt? De insertieheuristiek test elke mogelijke positie en kiest die welke de minste kilometers toevoegt. Zo vang je het onvoorziene op zonder alles te herberekenen.

Hoe ze samenwerken

Een goede motor schakelt deze logica's aaneen: clustering om te verdelen, initiële opbouw, dan 2-opt om bij te schaven, en insertie voor toevoegingen op het laatste moment. Alles onder reële beperkingen (capaciteit, tijdvensters, vaardigheden). De gebruiker ziet enkel een knop « optimaliseren » en de kilometerwinst voor/na.

Kant-en-klare optimalisatie, zonder doctoraat wiskunde. Probeer dropfleet 14 dagen gratis — zonder bankkaart, klaar in 5 minuten.