Effective local search algorithms for high school timetabling problems

This paper addresses the high school timetabling problem. The problem consists in building weekly timetables for meetings between classes and teachers with the goal of minimizing violations of specific requirements. In the last decades, several mixed-integer programs have been proposed and tested for this family of problems. However, medium and large size instances are still not effectively solved by these programs using state-of-the-art solvers and the scientific community has given special attention to the devising of alternative soft computing algorithms. In this paper, we propose a soft computing approach based on Iterated Local Search and Variable Neighborhood Search metaheuristic frameworks. Our algorithms incorporate new neighborhood structures and local search routines to perform an effective search. We validated the proposed algorithms on variants of the problem using seven public instances and a new dataset with 34 real-world instances including large cases. The results demonstrate that the proposed algorithms outperform the state-of-the-art approaches in both cases, finding the best solutions in 38 out of the 41 tested instances.     

Variable Neighborhood Search strategies for the Order Batching Problem

The Order Batching Problem is an optimization problem belonging to the operational management aspect of a warehouse. It consists of grouping the orders received in a warehouse (each order is composed by a list of items to be collected) in a set of batches in such a way that the time needed to collect all the orders is minimized. Each batch has to be collected by a single picker without exceeding a capacity limit. In this paper we propose several strategies based on the Variable Neighborhood Search methodology to tackle the problem. Our approach outperforms, in terms of quality and computing time, previous attempts in the state of the art. These results are confirmed by non-parametric statistical tests.     

Reactive Search strategies using Reinforcement Learning,local search algorithms and Variable Neighborhood Search

Optimization techniques known as metaheuristics have been applied successfully to solve different problems, in which their development is characterized by the appropriate selection of parameters (values) for its execution. Where the adjustment of a parameter is required, this parameter will be tested until viable results are obtained. Normally, such adjustments are made by the developer deploying the metaheuristic. The quality of the results of a test instance [The term instance is used to refer to the assignment of values to the input variables of a problem.] will not be transferred to the instances that were not tested yet and its feedback may require a slow process of “trial and error” where the algorithm has to be adjusted for a specific application. Within this context of metaheuristics the Reactive Search emerged defending the integration of machine learning within heuristic searches for solving complex optimization problems. Based in the integration that the Reactive Search proposes between machine learning and metaheuristics, emerged the idea of putting Reinforcement Learning, more specifically the Q-learning algorithm with a reactive behavior, to select which local search is the most appropriate in a given time of a search, to succeed another local search that can not improve the current solution in the VNS metaheuristic. In this work we propose a reactive implementation using Reinforcement Learning for the self-tuning of the implemented algorithm, applied to the Symmetric Travelling Salesman Problem.     

Variable Neighborhood Search for a Dynamic Rich Vehicle Routing Problem with time windows

A Dynamic Rich Vehicle Routing Problem with Time Windows has been tackled as a real-world application, in which customers requests can be either known at the beginning of the planning horizon or dynamically revealed over the day. Several real constraints, such as heterogeneous fleet of vehicles, multiple and soft time windows and customers priorities, are taken into consideration. Using exact methods is not a suitable solution for this kind of problems, given the fact that the arrival of a new request has to be followed by a quick re-optimization phase to include it into the solution at hand. Therefore, we have proposed a metaheuristic procedure based on Variable Neighborhood Search to solve this particular problem. The computational experiments reported in this work indicate that the proposed method is feasible to solve this real-world problem and competitive with the best results from the literature. Finally, it is worth mentioning that the software developed in this work has been inserted into the fleet management system of a company in Spain.     

一种SAT邻域的快速搜索算法

用局部搜索算法求解SAT问题．通常都需要在较大的邻域中。寻找合适的邻解。如果对邻域中的每个邻解。都通过重新判断每个子句是否为可满足来得到其可满足的子句个数．则时间耗费较多。已经有一些经典的处理方法．例如通过修改邻域结构．来减小搜索空间。从另外一个角度来考虑搜索过程．根据当前解和邻解的内在关系．介绍一种SAT邻域的快速搜索算法。该算法能在不影响解质量的前提下．快速寻找合适的邻解．从而进一步提高局部搜索算法的求解速度。另外．该算法还提供用于提高解质量的信息。有助于研究新的局部搜索算法。     

Hybridizations of evolutionary algorithms with Large Neighborhood Search

Recent developments of evolutionary algorithms (EAs) for discrete optimization problems are often characterized by the hybridization of EAs with local search methods, in particular, with Large Neighborhood Search. In this survey, we consider some of the most promising directions of this kind of hybridization and provide examples in the context of well-known optimization problems. We distinguish different approaches by the algorithmic components in which they make use of Large Neighborhood Search: initialization, recombination and the local improvement stages of hybrid EAs.     

An Adaptive Large Neighborhood Search for an E-grocery Delivery Routing Problem

