Percorrer por autor "Pires, F. M."
A mostrar 1 - 7 de 7
Resultados por página
Opções de ordenação
- Uma abordagem genética para o programa quadrático 0-1Publication . Schutz, G.; Pires, F. M.; Ruano, AntonioApresenta-se uma heurística para o programa quadrático 0-1 sem restrições. A abordagem utilizada baseia-se em algoritmos genéticos, combinando os operadores genéticos convencionais com estratégias de tipo ávido. Consegue-se assim um algoritmo simples e eficiente, mesmo para problemas de maior dimensão, competitivo com outras meta-heurísticas mais elaboradas. Descreve-se o estudo computacional realizado com um conjunto de problemas-teste, já utilizados na literatura sobre este tema. Os resultados obtidos encorajam a investigação neste sentido, uma vez que, se obtiveram, em tempos de execução muito reduzidos, soluções de boa qualidade, mesmo em problemas de dimensões elevadas.
- A computational study of a parallel Branch and Bound algorithm for the quadratic 0-1 programming problem on transputersPublication . Schutz, G.; Pires, F. M.; Ruano, AntonioDiscrete optimization problems are very difficult to solve, even if the dimantion is small. For most of them the problem of finding an ε-approximate solution is already NP-hard.
- Estudo computacional de um algoritmo genético para o problema de optimização de rotas de veículosPublication . Schutz, G.; Pires, F. M.; Ruano, AntonioO problema básico da distribuição e/ou recolha de produtos é um problema de Optimização Combinatória que consiste em determinar o conjunto de rotas que partem de um depósito central, cuja localização é conhecida, servem um conjunto de clientes com procuras e localizações pré - definidas, minimizando a distância total percorrida. Este é um problema NP-difícil, para o qual poucos métodos exactos foram desenvolvidos, sendo demasiado demorados e não sendo sequer exequíveis para a generalidade dos problemas de dimensão média. Assim, as abordagens mais comuns e eficientes baseiam-se em métodos heurísticos. Numa classificação superficial podem-se considerar duas classes de métodos heurísticos: os “clássicos” e os “modernos”. Os primeiros incluem, entre outros, os métodos construtivos de rota, os métodos de duas fases e os de melhoramento de rotas. Estes métodos foram basicamente desenvolvidos nos anos 60 e 70, embora continuem a ser utilizados e melhorados. Por outro lado, os métodos “modernos” têm como característica comum o recurso à pesquisa local utilizando técnicas de intensificação e diversificação dessa pesquisa. Entre outras, têm aparecido recentemente heurísticas baseadas em: Simulação de Têmpera; algoritmos Genéticos; Pesquisa Tabu; Algoritmos Difusos e Redes Neuronais. Combinações destas técnicas têm conduzido a algoritmos híbridos e a meta-heurísticas. Neste trabalho é feita a apresentação de um Algoritmo Genético para o Problema de Optimização de Rotas de Veículos. Apresenta-se a sua implementação e um estudo computacional comparativo com duas heurísticas “clássicas” num conjunto de problemas - teste conhecidos da literatura.
- Estudo das rotas de recolha de resíduos sólidos na região rural de FaroPublication . Schutz, G.; Pires, F. M.; Ruano, AntonioDescrevemos, neste trabalho, o problema da determinação de rotas para a recolha de resíduos sólidos na região rural de Faro. Este é um problema de optimização combinatória que pode ser resolvido usando técnicas próprias de problemas de “Vehicle Routing”. A resolução do problema foi solicitada pelos Serviços Municipalizados da Câmara Municipal de Faro que forneceram os mapas das rotas praticadas, bem como alguns outros elementos de que dispunham. Pretendiam os responsáveis pelos Serviços que se encontrasse um meio de, sem aumentar o número de veículos nem de funcionários, obedecer às novas leis de horários laborais, efectuar uma recolha mais frequente nalguns locais onde a densidade populacional tinha aumentado nos últimos anos e, simultaneamente, tentar minimizar as distâncias percorridas pelos veículos. Aplicámos a este problema alguns métodos heurísticos clássicos e, neste trabalho, apresentamos os resultados obtidos com uma adaptação de uma heurística baseada em algoritmos genéticos. Esta heurística já tinha mostrado ser competitiva com os métodos tradicionais na resolução de problemas-teste da literatura. Obtivemos algumas soluções que obedeciam às restrições impostas pelos Serviços, conseguiam diminuir as distâncias totais percorridas, melhorando, em todos os aspectos, o padrão de recolha que estava a ser efectuado. Estas soluções foram implementadas pelos Serviços Municipalizados, com resultados muito satisfatórios, confirmando, na prática, as previsões do estudo computacional.
- Estudo das rotas de recolha de resíduos sólidos na região rural de FaroPublication . Schutz, G.; Pires, F. M.; Ruano, AntonioDescreve-se o problema da determinação de rotas para a recolha de resíduos sólidos na região rural de Faro. Este é um problema de optimização combinatória que pode ser resolvido usando técnicas próprias de problemas de “Vehicle Routing”. A resolução do problema foi solicitada pelos Serviços Municipalizados da Câmara Municipal de Faro que forneceram os mapas das rotas praticadas, bem como alguns outros elementos de que dispunham. Pretendiam os responsáveis pelos Serviços que se encontrasse um meio de, sem aumentar o número de veículos nem de funcionários, obedecer às novas leis de horários laborais, efectuar uma recolha mais frequente nalguns locais onde a densidade populacional tinha aumentado nos últimos anos e, simultaneamente, tentar minimizar as distâncias percorridas pelos veículos. Aplicou-se a este problema alguns métodos heurísticos clássicos e, neste trabalho, apresentam-se os resultados obtidos com uma adaptação de uma heurística baseada em algoritmos genéticos. Esta heurística já tinha mostrado ser competitiva com os métodos tradicionais na resolução de problemas-teste da literatura. Obtiveram-se algumas soluções que obedeciam às restrições impostas pelos Serviços, conseguiam diminuir as distâncias totais percorridas, melhorando, em todos os aspectos, o padrão de recolha que estava a ser efectuado. Estas soluções foram implementadas pelos Serviços Municipalizados, com resultados muito satisfatórios, confirmando, na realidade, as previsões do estudo computacional.
- Implementing and testing branch-and-bound algorithm for the quadratic 0-1 problem on transputersPublication . Schutz, G.; Pires, F. M.; Ruano, AntonioDiscrete optimization problems are very difficult to solve, even if the dimention is small. For most of them the problem of finding an ε-approximate solution is already NP-hard. The branch-and-bound algorithms are the most used algorithms for solving exactly this sort of problems.
- Solving the quadratic 0-1 problemPublication . Schutz, G.; Pires, F. M.; Ruano, AntonioThe quadratic 0-1 programming is a discrete optimization problem, with many important applications. Difficult graph problems can be formulated and solved as a quadratic 0-1 programming problem. This is a NP-hard combinatorial problem very difficult to solve, even if the dimension is small. The branch-and-bound algorithms are the most used for solving exactly this sort of problems. In this paper, based on an efficient sequential branch-and-bound algorithm for the unconstrained quadratic 0-1 programming, we study the behaviour of its parallel implementation using transputers and present some computational results. We also analyse the workload distribution among processors.