[pt] A organização da operação do transporte marítimo pode ser descrita dentre três modelos: liner, industrial ou tramp. No setor de tramp, armadores buscam otimizar os lucros através de ganhos de capacidade e redução de custos, ao mesmo tempo em que atendem às demandas e às restrições colocadas pelos clientes, muitas vezes baseadas em contratos. O roteamento de navios se torna um tema relevante dado que disponibilidade e confiabilidade de datas são um grande diferencial, ainda mais no atual contexto de alta oferta de navios tramp no mercado e, consequentemente, fretes mais baixos. Assim, o objetivo desse trabalho é apresentar um modelo de programação inteira mista visando a maximização do lucro de viagens pertencentes a uma específica rota geográfica de uma empresa tramp. O problema trabalhado nessa dissertação é do tipo pick-up e delivery (coleta e entrega) com janelas de tempo, múltiplas cargas a bordo, frota heterogénea, cargas fracionadas entre navios, velocidades de navegação variáveis e termos de tempo de trânsito garantidos. Utilizando-se da otimização Branch-and-Bound, o modelo é comparado com programações mensal real feita de maneira empírica por profissionais experientes dessa empresa em que o modelo matemático gera soluções com reduções de até 7 por cento dos custos totais e desafiando paradigmas estabelecidos pelos programadores quando da realização do roteamento e programação dos navios. Tendo em vista tais resultados, o modelo se apresentou como oportunidade de implementação e melhoria do processo de programação dos navios e do nível de serviço junto aos clientes. / [en] The organization of the maritime transport operation can be defined among three models: liner, industrial or tramp. In the tramp sector, shipowners seek to optimize profits through capacity gains and cost savings, while meeting the demands and constraints placed by customers, often based on contracts. Vessel routing becomes as availability and reliability of dates is a great differential, especially in the current context of a high supply of tramp vessels in the market and, consequently, lower freight rates. Thus, the hereby objective is to present a mixed integer programming model aiming to maximize the profit of all voyages belonging to a specific geographical route of a tramp company. The problem solved with in this work can be defined as of pick-up and delivery with time windows, multiple cargoes on board, heterogeneous fleet, split loads, variable sailing speeds and guaranteed transit time terms. Using Branch-and-Bound optimization, the model is compared to actual monthly routing planning made empirically by experienced professionals of that company and the mathematical model generates solutions with reductions of up to 7 percent of total costs and challenging programmers established paradigms when routing and programming vessels. In view of these results, the model presented itself as an opportunity to be implemented and improve the vessel routing and planning process and level of service to customers.

[pt] O problema de Districting-and-routing é um problema estratégico no qual porções geográficas devem ser agregadas em regiões de entrega, e cada região de entrega possui um custo de roteamento estimado. Seu objetivo é de minimizar esses custos, além de garantir a divisão da região em distritos. A simulação para obter uma boa aproximação é muito custosa computacionalmente, enquanto mecanismos como buscas locais exigem que esse cálculo seja feito de forma muito eficiente, tornando essa estratégia de aproximação inviável para uma solução metaheurística. Grande parte das soluções existentes para esse problema utilizam de formulas de aproximação contínua para mensurar os custos de roteamento, funções essas que são rápidas de serem calculadas porém cometem erros significativos. Em contraste, propomos uma Rede Neural em Grafo (Graph Neural Network - GNN) que é usada como oráculo por um algoritmo de otimização. Nossos experimentos computacionais executados com dados de cidades do Reino Unido mostram que a GNN é capaz de produzir previsões de custos mais precisas em tempo computacional aceitável. O uso desse estimator na busca local impacta positivamente a qualidade das soluções, levando a uma economia de 10,35 por cento no custo de entrega estimado em relação a função Beardwood, que é comumente usada nesse cenários, e ganhos similares em comparação com outros métodos de aproximação. / [en] The districting-and-routing problem is a strategic problem in which basic geographical units (e.g., zip codes) should be aggregated into delivery regions, and each delivery region is characterized by a routing cost estimated over an extended planning horizon. The objective is to minimize the expected routing costs while ensuring regional separability through the definition of the districts. Repeatedly simulating routing costs on a set of scenarios while searching for good districts can be computationally intensive, so existing solution approaches for this problem rely on approximation functions. In contrast, we propose to rely on a graph neural network (GNN) trained on a set of demand scenarios, which is then used within an optimization approach to infer routing costs while solving the districting problem. Our computational experiments on various metropolitan areas show that the GNN produces accurate cost predictions. Moreover, using this better estimator during the search positively impacts the quality of the districting solutions and leads to 10.35 percent delivery-cost savings over the commonly-used Beardwood estimator and similar gains compared to other approximation methods.

