Wat is het handelsreizigersprobleem?
Het handelsreizigersprobleem zoekt de kortste route langs een reeks adressen. Het is de basis van routeplanning, maar zelf nog maar een klein deel ervan.
Het handelsreizigersprobleem, in het Engels traveling salesman problem of TSP, is de wiskundige vraag: wat is de kortste route die alle adressen precies één keer bezoekt en terugkomt bij het begin? Het klinkt eenvoudig, maar het aantal mogelijke volgordes groeit zo snel dat alles uitproberen al bij een paar tientallen adressen ondoenlijk is.
Voor één wagen met een lijst stops is het TSP precies de vraag die een routeplanner oplost. Zodra er meerdere wagens zijn, met capaciteit, venstertijden en pauzes, wordt het het Vehicle Routing Problem.
In de praktijk is de volgorde binnen een rit zelden het grootste probleem. De grootste winst zit in de verdeling van stops over de wagens.
Ook handig om te weten
- VRPHet Vehicle Routing Problem is het wiskundige vraagstuk achter routeplanning: stops zo over wagens verdelen dat de totale kosten zo laag mogelijk zijn.
- RouteplanningRouteplanning is het indelen van stops in ritten en het bepalen van de volgorde, rekening houdend met wagens, vensters en capaciteit.
- VenstertijdEen venstertijd is de periode waarin een klant levering accepteert, bijvoorbeeld tussen 6.00 en 9.00 uur. Buiten het venster mag je niet lossen.