An inexact algorithm for the sequential ordering problem

Given the directed G = (N, A) and the penalty matrix C, the Sequential Ordering Problem (hereafter, SOP) consists of finding the permutation of the nodes from the set N, such that it minimizes a C-based function and does not violate the precedence relationships given by the set A. Strong sufficient conditions for the infeasibility of a SOP's instance are embedded in a procedure for the SOP's pre-processing. Note that it is one of the key steps in any algorithm that attempts to solve SOP. By dropping the constraints related to the precedence relationships, SOP can be converted in the classical Asymmetric Traveling Salesman Problem (hereafter, ASTP). The algorithm obtains (hopefully) satisfactory solutions by modifying the optimal solution to the related Assignment Problem (hereafter, AP) if it is not a Feasible Sequential Ordering (hereafter, FSO). The new solution ‘patches’ the subtours (if any) giving preference to the patches with zero reduced cost in the linking arcs. The AP-based lower bound on the optimal solution to ATSP is tightened by using some of the procedures given in 1]. In any case, a local search for improving the initial FSO is performed; it uses 3- and 4-changed based procedures. Computational results on a broad set of cases are reported.