[pt] Redes Manhattan Street (MS) têm sido descritas como um arranjo linear bidimensional de nós, semelhante à configuração de ruas e avenidas de Manhattan. O roteamento por deflexão é implementado encaminhando os pacotes que atingem um determinado nó a uma de suas saídas de forma síncrona ou assíncrona. O principal objetivo deste trabalho consiste na simulação e análise de redes totalmente ópticas configuradas segundo a topologia MS. O roteamento por deflexão e o assincronismo são considerados, para evitar complexidade eletrônica e armazenamento de pacotes no domínio óptico. Serão apresentadas as características das redes MS, suas propriedades estruturais e os parâmetros utilizados para analisar seu desempenho. Uma metodologia analítica dedicada a obtenção teórica destes parâmetros será introduzida. Serão apresentados alguns conceitos básicos sobre simulação de redes;diversas simulações da rede proposta utilizando os protocolos UDP e TCP; uma descrição do software que foi utilizado para realizar as simulações; uma comparação entre os resultados obtidos através da simulação e os obtidos através da metodologia analítica; e uma análise do efeito da latência na vazão do protocolo TCP. / [en] Manhattan Street (MS) Networks are bidimensional linear node sets arranged as the avenues and streets of Manhattan. The simulation and analysis of all-optical MS networks is the central target of this paper. In order to avoid using complex electronics and/or optical domain buffers, the deflection routing and the asynchronism are taken into account in the analysis. Deflection routing is performed by conveying incoming packets towards one of the two outputs. The characteristics of MS Networks are presented, along with their structural properties and the parameters used for performance analysis. An analytical methodology for the theoretical obtaining of these parameters is described. Some basic concepts on network simulation are discussed. Several simulations of the proposed network are presented, using both UDP and TCP protocols, and the software used for simulations is also described. The obtained results are compared and discussed with respect to the previously described analytic methodologies. Finally, the effect of network latency on the TCP-protocol throughput is assessed.

[pt] A indústria de transporte marítimo é essencial para o comércio internacional. No entanto, no despertar da crise financeira de 2008, essa indústria foi severamente atingida. Nessas ocasiões, empresas de transporte só são capazes de obter lucro se suas frotas forem roteadas de forma eficaz. Neste trabalho, nós estudamos uma classe de problemas de roteamento de navios relacionados ao Pickup and Delivery Problem with Time Windows. Para resolver esses problemas, nós introduzimos um método heurístico e um exato. O método heurístico é uma meta-heurística híbrida com uma vizinhança larga baseada em set partitioning, enquanto o método exato é um algoritmo de branch-and-price. Nós conduzimos experimentos em um conjunto de instâncias baseadas em rotas de navios reais. Os resultados obtidos mostram que nossos algoritmos superam as metodologias estado da arte. Em seguida, nós adaptamos o conjunto de instâncias para modelar um problema de roteamento de navios no qual a velocidade em cada segmento de rota é uma variável de decisão, e o consumo de combustível por unidade de tempo é uma função convexa da velocidade e carga do navio. A fim de resolver esse novo problema de roteamento de navios com otimização de velocidade, nós estendemos nossa meta-heurística para encontrar decisões de velocidade ótimas em toda avaliação de solução vizinha de uma busca local. Nossos experimentos demonstram que essa abordagem pode ser altamente rentável, e que requer apenas um aumento moderado de recursos computacionais. / [en] The shipping industry is essential for international trade. However, in the wake of the 2008 financial crisis, this industry was severely hit. In these times, transportation companies can only obtain profit if their fleet is routed effectively. In this work, we study a class of ship routing problems related to the Pickup and Delivery Problem with Time Windows. To solve these problems, we introduce a heuristic and an exact method. The heuristic method is a hybrid metaheuristic with a set-partitioning-based large neighborhood, while the exact method is a branch-and-price algorithm. We conduct experiments on a benchmark suite based on real-life shipping segments. The results obtained show that our algorithms largely outperform the state-of-the-art methodologies. Next, we adapt the benchmark suite to model a ship routing problem where the speed on each sailing leg is a decision variable, and fuel consumption per time unit is a convex function of the ship speed and payload. To solve this new ship routing problem with speed optimization, we extend our metaheuristic to find optimal speed decisions on every local search move evaluation. Our computational experiments demonstrate that such approach can be highly profitable, with only a moderate increase in computational effort.

