A Combined Ferry Service Network Design and Dial-a-Ride System for the Kiel Fjord

Abstract

Utviklingen av autonom teknologi åpner for nye løsninger og kan revolusjonere dagens infrastruktur for offentlig transport ved å tilby hyppigere avganger, kortere omveier samt on-demand tjenester. Denne masteroppgaven omhandler fergenettverksdesign, og er skrevet i et operasjonsanalyseperspektiv. Oppgaven er en del av et større prosjekt på Christian-Albrechts-Universität Kiel, i Tyskland. Formålet med oppgaven er å presentere en matematisk modell og et simuleringsrammeverk, som kan gi beslutningsstøtte til implementeringen av et offentlig fergetilbud i Kielfjorden ved bruk av autonome ferger. Videre kan modellene føye seg til forskningen på offentlige transportnettverk, både når det gjelder faste timetabeller, og bruk av on-demandtjenester.

Et heltallsproblem er formulert for å designe ruter og velge deres respektive avgangsfrekvenser. Modellen er basert på en to-stegs optimeringsmetode hvor kandidatruter og deres avgangsfrekvenser konstrueres på forhånd, og deretter blir det optimale settet av ruter og frekvenser bestemt ved å løse heltallsproblemet. Målfunksjonen er formulert som et bi-objektiv hvor både maksimering av avgangsfrekvenser og minimering av reisetid for passasjerene blir tatt hensyn til. Disse to aspektene er vektet ved hjelp av en ulineær nyttefunksjon. Rutegenereringsalgoritmen genererer komplekse ruter med opptil to besøk i hver havn. Videre, som et tilskudd til litteraturen, blir det presentert en skranke på et minimum antall avgangsfrekvenser mellom hvert havnepar. Dette åpner opp for ytterligere kontroll over forbindelsene rutenettverket tilbyr.

Det er også formulert et problem som tar for seg kombinasjonen av et fast rutenettverk med en on-demandtjeneste, hvor fergene tilpasser sine ruter etter der det oppstår etterspørsel. Systemet modelleres slik at alle passasjerer kan reise uten behov for omstigning, og dette er per dags dato lite diskutert i litteraturen. Målet er å maksimere andelen av etterspørsel som kan bli møtt innenfor satte grenser av kundeservice, samtidig som total reisetid i systemet minimeres. Et simuleringsrammeverk er utviklet for å evaluere kvaliteten på systemet med ulike allokeringer av ferger på det faste nettverket og til bruk av on-demandtjenesten, og formålet er å oppnå innsikt i relasjoner mellom forutsigbarheten til et fast rutenettverk og fleksibiliteten til en on-demandtjeneste. I simuleringsrammeverket blir reiseforespørsler godtatt eller avvist, og de godtatte forespørslene allokeres enten til det faste rutenettverket eller til en on-demandferge. For å finne en optimal behandling av etterspørselen ved hjelp av on-demandtjenesten, er en innsettingsheuristikk utviklet og implementert.

Den presenterte optimeringsmodellen for å konstruere faste rutenettverk ble løst til optimalitet innenfor rimelig tid for opptil ti havner. På grunn av en kombinatorisk eksplosjon i genereringen av ruter skalerer modellen dårlig for instanser med flere enn ti havner. Resultatene fra modellen for øvrig indikerer at kundeservicenivået i Kiel kan bli betydelig forbedret fra slik det er i dag, både med tanke på avgangsfrekvenser og reisetid.

Resultatene fra analysene gjort med simuleringsrammeverket viser at den optimale allokeringen av ferger mellom de to tjenestene som tilbys (fast rutenettverk og on-demandtjeneste) varierer med mengden etterspørsel. I rushtid med høy etterspørsel kan det være fordelaktig med forutsigbarheten og effektiviteten til det faste rutenettverket, mens i perioder med mindre, mer sporadisk etterspørsel, kan det være fordelaktig å benytte seg av fleksibiliteten til en on-demandtjeneste. Videre er det observert at flåtestørrelse har mye å si for hvordan fergene bør allokeres. Et fast rutenettverk er fordelaktig når flåten er liten, men med større flåte kan flere on-demandferger føre til bedre utnyttelse. I tillegg virker det som bruken av skranker på et minimum antall avganger mellom hvert havnepar kan øke kundeservicenivået på det faste rutenettverket slik at et supplement med on-demandferger ikke er like nødvendig. Dette er et spennende funn som det oppfordres til å forske videre på. For å konkludere, indikerer funnene fra denne masteroppgaven, at ved hjelp av de presenterte beslutningsstøtteverktøyene kan nyvinningene innen autonom teknologi for passasjertransport utnyttes for fergetjenester, slik at det stadig mer etterspurte tilbudet for offentlig transport kan tas til nye høyder.

The evolution of autonomous mobility solutions may change public transportation as we know it by enabling more frequent departures, shorter detours, and on-demand services. This master's thesis presents an operations research study of a ferry service design, and it contributes to a larger project at Kiel University in Germany. The aim is to develop a mathematical model and a simulation system, which may provide decision support to the implementation of a public ferry service for passenger transportation in the Kiel fjord using autonomous ferries. Furthermore, the proposed models contribute to research on public transportation network design, both considering the construction of a fixed departure schedule and the use of dial-a-ride services.

Initially, this thesis presents a integer programming optimization model regarding the design of routes for a public ferry service, including the selection of departure frequencies. The model is based on a two-step optimization approach, where candidate combinations of routes and departure frequencies are generated a priori. Afterward, the solution network is constructed with a bi-objective approach which considers maximizing departure frequency and minimizing excess transit time through customized utility functions. The route generation procedure allows more complex structures with up to two visits to all ports in the route. Moreover, as an addition to current service network design literature, the concept of minimum required frequencies specific to origin-destination pairs is introduced. This enables greater control over the available connections offered by the service network for the operator.

Subsequently, this thesis formulates the problem of combining a fixed schedule service with a demand responsive service without passenger transfers, which has scarcely been studied in previous literature. The aim is to maximize the number of serviced requests within certain quality requirements while minimizing service time. A simulation system is developed to evaluate the effects of different ferry allocations, and the aim is to provide insights into the relations between the predictability of a fixed schedule with time tables and the responsiveness of a dial-a-ride service with on-demand routing. During the simulation, each passenger request is either accepted or rejected. Accepted requests are assigned to specific ferries by applying a constructed insertion heuristic, which also considers redirection of the dial-a-ride ferries.

The proposed optimization model to create fixed schedule departures is solved to optimality within reasonable time for up to ten ports. However, due to combinatorial explosion in the route generation procedure, the scalability is poor for additional ports. Apart from this, the results indicate that the level of customer service in Kiel may be improved compared to the current ferry service offering, both considering elevated departure frequency and reduced excess transit time.

The analyses conducted of the combined ferry service system reflect that the optimal fleet allocation between the two services to a large extent depends on the size of demand. Peak hours with high demand may benefit from the predictability of the fixed schedule, whereas off-peak periods with more scattered demand is suitable for an increased dial-a-ride service, due to its flexible and responsive behavior. Moreover, the fleet size also appears to affect the choice of allocation. Fixed schedule services are preferable for smaller fleets, while a predominant dial-a-ride service provides a higher level of customer service for larger fleets. In addition, applying minimum required frequencies can improve the performance of the fixed schedule, thus further research into this concept is encouraged. In conclusion, autonomous technology advancements combined with the proposed decision support tools may provide excellent customer service for public ferry transportation systems.