Ställ in TSP-problem
I kombinatorisk optimering är uppsättningen TSP , även känd som den generaliserade TSP , grupp TSP , One-of-a-Set TSP , Multiple Choice TSP eller Covering Salesman Problem , en generalisering av resandesäljarproblemet ( TSP), varvid det är krävs för att hitta en kortaste rundtur i en graf som besöker alla specificerade delmängder av en grafs hörn. Delmängderna av hörn måste vara disjunkta, eftersom fallet med överlappande delmängder kan reduceras till fallet med disjunkta. Den vanliga TSP är ett specialfall av den uppsatta TSP när alla delmängder som ska besökas är singlar . Därför är den inställda TSP också NP-hård .
Det finns en transformation för en instans av den inställda TSP till en instans av den asymmetriska standard-TSP. Tanken är att koppla varje delmängd till en riktad cykel med kanter som väger noll, och ärva de utgående kanterna från den ursprungliga grafen som skiftar en vertex bakåt längs denna cykel. Försäljaren, när han besöker ett hörn v i någon delmängd, går gratis runt cykeln och lämnar den från hörnet som föregår v med en utgående kant som motsvarar en utgående kant av v i den ursprungliga grafen.
Set TSP har många intressanta tillämpningar i flera vägplaneringsproblem. Till exempel kan ett tvåfordonssamverkande routingproblem omvandlas till en uppsättning TSP, snäva nedre gränser till Dubins TSP och generaliserade Dubins vägproblem kan beräknas genom att lösa en Set TSP.
Illustration från styckningsstockproblemet
endimensionell skärmaterial som tillämpas inom pappers-/plastfilmsindustrin innebär att man skär jumborullar till mindre. Detta görs genom att generera skärmönster vanligtvis för att minimera avfallet. När en sådan lösning väl har tagits fram kan man försöka minimera knivförändringarna genom att sekvensera om mönstren (upp och ner i figuren) eller flytta rullar åt vänster eller höger inom varje mönster. Dessa rörelser påverkar inte slöseriet med lösningen.
I ovanstående figur är mönster (bredd högst 198) rader; knivbyten indikeras av de små vita cirklarna; till exempel har mönster 2-3-4 en rulle i storlek 42,5 till vänster - motsvarande kniv behöver inte röra sig. Varje mönster representerar en TSP-uppsättning, vars ena permutationer måste besökas. Till exempel, för det sista mönstret, som innehåller två upprepade storlekar (två gånger vardera), finns det 5! / (2! × 2!) = 30 permutationer. Antalet möjliga lösningar på ovanstående instans är 12! × (5!) 6 × (6!) 4 × (7!) 2 / ((2!) 9 × (3!) 2 ) ≈ 5,3 × 10 35 . Ovanstående lösning innehåller 39 knivbyten och har erhållits genom en heuristik; det är inte känt om detta är optimalt. Transformationer till den vanliga TSP, som beskrivs i, skulle involvera en TSP med 5 520 noder.
Se även
- Fagnanos problem med att hitta den kortaste turen som besöker alla tre sidorna av en triangel