Simulation of a Dial-a-Ride Service with Autonomous Ferries in the Kiel Fjord

Abstract

Nylige teknologiske framskritt har muliggjort nye operasjonsmoduser. Man ser for seg at en endret kostnadsstruktur gjennom bruk av en helautonom flåte, gjør det mulig for å designe fleksible, kostnadseffektive, og klimavennlige transporttjenester. Gjennom prosjektet CAPTin Kiel, sikter denne masteroppgaven på å utforske muligheten til å tilby et on-demand fergetilbud med autonome ferger i Kielfjorden. Den tiltenkte flåten skal benytte mindre autonome ferger for å erstatte konvensjonelle større ferger, og dermed oppnå større fleksibilitet.

I denne masteroppgaven vil det Dynamiske Dial-a-Ride Problemet med Autononome Ferger (DDARP-AF) studeres gjennom simuleringer. Problemstillingen tar for seg designet av et on-demand fergetilbud, hvor innkommende forespørsler med potensielt meget kort innringingstid blir gjort kjent for tjenesteleverandøren etter at den initielle rute- og tidsplanleggingen av fergene har skjedd. Det karakteristiske dynamiske trekket medfører at den operasjonelle planleggingsprosedyren må kunne effektivt avgjøre om forespørsler kan imøtekommes fortløpende, og oppdatere ruteplanleggingen deretter. Det er særlig viktig at det nye fergetilbudet blir designet på en måte som gjør at det dekker forventet etterspørsel, og samtidig opprettholder et tilstrekkelig oppfattet servicenivå for passasjerene. Hovedutfordringen er å balansere ønsket servicenivå mot kostnaden til tjenesten sett fra operatørens perspektiv.

En simuleringsmodell er utviklet for å evaluere effektene av å endre forskjellige karakteristike innstillinger for fergetilbudet. En innsetningsheuristikk er valgt for å løse operasjonsplanleggingen, ettersom det er kritisk at operasjonsplanleggingsproblemet kan løses effektivt. Mulige innsetninger er begrenset av betjeningsvindurestriksjoner, maksimal reisetidsrestriksjoner, og fergekapasitetsrestriksjoner. Ytelsen til de ulike fergetilbudene kan måles med nøkkelindikatorer gitt av simuleringsresultat. Disse gjenspeiler både operatørens og passasjerenes perspektiv. Effektiviteten til forskjellige konfigurasjoner kan videre gi innsikt og beslutningsstøtte for anbefalt flåtekonfigurasjon og overordnet design av fergetilbudet.

Simuleringsmodellen er implementert i Python med det prosessorienterte diskret hendelsessimuleringsrammeverket Simpy. Testinstansene er karakterisert av forskjellige parameterverdier for størrelsen på betjeningsvinduet, maksimal reisetidskoeffisient, flåtesammensetning, og valg av objektivfunksjon. Testinstansene var simulert for tre forskjellige etterspørselsscenarioer med en tilsvarende planleggingshorisont på 500 timer for å forsikre en stabil ytelse og rapportert resultat.

Resultatene indikerer at innsetningsheuristikken ikke klarer å effektivt utnytte økt planleggingsfleksibilitet gjennom større betjeningsvinduer. Den gjennomsnittlige overflødige varigheten av en reise er særlig påvirket av verdien for maksimal reisetidskoeffisient, uavhengig av andre servicerelaterte parametere. Generelt var det lik ytelse for de forskjellige kombinasjonene av parameterverdier med ulike flåter og etterspørselsscenarioer. Større betjeningsvindu kombinert med en høy maksimal reisetidskoeffisient ga den generelt beste ytelsen med hensyn på møtt etterspørsel til tross for en høyere, men fortsatt akseptabelt nivå på gjennomsnittlig overflødig reisetid. Endringen i objektivfunksjonen i favør av å minimere gjennomsnittlig distanse seilet per ferge ga en positiv innvirkning på opp til 39 % på tjenestens evne til å imøtekomme forespørsler. Resultatet indikerer at overveldende betraktning til å minimere overflødig reisetid begrenser den generelle ytelsen til hele fergetilbudet.

En sensitivitetsanalyse av flåtestørrelsen antyder en nesten lineær proporsjonal relasjon mellom økt flåtestørrelse og møtt etterspørsel ved det høyeste etterspørselsscenarioet for en gitt konfigurasjon. Variasjon av flåtestørrelsen for en gitt konfigurasjon påvirker tilsynelatende ikke andre nøkkelindikatorer signifikant. Gitt preferansen til tilbyder av tjenesten, ble det funnet at en flåtestørrelse på minst 13 ferger kan tilby et tilstrekkelig akseptabelt fergetilbud ved det høyeste etterspørselsscenarioet.

Recent technological developments have enabled us to explore new modes of operations. It is believed that the changed cost structures due to the utilization of a fully autonomous fleet, allows for the design of flexible, cost-efficient, and climate-friendly mobility services. Through the project CAPTin Kiel, this thesis aims to study the opportunity to provide an on-demand ferry service with autonomous ferries in the Kiel Fjord. The intended fleet will utilize smaller autonomous ferries for replacing conventional large ferries in order to achieve greater flexibility.

In this thesis, the Dynamic Dial-a-Ride Problem with Autonomous Ferries (DDARP-AF) is studied through simulation. The problem concerns the design of an on-demand ferry service, where incoming requests with potentially very short call ahead times are made known to the service provider after the initial routing and scheduling of ferries. The highly dynamic nature entails that the operational planning procedure needs to efficiently determine if the requests can feasibly be served in an online manner and update the ferry schedules accordingly. It is essential that the new ferry service must be designed in a way that can meet the expected demand while being able to maintain an adequate level of service perceived by the passengers. The main challenge is being able to balance the desired service level against the cost of operating the service.

A simulation model is developed to evaluate the effects of changing various characteristics of the service. An insertion heuristic is chosen to solve the operational planning, as it is essential that the operational planning problem can be solved efficiently. Feasible insertions are determined by pickup time window constraints, maximum ride time constraints, and ferry capacity constraints. The performance of different services can be measured through key performance indicators defined from the simulation output, reflecting both the perspective of both the operator and passengers. The efficiency of various configurations can further provide insight and decision support in recommending the fleet configuration and overall design of the ferry service.

The simulation model is implemented in Python with the process-oriented discrete-event simulation framework Simpy. Test instances were characterized by parameter values for pickup time window widths, maximum ride time coefficient, fleet configurations, and the choice in the objective function. The test instances were simulated for three different demand scenarios over a planning horizon of 500 hours to assure long-term steady-state performance.

The results indicate that the insertion heuristic is not able to exploit increased planning flexibility through wider time window widths efficiently. The average excess ride time is significantly affected by the value of the maximum ride time coefficient, regardless of other service-related parameters. Generally, the combinations of service-related parameters performed similarly for different fleets and demand scenarios. A wider time window width combined with a high maximum ride time coefficient provided the overall best performance with regards to demand met at the expense of a higher, but still acceptable level of average excess ride time. The change of objective function in favor of minimizing average distance traveled per ferry provided a positive impact of up to 39 % in the service's ability to accommodate requests. The result implies that that excessive consideration towards minimizing excessive ride times limits the overall performance.

A sensitivity analysis of the fleet size suggested an almost linearly proportional relation between increased fleet size and demand met at the peak demand scenario for a given setting. Varying fleet size for a given setting does not seem to affect other key performance indicators significantly. Given the preference of the service provider, a fleet of at least 13 ferries is found to provide a sufficiently acceptable level of service in the peak demand scenario.