1,721,021 research outputs found
Multi-Neighborhood Simulated Annealing for the Capacitated Dispersion Problem
Full text linkWe propose a novel Multi-Neighborhood Simulated Annealing approach to address the Capacitated Dispersion Problem. It makes use of three neighborhoods, adapted from similar proposals from the literature. Our search method, properly engineered and tuned, is able to consistently improve the state-of-the-art methods on almost all instances from public benchmarks. In addition, we highlight the limitations of the current datasets and we propose a new, more challenging one, obtained by sampling data from real maps and population density. Finally, we propose two compact mathematical models that obtain good bounds on small/medium size instances as well as, with long runs, on large ones
Local Search for Integrated Predictive Maintenance and Scheduling in Flow-Shop
No full textWe address the Permutation Flow-Shop Scheduling Problem with Predictive Maintenance presented by Varnier and Zerhouni (2012), that consists in finding the integrated schedule for production and maintenance tasks such that the total production time and the advance of maintenance services are minimized. Predictive maintenance services are scheduled based on a prognostics system that is able to provide the remaining useful life of a machine. To solve this problem, we propose a local search method with neighborhoods specifically tailored for maintenance interventions. Computational experiments performed on generated benchmarks demonstrate the effectiveness and scalability of our method with respect to an exact technique based on the mathematical model proposed by Varnier and Zerhouni (2012)
Multi-neighbourhood simulated annealing for the ITC-2007 capacitated examination timetabling problem
No full textWe propose a multi-neighbourhood simulated annealing algorithm for the ITC-2007 version of the capacitated examination timetabling problem. The proposed solver is based on a combination of existing as well as newly proposed neighbourhoods that better exploit the disconnected structure of the underlying conflict graph and that explicitly deal with the assignment of exams to rooms. We use a principled tuning procedure to determine the parameters of the algorithm and assess the contribution of the various neighbourhoods by means of an ablation analysis. The resulting algorithm is able to compete with existing state-of-the-art solvers and finds several new best solutions for a variety of well-known problem instances
Correction to: Solving a home energy management problem by Simulated Annealing (Optimization Letters, (2020), 10.1007/s11590-020-01545-8)
No full textSolving a home energy management problem by Simulated Annealing
Simulated Annealing for the Home Healthcare Routing and Scheduling Problem
No full textHome healthcare services are carried out by trained caregivers who visit the patient’s home, perform their service operations that depend on the patient’s need (e.g., medical care or just instrumental activities of daily living), and then move to the next patient. We consider the home healthcare scheduling and routing problem, in the formulation proposed by Mankowska et al. (2014), which includes synchronization among services and time windows for patients. For this problem, we propose a local search approach based on a novel neighborhood operator and guided by the Simulated Annealing metaheuristic. We show that our approach, properly tuned in a statistically-principled way, is able to outperform state-of-the-art methods on most of the original instances made available by Mankowska et al
Local search approaches for the test laboratory scheduling problem with variable task grouping
Full text linkThe Test Laboratory Scheduling Problem (TLSP) is a real-world scheduling problem that extends the well-known Resource-Constrained Project Scheduling Problem (RCPSP) by several new constraints. Most importantly, the jobs have to be assembled out of several smaller tasks by the solver, before they can be scheduled. In this paper, we introduce different metaheuristic solution approaches for this problem. We propose four new neighborhoods that modify the grouping of tasks. In combination with neighborhoods for scheduling, they are used by our metaheuristics to produce high-quality solutions for both randomly generated and real-world instances. In particular, Simulated Annealing managed to find solutions that are competitive with the best known results and improve upon the state-of-the-art for larger instances. The algorithm is currently used for the daily planning of a large real-world laboratory
Solving a home energy management problem by Simulated Annealing
No full textWe consider the energy scheduling problem for a domestic setting proposed and modeled by Della Croce et al. (Comput Ind Eng 109:169–178, 2017). We solve it by means of a Simulated Annealing approach based on a complex neighborhood structure. We perform an extensive and statistically-principled tuning phase using F-Race, given that the solver is dependent on a set of parameters, which comprises the classical ones of Simulated Annealing and others related to the neighborhood structure. The experimental analysis shows that our solver outperforms all four methods proposed in the original work by Della Croce et al. in almost all instances
Multi-neighborhood Simulated Annealing for Nurse Rostering
No full textWe consider the Nurse Rostering problem, in the real-world formulation proposed by Curtois and Qu [8]. For this formulation, we propose a local search approach based on a combination of four neighborhoods guided by a Simulated Annealing metaheuristic, and we test it on the publicly available dataset. This research is still ongoing and the preliminary results show that we are able to obtain results in line with the state-of-the-art ones on a few instances (notably the largest ones), but currently fail to reach the optimal solutions
AL-log: Integrating Datalog and Description Logics.
No full textWe present an integrated system for knowledge representation, called AL-log, based on description logics and the deductive database language Datalog. AL-log embodies two subsystems, called structural and relational. The former allows for the definition of structural knowledge about classes of interest (concepts) and membership relation between objects and classes. The latter allows for the definition of relational knowledge about objects described in the structural component. The interaction between the two components is obtained by allowing constraints within Datalog clauses, thus requiring the variables in the clauses to range over the set of instances of a specified concept. We propose a method for query answering in AL-log based on constrained resolution, where the usual deduction procedure defined for Datalog is integrated with a method for reasoning on the structural knowledge
Reinforcement Learning for Multi-Neighborhood Local Search in Combinatorial Optimization
No full textThis study investigates the application of reinforcement learning for the adaptive tuning of neighborhood probabilities in stochastic multi-neighborhood search. The aim is to provide a more flexible and robust tuning method for heterogeneous scenarios than traditional offline tuning. We propose a novel mix of learning components for multi-neighborhood Simulated Annealing, which considers both cost-and time-effectiveness of moves. To assess the performance of our approach we employ two real-world case studies in timetabling, namely examination timetabling and sports timetabling, for which multi-neighborhood Simulated Annealing has already obtained remarkable results using offline tuning techniques. Experimental data show that our approach obtains better results than the analogous algorithm that uses state-of-the-art offline tuning on benchmarking datasets while requiring less tuning effort
- …
