PROGRAMA DE PÓS-GRADUAÇÃO EM INFORMÁTICA (PPGI)
UNIVERSIDADE FEDERAL DA PARAÍBA
- Telefone/Ramal
-
Não informado
Notícias
Banca de QUALIFICAÇÃO: FABIO CRUZ BARBOSA DE ALBUQUERQUE
Uma banca de QUALIFICAÇÃO de MESTRADO foi cadastrada pelo programa.
DISCENTE: FABIO CRUZ BARBOSA DE ALBUQUERQUE
DATA: 20/08/2015
HORA: 16: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. Multiple visits. Pickup and delivery.
PÁGINAS: 36
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 is a special case of the Capacitated Vehicle Routing Problem (CVRP) with pick-up and delivery of one commodity, the bikes. Yet, the demands of each station are allowed to be split into multiple visits. This work focuses on the part of the problem that aims to find the number of bikes to be picked up or delivered at each station by single-vehicle and the associated minimal cost route for a set of stations. Another particularity is that vehicle may arbitrarily drop its load at a station, leaving it in excess or, alternatively, pick more bikes from a station, even all of them, leaving it in default; both cases require later visits to balance stations inventory to their demands. 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. This work aims to develop a heuristic approach for the SBRP, based on the Iterated Local Search (ILS) metaheuristic combined with a Variable Neighborhood Descent with Random neighborhood ordering (RVND) as local search procedure. The algorithm is tested in a set of instances from the literature and preliminary results are competitive when compared to other approaches.
MEMBROS DA BANCA:
Presidente - 1859144 - ANAND SUBRAMANIAN
Interno - 1175878 - LUCIDIO DOS ANJOS FORMIGA CABRAL
Externo à Instituição - MANUEL IORI
Externo à Instituição - PUCA HUACHI VAZ PENNA