Titulo Estágio
Algorithmic Portfolio for Static Route Optimization
Áreas de especialidade
Sistemas Inteligentes
Engenharia de Software
Local do Estágio
Accenture (Lisboa)
Enquadramento
Na área de negócio da Logística, um conhecido problema de optimização é o Vehicle Routing Problem (VRP) que consiste numa generalização do Travelling Salesman Problem: dado um ponto central de distribuição de items, e uma lista de pontos de entrega dos mesmos, pretende-se descobrir qual a combinação óptima de rotas, cada uma delas por si só também optimizada, que minimiza algum critério (e.g. custo, tempo de distribuição, número de rotas, etc.). Não existem soluções algorítmicas conhecidas para o VRP que produzam resultados óptimos em tempo útil, dada a sua elevada complexidade computacional (NP-hard). Não obstante, este continua a ser um problema muito pertinente na indústria e várias abordagens heurísticas têm sido tentadas com o objectivo de obter a melhor aproximação possível.
Objetivo
O principal objectivo deste trabalho de Mestrado é desenhar e desenvolver uma ferramenta composta por um portfólio de algoritmos heurísticos alternativos que, para cada instância do problema dado, produza a melhor combinação de rotas de acordo com os vários algoritmos alternativos. Deverão ser consideradas e exploradas técnicas algorítmicas diversas e complementares entre si, nomeadamente Local Search, Ant Colony Optimization, métodos baseados em técnicas de Branch-and-Bound e em Cluster-First Route-Second, entre eventualmente outras a investigar.
O trabalho encontra-se dividido nos seguintes sub-objectivos:
1. Análise manual dos dados e sua ingestão
2. Investigação dos melhores métodos algorítmicos heurísticos para resolução do VRP
3. Especificação da arquitectura da solução, suas componentes e interfaces, estruturas de dados e algoritmos necessários para cumprir todos os requisitos;
4. Implementação dos vários métodos selecionados
5. Implementação do mecanismo de selecção dinâmica da solução por instância do problema
6. Validação da solução e sua generalidade
7. Análise de complexidade dos algoritmos e comparação da performance do sistema contra ferramentas existentes para resolver problemas compatíveis com esses sistemas;
8. Packetização da solução num WebService para fácil reutilização
9. Publicação: para além da escrita da tese e de um breve manual do utilizador, dependendo da qualidade dos resultados obtidos, poderá esperar-se a colaboração na submissão de um pedido de patente ou de artigo científico para publicação descrevendo o sistema implementado e sumarizando os principais resultados.
Plano de Trabalhos - Semestre 1
Para cumprir os objectivos acima, o trabalho será dividido nas seguintes tarefas:
Tarefa T1 — Análise manual dos dados e sua ingestão
* Período: Setembro 2018
* Descrição: Análise manual dos dados e sua ingestão para um formato uniforme a definir pelo aluno.
* Output: Especificação de Requisitos. Primeiras versões das subsecções de “Background”, “Motivation” e “Objectives” da secção “Introduction” do artigo/pedido de patente a ser submetido.
Tarefa T2 — Investigação dos melhores métodos algorítmicos heurísticos para resolução do VRP
* Período: Outubro 2018
* Descrição: Procura, análise e comparação dos vários métodos algorítmicos heurísticos para resolução do VRP
* Output: Estudo comparativo dos métodos conhecidos de resolução do VRP.
Tarefa T3 — Especificação da arquitectura da solução
* Período: Outubro-Novembro 2018
* Descrição: Especificação da arquitectura da solução. Especificação das várias estruturas de dados, métodos e algoritmos de optimização a implementar. Especificação do mecanismo de integração das soluções alternativas e de escolha da melhor para cada instância do problema. Definição de objectivos intermédios e plano detalhado.
* Output: Arquitectura. Primeira versão da secção “Approach” do artigo/pedido de patente a ser submetido. Plano de trabalho detalhado.
Tarefa T4 — Relatório intermédio
* Período: Dezembro 2018
* Descrição: Escrita do Relatório intermédio.
* Output: Relatório intermédio
Plano de Trabalhos - Semestre 2
Tarefa T5 — Revisões
* Período: Janeiro 2019
* Descrição: Ajustamento do plano de trabalhos e revisão do relatório incluindo as indicações do júri da defesa intermédia.
* Output: Objectivos, relatório e plano de trabalhos detalhado revistos.
Tarefa T6 — Implementação e Validação
* Período: Janeiro-Abril 2019
* Descrição: Implementação dos vários métodos selecionados. Implementação do mecanismo de selecção dinâmica da solução por instância do problema. Validação da solução e sua generalidade.
* Output: Sistema implementado, testado e validado. Primeira versão da descrição da secção “Implementation Principles” do artigo/pedido de patente a ser submetido.
Tarefa T7 — Packetização da solução num WebService para fácil reutilização
* Período: Maio 2019
* Descrição: Wrapping da ferramenta num WebService facilmente invocável e reutilizável
* Output: WebService de VRP optimization
Tarefa T8 — Comparação e Publicação
* Período: Abril-Maio 2019
* Descrição: Análise de complexidade dos algoritmos e comparação da performance do sistema contra ferramentas existentes para resolver problemas compatíveis com esses sistemas. Escrita e submissão da versão final do artigo, ou escrita da versão preliminar do pedido de patente.
* Output: Comparação detalhada de performance. Primeira versão da secção “Comparisons” do artigo a ser submetido. Versão final do artigo a ser submetido/preliminar do pedido de patente a ser submetido.
Tarefa T9 — Escrita da Tese
* Período: Janeiro-Maio 2019
* Descrição: Escrita do documento da Tese
* Output: Tese de Mestrado
Condições
O trabalho decorrerá na Accenture em Lisboa, sendo que o(a) aluno(a) usará um computador portátil da Accenture. O estágio terá uma remuneração mensal de 800€ de bolsa durante a duração (9 meses) do estágio. Este estágio tem a co-orientação do Prof. Luís Paquete, do DEI.
Observações
Os candidatos deverão cumprir os seguintes requisitos mínimos:
* Conhecimentos sólidos sobre algoritmia avançada, com especial interesse em problemas de optimização NP-hard
* Excelentes conhecimentos de programação
* Fluência em inglês
Orientador
Alexandre Miguel dos Santos Martins Pinto e Doutor Luís Paquete
alexandre.pinto@accenture.com 📩