Submitted by Fernando Souza (fernandoafsou@gmail.com) on 2017-08-15T11:46:12Z
No. of bitstreams: 1
arquivototal.pdf: 884446 bytes, checksum: 92314027dddef8365b4a2e655b65bd78 (MD5) / Made available in DSpace on 2017-08-15T11:46:13Z (GMT). No. of bitstreams: 1
arquivototal.pdf: 884446 bytes, checksum: 92314027dddef8365b4a2e655b65bd78 (MD5)
Previous issue date: 2016-05-20 / 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. / 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.
| Identifer | oai:union.ndltd.org:IBICT/oai:tede.biblioteca.ufpb.br:tede/9255 |
| Date | 20 May 2016 |
| Creators | Albuquerque, Fabio Cruz Barbosa de |
| Contributors | Subramanian, Anand |
| Publisher | Universidade Federal da Paraíba, Programa de Pós-Graduação em Informática, UFPB, Brasil, Informática |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFPB, instname:Universidade Federal da Paraíba, instacron:UFPB |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | 4679641312648529202, 600, 600, 600, 7879657947546587587, 3671711205811204509 |
Page generated in 0.0028 seconds