Cette thèse aborde le problème de tournées de véhicules périodiques (PVRP) lorsqu'il est appliqué au transport de marchandises convoitables. Des contraintes spécifiques relatives à la sécurité du convoi doivent être définies.Le problème de tournées de véhicules périodiques avec dispersion des instants de service (PVRPTS) est alors décrit puis modélisé mathématiquement. Le but est de servir un ensemble de clients sur plusieurs jours en respectant un degré de variation définit dans les heures de service. Le modèle obtenu est discuté et deux heuristiques constructives sont proposées et évaluées pour sa résolution.Une recherche locale itérée avec redémarrages (MS-ILS) est proposée pour ce problème. Les résultats obtenus montrent que cette méthode surpasse les deux précédentes sur toutes les instances de test. Elle est ensuite évaluée sur un problème plus classique de la littérature : le problème de tournées de véhicules avec fenêtres horaires souples (VRPSTW) et s'avère très compétitive, produisant de nouvelles meilleures solutions.La MS-ILS est ensuite transposée au problème de tournées de véhicules régulières (ConVRP). Contrairement au PVRPTS, il s'agit dans le ConVRP de servir régulièrement des clients aux demandes intermittentes. La méthode montre une flexibilité remarquable et produit de bons résultats.Pour finir, les développements effectués chez Nexxtep Technologies sont présentés. Ils comprennent la conception d'un logiciel commercial pour l'optimisation de tournées de véhicules et l'implémentation des méthodes développées / This thesis is dedicated to the periodic vehicle routing problem when applied to the transportation of valuable goods. Specifics constraints have to be defined to ensure the security of the convoy.The periodic vehicle routing problems with time spread constraints on services (PVRPTS) is defined and a mathematical model is given. The goal is to serve a set of customers over several days such that their visit times differ by a minimum amount. The depicted model is discussed and two constructive heuristics are designed and assessed.A Multi-start iterated local search (MS-ILS) is proposed to solve this problem. The results shows that the method outperform the two previous heuristics. For the sake of comparison with previous approaches, the MS-ILS is evaluated on a more classical problem : the vehicle routing problem with soft time windows (VRPSTW). The method proves to be very competitive, producing new best known solutions.The MS-ILS is then adapted to solve the consistent vehicle routing problem (ConVRP). Unlike the PVRPTS, the goal of the ConVRP is to deliver customers with intermittent demands with regularity in terms of service times and drivers. The method demonstrate his flexibility and produce good results. Finally, the developments performed at Nexxtep Technologies are depicted. They encompass commercial-software design and implementation of the proposed methods

Cette thèse porte sur l'étude du problème de tournées de véhicules compartimentés (Multi-Compartment Vehicle Routing Problem ou MC-VRP) dans le contexte de l'industrie de la nutrition animale. Les travaux de recherche et d'application sont concentrés sur la distribution dans le domaine agroalimentaire.En dépit d'une large application industrielle, les problèmes de MC-VRP ont été peu étudiés dans la littérature scientifique. Trois variantes du MC-VRP sont traitées dans cette thèse. D'une part, nous proposons les algorithmes "Greedy Randomized Adaptive Search Procedure" (GRASP) et "Iterated Local Search procedure" (ILS) pour résoudre le MC-VRP avec un compartiment de taille fixe dédié à chaque produit. Une extension de ce problème à des compartiments de tailles variables (Flexible Compartments Vehicle Routing Problem ou FC-VRP) est également résolue. D'autre part, nous proposons un GRASP et un Multi Start ILS pour la résolution du MC-VRP avec décisions d'affectation de chaque compartiment à un client et un produit.En dernier lieu, des travaux d'application industrielle sont présentés. Des tests d'évaluation de performances ont été réalisés dans un contexte de distribution d'aliments au bétail chez la société Nestal. Des outils d'aide à la décision ont été développés et mis en place dans cette société / This research concerns solving the Multi-Compartment Vehicle Routing Problem (MC-VRP) in the context of animal nutrition industry. Research and application work focuses on distribution in food industry.Despite its vast application in industry, little attention has been paid to the MC-VRP. We address three classes of MC-VRP in this research. Firstly, we propose two metaheuristics, "Greedy Randomized Adaptive Search Procedure" (GRASP) and "Iterated Local Search procedure" (ILS), in order to solve a MC-VRP with a fixed-sized compartment dedicated to each product. Also, an extension of this problem to variable-sized compartments which we call Flexible Compartments Vehicle Routing Problem (FC-VRP) is studied. Further, we propose a GRASP and a Multi Start ILS to solve a MC-VRP problem with assignment decisions of each compartment to one client and one product. Finally, some application work is presented. Experiments intended to measure performance in the context of food distribution to cattle were conducted for Nestal company. Decision support tools had been developed and implemented for this company