[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.

[pt] O problema de Roteamento de Veículos com restrição de capacidade (CVRP) é um dos problemas mais estudados em Otimização Combinatória. Sendo uma generalização imediata do conhecido problema do Caixeiro Viajante, o CVRP tem atraído a atenção dos pesquisadores mais proeminentes da área desde os anos 60. Um dos algoritmos mais importantes para a sua resolução foi proposto no início dos anos 80 quando um algoritmo utilizando uma relaxação Lagrangeana particularmente adequada provou ser bastante superior aos algoritmos contemporâneos. Este algoritmo sugeriu a utilização de técnicas de geração de colunas que, nos anos seguintes até o início dos anos 90, assumiram o rótulo de melhor algoritmo para o CVRP. Finalmente, em meados dos anos 90, algoritmos de planos de corte apresentaram resultados que convenceram a comunidade de que esta deveria ser a abordagem para resolver os problemas mais difíceis de CVRP. Esta dissertação apresenta uma revisão deste algoritmos anteriores e propõe um formulação que permite reunir o melhor deles. O algortimo resultante, que pode ser rotulado como de branch-and-cut-and-price, trabalha com um número exponencial de variáveis e restrições que definem um espaço relaxado de soluções que corresponde à interseção dos espaços de solução relaxados utilizados pelos algoritmos anteriores. Esta dissertação também descreve um implementação especial do algoritmo de programação dinâmica para resolução do problema de geração de colunas. Estratégias para fazer um branching robusto também são discutidas. Tudo isso permite construir um algoritmo que é capaz de ter uma boa performance quando aplicado a diferentes classes de instâncias. A experiência computacional mostrou que a abordagem proposta obtém limites inferiores consistentemente melhores que os dos algoritmos anteriores. Mais ainda, permite resolver em tempo hábil diferentes tipos de instâncias de até 135 vértices, incluindo 18 que foram resolvidas pela primeira vez. / [en] The Capacitated Vehicle Routing problem (CVRP) has been one of the most studied problems in the field of Combinatorial Optimization. A straight forward generalization of the popular Travelling Salesperson problem, the CVRP has drawn attention of the most prominent researchers since the early 60`s. One of the most important algorithms appeared in the early 80`s when a suitable Lagrangean relaxation algorithm has demonstrated to be far better than the contemporary ones. This algorithm suggested the use of column generation algorithms that succeeded to become the best ones in the late 80`s and early 90`s. Finally, in the mid 90`s, cutting plane methods presented results that convinced the community that this should be the approach for solving the hardest CVRP problems. This dissertation presents an overview of those early algorithms and proposes a formulation that allows uniting the best contributions of them. The resulting algorithm, labeled as a branch-and-cut-and-price algorithm, deals with exponentially many variables and constraints that define a relaxed solution space that is the intersection of the relaxed solution spaces considered in the previous algorithms. The dissertation also describes a specially devised dynamic programming algorithm to solve the column generation subproblem and discusses robust branching strategies that altogether allowed to build an algorithm that perfoms well on several different classes of instances. The computational experience has shown that the approach here proposed leads to lower bounds superior than the previous ones. Moreover, it allowed to consistently solve instances with up to 135 vertices, including 18 that were solved for the first time.

[pt] Redes ópticas convencionais exigem conversão eletro-óptica em cada nó para roteamento adequado dos pacotes. Adicionalmente, recursos de gerenciamento relevantes são requisitados para auxiliar o roteamento. Neste trabalho, inteligência e funcionalidade são introduzidas na camada física de redes ópticas com topologia em malha de modo a prover um esquema eficiente de roteamento de portadoras ópticas e endereçamento de pacotes. No arranjo apresentado ocorre que: (a) nenhuma conversão optoeletrônica (O/E/O) torna-se necessária, exceto nos nós fonte e destinação; (b). recursos de gerenciamento são praticamente dispensados na camada física. Ao representar a rede por grafos, critérios de custo mínimo são atingidos. Em seguida, utilizam-se algoritmos que, em consonância com os custos mínimos, levam ao roteamento. A conectividade desejada é então introduzida, com os algoritmos seguindo a técnica de reutilização de capacidade dentro um mesmo comprimento de onda. Desta forma, os caminhos de luz são determinados englobando todos os pares de nós da rede. Chamamos este arranjo de SWRA (Smart Wavelength Routing Assignment) dado que cada portadora segue de forma passiva seu exato caminho na rede. A implicação é a sensível redução nos custos, tanto pelo lado dos conversores O/E/O, bem como pelo lado do gerenciamento da rede. Demonstra-se que este arranjo pode estar sujeito a colisão de dados em uma mesma portadora. Uma solução é apresentada pela introdução de buffers elétricos de baixo custo, dimensionados através de ferramentas estatísticas. / [en] In conventional optical networks, optoelectronic conversions are needed in each node for the sake of a proper packet routing. Simultaneously, intensive managing resources should be allocated to accomplish the routing task. The correct introduction of intelligence and functionality within the network physical layer may lead to some advantages over conventional networks. Two advantages are worthwhile be mentioning (a)-no optoelectronic conversions (O/E/O) are needed, except for the source and destination nodes, and (b)-management resources are practically unnecessary within the physical layer. As the network uses a graph representation, it is possible to reach minimal cost criteria. Next, coping with the minimal cost, suitable algorithms are used for proper wavelength routing. The desired connectivity is introduced, and the algorithms will lead to the technique of capacity reuse within the wavelength. In this way, light-paths are obtained, linking all network node pairs. We called this arrangement as SWRA (Smart Wavelength Routing Assignment), since within the network each wavelength follows its precise path in a passive way. The result appears as a significant cost reduction, which reflects the lack of O/E/O converters and on the use of less management gear. However, this arrangement may suffer occasional data collision within any wavelength. Hence, a solution to avoid this impairment is presented and described, using low-cost electric buffers. Additionally, the statistical evaluation of those buffers is supplied. / [es] Redes ópticas convencionales exigen conversión eletro- óptica en cada nodo para un adequado ruteamiento de los paquetes. Adicionalmente, se necesitan recursos relevantes de gerenciamiento para auxiliar el ruteamiento. En este trabajo, inteligencia y funcionalidad son introducidas en la camada física de redes ópticas con topología en malla a fin de proporcionar un esquema eficiente de roteamiento de portadoras ópticas y direccionamiento de paquetes. En el arreglo presentado sucede que: (a) no es necesaria ninguna conversión optoeletrónica (O/E/O), excepto en los nodos fuente y destino; (b). recursos de gerenciamiento son prácticamente dispensados en la camada física. Al representar la rede por grafos, es posible alcanzar criterios de costo mínimo. Enseguida, se utilizan algoritmos que, en consonancia con los costos mínimos, conducen al roteamiento. La conectividad deseada se introduce con los algoritmos siguiendo la técnica de reutilización de la capacidad dentro de la misma longitud de onda. De esta forma, los caminos de luz se determinan englobando todos los pares de nodos de la red. Este arreglo se denomina SWRA (Smart Wavelength Routing Asignment) dado que cada portadora sigue de forma pasiva su exacto camiño en la red. La implicación de este procedimento es uma sensible reducción de los costos, tanto por el lado de los conversores O/E/O, así como por el lado del gerenciamiento de la red. Se demuestra que este arreglo puede estar sujeto a colisión de dados en una misma portadora. Se presenta una solución introduciendo buffers eléctricos de bajo costo, dimensionados a través de herramientas estadísticas.

[pt] Neste trabalho apresenta-se parâmetros/critérios de qualidade de serviço em redes ópticas. Partindo-se da definição de qualidade, sua importância e relevância em telecomunicações, direciona-se a discussão para a relação cliente - fornecedor onde o cliente pode ser visto como um indivíduo, uma corporação ou uma operadora. A partir dos parâmetros/critérios definidos, as características gerais das redes ópticas são analisadas. Sobre um ponto de vista técnico, define-se, fatores para a obtenção da qualidade de serviço desejada. A tecnologia de múltiplo acesso óptico é introduzida e estuda-se o caso WDM não apenas por sua grande conformidade com a Qualidade e a filosofia das redes totalmente ópticas mas também pela sua perfeita adequação à redes de alta velocidade e às propostas para a implementação de Terabit Offices. O aspecto para a alocação de comprimento de onda e o roteamento da rede apresentam-se como núcleo do trabalho. Um algoritmo é desenvolvido e simulações computacionais são analisadas, considerando, também, os aspectos de gerência da rede. Devido às relevâncias econômica e tecnológica das questões discutidas, perspectivas e tendências futuras são apresentadas. / [en] This work identifies some quality of service parameters / criteria to all optical networks. Starting with some definitions and the importance of quality in telecommunication the relationship between customer and supplier is analyzed. Next, the optical networks are studied. By using a technical vision, the main factors concerning quality are presented. The multiple access technology is introduced and WDM cases are more deeply studied, nor only by the great conformance with the quality aspects and all optical networks philosophy, but also for its match with the high speed networks and Terabit Offices implementation. The wavelength assignment and the routing problem are presented as they are the main point of this work. An algorithm is developed and a simulation is carried out considering the network management aspects. Due to the economical e technological importance of the subject, future trends are also presented.

[pt] O transporte escolar é fundamental para garantir o acesso e permanência dos alunos nas escolas públicas, principalmente nas áreas rurais, onde os estudantes estão localizados em uma grande área com baixa densidade e as estradas encontram-se em situações precárias. O presente trabalho tem como objetivo aplicar a metaheurística Iterated Local Search para o roteamento de 13.664 alunos da zona rural do estado do Rio de Janeiro. Para isso, considerouse o problema de roteamento de veículo escolares, do inglês School Bus Routing Problem (SBRP), com frota heterogênea e escola única, com o objetivo de minimizar o custo total considerando as restrições de capacidade dos veículos e distância máxima de percurso. Para aplicação do método, foram considerados os dados fornecidos pela Secretaria de Estado de Educação do Rio de Janeiro (SEEDUC-RJ). Os resultados são apresentados em dois cenários, o primeiro considera os dados de 79 rotas utilizadas pela SEEDUC-RJ para comparação dos resultados obtidos com o ILS. O método mostrou uma redução de 40,5 por cento no custo médio das rotas e 46 or cento na quilometragem média por aluno. O segundo cenário considera o roteamento da totalidade dos alunos, que foram divididos em 506 instâncias considerando escola e turno. A maior instância roteada possui 534 alunos. Os resultados consolidados por município são apresentados e mostram a concentração de municípios com maior custo médio por rota no noroeste fluminense. A implementação das rotas propostas pode trazer economia significativa com as despesas relacionadas ao transporte escolar rural, além de indicar um aumento no nível de serviço para os estudantes, com redução da quilometragem média por aluno. / [en] School transport is essential to ensure access and permanence of students in public schools, especially in rural areas, where students are located in a large area with low density and roads are in precarious conditions. This work aims to apply the Iterated Local Search metaheuristic to route 13.664 rural students in the state of Rio de Janeiro. For this, we considered the School Bus Routing Problem (SBRP), with heterogeneous fleet and single school, in order to minimize the total cost considering the vehicles capacity constraints and maximum travel distance. To apply the method, the data provided by Secretaria de Estado de Educação do Rio de Janeiro (SEEDUCRJ) were considered. The results are presented in two scenarios, the first considers data from 79 routes used by SEEDUC-RJ to compare the results obtained with the ILS. The method showed a reduction of 40.5 percent in the average cost of routes and 46 percent in the average mileage per student. The second scenario considers the routing of all students, who were divided into 506 instances considering school and shift. The largest routed instance has 534 students. The results consolidated by municipality are presented and show the concentration of municipalities with the highest average cost per route in northwestern Rio de Janeiro. The implementation of the proposed routes can bring significant savings with expenses related to rural school transport, in addition to indicating an increase in the level of service for students, with a reduction in the average mileage per student.

[pt] Serviços Médicos de Emergência (SME) proveem ajuda essencial a pessoas em situações de emergência, através de atendimento com primeiros socorros e transporte para unidades de saúde. Sistemas SME devem utilizar da melhor maneira possível seus recursos limitados de atendimento. Esse desafio já foi amplamente estudado por pesquisadores, na forma de problemas de roteamento de veículos, tanto estáticos quanto dinâmicos. No presente trabalho, estudamos um problema estático de roteamento de ambulâncias, cujo objetivo é minimizar o tempo ponderado de espera dos pacientes. O problema considera também o tempo acumulado de espera, restrições de compatibilidade de ambulâncias a serviços, seleção de pacientes, redirecionamento de ambulâncias e redistribuição de ambulâncias. Implementamos um algoritmo exato usando Branch and Price e uma formulação do problema como uma Partição de Conjuntos, usando código aberto. Estudamos os resultados obtidos com esse algoritmo e os comparamos com métodos heurísticos online estudados anteriormente. Para tal, utilizamos dados obtidos do SAMU da cidade do Rio de Janeiro. Os resultados possibilitam a avaliação do valor de informação perfeita nesse contexto e proveem resultados comparativos para embasar o futuro desenvolvimento de algoritmos online. / [en] Emergency Medical Service (EMS) systems provide life-saving support to people in emergency situations via first aid treatment and emergency transport to medical facilities. Such systems must strive to make the best use of their limited resources; they have thus been studied in the context of static and dynamic vehicle routing problems. In this work, we study a static ambulance routing problem aiming to minimize the weighted sum of patients waiting time while considering ambulance compatibility, patients priorities, ambulance redirection, and ambulance reassignment. We implement an exact Branch-andPrice algorithm over a Set Partitioning Formulation, study the results of this algorithm, and compare them to previously studied online heuristics using data from Rio de Janeiro s public SAMU system. The results obtained allow us to assess the value of perfect information in such systems, providing a comparative baseline for subsequent developments of online algorithms.