Novo Seminário CIO

Column Generation in Routing: Classical CVRP and Transport of Oil Rig Crews - Marcus Poggi (PUC-Rio)

05/06/2014, 15:00, Sala 6.4.31, Piso 4, Edf. C6, DEIO-FCUL

Abstract: Routing problems are naturally formulated by enumerating possible routes and combining them to derive an improved solution. This combination is done by solving a set partitioning problem that assures the set of chosen routes to visit all routing customers exactly once. Column generation techniques allow implicitly considering a huge number of routes and, when searching for an optimal solution, to consider all possible ones. This talk presents a real world application of column generation to the crew transportation from and to offshore oil rigs. The resulting algorithm solves an initial mixed integer program, that is followed by a column generation phase and finally executes a post processing. Details such as the allocation of the helicopter pilot lunch time are considered. This logistic deals daily with over 2000 passengers and more 40 helicopters of different types. The main goal is to increase the global safety by minimizing the number of offshore landings. Next, the talk proceeds to showing the key elements of state-of-the-art algorithms to optimally solve the classical capacitated vehicle routing problem (CVRP). In particular, the effect of the addition of bound improving polyhedral cuts to the set partitioning formulation on the subproblem, known as pricing problem, of finding improving routes/columns. An efficient resolution of the pricing all along the resulting branch-cut-and-price algorithm run is key to its overall performance. The careful choice of the columns to price and of the cuts to consider may allow solving to optimality CVRP instances of up to 360 customers.

O que fazem e o que pensam alguns membros da comunidade de Ciências? O nono Dictum et factum é com Carla Romero, técnica superior do Gabinete de Estudos Pós-graduados da Unidade Académica de Ciências.

A descoberta da localização precisa de uma espécie de GPS (Global Positioning System) no nosso cérebro (Moser e Moser, 2014), capaz de nos ajudar a responder a duas perguntas básicas “Onde estamos?” e “Como vamos até acolá?”, indispensáveis para a nossa vida normal, estimulou a discussão do tema computação espacial (ler a revista norte americana Communications Of the ACM, janeiro de 2016, páginas 72-81).

Joaquim Alves Gaspar, de 67 anos, investigador pós-doutoral do Centro Interuniversitário de História das Ciências e da Tecnologia, acaba de ser distinguido com uma Starting Grant do Conselho Europeu de Investigação, a primeira a ser atribuída a um membro da Faculdade de Ciências da Universidade de Lisboa. Em entrevista a Ciências apresenta o projeto “The Medieval and Early Modern Nautical Chart: Birth, Evolution and Use” alvo desta distinção, no valor de 1,2 milhões de euros, bem como o homem que pretende causar um impacto significativo na História da Cartografia, demonstrando a eficácia das suas ferramentas e ajudando a criar uma nova geração de cientistas nesta área.

O Conselho Europeu de Investigação atribuiu uma Starting Grant, no valor de 1,2 milhões de euros, a Joaquim Alves Gaspar, membro integrado do Centro Interuniversitário de História das Ciências e da Tecnologia (CIUHCT) e investigador principal do projeto “The Medieval and Early Modern Nautical Chart: Birth, Evolution and Use”.

"No momento atual o alerta de potencial erupção ainda não terminou uma vez que a atividade sísmica se mantém acima dos valores normais", escreve José Madeira em mais uma crónica de viagem.

"Comunicar significa tornar comum. E o que queremos tornar comum? Ciência. Esse é o objetivo", escreve em artigo de opinião Manuel Leite Valença.

César Garcia, curador convidado do Museu Nacional de História Natural da Universidade de Lisboa, investigador do cE3c e antigo aluno de Ciências, é o autor de uma das fotografias premiadas, escolha do editor, no âmbito da 4.ª edição do BMC Ecology Image Competition, uma iniciativa da BioMed Central.

A equipa da UNDAC (United Nations Disaster Assessment and Coordination)/ERCC (European Response Coordination Centre) da Comissão Europeia (CE) tem feito avaliação dos planos de emergência existentes e suas lacunas ou melhoramentos necessários, bem como reuniões com os principais agentes intervenientes a nível local em caso de catástrofe ou emergência.

Cerca de 60 alunos da EB1 S. João de Brito,  Agrupamento de Escolas de Alvalade, visitaram em julho passado o Departamento de Biologia Animal de Ciências.

Desde a chegada da equipa UNDAC/ERCC a sismicidade tem-se mantido em níveis estáveis após dois dias iniciais em que se tinha tornado progressivamente mais superficial (1 km abaixo do nível do mar).

O que fazem e o que pensam alguns membros da comunidade de Ciências? O oitavo Dictum et factum é com Vera Lopes, técnica superior do Departamento de Geologia de Ciências.

Os vencedores do galardão desenvolveram o melhor projeto de Net Zero Energy House.

Há espírito empreendedor nos corredores de Ciências e a prová-lo esteve a prestação dos alunos de Ciências e do ISCTE-IUL na Sessão Final da Disciplina de Projeto Empresarial.

Cerca de 14 alunos do ensino secundário decidiram passar uma semana das suas férias a frequentar a Escola de Verão de Energia, organizada pelos professores e alunos do mestrado integrado de Engenharia da Energia e do Ambiente, e que já vai na sua segunda edição.

Pedro Veiga, Luís Correia e Teresa Chambel, professores do Departamento de Informática (DI) de Ciências, participaram no primeiro E-Tech Portugal, ocorrido no início de junho de 2016, em Setúbal.

A racionalidade (homem racional) é inalcançável, porque a escolha ótima (identificada a maior parte das vezes com a utilidade máxima individual) é demasiado perfeita.

De acordo com o comunicado de imprensa emitido pela faculdade esta segunda-feira, para os investigadores a identificação de novos alvos moleculares é essencial para definir estratégias terapêuticas cada vez mais robustas nos doentes com fibrose quística. Entrevista com Carlos Farinha.

Participantes no laboratório

“A Química e os segredos de um chocolate perfeito”, “Olhando os átomos”, “A diversidade escondida dos oceanos: do microscópio ao DNA” e “As bactérias e a resistência a antibióticos” são só alguns exemplos dos projetos disponíveis no âmbito do

A Galeria Ciências é um espaço recente, dinâmico, polivalente, com grandes potencialidades.

José Pica

O que fazem e o que pensam alguns membros da comunidade de Ciências? O sétimo Dictum et factum é com José Pica, assistente técnico do Departamento de Biologia Vegetal de Ciências.

Crónica de Fernando Barriga e Sofia Martins, investigadores do IDL Ciências, em missão oceanográfica no Atlântico - TAG hydrothermal field.

A 2.ª corrida de carros solares tripulados em Portugal ocorre este sábado, 9 de julho de 2016, entre as 10h00 e as 14h00, no campus da Faculdade de Ciências da Universidade de Lisboa.

Gerson Miguel da Silva Lobo, estudante do 2.º ano do mestrado de Bioquímica, faleceu a 26 de junho de 2016. A Faculdade de Ciências da Universidade de Lisboa lamenta o triste acontecimento, apresentando as condolências aos familiares, amigos e colegas do Gerson Lobo.

A gestão das preferências tornou-se numa facilidade ao dispor do projetista e do programador, e o planeamento (relacionado com as ações ao longo do tempo) é capaz de transformar um problema como se de otimização se tratasse, sujeito a restrições, a objetivos múltiplos e a efeitos probabilísticos das ações.

Crónica de Fernando Barriga e Sofia Martins, investigadores do IDL Ciências, em missão oceanográfica no Atlântico - TAG hydrothermal field.

Páginas