Publications

2016
Christophe Duhamel, Philippe Mahey, Alexandre X. Martins, Rodney R. Saldanha, and Rodney R. Saldanha. 6/2016. “Model-hierarchical column generation and heuristic for the routing and wavelength assignment problem.” 4OR, 14, 2, Pp. 201–220. Link para acessoAbstract
The routing and wavelength assignment (RWA) problem typically occurs in wavelength division multiplexing optical networks. Given a number of available wavelengths, we consider here the problem of maximising the number of accepted connections with respect to the clash and continuity constraints. We first propose a new strategy which combines two existing models. This leads to an improved column generation scheme. We also present two heuristics to compute feasible solutions: a hybrid heuristic and the integer solution at the root node of the column generation. Our approaches are compared with the best existing results on a set of classic RWA instances.
Patrícia N. Pena, Tatiana Alves Costa, Regiane S. Silva, and Ricardo H. C. Takahashi. 2016. “Control of Flexible Manufacturing Systems under model uncertainty using Supervisory Control Theory and evolutionary computation schedule synthesis.” Information Sciences, 329, Pp. 491-502. Publisher's VersionAbstract

A new approach for the problem of optimal task scheduling in flexible manufacturing systems is proposed in this work, as a combination of metaheuristic optimization techniques with the supervisory control theory of discrete-event systems. A specific encoding, the word-shuffling encoding, which avoids the generation of a large number of infeasible sequences, is employed. A metaheuristic method based on a Variable Neighborhood Search is then built using such an encoding. The optimization algorithm performs the search for the optimal schedules, while the supervisory control has the role of codifying all the problem constraints, allowing an efficient feasibility correction procedure, and avoiding schedules that are sensitive to uncertainties in the execution times associated with the plant operation. In this way, the proposed methodology achieves a system performance which is typical from model-predictive scheduling, combined with the robustness which is required from a structural control.

Fernando Bernardes de Oliveira, Rasul Enayatifar, Hossein Javedani Sadaei, Frederico Gadelha Guimarães, and Jean-Yves Potvin. 2016. “A cooperative coevolutionary algorithm for the multi-depot vehicle routing problem.” Expert Systems with Applications, 43, Pp. 117-130. Publisher's VersionAbstract

The Multi-Depot Vehicle Routing Problem (MDVRP) is an important variant of the classical Vehicle Routing Problem (VRP), where the customers can be served from a number of depots. This paper introduces a cooperative coevolutionary algorithm to minimize the total route cost of the MDVRP. Coevolutionary algorithms are inspired by the simultaneous evolution process involving two or more species. In this approach, the problem is decomposed into smaller subproblems and individuals from different populations are combined to create a complete solution to the original problem. This paper presents a problem decomposition approach for the MDVRP in which each subproblem becomes a single depot VRP and evolves independently in its domain space. Customers are distributed among the depots based on their distance from the depots and their distance from their closest neighbor. A population is associated with each depot where the individuals represent partial solutions to the problem, that is, sets of routes over customers assigned to the corresponding depot. The fitness of a partial solution depends on its ability to cooperate with partial solutions from other populations to form a complete solution to the MDVRP. As the problem is decomposed and each part evolves separately, this approach is strongly suitable to parallel environments. Therefore, a parallel evolution strategy environment with a variable length genotype coupled with local search operators is proposed. A large number of experiments have been conducted to assess the performance of this approach. The results suggest that the proposed coevolutionary algorithm in a parallel environment is able to produce high-quality solutions to the MDVRP in low computational time.

George Henrique Godim da Fonseca, Haroldo Gambini Santos, Túlio Ângelo Machado Toffolo, Samuel Souza Brito, and Marcone Jamilson Freitas Souza. 2016. “GOAL solver: a hybrid local search based solver for high school timetabling.” Annals of Operations Research, 239, 1, Pp. 77-97. Publisher's VersionAbstract

This work presents a local search approach to the High School Timetabling Problem. The addressed timetabling model is the one stated in the Third International Timetabling Competition (ITC 2011), which considered many instances from educational institutions around the world and attracted seventeen competitors. Our team, named GOAL (Group of Optimization and Algorithms), developed a solver built upon the Kingston High School Timetabling Engine. Several neighborhood structures were developed and used in a hybrid metaheuristic based on Simulated Annealing and Iterated Local Search. The developed algorithm was the winner of the competition and produced the best known solutions for almost all instances.

