Search

Given a directed graph with n vertices, m edges and costs on the edges, the linear ordering problem (LOP) consists of finding a permutation of the vertices so that the total cost of the reverse edges is minimized, where an edge is called a reverse edge if its head vertex is at a position before the tail in the permutation. Known as an NP-hard problem, the LOP has a number of real-world applications such as the analysis of data called industry transaction table or input-output matrix (I/O table) in the field of economy. In this paper, we propose an algorithm based on tabu search for the LOP. We generalize an algorithm called TREE, which was proposed to search for a best solution in the neighborhood efficiently, so that the new algorithm can be incorporated in the tabu search algorithm and can search for a non-tabu best solution in the neighborhood efficiently. Our algorithm also features an adaptive control mechanism of the tabu tenure by using a cycling-detection mechanism based on a probabilistic analysis. Finally, we compare the experimental results of the proposed algorithm with those of an existing iterated local search algorithm (ILS). The proposed algorithm obtained better results than the ILS for many instances.

Round­robin tournaments are widely used in sports leagues such as football and baseball leagues. The round­robin tournament scheduling problem is one of the most well­known problems in sports scheduling. When creating a schedule for a round­robin tournament, various factors are considered such as travel distance of teams and the number of breaks. Among such factors, the carry­over effect is often considered to evaluate a schedule from the viewpoint of fairness. In this paper, we propose a metaheuristic algorithm for the problem of minimizing the carry-over effect value. For a complete graph whose edges describe all possible matches in a round­robin tournament, we consider a rainbow perfect matching, which we call a base matching, to describe a round of a schedule. By using the circle method, a round­robin tournament schedule can be generated from any base matching. Then we design a metaheuristic algorithm based on iterated local search to search for a “good” base matching, that is, one that generates a round­robin tournament schedule with a low carry­over effect value. We confirmed through computational experiments that our proposed algorithm obtained solutions with carry­over effect values equal to or lower than the best­known values for 15 out of the 17 tested instances with up to 40 teams. In addition, we updated the best­known records for 2 instances.