The Stochastic Electric-Vehicle Relocation Problem with Dynamic Pricing

Abstract

Bildelingstjenester har de siste årene blitt stadig mer utbredt. De positive virkningene disse tjenestene har på miljøet og en rekke økonomiske aspekter er noen av årsakene til deres økte populæritet. Bildelingstjenester bidrar også til å unngå problemer knyttet til trafikk og parkering.

I stasjonsbaserte bildelingstjenester blir biler plukket opp og levert til designerte stasjoner. I frittflytende systemer blir biler derimot plukket opp og levert hvor som helst innen et forhåndsdefinert område. Enveis, stasjonsbaserte systemer tillater kunder å levere bilene ved andre stasjoner enn der de ble plukket opp. Frittflytende og enveis, stasjonsbaserte systemer fører til at bildelingsoperatøren må opprettholde en balanse i bil-flåten. Dette problemet oppstår når biler blir avlevert i områder med lav etterspørsel og plukket opp i områder med høy etterspørsel. Elektriske biler har de siste årene blitt mer populært, hovedsakelig grunnet fremskritt innen batteriteknologi og økt fokus på miljø. For frittflytendede bildelingstjenester fører dette med seg utfordringen med å finne sted og tid til å sette de elektriske bilene til lading.

Ansatte av bildelingsoperatøren har tradisjonelt sett vært de som reposisjonerer bilene for å holde flåten balansert. Reposisjoneriner kan også håndteres ved at kunder blir insentivert med bonuser eller avgifter til å plukke opp biler i områder med lav etterspørsel og levere biler i områder med høy etterspørsel. Bruken av slike varierende bonuser og avgifter er det vi kaller dynamisk prising. Dynamisk prising fører til utfordringen knyttet til å forutse kundepreferanser og hvordan kunder reagerer på de forskjellige prisene.

I denne avhandlingen presenteres en modell for det Stokastiske Reposisjonseringsproblemet for Bildelingstjenester med Elektriske Biler og Dynamiske Priser (Stochastic Electric Vehicle Relocation Problem with Dynamic Pricing - SE-VReP-DP). Problemet går ut på å lage ruter og timeplaner for ansatte som skal flytte biler, og å dynamisk sette priser som insentiverer kunder til å bruke tjenesten på et vis som gagner bildelingsoperatøren ved å maksimere profitt. Vi formulerer et tostegs, stokastisk blandet heltallsprogrammeringsproblem for å håndtere usikkerheten knyttet til kundeoppførsel. Modellens input inkluderer initielle distribusjoner av biler, ansatte og kunder, initiellt batternivå for de elektriske bilene og potensielle priser for kundereisene. Usikkerhet blir introdusert i modellen gjennom en tilfeldig parameter. Modellen returnerer et sett av priser for kombinasjonen av områder for henting og levering av biler, i tillegg til ruter og timeplaner for de ansatte. Eilertsen et al. (2021) konkluderer med at modellen er for kompleks til å kunne løses av et kommersielt løsningsprogram når man har realistisk store instanser.

For å kunne løse instanser av reell størrelse foreslås en heuristisk løsningsmetode (en tommelfingermetode). Heuristikken som er utviklet er et adaptivt stort nabolagssøk (Adaptive Large Neighborhood Search - ALNS) integrert med lokalsøkoperatorer (Local Search). ALNS-heuristikken er tilpasset til den stokastiske settingen i SE-VReP-DP. Løsningsmetoden er dekomponert i to separate søk, der det første er for å finne priser og det andre er for å finne hvilke reposisjoneringer som skal gjøres av de ansatte. Både problemspesifikke og velkjente nedbrytnings- og reparasjonsoperatorer blir brukt i ALNS-heuristikken. Videre blir problemet løst i et simuleringsverktøy (rolling horizon framework), for å skape relevante diskusjoner for problemet i en reell setting.

