Rebalancing and Charging Strategies in Electric Bike Sharing Systems - A Two-Stage Stochastic Programming Column Generation Heuristic

Abstract

Denne oppgaven undersøker hvordan man kan maksimere kundetilfredshet i et elektrisk bysykkelsystem ved bruk av servicebiler som utfører batteribytter og rebalansering av sykler. I et elektrisk bysykkelsystem tilbys elektriske sykler for korttidsleie mellom stasjoner innenfor et bestemt geografisk område. Gjennomførte turer kan potensielt forårsake problemer i et bysykkelsystem, for eksempel ved at stasjoner tømmes for sykler, eller at stasjoner fylles opp og hindrer andre kunder fra å parkere. For å redusere forekomsten av slike tilfeller, benyttes gjerne et sett av servicebiler som kan reallokere sykler mellom stasjoner i løpet av dagen. Behovet for operasjonell beslutningsstøtte er større i et elektrisk bysykkelsystem sammenlignet med et tradisjonelt bysykkelsystem, da beslutningene også skal sørge for at syklene er ladet til enhver tid.

Oppgaven fokuserer på hvordan et ladet og balansert system kan oppnås ved bruk av batteribytter i kombinasjon med rebalansering av sykler mellom ladestasjoner og stasjoner uten lademulighet. Problemet som løses er definert som the Dynamic Stochastic Bicycle Rebalancing and Charging Problem (DSBRCP). Tidligere arbeid utført av Fosen og Haldorsen (2019) viser at eksakte løsningsmetoder ikke skalerer godt nok for å kunne løse problemet for realistiske størrelser av bysykkelsystemer innen rimelig tid. Basert på dette introduserer og implementerer vi en to-stegs stokastisk kolonnegenereringsheuristikk, som gjør det mulig å løse DSBRCP for bysykkelsystemet i Oslo på under ett minutt. Heuristikken skal fungere som et beslutningsverktøy for operasjonelle beslutninger i elektriske bysykkelsystemer.

DSBRCP-heuristikken består av tre steg: (1) Initialisere ruter og patterns, (2) Løse subproblem og (3) Løse masterproblemet. Første steg er implementert heuristisk, mens andre og tredje trinn løses til optimalitet. I første steg genereres et sett av rute- og pattern-kombinasjoner ved bruk av en forgreningsalgoritme. Hver av de initialiserte kombinasjonene får en poengsum ved å løse subproblemet for et bestemt scenario av kundeankomster i steg to. Kombinasjonen av rute, pattern og poengscore fra subproblemet utgjør en kolonne. Masterproblemet i steg tre kombinerer kolonnene for å finne de optimale beslutningene for hver servicebil, koordinert på tvers av alle biler.

Som inspirasjon til utvikling av heuristikken, presenteres en oversikt over tidligere publisert litteratur relatert til emnet. Forfatterne er ikke kjent med at DSBRCP er studert tidligere. Problemet overlapper imidlertid markant med det mye utforskede rebalanseringsproblemet i tradisjonelle bysykkelsystemer. De viktigste forskjellene mellom rebalanseringsproblemet i tradisjonelle bysykkelsystemer og DSBRCP er innføringen av depot, ladestasjoner og batteribytteaktiviteter – og implikasjonene dette får for de operasjonelle beslutningene i sin helhet. Vårt bidrag med denne masteroppgaven er dermed å utvide rebalanseringsproblemet til å også inkludere ladebeslutninger.

