Solving the Sequential Ordering Problem with Automatically Generated Lower Bounds

• Author(s) / Creator(s)

  • Hernadvolgyi, Istvan

• Technical report TR03-16. The Sequential Ordering Problem (SOP) is a version of the Asymmetric Traveling Salesman Problem (ATSP) where precedence constraints on the vertices must be observed. The SOP has many real life applications and it has proved to be a challenge as there are SOPs of order 40-50 vertices which have not yet been solved optimally with significant computational effort. We use a novel branch&bound search algorithm with lower bounds obtained from homomorphic abstractions of the original state space. Our method is asymptotically optimal. In one instance, it has proved a solution value to be optimal for an open problem while it also has matched best known solutions quickly for many unsolved problems from the TSPLIB. Our method of deriving lower bounds is general and applies to other variants of constrained ATSPs as well. | TRID-ID TR03-16

• Date created

  2003

• Subjects / Keywords

  • Asymmetric Traveling Salesman Problem
  • Sequential Ordering Problem

• Type of Item

  Report

• DOI

  https://doi.org/10.7939/R3XP6V500

• License

  Attribution 3.0 International