We consider the university course timetabling problem, which is one of the most studied problems in educational timetabling. In particular, we focus our attention on the formulation known as the curriculum-based course timetabling problem, which has been tackled by many researchers and for which there are many available benchmarks. The contribution of this paper is twofold. First, we propose an effective and robust single-stage simulated annealing method for solving the problem. Secondly, we design and apply an extensive and statistically-principled methodology for the parameter tuning procedure. The outcome of this analysis is a methodology for modeling the relationship between search method parameters and instance features that allows us to set the parameters for unseen instances on the basis of a simple inspection of the instance itself. Using this methodology, our algorithm, despite its apparent simplicity, has been able to achieve high quality results on a set of popular benchmarks. A final contribution of the paper is a novel set of real-world instances, which could be used as a benchmark for future comparison.
The proposed by @cite_1 follows a three stage scheme: in the initialization phase a feasible timetable is built using a fast heuristic; then the intensification and diversification phases are alternated through an adaptive tabu search in order to reduce the violations of soft constraints.
@cite_1
2073634948 1529628103 2161271108 1499047025
This paper presents an Adaptive Tabu Search algorithm (denoted by ATS) for solving a problem of curriculum-based course timetabling. The proposed algorithm follows a general framework composed of three phases: initialization, intensification and diversification. The initialization phase constructs a feasible initial timetable using a fast greedy heuristic. Then an adaptively combined intensification and diversification phase is used to reduce the number of soft constraint violations while maintaining the satisfaction of hard constraints. The proposed ATS algorithm integrates several distinguished features such as an original double Kempe chains neighborhood structure, a penalty-guided perturbation operator and an adaptive search mechanism. Computational results show the high effectiveness of the proposed ATS algorithm, compared with five reference algorithms as well as the current best known results. This paper also shows an analysis to explain which are the essential ingredients of the ATS algorithm. A new heuristic procedure for the transportation problem with exclusionary side constraints is developed and implemented. Tabu search, a meta-heuristic method, is used to guide the search to follow a path selectively to prevent from being trapped at local optimal solutions in order to find a global optimal or near global optimal solution. The simplex method on a graph is employed to lead the search from one solution to an adjacent solution in order to take advantage of the underlying network structure of the problem. In the procedure, net changes in cost and in infeasibility are used to measure the attractiveness of a move, and strategic oscillation is used to implement the intensification and diversification functions. A computational experiment was conducted to test the performance of the heuristic procedure and substantial computational results are reported. These results show that the new heuristic procedure finds very good quality solutions and outperforms an existing heuristic procedure in terms of both solution quality and CPU time. A novel concept for a decentralized adaptive traffic signal control in urban networks using in future available vehicle to infratructure (V2I) communication data is presented. The phase-based strategy takes advantage of the improved detection data and optimizes each time interval of 5 seconds the phase sequence in order to reduce the total queue length within a forecast horizon of 20 seconds. For optimization the methods of dynamic programming and complete enumeration are used. The methods are embedded in the simulation environment of the microscopic traffic simulator AIMSUN NG. The market penetration level is the critical factor that impacts the quality of the new signal control. Hence, various penetration levels are modelled. For reference TRANSYT-7F is used. This paper introduces a three-phase hybrid heuristic for a large-scale energy management and maintenance scheduling problem. The problem is to schedule maintenance periods and refueling amounts for nuclear power plants with a time horizon of up to five years, and handling a number of scenarios for future demand and prices. The goal is to minimize the expected total production cost. The first phase of the heuristic solves a constraint programming model of a simplified version of the problem, the second performs a local search, and the third handles overproduction in a greedy fashion. This work was initiated in the context of the ROADEF EURO Challenge 2010. In the concluding phase of the competition, our team ranked second in the junior category and sixth overall. After correcting a small implementation bug in the program that was submitted for final evaluation, our solver ranks first in the overall results from the competition.