Les problèmes de tournées de véhicules cumulatives avec capacité (CCVRP) sont étudiés dans cette thèse, où la minimisation de la somme des temps d'arrivée reflète mieux les objectifs stratégiques de la logistique humanitaire.Dans le problème de multiples tournées d’un véhicule cumulatif avec capacité (mt-CCSVRP), un seul véhicule est disponible et il peut effectuer plusieurs voyages. Un algorithme du plus court chemin avec contrainte de ressources est proposé pour résoudre ce problème, dans lequel les tournées deviennent des nœuds et les sites sont des ressources. Le réseau est orienté et acyclique en raison des propriétés particulières du mt-CCSVRP.Le problème de multiples tournées de véhicules cumulatives avec capacité (mt-CCVRP) est introduit, où plusieurs véhicules peuvent effectuer multiples voyages. Quatre programmes linéaires en nombre entiers (PLNE) sont proposés pour résoudre le CCVRP. Un PLNE pour le mt-CCVRP est proposé ainsi que trois métaheuristiques : une recherche locale itéré à démarrages multiples (MS-ILS), un algorithme mémétique avec gestion de la population (MA|PM) et une recherche locale évolutive à démarrages multiples (MS-ELS), qui appellent un algorithme de recherche local à voisinages variables (VND). Une méthode split à deux phases permet MA|PM et MS-ELS d'alterner entre deux espaces de solutions.Le problème de tournées de véhicules cumulatif avec capacité et des livraisons indirectes (CCVRP-ID) permet aux sites non visités si leurs demandes sont fournies par un véhicule auxiliaire. Un PLNE et un MS-ELS sont développés / The cumulative capacitated vehicle routing problems (CCVRP) are studied in this thesis, where the minimization of the sum of arrival times better reflects the strategic objectives of humanitarian logistics.In the multitrip cumulative capacitated single-vehicle routing problem (mt-CCSVRP), only one vehicle is available and it can perform multiple trips. An exact resource constrained shortest path algorithm is proposed for this problem, in which trips become nodes and sites are resources. The resulting network is proven to be directed and acyclic due to the special properties of the mt-CCSVRP.The multitrip cumulative capacitated vehicle routing problem (mt-CCVRP) is introduced, where several vehicles can do multiple trips. Four mixed integer linear programs (MILP) are proposed to solve the CCVRP. For the mt-CCVRP a MILP is also given as well as three metaheuristics: a multi-start iterated local search (MS-ILS), a memetic algorithm with population management (MA|PM) and a multi-start evolutionary local search (MS-ELS), which call a variable neighborhood descent algorithm (VND). A two phases split method allows MA|MS and MS-ELS to alternate between two spaces of solutions.The cumulative capacitated vehicle routing problem with indirect deliveries (CCVRP-ID) allows unvisited sites if their demands are provided by an auxiliary vehicle. An MILP and an MS-ELS are developed

