???item.export.label??? ???item.export.type.endnote??? ???item.export.type.bibtex???

Please use this identifier to cite or link to this item: http://tede.biblioteca.ufpb.br:8080/handle/tede/9255
???metadata.dc.type???: Dissertação
Title: Uma abordagem heurística para um problema de rebalanceamento estático em sistemas de compartilhamento de bicicletas
???metadata.dc.creator???: Albuquerque, Fabio Cruz Barbosa de 
???metadata.dc.contributor.advisor1???: Subramanian, Anand
???metadata.dc.description.resumo???: O Problema do Rebalanceamento Est atico de Bicicletas (Static Bike Rebalancing Problem, SBRP) e um recente problema motivado pela tarefa de reposicionar bicicletas entre esta c~oes em um sistema self-service de compartilhamento de bicicletas. Este problema pode ser visto como uma variante do problema de roteamento de ve culos com coleta e entrega de um unico tipo de produto, onde realizar m ultiplas visitas a cada esta c~ao e permitido, isto e, a demanda da esta c~ao pode ser fracionada. Al em disso, um ve culo pode descarregar sua carga temporariamente em uma esta c~ao, deixando-a em excesso, ou, de maneira an aloga, coletar mais bicicletas (at e mesmo todas elas) de uma esta c~ao, deixando-a em falta. Em ambos os casos s~ao necess arias visitas adicionais para satisfazer as demandas reais de cada esta c~ao. Este trabalho lida com um caso particular do SBRP, em que apenas um ve culo est a dispon vel e o objetivo e encontrar uma rota de custo m nimo que satisfa ca as demandas de todas as esta c~oes e n~ao viole os limites de carga m nimo (zero) e m aximo (capacidade do ve culo) durante a rota. Portanto, o n umero de bicicletas a serem coletadas ou entregues em cada esta c~ao deve ser determinado apropriadamente a respeitar tais restri c~oes. Trata-se de um problema NP-Dif cil uma vez que cont em outros problemas NP-Dif cil como casos particulares, logo, o uso de m etodos exatos para resolv^e-lo e intrat avel para inst^ancias maiores. Diversos m etodos foram propostos por outros autores, fornecendo valores otimos para inst^ancias pequenas e m edias, no entanto, nenhum trabalho resolveu de maneira consistente inst^ancias com mais de 60 esta c~oes. O algoritmo proposto para resolver o problema e baseado na metaheur stica Iterated Local Search (ILS) combinada com o procedimento de busca local variable neighborhood descent com ordena c~ao aleat oria (randomized variable neighborhood descent, RVND). O algoritmo foi testado em 980 inst^ancias de refer^encia na literatura e os resultados obtidos s~ao bastante competitivos quando comparados com outros m etodos existentes. Al em disso, o m etodo foi capaz de encontrar a maioria das solu c~oes otimas conhecidas e tamb em melhorar os resultados de inst^ancias abertas.
Abstract: The Static Bike Rebalancing Problem (SBRP) is a recent problem motivated by the task of repositioning bikes among stations in a self-service bike-sharing systems. This problem can be seen as a variant of the one-commodity pickup and delivery vehicle routing problem, where multiple visits are allowed to be performed at each station, i.e., the demand of a station is allowed to be split. Moreover, a vehicle may temporarily drop its load at a station, leaving it in excess or, alternatively, collect more bikes (even all of them) from a station, thus leaving it in default. Both cases require further visits in order to meet the actual demands of such station. This work deals with a particular case of the SBRP, in which only a single vehicle is available and the objective is to nd a least-cost route that meets the demand of all stations and does not violate the minimum (zero) and maximum (vehicle capacity) load limits along the tour. Therefore, the number of bikes to be collected or delivered at each station should be appropriately determined in order to respect such constraints. This is a NP-Hard problem since it contains other NP-Hard problems as special cases, hence, using exact methods to solve it is intractable for larger instances. Several methods have been proposed by other authors, providing optimal values for small to medium sized instances, however, no work has consistently solved instances with more than 60 stations. The proposed algorithm to solve the problem is an iterated local search (ILS) based heuristic combined with a randomized variable neighborhood descent (RVND) as local search procedure. The algorithm was tested on 980 benchmark instances from the literature and the results obtained are quite competitive when compared to other existing methods. Moreover, the method was capable of nding most of the known optimal solutions and also of improving the results on a number of open instances.
Keywords: Metaheurísticas
Bike-sharing
Roteamento de veículos
Coleta e entrega com múltiplas visitas
Metaheuristics
Bike-sharing
Vehicle routing
Split pickup and delivery
Iterated local search
???metadata.dc.subject.cnpq???: CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Language: por
???metadata.dc.publisher.country???: Brasil
Publisher: Universidade Federal da Paraíba
???metadata.dc.publisher.initials???: UFPB
???metadata.dc.publisher.department???: Informática
???metadata.dc.publisher.program???: Programa de Pós-Graduação em Informática
Citation: ALBUQUERQUE, Fábio Cruz Barbosa de. Uma abordagem heurística para um problema de rebalanceamento estático em sistemas de compartilhamento de bicicletas. 2016. 89 f. Dissertação (Mestrado em Informática)-Universidade Federal da Paraíba, João Pessoa, 2016.
???metadata.dc.rights???: Acesso Aberto
URI: http://tede.biblioteca.ufpb.br:8080/handle/tede/9255
Issue Date: 20-May-2016
Appears in Collections:Programa de Pós-Graduação em Informática

Files in This Item:
File Description SizeFormat 
arquivototal.pdfArquivo Total863.72 kBAdobe PDFDownload/Open Preview


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.