Data fra bysykkelsystemet i Oslo, som opereres av Urban Infrastructure Partners (UIP), er brukt til å lage et simuleringsrammeverk. Simuleringen skal etterligne realistiske kundeinteraksjoner i et bysykkelsystem i løpet av en dag. Dette brukes som et hjelpemiddel for å bedømme den langsiktige kvaliteten på operasjonelle beslutninger som gjennomføres i systemet. Dette gjøres ved å måle antall kundeforespørsler som ikke kan oppfylles i løpet av en dag. Et eksempel på et slikt tilfelle er en kunde som ønsker å starte en tur fra en stasjon uten sykler. Simuleringsrammeverket gir også mulighet for å vurdere alternative lade- og rebalanseringsstrategier mot hverandre. I tillegg til den to-stegs stokastisk kolonnegenereringsheuristikken (DSBRCP-heuristikk), introduseres to alternative heuristikker; en strategi uten bruk av servicebiler, og en strategi inspirert av UIPs nåværende tilnærming til rebalansering. Analyser viser at DSBRCP-heuristikken er i stand til å forhindre 50% flere tilfeller av uoppfylte kundeforespørsler målt mot den UIP-inspirerte strategien når fem bilder opererer i systemet. Forbedringen tilsvarer en reduksjon på 23.3% fra et system uten drift av servicebiler.

This thesis explores the utility of combining battery swaps and bike relocation efforts by means of service vehicles in an electric bike sharing system (BSS). In an electric BSS, electric bikes are available for short-term rent between stations located in a defined geographical area. With time, customer trips cause potential problems in a BSS related to e.g. flat batteries or accumulation of bikes in some parts of the system. This prompts the need for effective charging solutions and bike relocation strategies to maintain an efficient BSS that displays high levels of customer satisfaction.

There are several possible approaches to maintain an efficient electric BSS; this thesis focuses on how a charged and balanced system may be achieved using battery swaps in combination with relocation of bikes between charging and non-charging stations. The problem is defined as the Dynamic Stochastic Bicycle Rebalancing and Charging Problem (DSBRCP). In previous work conducted by Fosen and Haldorsen (2019) on a simpler version of the problem, we know that exact solution methods are incapable of solving this problem for fully sized systems within reasonable time. Therefore, this thesis introduces and implements a two-stage stochastic programming column generation heuristic capable of solving this problem for real-world instances. This heuristic aims to be of value as a decision making tool when organizing electric BSSs.

The DSBRCP heuristic is composed of three main steps; (1) initializing routes and patterns, (2) solving subproblems, and (3) solving a master problem. The first step is implemented heuristically, while the second and third step find optimal solutions. In the first step, a set of routes and pattern combinations are generated using a branching algorithm. For each of the initialized route and pattern combinations, a score for the combination is found by solving a subproblem in step two. Together, the first and second step construct a column that is passed to the master problem. The master problem combines these columns to find the optimal first stage decisions for each vehicle.

An overview of previously published literature related to the topic is included in this thesis. To the author's knowledge, the DSBRCP has not been studied before. However, it has significant overlaps with the more explored bicycle rebalancing problem, which solves a less complex rebalancing problem in traditional BSSs, where charging decisions are excluded. The main distinctions between the present problem and the rebalancing problem are the introduction of depot, charging stations, and battery swap activities. Thus, our contribution is to solve the extended rebalancing problem that also incorporates charging decisions by means of battery swaps and charging stations.

Data from the BSS in Oslo, operated by Urban Infrastructure Partners (UIP), is used to create a simulation framework reflecting a real-world test environment for the two-stage stochastic programming column generation heuristic. Using this framework, a computational study is conducted to assess solution time and discover the optimal parameter configurations. From the study, we observe that the solution time is highly dependent on the required number of subproblems to solve, which is driven by the number of service vehicles, the number of subproblem scenarios, and the branching factor when initializing routes.

The simulation framework is also used to provide managerial insights and evaluate the performance of service vehicles guided by heuristic decisions. To evaluate this, the number of violations occurring during a day when employing the heuristic is compared to employing alternative strategies on the same day. Two alternative strategies are introduced: a strategy with no operations and a strategy inspired by UIP's current operations. From the analyses, we observe that the DSBRCP heuristic is able to prevent 50% more violations in a day than the UIP-inspired strategy when employing five service vehicles. The improvement corresponds to a 23.3% reduction in daily violations when compared to a system with no service vehicle operations.