FenixEdu™

Dissertação

{en=Solving the Car Sequencing Problem form a Multiobjective Perspective} {} EVALUATED

Detalhes: {pt=Em 2003 a Sociedade Francesa de Investigação Operacional organizou, com o apoio da Renault, um concurso designado ROADEF‟2005 Challenge. O objectivo desta competição consistia em desenvolver um algoritmo para resolver uma nova versão multi-objecivo do já conhecido Car Sequencing Problem. Este problema consiste em ordenar um conjunto de veículos ao longo da linha de produção procurando minimizar o número de violações dos rácios de restrição e o número de mudanças de cor. O objectivo desta tese consiste em resolver esta nova versão multi-objectivo do Car Sequencing Problem, mas usando uma noção de optimalidade diferente, designada de optimalidade de Pareto. A vantagem desta noção de óptimo é que o decisor não necessita de realizar qualquer tipo de julgamento sobre a relevância dos objectivos. Para além desta o conhecimento das diversas soluções de Pareto permitem ao decisor aprender mais sobre as contrapartidas entre as diversas soluções. Para resolver este problema começamos por propor um algoritmo exacto, designado de ε-constraint, que nos permite obter soluções eficientes cuja imagem no espaço dos objectivos corresponde ao conjunto não-dominado também conhecido por frente de Pareto. Contudo, devido a determinadas limitações computacionais este método revelou-se incapaz de resolver instâncias mais exigentes. Tendo em consideração as limitações dos métodos exactos acima referidos propomos um segundo método, uma heurística baseada em processos de procura local que nos permitem obter, pelo menos, soluções que estão próximas das óptimas num curto período de tempo., en=In 2003, the French Society of Operations Research jointly with Renault launched the ROADEF‟2005 Challenge. The purpose of this competition was to develop an algorithm to solve a new multiobjective version of the well known Car Sequencing Problem (CSP). This problem consists in sequencing a given set of vehicles along an assembly line while minimizing the number of violations of ratio constraints and the number of color changes. The aim of this thesis is to solve the ROADEF‟2005 CSP version, but using a different notion of optimality, called Pareto optimality. The advantage of this approach is that the decision maker does not have to judge the objectives about their priority. In addition it allows him to learn more about the trade-offs between the objectives. In order to solve the CSP we start by proposing an exact algorithm (ε-constraint) that allows us to obtain all the nondominated points and respective efficient solutions. However, since this exact approach takes an infeasible amount of time to solve hard instances we further propose an heuristic scheme, based on local search procedures that enable us to obtain, at least, an approximation to the nondominated set in a much shorter period of time.}
Keywords: {pt=Car Sequencing Problem, Optimalidade de Pareto, Epsilon-Constraint, Heurística., en=Car Sequencing Problem, Pareto optimality, Epsilon-Constraint, Heuristic.}

Discussão: dezembro 20, 2007, 14:0