(traveling salesman problem) – ett klassiskt matematiskt problem som kan verka enkelt, men som kan vara mycket besvärligt att lösa. – En handelsresande ska besöka ett antal städer. Avstånden mellan städerna är kända. Vilken är då den kortaste resväg han kan välja om han ska besöka varje stad och återvända till utgångspunkten? (Det finns varianter, beroende på om man får resa genom varje stad fler än en gång, eller bara en gång.) – I vissa fall är lösningen uppenbar, till exempel om städerna ligger i rät linje. Men en metod för lösning måste kunna tillämpas på alla tänkbara grupper av städer. – Redan när problemet gäller tio städer finns det över 3,6 miljoner tänkbara rutter (och det är bortsett från att man kan passera samma stad flera gånger). Ökar man antalet städer ytterligare blir problemet snart ohanterligt. Det tillhör därför den grupp av matematiska problem som kallas för NP‑fullständiga. – Det gäller också att bevisa att man verkligen har funnit den kortaste vägen. Och det finns ingen känd metod för att bevisa att man verkligen har funnit den kortaste vägen, förutom att gå igenom alla tänkbara lösningar och jämföra dem. Det är det som gör att handelsresandeproblemet räknas som NP‑fullständigt. – Det mest omfattande handelsresandeproblem som hittills har lösts gäller 24 978 orter i Sverige: kortaste vägen om man vill besöka alla är 72 500 kilometer. – Problemet har praktisk tillämpning, till exempel inom trafikplanering och när man konstruerar elektroniska kretsar. Men i praktisk verksamhet brukar man inte behöva bevisa att man har hittat den absolut kortaste vägen: det räcker med en lösning som är bättre än alla tidigare. (Det finns fusklösningar som ofta ger tillräckligt bra, men inte perfekt, resultat. En enkel fusklösning är att alltid resa till närmaste obesökta stad på listan.) – En nära släkting till handelsresandeproblemet är Hamiltons problem. – Se Wikipedia.
[matematik] [transport och logistik] [ändrad 28 februari 2022]