Cette thèse aborde le problème de tournées de véhicules (VRP) adressant des incertitudes via l'optimisation robuste, en donnant le VRP Robuste (RVRP). D'abord, les incertitudes sont intégrées sur les temps de trajet. Ensuite, une version bi-objectif du RVRP (bi-RVRP) est considérée en prenant en compte les incertitudes sur les temps de trajet et les demandes. Pour résoudre le RVRP et le bi-RVRP, différentes méthodes sont proposées pour déterminer des solutions robustes en minimisant le pire cas. Un Programme Linéaire à Variables Mixtes Entières (MILP), six heuristiques constructives, un algorithme génétique (GA), une procédure de recherche locale et quatre stratégies itératives à démarrage multiple sont proposées : une procédure de recherche constructive adaptive randomisée (GRASP), une recherche locale itérée (ILS), une ILS à démarrage multiple (MS-ILS), et une MS-ILS basée sur des tours géants (MS-ILS-GT) convertis en tournées réalisables grâce à un découpage lexicographique. Concernant le bi-RVRP, le coût total des arcs traversés et la demande totale non satisfaite sont minimisés sur tous les scénarios. Pour résoudre le problème, différentes versions de métaheuristiques évolutives multi-objectif sont proposées et couplées à une recherche locale : l'algorithme évolutionnaire multi-objectif (MOEA) et l'algorithme génétique avec tri par non-domination version 2 (NSGAII). Différentes métriques sont utilisées pour mesurer l’efficience, la convergence, ainsi que la diversité des solutions pour tous ces algorithmes / This work extends the Vehicle Routing Problem (VRP) for addressing uncertainties via robust optimization, giving the Robust VRP (RVRP). First, uncertainties are handled on travel times/costs. Then, a bi-objective version (bi-RVRP) is introduced to handle uncertainty in both, travel times and demands. For solving the RVRP and the bi-RVRP different models and methods are proposed to determine robust solutions minimizing the worst case. A Mixed Integer Linear Program (MILP), several greedy heuristics, a Genetic Algorithm (GA), a local search procedure and four local search based algorithms are proposed: a Greedy Randomized Adaptive Search Procedure (GRASP), an Iterated Local Search (ILS), a Multi-Start ILS (MS-ILS), and a MS-ILS based on Giant Tours (MS-ILS-GT) converted into feasible routes via a lexicographic splitting procedure. Concerning the bi-RVRP, the total cost of traversed arcs and the total unmet demand are minimized over all scenarios. To solve the problem, different variations of multiobjective evolutionary metaheuristics are proposed and coupled with a local search procedure: the Multiobjective Evolutionary Algorithm (MOEA) and the Non-dominated Sorting Genetic Algorithm version 2 (NSGAII). Different metrics are used to measure the efficiency, the convergence as well as the diversity of solutions for all these algorithms

[pt] Problemas de geração de grades horárias visam agendar eventos a fim de satisfazer demandas, ao mesmo tempo que satisfazem restrições adicionais. Uma solução é boa se todas as grades horárias resultantes são aceitáveis para todas as pessoas e recursos envolvidos. Para a geração de grades horárias escolares, um número conhecido de aulas, envolvendo estudantes, professores e salas de aula, deve ser agendado ao longo da semana, enquanto limitações operacionais, institucionais, pedagógicas e pessoais devem ser satisfeitas. A alta dificuldade do problema tem levado muitos pesquisadores a trabalhar em abordagens de resolução para o mesmo desde o início dos anos 60. Encontrar uma solução aplicável em um cenário do mundo real implica em satisfazer vários requisitos de qualidade e em não ignorar questões políticas, o que torna o problema clássico muito mais intrincado. Este trabalho descreve uma abordagem baseada em programação inteira mista (MIP) desenvolvida para resolver um problema real de geração de grades horárias escolares e discute ideias e desafios encarados durante a fase de implantação da solução em algumas escolas brasileiras. Em contraste com outros trabalhos na área, o compartilhamento de professores entre diferentes unidades de uma escola é considerado. Experimentos computacionais foram realizados para cenários cujo número de unidades varia de 2 a 15, o número de professores de 35 a 471, e o número de turmas de 16 a 295. Diferentes estratégias foram combinadas, visando a convergência da procura por boas soluções. Por fim, os resultados são avaliados e as melhores abordagens são destacadas. / [en] Timetabling problems look to schedule meetings in order to satisfy a set of demands, while respecting additional constraints. In a good solution the resulting timetables are acceptable to all people and resources involved. In school timetabling, a given number of lectures, involving students, teachers and classrooms, need to be scheduled over the week, while having to satisfy operational, institutional, pedagogical and personal restrictions. The difficulty of the problem has driven many researchers to work on solving approaches for it since the early 1960 s. Finding an actual solution to a real world scenario implies satisfying many quality requirements and not ignoring the political issues, which turns the classical problem much more intricate. This work describes an approach based on mixed integer programming (MIP) developed for solving a real-world school timetabling problem and discusses ideas and issues faced during solution deployment phase for some Brazilian schools. In contrast to other works on school timetabling, teaching staff sharing between distinct school units are considered. Computational experiments were performed for scenarios whose number of school units varies from 2 to 15, number of teachers varies from 35 to 471 and number of classes varies from 16 to 295. Different strategies were combined aiming at converging to good solutions. Finally, results are evaluated and the best approaches are highlighted.