George H. G. Fonseca, Haroldo G. Santos, and Eduardo G. Carrano. 2016. “Late acceptance hill-climbing for high school timetabling.” Journal of Scheduling, 19, 4, Pp. 453-465. Publisher's VersionAbstract

The application of the Late Acceptance Hill-Climbing (LAHC) to solve the High School Timetabling Problem is the subject of this manuscript. The original algorithm and two variants proposed here are tested jointly with other state-of-art methods to solve the instances proposed in the Third International Timetabling Competition. Following the same rules of the competition, the LAHC-based algorithms noticeably outperformed the winning methods. These results, and reports from the literature, suggest that the LAHC is a reliable method that can compete with the most employed local search algorithms.

Marina Soares Almeida, Mônica do Amaral, and Reinaldo Morabito. 2016. “Um estudo sobre localização de terminais intermodais na rede de escoamento da soja brasileira.” Production, 26, 3, Pp. 562-580. Publisher's VersionAbstract

A soja é um dos principais produtos agrícolas brasileiros. Do total colhido, aproximadamente 40% é destinado à exportação. Como as lavouras estão concentradas principalmente na região central no país, essa soja percorre, em geral, grandes distâncias até os portos marítimos. Nesse caso, o transporte intermodal pode tornar mais eficiente e econômica a movimentação de grandes volumes por longas distâncias. Analisa-se, neste estudo, a aplicação de um modelo de programação matemática para apoiar decisões de fluxo de soja e localização de terminais intermodais. Com base em dados secundários, foram propostas três redes alternativas de escoamento, com diferentes áreas de abrangência e possibilidade de utilização de ferrovias ainda em construção ou projeto. Foram considerados os principais estados produtores e movimentadores da soja. Experimentos computacionais resultaram em fluxos de escoamento e localização de terminais condizentes com a realidade. Cenários alternativos da rede também foram analisados, evidenciando o potencial de análise dessa ferramenta de otimização.

George H. G. Fonseca, Haroldo G. Santos, and Eduardo G. Carrano. 2016. “Integrating matheuristics and metaheuristics for timetabling.” Computers & Operations Research, 74, Pp. 108-117. Publisher's VersionAbstract

The High School Timetabling Problem requires the assignment of times and resources to events, while sets of required and desirable constraints must be considered. The most common approach for this problem is to employ metaheuristic methods. This work presents a matheuristic approach that combines a Variable Neighbourhood Search algorithm with mathematical programming-based neighbourhoods for high school timetabling. Computational experiments on well-known benchmark instances demonstrate the success of the proposed hybrid approach, which outperforms the standalone Variable Neighbourhood Search algorithm by far. Additionally, the proposed algorithm was able to improve 15 out of 17 current best known solutions in a very famous benchmark set.

