Wat is het handelsreizigersprobleem?
Een chauffeur moet 20 adressen beleveren en dan terug naar het depot. In welke volgorde om de minste kilometers te rijden? Die vraag heet het handelsreizigersprobleem (TSP, Travelling Salesman Problem). Zodra u meerdere voertuigen, laadcapaciteiten en uren toevoegt, wordt het het vehicle routing problem (VRP) — de wiskundige kern van elke dispatchsoftware.
Waarom het moeilijker is dan het lijkt
Het VRP is NP-moeilijk: het herleidt tot het handelsreizigersprobleem, waarvoor op grote schaal geen snel exact algoritme bekend is. De reden is combinatorisch. Voor tien stops bestaan al honderdduizenden volgordes; voor twintig stops gaat het aantal combinaties elk begrip te boven. Alles uitproberen — « brute kracht » — wordt onmogelijk voorbij een handvol punten, zelfs voor een computer.
Daarom kan een menselijke planner, hoe ervaren ook, 40 leveringen met tijdvensters niet uit het hoofd optimaliseren. Het brein vindt een « behoorlijke » oplossing, zelden de beste.
De oplossing: heuristieken
Omdat het optimum niet gegarandeerd kan worden, zoeken we snel een zeer goede oplossing. Dat is de rol van heuristieken. De bekendste, 2-opt, werd in 1958 voorgesteld door Croes: ze neemt een route, verwijdert twee segmenten en verbindt ze anders; daalt de totale afstand, dan blijft de wijziging behouden, en zo verder tot er niets meer te verbeteren valt. Gecombineerd met andere technieken levert ze in seconden routes op die het optimum benaderen.
De beperkingen van de echte wereld
Een goede motor minimaliseert niet enkel de afstand. Hij houdt rekening met voertuigcapaciteit, leveringsvensters, servicetijd per stop, vereiste vaardigheden en steeds vaker realtimeverkeer. Elke bijkomende beperking verzwaart de berekening — vandaar het nut van een specifieke tool in plaats van een kaart en een spreadsheet.
Wat het concreet verandert
De inzet is financieel. Volgens sectoranalyses van de fleetmanagementmarkt leveren routeoptimalisatie, minder stationair draaien en rijgedragmonitoring brandstofbesparingen van zo'n 10 tot 30 % op. Voor een kmo met enkele voertuigen rationaliseert u zo een volledige kostenpost.
- TSP/VRP is NP-moeilijk: geen gegarandeerd optimum op grote schaal
- Brute kracht wordt onmogelijk vanaf enkele tientallen stops
- 2-opt (Croes, 1958) geeft uitstekende routes in seconden
- Voordeel: 10 tot 30 % brandstofbesparing volgens sectoranalyses
Laat het algoritme uw ritten berekenen. Probeer dropfleet 14 dagen gratis — zonder bankkaart, klaar in 5 minuten.
Bronnen
Dit artikel is gebaseerd op verifieerbare openbare bronnen: