Banca de DEFESA: FABIO CRUZ BARBOSA DE ALBUQUERQUE

Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
DISCENTE: FABIO CRUZ BARBOSA DE ALBUQUERQUE
DATA: 20/05/2016
HORA: 14:00
LOCAL: Centro de Informática
TÍTULO: A METAHEURISTIC APPROACH FOR THE STATIC REBALANCING PROBLEM IN BIKE-SHARING SYSTEMS
PALAVRAS-CHAVES: Metaheuristics. Bike-sharing. Vehicle Routing. Split Pickup and delivery. Interated 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: 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 from a station (even all of them), 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 find 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 variable neighborhood descent with random neighborhood ordering (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 finding most of the known optimal solutions and also of improving the results on a number of open instances.
MEMBROS DA BANCA:
Interno - 1859144 - ANAND SUBRAMANIAN
Interno - 1175878 - LUCIDIO DOS ANJOS FORMIGA CABRAL