Reizende verkopersprobleem opgelost

Het handelsreizigersprobleem is het probleem om de kortste route te vinden die de buitendienstmedewerkers moeten nemen, gegeven een lijst met specifieke bestemmingen.

Een verkoper wil een paar locaties bezoeken om goederen te verkopen. Hij kent de namen van de gebieden en de afstanden tussen elk. Wat is de kortste route die de verkoper moet volgen, zodat hij elke locatie slechts één keer bezoekt voordat hij terugkeert naar het startpunt?

Circuit probleem

De TSP is een uitbreiding van het Hamiltoniaanse circuitprobleem. Het is een oud probleem in de informatica dat implicaties heeft voor de complexiteitstheorie en het P versus NP-probleem.

Het voertuig planningsprobleem en het reizende verkopersprobleem zijn beide generalisaties van TSP. In 1972 bewees Richard Karp dat het Hamilton-cyclusprobleem NP-compleet was, een klasse van combinatorische optimalisatieproblemen.

Dit betekent dat de TSP NP-hard was. En de complexiteit van het berekenen van de beste route zal facultatief toenemen naarmate er meer bestemmingen aan het probleem worden toegevoegd. Er kunnen bijvoorbeeld drie mogelijke routes zijn in vier steden. Maar er kunnen 360 mogelijke routes zijn in zes steden.

Pad berekenen

Dit komt omdat wetenschappers niet alleen het meest efficiënte pad berekenen, maar ook het pad dat werkt. Deze berekening gebruikt de brute-force-benadering om het probleem op te lossen door elke mogelijkheid uit te zoeken en vervolgens de beste te kiezen. Met andere woorden, zoek naar elk uniek pad dat de verkoper zou kunnen nemen.

Hoewel de rekenproblemen toenemen met elke stad die aan het reisschema wordt toegevoegd, hebben computerwetenschappers sinds het begin van de jaren 90 de optimale oplossing voor dit probleem voor duizenden steden berekend.

Veel dorpen en steden kunnen bijvoorbeeld deel uitmaken van het leveringsgebied van een grote logistieke dienstverlener. Het uitzoeken van de kortste route tussen alle stops die het voertuig dagelijks moet maken, zou veel tijd en geld besparen.

Waarom is het handelsreizigerprobleem zo moeilijk?

In theorie kan de TSP worden opgelost door elke retourroute te controleren om de kortste te vinden. Naarmate het aantal steden groeit, overtreft het overeenkomstige aantal retourvluchten echter de mogelijkheden van de snelste computers.

In de begintijd van computers hoopten computerwetenschappers dat iemand binnen een redelijke tijd een verbeterd algoritme zou ontwikkelen om het probleem op te lossen.

Hoewel wetenschappers vooruitgang hebben geboekt met specifieke scenario’s, was er geen efficiënte probleemoplosser voor handelsreizigers. Een one-size-fits-all algoritme is misschien niet eens mogelijk.

Route optimalisatie

Dat is een echte uitdaging en hier komt route-optimalisatie. Bij routeoptimalisatie draait alles om het vinden van de snelste, kortste en meest brandstofefficiënte route voor een reeks tussenstops.

Hoe het probleem van de handelsreiziger op te lossen met een routeplanner? Naarmate jouw team groeit, wordt routeplanning onvermijdelijk te complex om te beheren met pen en papier of standaardtools zoals Google Maps of Waze.

Onvoorziene situaties zoals verkeersopstoppingen maken het een uitdaging om op tijd te verschijnen. Een evenwichtige verdeling van de werklast is moeilijk als je planningen handmatig probeert te optimaliseren. Je loopt ook het risico jouw operationele kosten te verhogen. Vaak in de vorm van verspilde brandstof en salarissen door langere rijtijd.

Bovendien zullen uw klanten geïrriteerd raken als jouw verkopers te laat komen opdagen of jouw chauffeurs niet op tijd leveren.

Transport planner

Een transport planner is de perfecte oplossing voor het probleem van handelsreizigers.

Een betrouwbare routeplanner zal de rijtijd en het brandstofverbruik verminderen door binnen enkele seconden de meest efficiënte route voor jouw team te vinden.