Online shopping has become ever more indispensable to many people with busy schedules who have a growing need for services ranging for a wide variety of goods, which include standard (or “staple”) goods as well as “premium” goods, i.e. goods such as organic food, specialty gifts, etc. that offer higher value to consumers and higher profit margins to retailers. In this paper, we introduce a new mathematical programming formulation and present an efficient solution approach for planning the delivery services of online groceries to fulfill this diverse consumer demand without incurring additional inventory costs. We refer to our proposed model as the E-grocery Delivery Routing Problem (EDRP) as it generically represents a family of problems that an online grocery is likely to face. The EDRP is based on a distribution network where premium goods are acquired from a set of external vendors at multiple locations in the supply network and delivered to customers in a single visit. To solve this problem, we develop an improved Adaptive Large Neighborhood Search (ALNS) heuristic by introducing new removal, insertion, and vendor selection/allocation mechanisms. We validate the performance of the proposed ALNS heuristic through an extensive computational study using both the well-known Vehicle Routing Problem with Time Windows instances of Solomon and a set of new benchmark instances generated for the EDRP. The results suggest that the proposed solution methodology is effective in obtaining high quality solutions fast.     

Multiple Phase Neighborhood Search-GRASP for the Capacitated Vehicle Routing Problem

Greedy Randomized Adaptive Search Procedure (GRASP) has been proved to be a very efficient algorithm for the solution of the Traveling Salesman Problem. Also, it has been proved that expanding the local search with the use of two or more different local search strategies helps the algorithm to avoid trapping in a local optimum. In this paper, a new modified version of GRASP, called Multiple Phase Neighborhood Search-GRASP (MPNS-GRASP), for the solution of the Vehicle Routing Problem is proposed. In this method, a stopping criterion based on Lagrangean Relaxation and Subgradient Optimization is utilized. In addition, a different way for expanding the neighborhood search is used based on a new strategy, the Circle Restricted Local Search Moves strategy. The algorithm was tested on two sets of benchmark instances and gave very satisfactory results. In both sets of instances the results have solution qualities with average values near to the optimum values and in a number of them the algorithm finds the optimum. The computational time of the algorithm is decreased significantly compared to other heuristic and metaheuristic algorithms due to the fact that the new strategy, the Expanding Neighborhood Search Strategy, is used.     

Variable and adaptive neighbourhood search algorithms for rail rapid transit timetabling problem

Supplying affordable and efficient transportation services to the users is one of the main tasks of the public transport systems. In this study, the objective is the minimization of the total and maximum waiting time of the passengers through optimization of the train timetables for urban rail transit systems. For this purpose, mixed-integer linear and non-linear programming models are developed which could solve the small to medium-sized test instances optimally. In order to tackle large instances, adaptive and variable neighbourhood search algorithms are designed based on different novel solution encoding schemes and decoding approaches. The effectiveness of the proposed models and solution methods are illustrated through the application to the Tehran intercity underground rail lines in IRAN. The outcomes demonstrate that the variable neighbourhood search algorithm outperforms the adaptive step-size neighbourhood search method in the different scenarios of the real case. Furthermore, the generated headway for the period of study result in a significant reduction in total waiting time of the passengers compared with the current baseline timetables.     

A hybrid particle swarm optimization based algorithm for high school timetabling problems

In this contribution a hybrid particle swarm optimization (PSO) based algorithm is applied to high school timetabling problems. The proposed PSO based algorithm is used for creating feasible and efficient high school timetables. In order to demonstrate the efficiency of the proposed PSO based algorithm, experiments with real-world input data coming from many different Greek high schools have been conducted. Computational results show that the proposed hybrid PSO based algorithm performs better than existing approaches applied to the same school timetabling input instances using the same evaluation criteria.     

Variable Neighborhood Search for extremal vertices : The AutoGraphiX-III system

More than fifteen years after the beginning of the development of AutoGraphiX (AGX), a third version of the software is made available. Since the program was rewritten from scratch, it was the opportunity to look forward and consider new avenues. From the user׳s point of view, the interface is completely changed, which allows the display of multiple information which was not possible in the previous versions. However, one of the main improvements is that it is designed to help researchers in the field of complex networks. In these days when increasing research is applied to complex networks (such as social networks), the use of quantities related to vertices, indicating the centrality (the importance of an actor in the network measured as a topological indicator) naturally leads researchers toward the mathematical study of these quantities. This new paradigm implies a complete change in the optimization algorithm that now natively handles multi objective optimization problems involving vertex-related measures.     

Hybrid Adaptive Large Neighborhood Search for the Optimal Statistic Median Problem

In this paper, the problem of maximizing the median of a convex combination of vectors having important applications in finance is considered. The objective function is a highly nonlinear, nondifferentiable function with many local minima and the problem was shown to be APX hard. We present two hybrid Large Neighborhood Search algorithms that are based on mixed-integer programs and include a time limit for their running times. We have tested the algorithms on three testbeds and showed their superiority compared to other state-of-the-art heuristics for the considered problem. Furthermore, we achieved a significant reduction in running time for large instances compared to solving it exactly while retaining high quality of the solutions returned.     

求解UCARPP问题的变邻域搜索算法

