Incorporating Neighborhood Interactions and Vehicle Coordination in Bike Sharing Rebalancing with the X-PILOT Method

Abstract

Denne oppgaven undersøker effekten av nabolagsinteraksjoner og koordinering av servicebiler i bysykkelsystemer (BSS). På grunn av ujevn fordeling av etterspørselen mellom stasjonene i BSS, er det en betydelig utfordring for operatører å opprettholde balanse i systemene. Når stasjonene blir helt tomme eller fulle, kan brukerne enten gi opp forsøket på å hente ut en sykkel eller dra til nabostasjoner, noe som overfører etterspørselen. For å sikre et effektivt BSS, brukes servicebiler til å reallokere sykler mellom ubalanserte stasjoner. Disse operasjonene gjøres vanligvis i løpet av dagen i et dynamisk miljø, der usikkerhet i kundens etterspørsel skaper stokastisitet. For å håndtere kompleksitetene ved rebalansering under slike forhold, formulerer vi det dynamiske stokastiske bysykkelrebalanseringsproblemet med nabolagsinteraksjoner (DSBRPNI). En mangel i eksisterende forskning er identifisert, der interaksjoner mellom stasjoner ofte blir oversett. Derfor er hovedformålet med denne oppgaven å undersøke konsekvensene av nabolagsinteraksjoner, og å utvikle en løsningsmetode som hensyntar slike effekter.

For å løse dette beregningstunge problemet utvikler vi en metaheuristisk metode kalt Explorative Preferred Iterative LOokahead Technique (X-PILOT), som bygger på PILOT-metoden av Voß (2005). Anvendt på DSBRPNI kan vår metode effektivt løse problemet samtidig som viktige hensyn fra virkeligheten blir ivaretatt. X-PILOT unngår kortsiktighet ved å vurdere fremtidige implikasjoner av beslutninger ved bruk av lookahead-teknikker. Videre introduserer metoden en ny konstruksjonsalgoritme som muliggjør forbedret ressursbruk og utnyttelse av synergier i et system med flere servicebiler.

For å få en presis evaluering av kvaliteten på vår løsningsmetode, implementeres den i en diskret hendelsessimulator som etterligner virkelige BSS. Historiske data fra Trondheim Bysykkel, Bergen Bysykkel, Oslo Bysykkel og Citi Bike New York brukes til å generere realistiske testinstanser med varierende størrelser og etterspørselsmønstre. Vi forbedrer nøyaktigheten i simulatoren ved å introdusere en roaming-modul som avgjør om brukere drar til nabostasjoner når de ankommer tomme stasjoner. I tillegg foreslår vi en ny evalueringsmetode med mål om å gi presise vurderinger av systemets ytelse ved å hensynta roaming. Resultatene indikerer at den nye metoden kan gi betydelig ulike tolkninger sammenlignet med tradisjonelle metoder.

Beregningsstudien viser at valget av bredde-parameter i X-PILOT har betydelig innvirkning på løsningens kvalitet. Videre viser studien at lengre tidshorisonter fører til færre mislykkede hendelser, hvilket fremhever verdien av X-PILOT sine lookahead-funksjoner. Vi demonstrerer at løsningsmetoden har høy ytelse, og løser New York-instansen bestående av over 900 stasjoner og fem servicebiler på få sekunder.

Til slutt sammenlignes vår løsningsmetode med andre benchmark-metoder. X-PILOT presterer bedre enn de alternative metodene for alle instanser. Spesielt utmerker X-PILOT seg på koordinering av kjøretøy. Vi viser at marginalnytten med ekstra servicebiler er større for X-PILOT, noe som indikerer en mer koordinert tilnærming. Effekten av å hensynta nabolagsinteraksjoner i beslutningstakingen blir også evaluert. I små systemer med en høy grad av balanse er effekten ubetydelig. Imidlertid viser vi at inkludering av nabolagsinteraksjoner fører til færre mislykkede hendelser i større og mer ubalanserte systemer, som i Oslo og New York.

This thesis examines the dynamics of neighborhood interactions and coordination of service vehicles within bike sharing systems (BSSs). Due to uneven distribution of demand across stations in BSSs, keeping the systems in balance is a significant challenge for operators. As stations become fully starved or congested, users may either abandon their attempts to pick up a bike or opt for neighboring stations, causing a spillover of demand. To ensure an efficient BSS, service vehicles are utilized to redistribute bikes between imbalanced stations. These rebalancing operations normally take place within a dynamic environment throughout the day, with uncertainty in customer demand causing stochasticity. To address the complexities of rebalancing under such conditions, this thesis formulates the Dynamic Stochastic Bicycle Rebalancing Problem with Neighborhood Interactions (DSBRPNI). A gap in existing research is identified, wherein the interactions between stations are frequently overlooked. Therefore, the main purpose of this thesis is to investigate the impacts of neighborhood interactions and to develop a solution method that incorporates such effects.

To solve this computationally challenging problem, we develop a metaheuristic called the Explorative Preferred Iterative LOokahead Technique (X-PILOT), which builds on the PILOT method by Voß (2005). When applied to the DSBRPNI, our method can efficiently solve the problem while incorporating essential real-life considerations. X-PILOT seeks to avoid myopia by assessing the future implications of rebalancing decisions using lookahead techniques. Furthermore, the method features a novel construction algorithm that facilitates improved resource utilization and exploitation of synergies within a multi-vehicle system.

To evaluate the quality of our solution method accurately, it is implemented in a discrete-event simulator that emulates real BSSs. Historical data from Trondheim City Bike, Bergen City Bike, Oslo City Bike and Citi Bike New York is used to generate realistic test instances of varying sizes and demand patterns. We enhance the accuracy of the simulator by introducing a roaming module that determines whether users roam to neighboring stations when starved stations are encountered. Additionally, we propose a novel evaluation metric aimed at providing precise assessments of system performance by incorporating roaming. Results indicate that the new metric can provide significantly different interpretations compared to traditional metrics.

The computational study shows that the choice of branching width in X-PILOT significantly impacts solution quality. Furthermore, the study shows that longer time horizons lead to fewer failed events, highlighting the value of X-PILOT's lookahead feature. The solution method is proven to exhibit high computational performance, solving the New York instance consisting of over 900 stations and five service vehicles within few seconds.

Lastly, our solution method is compared to other benchmark policies. For all tested instances, X-PILOT outperforms the alternatives in terms of service rates. Specifically, X-PILOT excels in coordination of vehicles. We demonstrate that the marginal benefit of additional vehicles is greater for X-PILOT, indicating that a more coordinated approach is achieved. The effect of incorporating neighborhood interactions into decision making is also evaluated. In small systems with a high degree of unassisted balance, the effect is negligible. However, in larger and more imbalanced systems, we show that the incorporation of neighborhood interactions results in fewer failed events.