Generaliserat resandeförsäljarproblem

De enklaste heuristiska metoderna för att lösa det generaliserade resandeförsäljarproblemet inkluderar den giriga algoritmen , som vid varje steg väljer kanten av lägsta kostnad från uppsättningen av kanter som inte bryter mot lösningens korrekthet, samt den mer effektiva Nearest Neighbor metod, som utgår från en godtycklig vertex och vid varje steg läggs till lösningen, den vertex som ligger närmast den senast läggs till. Det finns även andra heuristiker som är modifieringar av välkända heuristiker för vanliga resandeförsäljarproblem.

I synnerhet används ofta följande typer av lokal sökning :

• 2-opt , som används flitigt i många kombinatoriska optimeringsproblem, reducerar till att ta bort två kanter från turen och infoga två nya kanter som inte bryter mot korrektheten av lösningen (i fallet med 2-opt, kanterna som ska infogas är unikt bestämda). En tur anses vara ett lokalt minimum om det inte finns några kanter i den vars utbyte skulle leda till en förbättring av lösningen. Sålunda är både grannskapets storlek och heuristikens komplexitet , där  är antalet kluster.
• 3-opt liknar 2-opt, dock tas inte två, utan tre kanter bort på varje. I fallet med 3 alternativ finns det åtta icke-triviala sätt att infoga nya kanter för att återställa turens korrekthet. Ett av dessa sätt bevarar riktningen för vart och ett av turfragmenten, vilket är en viktig egenskap för asymmetriska problem. Storleken på grannskapet och komplexiteten i heuristiken är .
• Det finns naturliga modifieringar av 2-opt och 3-opt algoritmer, som dessutom inkluderar sökningen efter optimala hörn inom föränderliga kluster.
• "Infogning" är ett specialfall av 3-opt. Vid varje iteration tar algoritmen bort vertexet och försöker hitta en mer gynnsam position för den. Algoritmens komplexitet är . En modifiering används i stor utsträckning som beaktar infogningen inte bara av en avlägsen vertex, utan också av vilken annan vertex som helst i motsvarande kluster.
• Klusteroptimering är en lokal sökning som är specifik för det generaliserade resandeförsäljarproblemet. Kärnan i algoritmen är att hitta den kortaste vägen genom en given sekvens av kluster. Med andra ord inkluderar algoritmens grannskap alla turer som inte skiljer sig från originalet med mer än valet av hörn inom vart och ett av klustren. Storleken på det undersökta området är:

var  är klustret numrerat . Genom att tillämpa sökningen efter den kortaste vägen i en speciellt konstruerad graf, hittar algoritmen ett lokalt minimum för , där . Klusteroptimering tillhör således klassen av lokala sökningar med en mycket stor stadsdel , det vill säga den utforskar en exponentiell grannskap i polynomtid.