[pt] O planejamento e a gestão de atividades esportivas é uma área promissora e pouco explorada para aplicações de Pesquisa Operacional. Os problemas nesta área são em geral de formulação simples e alcançam grande difusão nos meios de comunicação. Embora sua formulação seja simples, em geral estes problemas são difíceis de serem resolvidos em termos computacionais. Os resultados de muitos trabalhos acadêmicos nesta área têm sido aceitos como soluções para problemas reais e várias soluções vem sendo implementadas na prática. Esta tese tem como objetivo principal estudar dois tipos de problemas que surgem na área de esportes: a programação de tabelas e os problemas da classificação. A programação de tabelas para competições esportivas é uma tarefa difícil, na qual diversas técnicas de otimização combinatória têm sido aplicadas. Nesta tese, formula-se o Problema do Torneio com Viagens Espelhado como um problema de otimização em grafos. O problema é resolvido utilizando- se algoritmos aproximados. Apresentam-se duas heurísticas para este problema. A primeira é muito rápida e serve para fornecer soluções iniciais para a segunda, que é capaz de obter soluções de boa qualidade em tempos razoáveis. São deduzidos limites duais para um tipo particular de instâncias. Estes limites permitem provar a otimalidade das soluções obtidas heuristicamente para instâncias muito maiores do que as maiores instâncias resolvidas na literatura. Por ultimo, é apresentado um modelo de programação linear inteira para o problema, ao qual são acrescentadas desigualdades válidas. Os problemas da classificação visam obter condições, necessárias e suficientes, para a classificação de uma determinada equipe para as finais de um campeonato em relação ao número de pontos a ser obtido. São apresentados modelos de programação linear inteira que permitem resolver estes problemas no contexto do Campeonato Brasileiro de Futebol. / [en] Sports management is a very attractive and not very explored area for applications of Operations Research. Problems in this area use to have simple formulations and reach a big coveragge by the media. Although their formulations are simple, in general these problems are difficult to be solved in computational terms. The results of many academic works in this area have been accepted as solutions for real problems and some solutions are being implemented. This thesis has the main objective of studying two types of problems that appear in the sports area: the fixture creation and the qualification problems. Fixture creation (also known as sport scheduling) for sport competitions is a difficult task, in which several combinatorial optimization techniques has been applied. In this thesis, the Mirrored Traveling Tournament Problem is formulated as a graph optmization problem. The problem is solved using approximation algorithms. Two heuristics are introduced for this problem. The first one is very fast and is used to supply initial solutions for the second one which is able to obtain high quality solutions in reasonable computation times. Dual limits are deduced for a particular type of instances. These limits allow to prove the optimality of the heuristically abtained solutions for instances that are much bigger than those soved in the literature. Finally, an integer programming model is introduced in wich valid inequalities are added. The qualification problems aim to obtain necessary and sufficient conditions for the playoffs qualification of a given team in terms of the number of points to be obtained. Integer programming models are introduced which allow solving these problems in the context of the Brazilian Football Championship.

In this thesis we investigate the application of two heuristic methods, genetic algorithms and tabu/scatter search, to the optimisation of realistic portfolios. The model is based on the classical mean-variance approach, but enhanced with floor and ceiling constraints, cardinality constraints and nonlinear transaction costs which include a substantial illiquidity premium, and is then applied to a large I 00-stock portfolio. It is shown that genetic algorithms can optimise such portfolios effectively and within reasonable times, without extensive tailoring or fine-tuning of the algorithm. This approach is also flexible in not relying on any assumed or restrictive properties of the model and can easily cope with extensive modifications such as the addition of complex new constraints, discontinuous variables and changes in the objective function. The results indicate that that both floor and ceiling constraints have a substantial negative impact on portfolio performance and their necessity should be examined critically relative to their associated administration and monitoring costs. Another insight is that nonlinear transaction costs which are comparable in magnitude to forecast returns will tend to diversify portfolios; the effect of these costs on portfolio risk is, however, ambiguous, depending on the degree of diversification required for cost reduction. Generally, the number of assets in a portfolio invariably increases as a result of constraints, costs and their combination. The implementation of cardinality constraints is essential for finding the bestperforming portfolio. The ability of the heuristic method to deal with cardinality constraints is one of its most powerful features. / Decision Sciences / M. Sc. (Operations Research)

