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.

In this paper, we analyze the complexity of the gear placement problem (GPP). In the GPP, we are given a rectangular plane, called a gearbox, on which a torque generator source and a set of gears, called target gears, are placed. The task is to find a placement of a set of gears called sub-gears, to connect every target gear to the torque generator source so that every target gear rotates in a given direction. The objective is to minimize the number of sub-gears to be used. We prove that the GPP is NP-hard by giving a reduction from the Hamiltonian path problem on 3-regular planar graphs, which is known to be NP-complete, to the GPP. We also present an upper bound for the number of sub-gears to be placed.

We address the selective pickup and delivery problem with time-window constraints, which is a problem of finding vehicle routes that pick up commodities at stores and deliver them to customers so as to minimize the total distance of the routes under capacity and time-window constraints. In this paper, to design a local search method for this problem, we consider the following: Given the order of customers in a route, we determine the pickup stores and optimal times of visiting at customers so that the total distance is minimized. This is called the optimal pickup point problem and is a subproblem of the selective pickup and delivery problem with time-window constraints. We show that the optimal pickup point problem is NP-hard in general, and then we propose dynamic programmingmethods, which can obtain upper and lower bounds in linear time, and optimal solution in pseudo-polynomial time.

The periodic vehicle routing problem (PVRP) is a generalization of the vehicle routing problem (VRP) to a planning period of more than one day. A fleet of vehicles needs to deliver goods periodically to each customer so that the delivery dates meet the request of the customer. This paper introduces a new model of PVRP, the periodic vehicle routing problem with flexible delivery dates, which covers a wider range of applications and is able to answer more diverse customer requirements. We propose an algorithm based on iterated local search (ILS), which is a metaheuristic approach that involves an iterative application of a local search algorithm and the use of perturbation as a diversification mechanism. Computational results show that our proposed method performed competitively in solving the standard PVRP. Moreover, we confirm that our new model can reduce the cost for more general instances.

The overall planning process undertaken by a bus company is traditionally composed of five sub-processes: timetabling, vehicle scheduling, maintenance scheduling, crew scheduling, and crew rostering. Solving the full optimization problem is believed to be computationally intractable, and therefore in practice the five sub-processes are usually optimized in sequence. In this paper, we present a model that integrates the problems of vehicle scheduling and maintenance scheduling. The objective is to minimize the differences in mileage between buses, the total distance traveled, and the daily differences in the number of maintenance tasks. We propose a heuristic algorithm using the framework of greedy randomized adaptive search procedure (GRASP), and we improve the neighborhood search procedure by using an ordered list of possible trips. We compare the neighborhood search procedure with and without this mechanism and show that the ordered list reduces the number of neighbors to be checked by more than 95%, and it reduces the time to obtain solutions of the same or better quality by an average of 70%. Through computational experiments on instances generated from real-world data, we show that the proposed algorithm finds solutions that are as good as or better than those obtained by a commercial solver in less than 5% of the time required by the latter.

The rectilinear block packing problem is a problem of packing a set of rectilinear blocks into a larger rectangular container with fixed width and unrestricted height. A rectilinear block is a polygonal block whose interior angles are either 90◦ or 270◦. The objective is to pack all the blocks into the container so as to minimize the height of the container. This problem is among classical combinatorial optimization problems and is known to be NP-hard. In this paper, we propose two exact algorithms for the rectilinear block packing problem: one is based on two IP problems and the other is based on a new solution representation. The basic idea of our algorithms is that we iteratively compute lower and upper bounds on the optimal value until the lower bound on the value of an optimal solution for the current search space becomes larger than or equal to the best upper bound found during the search by then, or the search space becomes empty, which means that an optimal solution of this problem has been found. The computational results show that both algorithms obtain five exact and one heuristic solutions for six instances. The algorithm based on a new solution representation improves the running time of the algorithm based on two IP problems.

The management of the automobile industry has changed recently because of the influence of the financial crisis and the industrial boom in developing countries such as Brazil, Russia, India, and China (BRICs). In this paper, we consider a global automobile-production optimization problem (GAPOP), which we model as a mixed integer programming (MIP) problem. The GAPOP determines global production bases and transportation plans to minimize the total cost of production, transportation, and facilities. It is a unified model that contains the facility location, production planning and transportation problems. We analyze the model for instances generated from real-world data with up to 20 production bases and 133 importing countries for the 18 years from 1997 to 2014. The computational results show that near-optimal solutions to our model are close to the present real-world situation. We also analyze our model with various parameter settings and observe from the results that, at each production base, changes in the number of production lines are affected mainly by labor and material costs. In addition, the proportion of each automobile type when allocating production is influenced by the material costs of all automobile types and the demands of nearby importing countries. Our model is expected to be of use to the automobile industry for making forecasts.

In this paper, we consider the crew pairing problem in airline scheduling that calls for assigning crew members in order to cover all flights with the minimum total person-days under the constraints that the schedule of each crew member does not violate given constraints on the total working time, flying time, and the number of landings. In practical applications, it is difficult to create an efficient schedule satisfying all the constraints. We formulate the problem as a set covering problem and apply an LP-based column generation approach to generate a candidate set of schedules. We propose a branch-and-bound method based upon a resource constrained dynamic programming for the column generation procedure. Computational results are given for a number of large-scale instances with up to 10,000 flights.

In this paper, we propose a heuristic algorithm for a container loading problem for logistic platforms, which is the problem for the Challenge Renault/ESICUP 2015. The three-dimensional container loading problem involves packing a set of cuboid items into bins so as to minimize the total volume used. In this paper, we propose an effective approach to solve this problem based on a greedy strategy. We first generate high-quality stacks that consist of some items and then pack these stacks on the floor of bins, considering the resulting problem as a two-dimensional bin packing problem. The proposed algorithm is tested on a series of instances provided for the challenge. The computational results show that the proposed algorithm performs well on these instances.

A real-time system receives input from the outside, processes it through a sequence of tasks and outputs the result to the outside. Each process corresponds to a sequence of tasks called path and the time from input to output is called response time. For each path, a response time must always be within a specified time. Our objective is to schedule tasks so that the time constraints for all paths are satisfied. In this paper, we adopt a scheduling method based on a scheduling table, which specifies a schedule of a finite time period and is used repeatedly to define the schedule of longer time periods. In order to calculate response times for a schedule efficiently, we introduce a concept called active path. In our algorithm, a scheduling table is searched by a local search. The neighborhood search is accelerated by using precedence relations that are introduced to preserve active paths of a scheduling table. Finally, we report computational results for sample instances from a company.

We consider a real-time system that requires the time stimuli to the system are processed through sequences of tasks to be within specified upper bounds, where the set of tasks can be the mixture of preemptive and non-preemptive tasks, and we propose an algorithm to design a static priority scheduling for the system. In the algorithm, local search is used to determine priorities of tasks, and whenever the priorities are fixed, the periods of tasks are determined. This subproblem can be described as a mathematical programming formulation and is solved via linear programming techniques. Finally, we report computational results for sample instances from a company.