Resultatene indikerer at innføring av dynamisk prising gir høyere profitt og at ALNS-heuristikken utkonkurrerer en kommersiell løser for instanser av reell størrelse. For de største instansene klarer ikke en kommersiell løser å finne en gyldig løsning i det hele tatt innen kjøretidsbegrensningen. Videre viser resultatene at dynamiske priser kan påvirke oppførselen til både kunder og ansatte, og inviterer til diskusjon rundt rollen til de ansatte i bildefor bør forskjellige implementasjoner og konfigurasjoner vurderes for å videre forbedre resultatene fra den heurstiske løsningsmetoden. lingstjenesten. Resultatene viser også at ALNS-heuristikken gjør det bedre når kjøretiden øker, noe som indikerer at heuristikken kan forbedres for å finne de gode løsningene på kortere tid. Der

Car-sharing services have increased in popularity and size in recent years. These services' positive effects on the environment and several economic aspects are among the reasons for their increased popularity. Additionally, car-sharing services help mitigate issues related to congestion and parking problems.

In station-based car-sharing services, cars can be picked up and dropped off at designated stations, while in free-floating services, cars can be picked up and dropped off anywhere within a predefined service area. One-way station-based services allow customers to drop the car off at a different location than the pick-up location. Free-floating systems and one-way station-based systems lead to cars being differently located at any hour, and thus the challenge of rebalancing the fleet of cars occurs for the car-sharing operator (CSO). This core of the rebalancing problem is that customers drop off cars in low-demand areas and wish to pick up cars in high-demand areas. Further, electric vehicles have become more common in recent years, primarily due to progress in battery technology and increased environmental awareness. For free-floating car-sharing services, the additional challenge of finding the time and place to relocate electric vehicles for charging arises.

Employees of the CSO have traditionally performed relocations of the cars to maintain a balanced fleet. Revenue management via dynamically setting prices can also help redistribute the cars by introducing fees or bonuses to incentivize customers to move cars to preferable destinations. Additionally, the use of dynamic pricing can have a positive impact on the CSO's profit by exploiting the customers' willingness to pay. However, using dynamic pricing leads to new challenges for the CSO in predicting customer preferences and their reactions to different prices.

This thesis presents a model for the Stochastic Electric Vehicle Relocation Problem with Dynamic Pricing (SE-VReP-DP). The problem includes routing and scheduling of relocations performed by employees and dynamically setting prices through fees that incentivize desirable customer trips, with the goal of maximizing the profit of the CSO. We formulate a two-stage stochastic mixed-integer programming model to handle the uncertainty in customer behavior. The model's input includes initial vehicle, employee and customer distributions, initial battery levels of the electric vehicles, and potential customer trip fees. A random term influencing customer behavior introduces stochasticity to the model. The model returns a set of fees for the combinations of pick-up and drop-off areas, in addition to routes and schedules for employee-based relocations. Eilertsen et al. (2021) concluded that the model is too complex for a commercial solver to solve within a reasonable amount of time when using real-sized instances.

A heuristic approach is taken to solve real-sized instances. The heuristic developed in this thesis is an Adaptive Large Neighborhood Search (ALNS) heuristic integrated with two Local Search (LS) algorithms, adapted to solve the two-stage stochastic programming model of the SE-VReP-DP. The heuristic solution method is decomposed into searching for prices to be assigned to the customers' trips and employee-based relocations separately. A rolling horizon framework is presented to gain managerial insight, using the proposed heuristic to solve the SE-VReP-DP on an hourly basis throughout a work day.

The results presented in this thesis reveal that the proposed heuristic outperforms a commercial solver in solving real-sized instances within a reasonable amount of time. For the largest instances, the commercial solver is unable to find any solution at all, while the heuristic quickly finds a solution. Further, dynamic pricing tends to yield higher profits for the CSO. The average profits gained from satisfying a customer are higher with dynamic pricing, indicating the prices better exploit the customers' willingness to pay. Using the rolling horizon framework reveals that dynamic pricing affects how employees and customers behave, leading to customers performing necessary charging of the fleet to a larger extent than without dynamic pricing.

The results also indicate that the ALNS heuristic performs better when increasing the runtime. This result implies that improvements could be made to the ALNS heuristic to find better solutions in less time. Different implementations and configurations should therefore be considered to further improve the performance of the proposed heuristic solution method.