DANTAS, Allberson Bruno de Oliveira. Uma Interface de Programação Distribuída para Aplicações em Otimização Combinatória. 2011. 79 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Programa de Pós-Graduaçõa em Ciência da Computação, Fortaleza-CE, 2011. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-05-24T16:25:19Z No. of bitstreams: 1 2011_dis_abodantas.pdf: 805347 bytes, checksum: c9671608a7d738f843239856e546e201 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-05-24T16:27:03Z (GMT) No. of bitstreams: 1 2011_dis_abodantas.pdf: 805347 bytes, checksum: c9671608a7d738f843239856e546e201 (MD5) / Made available in DSpace on 2016-05-24T16:27:03Z (GMT). No. of bitstreams: 1 2011_dis_abodantas.pdf: 805347 bytes, checksum: c9671608a7d738f843239856e546e201 (MD5) Previous issue date: 2011 / This work was motivated by the need of exploiting the potential of distributed paralelism in combinatorial optimization applications. propose a distributed programming interface, To achieve this goal, we in which we cherish two main requirements: e ciency and reuse. The rst stems from the need of HPC (High applications require maximum possible performance. Performance Computing) Therefore, we specify our interface as an extension of the MPI library, which is assumed to be e cient for distributed applications. The reuse requirement must make compatible two important features: asynchronism and collective operations. Asynchronism must be present at our interface, once most of combinatorial optimization applications have an asynchronous nature. Collective operations are features that should be available in the interface, so that they can be used by applications in their execution. In order reach the reuse requirement, we based this interface on the Event- and Pulse-driven Models of Distributed Computing, once they are asynchronous and allow the incorporation of collective operations. We implemented partially the interface de ned in this work. In order to validate the use of the inteface by combinatorial optimization applications, we selected two applications and implemented them using our interface. They are the Branch-and-Bound technique and the Maximum Stable Set Problem (MSSP). We also provide some experimental results. / Este trabalho foi motivado pela necessidade da exploração do potencial do paralelismo distribuído em aplicações em Otimização Combinatória. Para tanto, propomos uma interface de programação distribuída, na qual prezamos dois requisitos principais: eficiência e reuso. O primeiro advém da necessidade de aplicações de CAD exigirem máximo desempenho possível. Assim sendo, especificamos esta interface como uma extensão da biblioteca MPI, a qual é assumida como eficiente para aplicações distribuídas. O requisito reuso deve tornar compatíveis duas características importantes: assincronismo e operações coletivas. O assincronismo deve estar presente na interface, uma vez que as aplicações em Otimização Combinatória, em sua maioria, possuem uma natureza assíncrona. Operações coletivas são funcionalidades que devem estar disponíveis na interface, de modo que possam ser utilizadas por aplicações em suas execuções. Tendo em vista atender o requisito reuso, baseamos esta interface nos Modelos de Computação Distribuída Dirigidos por Eventos e por Pulsos, pois os mesmos são assíncronos e permitem a incorporação de operações coletivas. Implementamos parcialmente a inteface definida neste trabalho. Tendo em vista validar uso desta inteface por aplicações em Otimização Combinatória, selecionamos duas aplicações e as implementamos utilizando a interface. São elas a técnica Branch-and-Bound e o Problema do Conjunto Independente Máximo (CIM). Fornecemos também alguns resultados experimentais.

