Abstrakt. Sequential Ordering Problem (SOP) är en version av Asymmetrisk Traveling Salesman Problem (ATSP) där företräde begränsningar på hörnen måste också iakttas. SOP har många verkliga tillämpningar och det har visat sig vara en stor utmaning (det finns SOP med 40-50 hörn som inte har lösts optimalt ännu med betydande beräkningsansträngning). Vi använder nya gren & bundna sökalgoritmer med lägre gränser som erhållits från homomorfa abstraktioner av det ursprungliga tillståndet utrymme. Vår metod är asymptotiskt optimal. I ett fall har det visat sig vara ett lösningsvärde som är optimalt för ett öppet problem, samtidigt som det också har matchat de mest kända lösningarna snabbt för många olösta problem från TSPLIB. Vår metod för att härleda lägre gränser är allmän och gäller även för andra varianter av begränsade ATSPs.
En liknande idé utnyttjades av REF, som anser en gren-och-bunden algoritm baserad på homomorfa abstraktioner av sökytan för den sekventiella beställning problem.
Solving the sequential ordering problem with automatically generated lower bounds
{'venue': 'Proceedings of Operations Research 2003', 'journal': None, 'mag_field_of_study': ['Mathematics']}