Browsing by Author "Maculan Filho, Nelson"

Now showing 1 - 4 of 4
  • No Thumbnail Available
    Item
    Uma heurística para o problema de programação de horários em escolas.
    (2001) Souza, Marcone Jamilson Freitas; Maculan Filho, Nelson; Ochi, Luiz Satoru
    Apresentamos GBT-II, uma heurística para resolver problemas de programação de horários em escolas. A partir de uma solução inicial gerada por um procedimento construtivo parcialmente guloso, um procedimento de Busca Tabu inicia sua pesquisa. Quando uma solução sem sobreposições, mas com, possivelmente, algum outro tipo de inviabilidade, é gerada, acionamos um procedimento chamado intraturmas-Intertumas para tentar recuperar a viabilidade. Sendo bem sucedido, ele é novamente acionado, agora para tentar melhorar a capacidade da agenda dos professores, bem como outras medidas de qualidade. Após um certo número de interações sem melhora, todo o processo, desde a geração de uma solução inicial, é repetido até que uma condição de parada seja satisfeita . Resultados computacionais mostram que a tilização do procedimento Intraturmas-Interturmas faz produzir soluções melhores rapidamente.
  • No Thumbnail Available
    Item
    Large neighborhoods with implicit customer selection for vehicle routing problems with profits.
    (2015) Vidal, Thibaut Victor Gaston; Maculan Filho, Nelson; Ochi, Luiz Satoru; Penna, Puca Huachi Vaz
    We consider several vehicle routing problems (VRP) with profits, which seek to select a subset of customers, each one being associated with a profit, and to design service itineraries. When the sum of profits is maximized under distance constraints, the problem is usually called the team orienteering problem. The capacitated profitable tour problem seeks to maximize profits minus travel costs under capacity constraints. Finally, in the VRP with a private fleet and common carrier, some customers can be delegated to an external carrier subject to a cost. Three families of combined decisions must be taken: customer’s selection, assignment to vehicles, and sequencing of deliveries for each route. We propose a new neighborhood search for these problems, which explores an exponential number of solutions in pseudo-polynomial time. The search is conducted with standard VRP neighborhoods on an exhaustive solution representation, visiting all customers. Since visiting all customers is usually infeasible or suboptimal, an efficient select algorithm, based on resource constrained shortest paths, is repeatedly used on any new route to find the optimal subsequence of visits to customers. The good performance of these neighborhood structures is demonstrated by extensive computational experiments with a local search, an iterated local search, and a hybrid genetic algorithm. Intriguingly, even a local-improvement method to the first local optimum of this neighborhood achieves an average gap of 0.09% on classic team orienteering benchmark instances, rivaling with the current state-of-the-art metaheuristics. Promising research avenues on hybridizations with more standard routing neighborhoods are also open.
  • No Thumbnail Available
    Item
    Melhorando quadros de horário de escolas através de caminhos mínimos.
    (2000) Souza, Marcone Jamilson Freitas; Maculan Filho, Nelson; Ochi, Luiz Satoru
  • No Thumbnail Available
    Item
    Strong bounds with cut and column generation for class-teacher timetabling.
    (2012) Santos, Haroldo Gambini; Uchoa, Eduardo; Ochi, Luiz Satoru; Maculan Filho, Nelson
    This work presents an integer programming formulation for a variant of the ClassTeacher Timetabling problem, which considers the satisfaction of teacher preferences and also the proper distribution of lessons throughout the week. The formulation contains a very large number of variables and is enhanced by cuts. Therefore, a cut and column generation algorithm to solve its linear relaxation is provided. The lower bounds obtained are very good, allowing us to prove the optimality of previously known solutions in three formerly open instances.