Made available in DSpace on 2016-12-23T13:51:53Z (GMT). No. of bitstreams: 1 Cristiane Coutinho Meneguzzi.pdf: 2106158 bytes, checksum: 65c537220893be6e9c9d64b3001fef07 (MD5) Previous issue date: 2011-10-04 / Na área florestal, ainda é dada maior ênfase ao desenvolvimento de estudos envolvendo as etapas de colheita e transporte florestal, por serem diretamente responsáveis pelo custo final da madeira. Entretanto, diversas outras etapas possuem grande potencial para estudos, como é o caso do inventário florestal. Informações fornecidas pelo inventário florestal são importantes no planejamento de todo empreendimento florestal, pois subsidiam qualquer tomada de decisão envolvendo recursos florestais. Nesta pesquisa, utilizou-se o modelo de roteamento de veículos (PRV) no planejamento dessa atividade. O PRV e suas variantes vêm sendo amplamente estudados nos últimos anos, principalmente pela sua aplicabilidade e eficiência em gerar soluções apresentando redução de custo e/ou distâncias. O objetivo geral foi otimizar o planejamento da atividade de inventário florestal a partir de um modelo PRV e avaliar a importância do uso desta técnica no rendimento das atividades. Dentre os fatores que influenciam neste rendimento, a dispersão espacial, característica básica dos povoamentos florestais, é um fator controlável a partir do uso de técnicas que possibilitem associá-lo ao planejamento. Estudos mostram que essa associação traz resultados significativos / On Forest field, studies in development of forest harvesting and transport still being the most emphasized subject, for being directly responsible for the final cost of wood. However, other different phases are a big potential for studies, as Forest Inventory. Information provided by the Forest Inventory are important for all planning of Forest Enterprise, as it bases any decision making involving forest resources. On this present research, was based on vehicle routing problem for planning this task. The vehicle routing problem and its variants has being largely studied on the last years, mainly for its applicability and efficiency for given solutions resulting in cost and distance reduction. The general objective of the present study is optimize the Inventory Forest planning from a vehicle routing problem and evaluate the importance of this technique on its productivity. Among the factors that influence this productivity, the spatial dispersion , basic feature of forest stands, it is one controllable factor from the use of technique that makes possible matches with planning. Studies shows that this match brings out significant results

[pt] Nas redes de fibras óticas, as informações são transmitidas na forma de um sinal luminoso através de uma fibra ótica. A tecnologia de multiplexação WDM permite a transmissão simultânea de vários sinais em um mesmo enlace. As conexões entre estações terminais são estabelecidas na forma de caminhos óticos, que são definidos em função de sua rota e do comprimento de onda no qual são multiplexados. Conversores de comprimentos de onda não são considerados neste trabalho. Conseqüentemente, os caminhos óticos devem permanecer com o mesmo comprimento de onda em todos os enlaces do transmissor ao receptor. O Problema de Roteamento e Atribuição Mínima de Comprimentos de Onda (min- RWA) consiste em estabelecer um conjunto de conexões entre pares de estações e atribuir um determinado comprimento de onda para cada uma delas, de forma que caminhos óticos que compartilhem algum enlace da rede tenham comprimentos de onda diferentes e que o número total de comprimentos de onda utilizados seja mínimo. Neste trabalho, uma nova heurística é proposta para min-RWA, onde k possíveis rotas são calculadas para cada conexão e, em seguida, uma rota (dentre as rotas pré-calculadas) e um comprimento de onda são atribuídos a cada conexão resolvendo-se um Problema de Coloração de Partições (PCP). O PCP é um problema de coloração em grafos particionados, ou seja, grafos onde os vértices estão particionados em subconjuntos disjuntos. O PCP consiste em selecionar e colorir um único vértice de cada subconjunto, de modo que dois vértices adjacentes, no grafo induzido pelos vértices selecionados tenham cores diferentes e que o número total de cores utilizadas seja mínimo. Nesta dissertação, são apresentadas e propostas novas heurísticas para PCP e min-RWA. Estas heurísticas são comparadas com as melhores conhecidas na literatura. / [en] In optical networks, the information is transmitted along the optical fibers as optical signals. Wavelength Division Multiplexing (WDM) allows more efficient use of the huge capacity of optical fibers, as far as it permits the simultaneous transmission of different channels along the same fiber, each of them using a different wavelength. The connections are established by lightpaths, in which the signal is converted to the optical domain and reaches the receptor without conversion to the electrical domain. A lightpath is defined by a route and a wavelength. We assume that wavelength conversion along a lightpath is not permitted, since this technology is not yet fully available. Therefore, each lightpath should use the same wavelength from the transmitter to the receiver. The Routing and Wavelength Assignment problem consists in routing a set of lightpaths and assigning a wavelength to each of them. All connection requirements are known beforehand and one seeks to minimize the total number of wavelengths used for routing these connections, so as that two lightpaths sharing a common link use different wavelengths. In this work, we propose a new heuristic in which min-RWA is solved by a combined approach involving the computation of alternative routes for the lightpaths, followed by the solution of a Parttion Coloring Problem (PCP). Given a graph where the vertex set is partitioned in disjoint susets, PCP consists in selecting and coloring only one vertex in each subset, so as that every two adjacent colored nodes have different colors and the total number of colors used is minimum. We present and propose new heuristics for PCP and min-RWA. Computational experiments are reported comparing the new heuristics and those which already appeared in the literature.