针对无向网络中带有收益值有容限的弧路径问题,提出一种变邻域搜索算法。生成需求边的有序列,以相同概率初始化每条边的方向,采用分割算法构造初始解,运用6种邻域结构进行广域搜索,使用局部搜索算法改进解,利用旋轮法选择邻域结构。实验结果表明,该算法能提高效率,避免早期陷入局部最优,稳定性较好。     

时空相关的混载校车路径问题邻域搜索

为节约混载校车路径问题求解过程中邻域解搜索的时间,引入时空距离和时空相关度概念,将邻域搜索空间限定在合理的范围内.该算法首先计算站点间的时空距离,再附加上简单约束的预判断,从而得到时空相关度矩阵.然后对于任意学生乘车站点,将其他可能与之直接相连的站点按照时空相关度排序,形成一个邻接列表.在邻域搜索过程中,通过限定邻接列表长度,仅尝试最终接受概率较大的一部分移动操作,以此缩小邻域搜索空间,从而提高算法效率.在国际标准案例上的测试结果表明,基于时空相关度的搜索策略能在基本不降低求解质量的情况下,平均节省50％以上的求解时间.     

结合变邻域搜索的竞争Hopfield神经网络解决最大分散度问题

提出一种结合变邻域搜索的离散竞争Hopfield神经网络,用于求解最大分散度问题。为了克服神经网络易陷入局部最小值的问题,将变邻域搜索的思想引入到离散竞争Hopfield神经网络中,一旦网络陷入局部最小值,变邻域搜索能帮助神经网络动态改变搜索邻域,从而跳出局部最小值去搜寻更优的解。最后,针对最大分散度问题的实验结果表明,提出的算法具有良好的性能。     

Variable neighborhood descent heuristic for solving reverse logistics multi-item dynamic lot-sizing problems

The multi-product dynamic lot sizing problem with product returns and recovery is an important problem that appears in reverse logistics and is known to be NP-hard. In this paper we propose an efficient variable neighborhood descent heuristic algorithm for solving this problem. Furthermore, we present a new benchmark set with the largest instances in the literature. The computational results demonstrate that our approach outperforms the state-of-the-art Gurobi optimizer.     

Solving the high school timetabling problem using a hybrid cat swarm optimization based algorithm

In this contribution we present the application of a hybrid cat swarm optimization (CSO) based algorithm for solving the school timetabling problem. This easy to use, efficient and fast algorithm is a hybrid variation of the classic CSO algorithm. Its efficiency and performance is demonstrated by conducting experiments with real-world input data. This data, collected from various high schools in Greece, has also been used as test instances by many other researchers in their publications. Results reveal that this hybrid CSO based algorithm, applied to the same school timetabling test instances using the same evaluation criteria, exhibits better performance in less computational time compared to the majority of other existing approaches, such as Genetic Algorithms (GAs), Evolutionary Algorithms (EAs), Simulated Annealing (SA), Particle Swarm Optimization (PSO) and Artificial Fish Swarm (AFS). The algorithm's main process constitutes a variation of the classic CSO algorithm, properly altered so as to be applied for solving the school timetabling problem. This process contains the main algorithmic differences of the proposed approach compared to other algorithms presented in the respective literature.     

A high performing metaheuristic for multi-objective flowshop scheduling problem

Genetic algorithm is a powerful procedure for finding an optimal or near optimal solution for the flowshop scheduling problem. This is a simple and efficient algorithm which is used for both single and multi-objective problems. It can easily be utilized for real life applications. The proposed algorithm makes use of the principle of Pareto solutions. It mines the Pareto archive to extract the most repetitive sequences, and constitutes artificial chromosome for generation of the next population. In order to guide the search direction, this approach coupled with variable neighborhood search. This algorithm is applied on the flowshop scheduling problem for minimizing makespan and total weighted tardiness. For the assessment of the algorithm, its performance is compared with the MOGLS [1]. The results of the experiments allow us to claim that the proposed algorithm has a considerable performance in this problem.     

Search based algorithms for test sequence generation in functional testing

ContextThe generation of dynamic test sequences from a formal specification, complementing traditional testing methods in order to find errors in the source code.ObjectiveIn this paper we extend one specific combinatorial test approach, the Classification Tree Method (CTM), with transition information to generate test sequences. Although we use CTM, this extension is also possible for any combinatorial testing method.MethodThe generation of minimal test sequences that fulfill the demanded coverage criteria is an NP-hard problem. Therefore, search-based approaches are required to find such (near) optimal test sequences.ResultsThe experimental analysis compares the search-based technique with a greedy algorithm on a set of 12 hierarchical concurrent models of programs extracted from the literature. Our proposed search-based approaches (GTSG and ACOts) are able to generate test sequences by finding the shortest valid path to achieve full class (state) and transition coverage.ConclusionThe extended classification tree is useful for generating of test sequences. Moreover, the experimental analysis reveals that our search-based approaches are better than the greedy deterministic approach, especially in the most complex instances. All presented algorithms are actually integrated into a professional tool for functional testing.