2015
Thiago A.O.Silva, Mauricio C. de Souza, Rodney R. Saldanha, and Edmund K.Burke. 2015. “Surgical scheduling with simultaneous employment of specialised human resources.” European Journal of Operational Research, 245, 3, Pp. 719-730. Publisher's VersionAbstract
Surgical scheduling is a challenging problem faced by hospital managers. It is subject to a wide range of constraints depending upon the particular situation within any given hospital. We deal with the simultaneous employment of specialised human resources, which must be assigned to surgeries according to their skills as well as the time windows of the staff. A particular feature is that they can be assigned to two surgeries simultaneously if the rooms are compatible. The objective is to maximise the use of the operating rooms. We propose an integer model and integer programming based heuristics to address the problem. Computational experiments were conducted on a number of scenarios inspired by real data to cover different practical problem solving situations. Numerical results show that relaxations provide tight upper bounds, and relax-and-fix heuristics are successful in finding optimal or near optimal solutions.
2011
Eduardo Uchoa, Túlio A. M. Toffolo, Mauricio C. de Souza, Alexandre X. Martins, and Ricardo Fukasawa. 11/29/2011. “Branch-and-cut and hybrid local search for the multi-level capacitated minimum spanning tree problem.” Networks. Link para acessoAbstract
We propose algorithms to compute tight lower bounds and high quality upper bounds (UBs) for the multilevel capacitated minimum spanning tree problem. We first develop a branch-and-cut algorithm, introducing some new features: (i) the exact separation of cuts corresponding to some master equality polyhedra found in the formulation; (ii) the separation of Fenchel cuts, solving LPs considering all the possible solutions restricted to small portions of the graph. We then use that branch-and-cut within a GRASP that performs moves by solving to optimality subproblems corresponding to partial solutions. The computational experiments were conducted on 450 benchmark instances from the literature. Numerical results show improved best known (UBs) for almost all instances that could not be solved to optimality. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012
Alexandre Xavier Martins, Christophe Duhamel, Mauricio Cardoso de Souza, Rodney Rezende Saldanha, and Philippe Mahey. 2011. “A VND-ILS Heuristic to Solve the RWA Problem.” Network Optimization, Pp. 577-582. Link para acessoAbstract
The Routing and Wavelength Assignment problem occurs in optical networks where communication requests fulfilled without inducing wavelength conflicts. We propose a VND-ILS algorithm which is a hybridization of both the ILS metaheuristic and the VND local search. Three neighborhood structures are defined for the VND as well as a perturbation step in the ILS. The efficiency of our approach is illustrated on classical realistic RWA instances. The computational results show our method outperforms some of the best existing methods in the literature.
2009
Alexandre X. Martins, Mauricio C. de Souza, Marcone J. F. Souza, and Túlio A. M. Toffolo. 4/2009. “GRASP with hybrid heuristic-subproblem optimization for the multi-level capacitated minimum spanning tree problem.” Journal of Heuristics, 15, 2, Pp. 133–151. Link para acessoAbstract
We propose a GRASP using an hybrid heuristic-subproblem optimization approach for the Multi-Level Capacitated Minimum Spanning Tree (MLCMST) problem. The motivation behind such approach is that to evaluate moves rearranging the configuration of a subset of nodes may require to solve a smaller-sized MLCMST instance. We thus use heuristic rules to define, in both the construction and the local search phases, subproblems which are in turn solved exactly by employing an integer programming model. We report numerical results obtained on benchmark instances from the literature, showing the approach to be competitive in terms of solution quality. The proposed GRASP have in fact improved the best known upper bounds for almost all of the considered instances.
Thiago Augusto Oliveira de Silva and Leonardo P. Santiago. 2009. “New product development projects evaluation under time uncertainty.” Pesquisa Operacional, 29, 3, Pp. 517-532.Abstract
The development time is one of the key factors that contribute to the new product development success. In spite of that, the impact of the time uncertainty on the development has been not fully exploited, as far as decision supporting models to evaluate this kind of projects is concerned. In this context, the objective of the present paper is to evaluate the development process of new technologies under time uncertainty. We introduce a model which captures this source of uncertainty and develop an algorithm to evaluate projects that incorporates Monte Carlo Simulation and Dynamic Programming. The novelty in our approach is to thoroughly blend the stochastic time with a formal approach to the problem, which preserves the Markov property. We base our model on the distinction between the decision epoch and the stochastic time. We discuss and illustrate the applicability of our model through an empirical example.
2005
Aloísio Castro Gomes de Júnior, Marcone Jamilson Freitas Souza, and Alexandre Xavier Martins. 2005. “Simulated annealing aplicado à resolução do problema de roteamento de veículos com janela de tempo.” ANPET - Associação Nacional de Pesquisa e Ensino em Transportes, 13, 2. Link para acessoAbstract
Este trabalho apresenta um algoritmo eficiente, baseado na metaheurística Simulated Annealing (SA), para resolver o Problema de Roteamento de Veículos com Janela de Tempo. Esse problema tem como objetivo determinar as rotas de custo mínimo para uma frota de veículos de mesma capacidade, atendendo à demanda de um conjunto de clientes, para os quais o atendimento somente é possível dentro de um intervalo de tempo determinado, chamado janela de tempo. A metodologia proposta, denominada SA-RAI, incorpora ao algoritmo Simulated Annealing clássico, mecanismos auto-adaptativos para determinação da temperatura inicial e número de iterações em uma mesma temperatura. Nesta metodologia, quando a temperatura atinge um valor limiar, a mesma é reaquecida um certo número de vezes, possibilitando escapar de ótimos locais. Além disso, ela conta com uma fase de intensificação. Sempre que uma melhor solução é encontrada, ela é submetida a um procedimento de refinamento, visando ao seu melhoramento. A metodologia foi aplicada a 168 problemas-teste da literatura e 13 novos melhores resultados foram encontrados.

Páginas