Banca de DEFESA: FÁBIO CRUZ BARBOSA DE ALBUQUERQUE

Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
DISCENTE: FÁBIO CRUZ BARBOSA DE ALBUQUERQUE
DATA: 20/05/2016
HORA: 14:00
LOCAL: Centro de Informática
TÍTULO: Uma abordagem heurística para um problema de rebalanceamento estático em sistemas de compartilhamento de bicicletas.
PALAVRAS-CHAVES: Meta-heurísticas. Bike-sharing. Roteamento de veículos. Coleta e entrega com múltiplas visitas. Iterated local search.
PÁGINAS: 80
GRANDE ÁREA: Ciências Exatas e da Terra
ÁREA: Ciência da Computação
SUBÁREA: Teoria da Computação
RESUMO: O problema do rebalanceamento estatico de bicicletas (static bike rebalancing problem, SBRP) e um recente problema motivado pela tarefa de reposicionar bicicletas entre estacoes em um sistema self-service de compartilhamento de bicicletas. Este problema pode ser visto como uma variante do problema do roteamento de veiculos com coleta e entrega de um unico tipo de produto, onde realizar multiplas visitas a cada estacao e permitido, i.e., a demanda da estacao pode ser fracionada. Alem disso, um veiculo pode descarregar sua carga temporariamente em uma estacao, deixando-a em excesso, ou, de maneira analoga, coletar mais bicicletas de uma estacao (ate mesmo todas elas), deixando-a em falta. Em ambos os casos sao necessarias visitas adicionais para satisfazer as demandas reais de cada estacao. Este trabalho lida com um caso particular do SBRP, em que apenas um veiculo esta disponivel e o objetivo e encontrar uma rota de custo minimo que satisfaca as demandas de todas as estacoes e nao viole os limites de carga minimo (zero) e maximo (capacidade do veiculo) durante a rota. Portanto, o numero de bicicletas a serem coletadas ou entregues em cada estacao deve ser determinado apropriadamente a respeitar tais restricoes. Trata-se de um problema NP-Dificil uma vez que contem outros problemas da mesma classe como casos particulares, logo, o uso de metodos exatos para resolve-lo e intratavel para instancias maiores. Diversos metodos foram propostos por outros autores, fornecendo valores otimos para instancias pequenas e medias, no entanto, nenhum trabalho resolveu de maneira consistente instancias com mais de 60 estacoes. O algoritmo proposto para resolver o problema e baseado na meta-heuristica iterated local search (ILS) combinada com o procedimento de busca local de descida em vizinhanca variavel com ordenacao aleatoria (variable neighborhood descent with random neighborhood ordering, RVND). O algoritmo foi testado em 980 instancias de referencia na literatura e os resultados obtidos sao bastante competitivos quando comparados com outros metodos existentes. Alem disso, o metodo foi capaz de encontrar a maioria das solucoes otimas conhecidas e tambem melhorar os resultados em um numero de instancias abertas.
MEMBROS DA BANCA:
Interno - 1859144 - ANAND SUBRAMANIAN
Interno - 1175878 - LUCIDIO DOS ANJOS FORMIGA CABRAL
Externo ao Programa - 000.000.000-00 - MANUEL IORI - UNIBO