| dc.description.abstract | Samkjøring fremstår som en lovende løsning på trafikkutfordringene man møter i forsteder og landlige områder. Hovedpoenget er å redusere trafikkbelastningen og karbonutslippene, og fremme fellesskapsfølelsen ved å dele reisekostnadene blant deltakerne. Potensialet for disse effektene er særlig uttalt i regioner som Sotra og området rundt Bergen, hvor både geografien og demografien fører til en økt avhengighet av private kjøretøy. Et område med en stor trafikkbelastning er Sotrabroen, broen som forbinder Sotra og Bergen. Til tross for de uttalte fordelene med samkjøring har dette ikke blitt et utbredt alternativ. Dette skyldes muligens utfordringer knyttet til koordrinering og hvordan man kan gjøre samkjøring lettvint for alle de involverte.
I denne masteroppgaven addresser vi disse utfordringene ved å utvikle en koordineringsmetode for et samkjøringssystem, kalt Static Ridesharing Routing Problem with Flexible Locations (SRRPFL). Hovedmålet med denne metoden er å bestemme effektive ruter. Ved å legge opp til at passasjerer kan bli plukket opp og levert på fleksible lokasjoner har SRRPFL som sitt primære mål å maksimere antall passasjerer som blir plukket opp og levert, mens det sekundære målet er å minimere den totale reisetiden for sjåførene. SRRPFL tar hensyn til individuelle reisebehov, som start- og sluttlokasjoner, maksimal reisetid for sjåfører og passsasjerer og ankomstvinduet til sjåfører og passasjerer.
For å løse SRRPFL introduseres en eksakt matematisk modell. Imidlertid, for realistiske probleminstanser blir denne modellen for tidkrevende å løse. Derfor er en adaptive large neighborhood search (ALNS) heuristikk, inkludert utvidelser med lokaløsk og settpartisjonsformulering, blitt implementert. Denne heuristikken er skreddersydd for SRRPFL og designet for å produsere løsninger raskt, samtidig som den sikrer høy kvalitet på løsnningene.
Etter at ALNS-heuristikken er testet på probleminstanser generert på ekte data fra Telia, kan man observere at ALNS-heuristikken produserer løsninger av høy kvalitet. Disse testene viser også at bruken av fleksible lokasjoner kan øke antaller passasjerer som blir plukket opp merkbart. Dette vil igjen kunne redusere behovet for individuell bilbruk og avlaster derfor trafikkbelastningen. Ved å tilpasse seg behovene og preferansene til sjåførene og passasjerene vil fleksible lokasjoner kunne bidra til å redusere antall kilometer kjørt, som igjen vil resultere i lavere CO2-utslipp. Hvis man sammenligner de to scenariene med fleksible lokasjoner og uten fleksible lokasjoner, observerer man at scenariet med fleksible lokasjoner overgår sin motpart både i form av antall opplukkede passasjerer, men også i redusert reiseavstand og reisetid. | |
| dc.description.abstract | Ridesharing has emerged as a promising solution to the transportation challenges faced by suburban and rural areas. At its core, it aims to reduce traffic congestion, decrease carbon emissions, and foster a sense of community by sharing travel expenses among participants. This potential is particularly pronounced in regions like Sotra and the greater Bergen area in Norway, where geographical and demographic characteristics result in an increased reliance on private vehicles. One notable area of congestion is Sotrabroen, the primary bridge connecting Sotra to Bergen, which experiences high traffic volumes, increasing the negative environmental impacts. Despite these advantages, ridesharing has not yet become a mainstream alternative due to challenges such as schedule coordination and convenience issues.
This thesis addresses these challenges by developing a coordination method for a ridesharing system, identified as the Static Ridesharing Routing Problem with Flexible Locations (SRRPFL). The primary objective of this method is to design efficient routes. By enabling vehicles to pick up and deliver passengers at various flexible locations, the method primarily aims to maximize passenger participation and, secondarily, to minimize the total travel time for drivers. The SRRPFL takes into account individual travel needs, such as origin and destination locations, along with preferences including maximum travel time and arrival time window.
To solve the SRRPFL, an exact mathematical arc-flow mixed integer programming model is formulated. However, for realistic and large-scale problem instances, using a commercial solver proves too time-consuming. Therefore, an adaptive large neighborhood search (ALNS) heuristic, including extensions of local search and a set-partitioning formulation, is implemented. This heuristic approach is tailored for the SRRPFL, and designed to deliver solutions quickly while still ensuring a high level of solution quality.
Tests on instances, based on real data provided by Telia, reveal that the ALNS heuristic produces high-quality solutions. These tests also demonstrate that the use of flexible locations notably increases passenger participation in the ridesharing scheme, thereby reducing the need for individual car usage and alleviating traffic congestion. By adapting to the needs and preferences of potential participants, the flexibility of locations reduces travel distance and travel time for drivers, subsequently resulting in lower CO2 emissions. When comparing models, the one featuring flexible locations outperforms its inflexible counterpart not just in terms of the number of passengers participating, but also in operational metrics like reduced travel distance and travel time. | |
