Dissertação

{pt_PT=Planning Nightly Rebalancing in Bike Sharing Systems: GIRA case study} {} EVALUATED

{pt=Actualmente, quase todas as grandes cidades têm alguma rede de bicicletas partilhadas. Porém, fluxos de utilização assimétricos deixam a rede desequilibrada: algumas estações têm excesso de bicicletas, impedindo o estacionamento dos utilizadores que chegam, e outras não têm suficientes para satisfazer a procura. Tipicamente, uma ou mais carrinhas reposicionam as bicicletas de modo a que a rede retome o estado de equilíbrio. É em optimizar a rota destas carrinhas que consiste o denominado “Bike Rebalancing Problem” (BRP). Este trabalho avaliou algumas das formulações existentes para resolver o BRP e seleccionou aquela que considerou melhor se ajustar à rede de Lisboa, a GIRA, o caso de estudo em causa. Foram feitas generalizações à formulação MILP escolhida, de modo a que fossem considerados os diferentes tipos de veículos e bicicletas, a autonomia de cada veículo e a duração da sua rota e as estações que não requerem uma acção de reposicionamento mas sim de inspecção. Além disso, introduziu-se no modelo a possibilidade de temporariamente guardar bicicletas numa estação intermédia da rota, como forma de contornar as restrições impostas pelos limites de capacidade dos veículos. Após estudar a incorporação de alguns simples procedimentos de aceleração do processo, o modelo, resolvido num esquema de Branch-and-Cut, recalculou as rotas de cinco datas do caso de estudo e comparou-as com aquelas que foram efectivamente decididas, tendo obtido, em tempo útil, diminuições no comprimento total da rota entre os 30% e os 75%. , en=Nowadays, almost all major cities have some variant of a Bike Sharing System. However, asymmetric usage flows leave the network unbalanced: some stations have an excess of bikes, preventing the parking of incoming users, while others do not have enough to meet the demand. Typically, one or more vans reposition bikes so that the network returns to a steady state. It is in optimizing the route of these vans that consists of the so-called "Bike Rebalancing Problem" (BRP). This work evaluated some of the existing formulations to solve the BRP and selected the one considered the best fitting for the Lisbon case study, the GIRA network. The chosen MILP formulation has been generalized, in order to take into account the different types of vehicles and bicycles, the autonomy of each vehicle, the duration of its route and the stations that do not require repositioning but inspection actions. Besides, the possibility of temporarily storing bicycles at an intermediate route station has been introduced in the model, as to relax the restrictions imposed by the vehicles’ capacity. After studying the incorporation of some simple acceleration procedures, the model, solved in a Branch-and-Cut scheme, recalculated under an established time-stretch the routes of five case study instances. Comparing the results with the routes that were actually performed, a 30% to 75% decrease in the total length has been verified for every instance. }
{pt=Bicicletas partilhadas, Bike Rebalancing Problem, Reposicionamento, Optimização, MILP, Branch-and-Cut, en=Bike Sharing Systems, Bike Rebalancing Problem, Repositioning, Optimization, MILP, Branch-and-Cut}

Julho 11, 2019, 16:45

Orientação

ORIENTADOR

António Ramos Andrade

Departamento de Engenharia Mecânica (DEM)

Professor Auxiliar

ORIENTADOR

José Maria Campos da Silva André

Departamento de Engenharia Mecânica (DEM)

Professor Auxiliar